Metody wyboru dekompozycji dla algorytmu z wykorzystaniem zbiorów niezgodności i ich wpływ na minimalizację generatorów indeksów

• Autorzy: Mazurkiewicz T. , Łuba T.

Identyfikatory

DOI

10.15199/59.2018.8-9.36

Warianty tytułu

EN

Methods of decomposition selection in the algorithm using discernibility sets and their influence on index generation units minimization

• Konferencja: Krajowe Sympozjum Telekomunikacji i Teleinformatyki (12-14.09.2018 ; Bydgoszcz, Polska)
• Języki publikacji: PL

Abstrakty

PL

Minimalizacja wykorzystania pamięci wydaje się kluczowym zadaniem dla efektywnej realizacji sprzętowej funkcji generowania indeksów. W tym celu stosuje się algorytmy dekompozycji liniowej. W niniejszej pracy przedstawiono nową metodę wyboru dekompozycji dla algorytmu z bramkami XOR, wykorzystującego zbiory niezgodności. Przedstawione w artykule wyniki dla koderów m z 16 i m z 20 dowodzą skuteczności proponowanej metody.

EN

Memory minimization seems to be the main problem of effective index generation functions hardware implementation. A linear decomposition can be used to reduce memory size. In this paper a new method of decomposition selection for algorithm with EXOR gates, which uses discernibility sets, is proposed. Presented results show its effectiveness for m-out-of-16 and m-out-of-20 functions.

Słowa kluczowe

PL

funkcja generowania indeksów; funkcje boolowskie; dekompozycja liniowa; minimalizacja liczby zmiennych

EN

index generation functions; boolean functions; linear decomposition; variable minimization

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
• Rocznik: 2018
• Tom: nr 8-9
• Strony: 722--725, CD
• Opis fizyczny: Bibliogr. 9 poz., rys., tab.

Twórcy

autor

Mazurkiewicz T.

• Instytut Matematyki i Kryptologii, Wydział Cybernetyki, Wojskowa Akademia Techniczna, ul. Urbanowicza 2, 00-908 Warszawa

autor

Łuba T.

• Warszawska Wyższa Szkoła Informatyki, ul. Marka Edelmana 17, 00-169 Warszawa

Bibliografia

• [1] Astola Jaakko (et al.). 2016. "An algebraic approach to reducing the number of variables of incompletely defined discrete functions", IEEE 46th International Symposium on Multiple-Valued Logic (ISMVL): 107-112.
• [2] Borowik Grzegorz, Tadeusz Łuba. 2014. "Fast Algorithm of Attribute Reduction Based on the complementation of Boolean Function". Advanced Methods and Applications in Computational Intelligence, ch. 2: 25-41.
• [3] Łuba Tadeusz, Janusz Rybnik. 1993. "Algorithmic Approach to Discernibility Function with Respect to Attributes and Objects Reduction". Foundations of Computing and Decision Sciences, vol. 18, no. 3-4, 241-258.
• [4] Łuba Tadeusz, Grzegorz Borowik. 2015. "Synteza logiczna", Oficyna Wydawnicza PW, Warszawa.
• [5] Łuba Tadeusz, Krzysztof Poźniak, Bogdan Zbierzchowski. 2016. "Redukcja i kompresja zmiennych w syntezie funkcji generowania indeksów". Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne, nr 10: 1230-1236.
• [6] Łuba Tadeusz, Tomasz Mazurkiewicz. 2018. "Synteza generatorów indeksów metodami dekompozycji liniowej i funkcjonalnej", Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne, nr 5: 122-128.
• [7] Mazurkiewicz Tomasz, Tadeusz Łuba. 2017. "Redukcja liczby zmiennych do reprezentacji funkcji generowania indeksów", Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne, nr 8-9: 795-798.
• [8] Sasao Tsutomu. 2011. "Memory-Based Logic Synthesis", Springer New York Dordrecht Heidelberg London.
• [9] Sasao T., Fumishi I., Iguchi Y. 2015 "On an exact minimization of variables for incompletely specified index generation functions using SAT", Note on Multiple- Valued Logic in Japan: 1-8.