Boole'owski rachunek różniczkowy w dekompozycji funkcji logicznych implementowanych w układach FPGA

• Autorzy: Hrynkiewicz E. , Kołodziński S.

Warianty tytułu

EN

Boolean Differential Calculus in decomposition of logic functions implemented in FPGA

• Języki publikacji: PL

Abstrakty

PL

W referacie przedstawiony jest problem przydziału zmiennych do zbioru wolnego i związanego przy dekompozycji funkcji logicznych. Jako przykład rozważana jest dekompozycja Ashenhursta funkcji implementowanych w układach FPGA typu LUT. Zaprezentowane rozwiązanie polegające na wykorzystaniu Boole'owskiego rachunku różniczkowego problemu jest bardzo wygodne wtedy kiedy proces dekompozycji prowadzony jest w dziedzinie spektralnej Reeda-Mullera. Uzyskiwane podziały zmiennych dla układów testowych są bardzo korzystne z punktu widzenia wyników dekompozycji.

EN

In the paper the problem of input variables assigning to the free and bounded sets during logic function decomposition is investigated. The Ashenhurst decomposition is considered with respect to implementation of logic functions in LUT based FPGA. The method of finding profitable input variables partitioning is based on utilization of Logic Differential Calculus. The elaborated method is very convenient, especially if decomposition is carried out in the Reed-Muller spectral domain because the Boolean differentials can be easily calculated from Reed-Muller forms of a logic function which are simply calculated as the reverse Reed-Muller transform. As it can be seen in Table 2, the obtained subsets of variables are very useful from the point of view of decomposition. The results presented in Table 2 are not only an effect of the Ashenhurst decomposition but the Curtis decomposition, too. So, if it was not possible to execute the Ashenhurst decomposition, the Curtis decomposition presented in [6] was performed.

Słowa kluczowe

PL

dekompozycja; FPGA; różniczki boole'owskie

EN

decomposition; FPGA; Boolean differentials

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2009
• Tom: R. 55, nr 8
• Strony: 621--623
• Opis fizyczny: Bibliogr. 11 poz., rys., tab., wzory

Twórcy

autor

Hrynkiewicz E.

autor

Kołodziński S.

• Politechnika Śląska, Gliwice,

Bibliografia

• [1] S. B. Akers: On the Theory of Boolean Functions, Journal of Society Indust. Appl. Math., No 7. 1959.
• [2] R. L. Ashenhurst: The Decompositions of Switching Functions, Proceedings of International Symposium on the Theory of Switching Functions, April, 1957.
• [3] S. Yang: Logic Synthesis and Optimisation Benchmarks User Guide Ver. 3.0, Microelectronic Center of North Carolina, January 15, 1991.
• [4] H. A. Curtis: A New Approach to the Design of Switching Circuits, Princeton, NJ, Van Nostrand, 172-194, 1962.
• [5] D. H. Green: Modern Logic Design, Addison Wesley, 1986.
• [6] E. Hrynkiewicz, S. Kołodziński: Decomposition of Logic Functions in Reed-Muller Spectral Domain, Proceedings of IEEE Workshop on Design and Diagnostics of Electronic Circuits and Systems, Kraków, Poland, April 11-13, 2007.
• [7] S. Kołodziński: Dekompozycja funkcji logicznych metodami spektralnymi zorientowana na realizację tych funkcji w układach FPGA typu tablicowego, Rozprawa doktorska, Politechnika Śląska Gliwice 2003.
• [8] T. Łuba, H. Selvaraj: A General Approach to Boolean Function Decomposition and Its Application in FPGA-based Synthesis, VLSI Design, Special Issue on Decomposition in VLSI Design, Vol. 3, No 3-4, 1995.
• [9] S. Minato: Binary decision Diagrams and Application for VLSI CAD, Springer, 1996.
• [10] T. Sasao, K. Kurimoto: Three Parameters to Find Functional Decomposition, Proceedings of Asia and South Pacific Design Automation Conference, Yokohama, Japan, January 26-28, 2000.
• [11] S. N. Yanushkevitch: Boolean Differential Calculus in Multi-Value Logic Design, DSc Thesis, Szczecin University of Technology, Poland, 1998.