Utilizing Common Information in Disjoint Decomposition of Multioutput Boolean Functions

• Autorzy: Morawiecki P. , Rawski M.

Warianty tytułu

PL

Wykorzystanie wspólnej informacji w dekompozycji rozłącznej wielowyjściowych funkcji boolowskich

• Języki publikacji: EN

Abstrakty

EN

In the article it is described a new method of using a disjoint decomposition as a part of a functional decomposition. The functional decomposition has important applications in many fields of modern engineering and science (FPGA synthesis, information systems, neural networks and many others). The presented algorithm is dedicated to multioutput boolean functions. The concept is based on dividing the complex function into single output functions and then utilizing common information existing in these functions. To test the algorithm, the prototype tool was implemented and the results are presented in the paper.

PL

W artykule zostanie przedstawiona nowa metoda wykorzystania dekompozycji rozłącznej jako elementu dekompozycji funkcjonalnej. Dekompozycja funkcjonalna ma zastosowania w wielu dziedzinach elektroniki, informatyki czy telekomunikacji (np. synteza układów FPGA, systemy informacyjne, sieci neuronowe, synteza filtrów cyfrowych). Zaproponowany algorytm dedykowany jest wielowyjściowym funkcjom boolowskim. Działanie algorytmu bazuje na dekompozycji równoległej i wykorzystaniu wspólnej informacji tkwiącej w dekomponowanych podfunkcjach.

Słowa kluczowe

EN

logic synthesis; functional decomposition

PL

synteza logiczna; dekompozycja funkcjonalna

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2008
• Tom: R. 54, nr 8
• Strony: 559--561
• Opis fizyczny: Bibliogr. 11 poz., rys., tab., wzory

Twórcy

autor

Morawiecki P.

autor

Rawski M.

• Zakład Informatyki, Wyższa Szkoła Handlowa w Kielcach,

Bibliografia

• [1] M. Nowicka, “Zrównoważona metoda odwzorowania technologicznego dla układów FPGA. Praca doktorska”, Wydział Elektroniki i Technik Informacyjnych, Politechnika Warszawska, 1999.
• [2] M. Nowicka, M. Rawski, T. Łuba, „FPGA-based decomposition of boolean functions. Algorithms and implementation. Proceeding of the 6th International Conference on Advanced Computer Systems, 1999.
• [3] R. L. Ashenhurst. The decomposition of switching functions. Internation Symposium on the Theory of Switching Functions, April 1959.
• [4] J. A. Brzozowski and T. Łuba, “Decomposition of Boolean Functions Specified by Cubes”, Journal of Multiple-Valued Logic and Soft Computing, Vol. 9, Old City Publishing, Inc., Philadelphia, 2003, pp. 377–417.
• [5] Chang S. C., Marek-Sadowska M., Hwang T. T., „Technology Mapping for TLU FPGAs Based on Decomposition of Binary Decision Diagrams”, IEEE Trans. on CAD, Vol. 15, No.10, pp. 1226-1236, 1996.
• [6] Collaborative Benchmarking Laboratory, Department of Computer Science at North Carolina State University, http://www.cbl.ncsu.edu: 16080/benchmarks/
• [7] Sentovich E.: SIS: A system for Sequential Circuits Synthesis. Electronics Research Laboratory Memorandum, No. VCB/ERLM92/41, University of California, Berkeley, 1992.
• [8] P. Morawiecki, M. Rawski, „Input Variable Partition Method in Functional Decomposition based on Shannon Expansion”, Konferencja Reprogramowalne Układy Cyfrowe, RUC Szczecin 2007.
• [9] M. Rawski, P. Morawiecki, H. Selvaraj, “Decomposition of Combinational Circuits Described by Large Truth Tables”, Proceedings of Eighteenth International Conference on Systems Engineering, Coventry, United Kingdom, September 5-7 2006, pp. 401 - 406.
• [10] T. Luba, H. Selvaraj, M. Nowicka, A. Kraśniewski, “Balanced multilevel decomposition and its applications in FPGA-based synthesis”, In: Logic and Architecture Synthesis (G.Saucier, A.Mignotte ed.), Chapman&Hall, 1995.
• [11] A. Chojnacki, Effective and Efficient Circuit Sythesis for LUT FPGAs Based on Functional Decomposition and Information Relationship Measures. Praca doktorska, Technishe Universiteit Eindhoven, 2004.