Functional Decomposition System Dedicated to Multi-Output Boolean Functions

• Autorzy: Morawiecki P.
• Języki publikacji: EN

Abstrakty

EN

The functional decomposition has important applications in many fields of modern engineering and science (FPGA synthesis, information systems, neural networks and many others). In this paper, a new method for functional decomposition is presented. The proposed approach is dedicated to the multi-output boolean functions. It uses the concept of dividing the complex function into single-output functions and utilizing common information between these functions. Additionally, it allows the multi-output function to be represented as a set of separate truth tables for each output, which might be very beneficial for time and memory usage of the system. To test the proposed solutions, a prototype tool was implemented and the results are presented in the paper.

Słowa kluczowe

EN

Boolean function; logic synthesis; functional decomposition

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: Electronics and Telecommunications Quarterly
• Rocznik: 2009
• Tom: Vol. 55, No 3
• Strony: 453--470
• Opis fizyczny: Bibliogr. 22 poz., tab., wykr.

Twórcy

autor

Morawiecki P.

• Kielce University of Commerce, Institute of Computer Science, Peryferyjna 15, 25-562 Kielce, Poland,

Bibliografia

• 1. 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
• 2. J. A. Brzozowski and T. Luba: Decomposition of Boolean Functions Specified by Cubes, Journal of Multiple-Valued Logic and Soft Computing, Vol. 9, pp. 377-417, Old City Publishing, Inc., Philadelphia, 2003
• 3. A. Opara: Dekompozycyjne metody syntezy układów kombinacyjnych wykorzystujące binarne diagramy decyzyjne. Praca doktorska, Politechnika Śląska, 2009
• 4. C. W. Chang and M. Marek-Sadowska: Finding maximal symmetric groups variables in incompletely specified Boolean functions. International Workshop on Logic Synthesis, Lake Tahoe, June 1999
• 5. P. Morawiecki, M. Rawski: Input Variable Partition Method in Functional Decomposition based on Shannon Expansion, Konferencja Reprogramowalne Układy Cyfrowe, RUC Szczecin 2007
• 6. M. Rawski, P. Morawiecki, H. Selvaraj: Decomposition of Combinational Circuits Described by Large Truth Tables, Proceedings of Eighteenth International Conference on Systems Engineering, pp. 401-406, Coventry, United Kingdom, September 5-7 2006
• 7. 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
• 8. M. Nowicka: Zrównoważona metoda odwzorowania technologicznego dla układów FPGA. Praca doktorska, Wydzial Elektroniki i Technik Informacyjnych, Politechnika Warszawska, 1999
• 9. M. Rawski, L. Jóźwiak, M. Nowicka, T. Łuba: Non-Disjoint Decomposition of Boolean Functions and Its Application in FPGA-oriented Technology Mapping, Proc. of the EUROMICRO'97 Conference, Budapest, Hungary, Sept. 1-4, 1997, pp. 24-30, IEEE Computer Society Press, 1997
• 10. T. Łuba, H. Selvaraj: A General Approach to Boolean Function Decomposition and its Applications in FPGA-based Synthesis. VLSI Design. Special Issue on Decompositions in VLSI Design, vol. 3, Nos. 3-4, 289-300, 1995
• 11. S. C. Chang, M. Marek-Sadowska, and T. T. Hwang: Technology Mapping for TL FPGAs Based on Decomposition of Binary Decision Diagrams, IEEE Trans. on CAD, vol. 15 No. 10, pp. 1226-1236, October, 1996
• 12. C. Files, M. Perkowski: Multi-Valued Functional Decomposition as a Machine Learning Method, ISMVL'98, pp. 173-178, Fukuoka, Japan, 1998
• 13. M. Rawski: Decomposition of Boolean Function Sets, Kwartalnik Elektronika i Telekomunikacja II'2007
• 14. A. Opara, D. Kania: Synteza wielowyjsciowych układów logicznych prowadząca do wykorzystania wspólnych bloków logicznych. Pomiary Automatyka Kontrola, 7, 2007
• 15. A. Opara, D. Kania: Wykorzystanie pseudo-mtbdd w dekompozycji zespotu funkcji. Pomiary Automatyka Kontrola, 8, 2008
• 16. P. Morawiecki: Zastosowanie algorytmów ewolucyjnych przy doborze zmiennych w dekompozycji szeregowej. Praca inżynierska. Wydzial Elektroniki i Technik Informacyjnych. Politechnika Warszawska, 2003
• 17. H. Sawada, T. Suyama, A. Nagoya: Logic synthesis for look-up table based fpgas using functional decomposition and boolean resubstitution. IEICE Transactions on Information and Systems, 1997
• 18. A. Chojnacki: Effective and Efficient Circuit Sythesis for LUT FPGAs Based on Functional Decomposition and Information Relationship Measures. Praca doktorska, Technische Universiteit Eindhoven, 2004
• 19. T. Sasao, M. Matsuura, Y. Iguchi, and S. Nagayama: Compact BDD Representations for Multiple-Output Functions and Their Application. ISMVL pp. 207-212, 2001
• 20. www.altera.com
• 21. G. De Micheli: Synthesis and Optimization of Digital Circuits. McGraw-Hill, 1994
• 22. T. Sasao, and M. Fujita: Representations of Discrete Functions. Kluwer Academic Publishers, 1996