Functional decomposition of combinational logic circuits with PKmin

• Autorzy: Michalski T. , Kokosiński Z.

Identyfikatory

DOI

10.4467/2353737XCT.16.257.6056

Warianty tytułu

PL

Dekompozycja funkcjonalna kombinacyjnych układów logicznych w programie PKmin

• Języki publikacji: EN

Abstrakty

EN

In this paper, an application of the PKmin program for functional decomposition of multiinput multi-output combinational circuits is presented. The main focus is on balanced multilevel decomposition of logic circuits into minimal number of blocks, such as LUTs in FPGAs. Reduction of the input redundancy is available. Decomposition schemes include parallel, joint/disjoint serial and a mixed one. The decomposition with PKmin can be automated by means of a heuristic algorithm or can be supervised by the designer. A distinctive feature of PKmin is the visualization of the design steps and the final layout of blocks and their interconnections. PKmin is compared in an example with the program DEMAIN.

PL

W artykule przedstawiono zastosowanie programu PKmin do dekompozycji funkcjonalnej wielowyjściowych układów kombinacyjnych, a w szczególności do wielopoziomowej dekompozycji układów na minimalną liczbę bloków funkcjonalnych, takich jak komórki LUT w makrokomórkach FPGA. Możliwa jest wstępna redukcja wejść, a następnie dekompozycje: równoległa, szeregowa łączna i rozłączna oraz mieszana. Proces dekompozycji może być zautomatyzowany lub nadzorowany przez projektanta w trybie interaktywnym. Wyróżnikiem PKmin jest wizualizacja procesu projektowania. Końcowy schemat układu zawiera bloki składowe LUT oraz ich połączenia. Program PKmin został porównany na przykładzie z programem DEMAIN.

Słowa kluczowe

EN

combinatorial logic circuit; FPGA; functional decomposition; LUT; PKmin

PL

układ kombinacyjny; FPGA; dekompozycja funkcjonalna; LUT; PKmin

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Czasopismo Techniczne. Elektrotechnika
• Rocznik: 2016
• Tom: Y. 113, iss. 2-E
• Strony: 191--202
• Opis fizyczny: Bibliogr. 15 poz., il.

Twórcy

autor

Michalski T.

• Nokia Solutions and Networks, Wrocław, Poland

autor

Kokosiński Z.

• Department of Automatic Control and Information Technologies, Faculty of Electrical and Computer Engineering, Cracow University of Technology

Bibliografia

• [1] De Micheli G., Synthesis and optimization of digital circuits, McGraw-Hill, 1994.
• [2] Kapralski A., Skarbek W., Problem of searching minimum base in Boolean tables, Podstawy sterowania, 1986, 257–265.
• [3] Kokosiński Z. Michalski T., Synthesis of 2-level combinatorial circuits with PKmin, Technical Transactions – Automatic Control, 1-AC/2012, 93–113 (in Polish).
• [4] Łuba T., Design of digital circuits, Chapter 9.4: DEMAIN system, Oficyna Wydawnicza Politechniki Warszawskiej, Warszawa 2005 (in Polish).
• [5] Michalski T., Approximation algorithms for minimization of multiple-input multiple-output combinatorial circuits, M.S. thesis, Cracow University of Technology, Kraków 2010. (in Polish)
• [6] Mishchenko A., Chatterjee S., Brayton R., DAG-Aware AIG Rewriting. A Fresh Look at Combinational Logic Synthesis, Proc. 43st ACM/IEEE Design Automation Conference, San Francisco, USA, 2006, 532–535.
• [7] Njuguna R., A survey of FPGA benchmarks, an electronic report available at http://www.cse.wustl.edu/~jain/cse567-08/ftp/fpga/
• [8] Nowicka M., Rawski M.,Tomaszewicz P.,Sapiecha P., Decomposition of Boolean Circuits based on Graph Colouring Heuristics, Materiały Krajowego Sympozjum Telekomunikacji, Tom B, Bydgoszcz 1997, 242–250.
• [9] Nowicka M., Łuba T., Rawski M., FPGA-Based Decomposition of Boolean Functions. Algorithms and Implementation, Proc. of the 6th International Conference on Advanced Computer Systems, Szczecin 1999, 502–509.
• [10] Nowicka M., Kraśniewski A., Zbierzchowski B., A method for designing of high speed FPGA circuits, Materiały III Krajowej Konferencji Reprogramowalne Układy Cyfrowe RUC’2000, Szczecin 2000, 97–104 (in Polish)
• [11] Salauyou V., Klimowicz A., Logic synthesis of digital circuits in programmable structures, Oficyna Wydawnicza Politechniki Białostockiej, Białystok 2010 (in Polish).
• [12] Sasao T., Matsuura M., A Method to Decompose Multiple-Output Logic Functions, Proc. 41st Design Automation Conference, San Diego 2004, 428–433.
• [13] Sklyarov V., Skliarova I., Barkalov A., Titarenko L., Synthesis and optimization of FPGA-based systems, Lecture Notes in Electrical Engineering, Vol. 294, Springer 2014.
• [14] PKmin www site: http://www.pkmin.za.pl/
• [15] DEMAIN www site: http://www.zpt.tele.pw.edu.pl/oprogramowanie/demain.html