Implementacja algorytmu syntezy układów odwracalnych w strukturach FPGA

• Autorzy: Gracki K. , Skorupski A. , Pawłowski M. , Kerntopf P.

Warianty tytułu

EN

FPGA implementation of a reversible circuit synthesis algorithm

• Języki publikacji: PL

Abstrakty

PL

Synteza układów odwracalnych prowadząca do uzyskania układu optymalnego (składającego się z minimalnej liczby bramek) jest problemem bardzo trudnym. Dlatego często rezygnuje się z optymalności na rzecz prostszych metod projektowania. W niniejszym artykule przedstawiono wyniki prac związanych z możliwością implementacji uniwersalnego układu, który wykorzystuje pewien heurystyczny algorytm i pozwala na realizację dowolnej funkcji trzech zmiennych. Prowadzone prace wykorzystują układy FPGA i ich opisy w języku VHDL.

EN

Optimal synthesis of reversible circuit synthesis is a hard task. This why simpler algorithms are developed for finding suboptimal solutions. We show a simple heuristic algorithm implemented in a programmable FPGA circuit. In this paper the new algorithm and its hardware implementation in VHDL are described. The presented algorithm is based on some feature of reversible functions, namely, on the ordering of columns in the truth table for a given reversible function. We define the so called s-distance as a minimal length of gates cascade which is capable to order a column of the truth table, i.e. to transform a right side column to become identical to the corresponding left side column. It is possible to store s-distances for all possible columns. For every function the SF-distance is defined as the sum of all column s-distances. The proposed simple algorithm selects the gates which lead to the minimal SF-distance for the rest function (a rest function is the function to be still implemented after the given gate has been selected). The process is repeated until the consecutive rest function will become the identity function. The algorithm can be implemented using the FPGA circuit as the block scheme from Fig. 3. The description of this module using VHDL is presented and discussed.

Słowa kluczowe

PL

odwracalne układy logiczne; język VHDL; układy FPGA

EN

reversible logic circuits; VHDL language; FPGA circuits

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2014
• Tom: R. 60, nr 7
• Strony: 477--479
• Opis fizyczny: Bibliogr. 6 poz., tab., rys.

Twórcy

autor

Gracki K.

• Politechnika Warszawska, Wydział Elektroniki i Technik Informacyjnych, ul. Nowowiejska 15/19, 00-665 Warszawa

autor

Skorupski A.

• Wyższa Szkoła Menedżerska, Wydział Informatyki Stosowanej i Technik Bezpieczeństwa, ul. ul. Kawęczyńska 36, 03-772 Warszawa

autor

Pawłowski M.

• Politechnika Warszawska, Wydział Elektroniki i Technik Informacyjnych, ul. Nowowiejska 15/19, 00-665 Warszawa

autor

Kerntopf P.

• Uniwersytet Łódzki, Wydział Fizyki i Informatyki Stosowanej , ul. Pomorska 149/153, 90-236 Łódź

Bibliografia

• [1] De Vos A.: Reversible Computing. Fundamentals, Quantum Computing, and Applications, Wiley-VCH, Berlin 2010.
• [2] Skorupski A., Szyprowski M., Kerntopf P.: Algorytm syntezy kombinacyjnych układów odwracalnych. Pomiary Automatyka Kontrola, vol. 57, s. 858-860, 2011.
• [3] Skorupski A., Pawłowski M., Gracki K., Kerntopf P.: Modelowanie w FPGA szyfratorów implementowanych w logice odwracalnej. Pomiary Automatyka Kontrola, vol. 58, s. 620-622, 2012.
• [4] Golubitsky O., Maslov D.: A study of optimal 4-bit reversible Toffoli circuits and their synthesis. IEEE Transactions on Computers, vol. 61, no. 9, s. 1341-1353, 2012.
• [5] Pawłowski M., Skorupski A.: Projektowanie złożonych układów cyfrowych, WKŁ Warszawa 2010.
• [6] Cyclone IV Device Handbook, Altera Corporation 2013.