Synteza dwupoziomowych układów kombinacyjnych w programie PKmin

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

Warianty tytułu

EN

Synthesis of 2-level combinatorial circuits with PKmin

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono nowy program PKmin stanowiący użyteczne narzędzie do syntezy kombinacyjnych układów cyfrowych. Program został skonstruowany na podstawie wyników wieloletnich badań prowadzonych w Politechnice Krakowskiej i może wspierać syntezę dwupoziomowych układów Semi Custom i Full Custom realizowanych na bramkach logicznych, układów dwupoziomowych opartych na PLA, układów wielopoziomowych a także dekompozycję funkcjonalną funkcji logicznych pod kątem implementacji w układach FPGA. Artykuł zawiera wyniki badań porównawczych algorytmów syntezy implementowanych w programie PKmin oraz porównanie efektywności programów PKmin i Espresso w zakresie syntezy układów dwupoziomowych realizowanych na bramkach i PLA.

EN

In this paper a new design tool is presented that is useful in automated synthesis of combinatorial logic. PKmin program is devoted for synthesis of 2-level circuits composed of gates and PLAs, multi-level circuits and a functional decomposition of logical functions for LUT-based logic implementations in FPGA. It has been built on the basis of the research conducted at Cracow University of Technology. In the paper design algorithms implemented in PKmin are mutually compared. Then, an experimental efficiency comparison of gate and PLA-based 2-level synthesis with PKmin and Espresso design tools is reported.

Słowa kluczowe

PL

układ kombinacyjny; PLD; minimalizacja funkcji logicznej; algorytm Kapralskiego; algorytm Kazakowa; PKmin; Espresso

EN

combinatorial logic; PLD; logical function minimization; Kapralski algorithm; Kazakov algorithm; PKmin; Espresso

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Czasopismo Techniczne. Automatyka
• Rocznik: 2012
• Tom: R. 109, z. 1-AC
• Strony: 93--113
• Opis fizyczny: Bibliogr. 21 poz., wz., tab.

Twórcy

autor

Kokosiński Z.

• Katedra Automatyki i Technik Informacyjnych, Wydział Inżynierii Elektrycznej i Komputerowej, Politechnika Krakowska

autor

Michalski T.

• Nokia Siemens Networks, Wrocław

Bibliografia

• [1] Byrtek M., Porównanie efektywności programów PKmin i DEMAIN we wspomaganej komputerowo syntezie wielowyjściowych układów kombinacyjnych, praca magisterska, Politechnika Krakowska, Kraków 2012.
• [2] De Micheli G., Synteza i optymalizacja układów cyfrowych, WNT, Warszawa, 1998.
• [3] Jacobson H.M., Myers C.J., Efficient algorithms for exact two-level hazardfree logic minimization, IEEE Trans. on CAD of Integrated Circuits and Systems, vol. 21(11), 2002, 1269-1283.
• [4] Kaglial A., Balachandran S., Set-cover heuristics for two-level logic minimization, VLSI Design, 2012, 197-202.
• [5] Kapralski A., Przestrzenie boolowskie i ich zastosowanie do syntezy układów przełączających, Wydawnictwo Politechniki Krakowskiej, Kraków 1979.
• [6] Kapralski A., Zarys teorii układów przełączających i teorii informacji, Wydawnictwo Politechniki Krakowskiej, Kraków 1985.
• [7] Kapralski A., Skarbek W., Problem of searching minimum base in Boolean tables, Podstawy Sterowania, 1986, 257-265.
• [8] Kerntopft P., Michalski A., Wybrane zagadnienia syntezy kombinacyjnych układów logicznych, PWN, Warszawa 1972.
• [9] Kokosiński Z., O efektywności algorytmów syntezy kombinacyjnych układów logicznych, Prace III Ogólnopolskiej Konferencji Naukowo-Technicznej SEMTRAK, Kraków–Janowice 1986.
• [10] Kokosiński Z., Analysis of the Sarje method for minimization multi-output switching circuits, Bull. Applied Math., vol. XLIX, 1987, 299-306.
• [11] Liu Y.-Y., Wang K.-H., Hwang T.-T., Crosstalk minimization in logic synthesis for PLAs, ACM Trans. Design Autom. Electr. Syst., vol. 11(4), 2006, 890-915.
• [12] Łuba T., Synteza układów logicznych, Oficyna Wydawnicza Politechniki Warszawskiej, Warszawa 2005.
• [13] Łuba T. (red.), Synteza układów cyfrowych, WKiŁ, Warszawa 2003.
• [14] Michalski T., Przybliżone algorytmy syntezy wielowyjściowych kombinacyjnych układów logicznych, praca magisterska, Politechnika Krakowska, Kraków 2010.
• [15] Rushdi A.M., Ba-Rukab O.M., A purely map procedure for two-level multipleoutput logic minimization, Int. J. Comput. Math., vol. 84(1), 2007, 1-10.
• [16] Salauyou V., Klimowicz A., Synteza logiczna układów cyfrowych w strukturach programowalnych, Oficyna Wydawnicza Politechniki Białostockiej, Białystok 2010.
• [17] Sysło M., Deo N., Kowalik J., Algorytmy optymalizacji dyskretnej, Wydawnictwo Naukowe PWN, Warszawa 1995.
• [18] Umans C., Villa T., Sangiovanni-Vincentellio A.L., Complexity of two-level logic minimization, IEEE Trans. on CAD of Integrated Circuits and Systems, vol. 25(7), 2006, 1230-1246.
• [19] Strona programu PKmin (2010): http://www.pkmin.za.pl/
• [20] Strona DEMAIN: http://www.zpt.tele.pw.edu.pl/oprogramowanie/demain.html
• [21] Strona programu ZUBR (2007): http://aragorn.pb.bialystok.pl/~zubr/