Wyniki wyszukiwania - BazTech

1

Heurystyczny algorytm syntezy quasi-optymalnych układów odwracalnych

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

Studia Informatica

|

2014

|

Vol. 35, nr 4

33--43

PL

W artykule przedstawiono nową metodę syntezy układów odwracalnych. Polega ona na stopniowym porządkowaniu bitów w kolejnych kolumnach części wyjściowej tablicy prawdy odwracalnej funkcji boolowskiej, aż do momentu zrównania części wyjściowej tablicy z jej częścią wejściową. Długość szacunkowej sekwencji bramek, która uporządkowałaby bity we wszystkich kolumnach wyjściowych, stanowi kryterium wyboru bramki w każdym kroku iteracji proponowanego algorytmu. Dla ponad 80% funkcji odwracalnych trzech zmiennych algorytm ten generuje układy optymalne.

EN

In this paper a new method of reversible circuits synthesis is presented. The method is based on iterative ordering of bits in subsequent output columns of the truth table of a reversible function until the output part of the truth table becomes identical with the input part. The length of the estimated shortest sequence which would guarantee the proper order of bits in all output columns is a criterion for choosing a gate at each step of the proposed algorithm. For over 80% of 3-variable reversible functions the algorithm generates optimal circuits.

2

Rekonfigurowanie funkcji odwracalnych modelowanych w układzie FPGA

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

Pomiary Automatyka Kontrola

|

2014

|

R. 60, nr 7

471--473

PL

Układy FPGA dobrze nadają się do modelowania układów odwracalnych, których implementacje sprzętowe są dopiero w stadium opracowywania. Układy odwracalne umożliwiają prostą realizację szyfratorów i deszyfratorów. W artykule rozpatrzono działanie dwóch szesnasto-bramkowych kaskad zbudowanych z cztero-wejściowych bramek odwracalnych NCT, aby uzyskać bajtowo zorientowany szyfrator. Zbiór bramek NCT o co najwyżej czterech wejściach zawiera 32 bramki, więc dla skonfigurowania jednej bramki potrzeba 5 bitów. Zatem kaskada może być określona przez 80-bitowe słowo, co dla dwóch kaskad daje 160-bitowy klucz. Po każdym wejściowym bajcie obie kaskady są rekonfigurowane za pomocą odpowiedniego przesuwania 80-bitowych słów. Sposoby przesuwania są określane przez dodatkowe bity klucza pomocniczego.

EN

FPGAs can be applied to modeling of reversible circuits because their practical realization is still under development. This technique enables implementing substitution ciphers. We try to build a byte-oriented stream cipher. Such a cipher uses two four-input and four-output cascades. Each of the cascades contains 16 reversible NCT gates. Because there exist 32 different NCT gates having at most four inputs we use 80 bits (16×5 bits) to determine one cascade so for two cascades 160 bits are needed. These bits are called the base key and are stored in the memory of a cipher. At the beginning of encryption the key is loaded to a circular shift register. After each input byte (a clock period) the contents of the shift register is shifted by a specified number of bits. The number of bits by which the register contents is shifted constitutes the second part of the cipher key. The shifting process causes changes in cascades after each input byte. If shifting the key is the same during both encryption and decryption, then the cipher will work correctly. In the paper, we present some methods of key shifting. If the register contents is shifted by 5 bits, then each gate is replaced by its predecessor (the first gate is replaced by the last one). The results of different shifting modes are presented showing that in all cases correct encryption/decryption is performed. For modeling and simulation of synthesis we used test-bench software ActiveHDL v 8.2 from ALDEC.

3

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

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

Pomiary Automatyka Kontrola

|

2014

|

R. 60, nr 7

477--479

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.

4

Szyfrator wykorzystujący odwracalne układy logiczne

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

Elektronika : konstrukcje, technologie, zastosowania

|

2014

|

Vol. 55, nr 8

102-107

PL

Celem pracy jest realizacja prostego szyfratora i deszyfratora. Przedstawiona implementacja wykorzystuje tzw. układy odwracalne. Własności bramek odwracalnych pozwalają na łatwe ich modelowanie w układach FPGA. Niniejszy artykuł pokazuje, jak w układzie FPGA można zaimplementować prosty szyfrator i deszyfrator strumieniowy, zmieniające swoją strukturę w zależności od klucza szyfrującego. Pokazano również możliwości modyfikacji projektu zwiększające odporność na ataki.

EN

The simple implementation of a cipher using reversible circuits was the aim of this work. For prototyping of the cipher we built a model using FPGA circuits. In such a case it was possible to show how structure of a reversible cascade implementing the cipher changes depending on the cipher key. Each gate used in a cascade of reversible gates is determined by the key word. Choosing different key words we get different cascades and different substitution encryption. We try to add some units to control a key value during each step of encryption and in this manner we are able to achieve more complex encryption.

5

Synteza układów odwracalnych metodą różnicową

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

Pomiary Automatyka Kontrola

|

2013

|

R. 59, nr 8

784--786

PL

W niniejszej pracy przedstawiony jest prosty algorytm projektowania układów odwracalnych. Proponowany algorytm polega na wyznaczeniu dla danej funkcji zbioru bramek (nazywanego zbiorem bramek pierwszych), które mogą znajdować się na początku układu kaskadowego realizującego zadaną funkcję. Po wyznaczeniu takiego zbioru można wybrać jeden z jego elementów, a następnie powtórzyć algorytm dla tzw. funkcji resz-towej. Postępuje się tak, aż do momentu, gdy funkcja resztowa stanie się funkcją identycznościową. Liczba iteracji algorytmu jest równa liczbie bramek projektowanej kaskady.

EN

Research on reversible logic circuits is motivated by advances in quantum computing, nanotechnology and low-power design. Im-plementation of such functions is realized by special gates. These gates always form a cascade circuit. Minimization of such circuits is a very difficult problem. In this paper a novel concept of synthesis of reversible logic is presented. For simplicity, the method is described for three variables only but it is scalable for more variables. The proposed method is based on XOR function applied to input and output sides of the truth table of a function to be synthesized. The result of applying XOR function indicates bits in the truth table which have to be changed by reversible gates. Due to this property the number of analyzed gates is small. We present the comparison of three variants of the difference method. Each of them leads to different numbers of 3-variable functions for which exact optimal circuits have been found.

6

Projektowanie odwracalnych układów w architekturze LNN

Szyprowski M., Kerntopf P.

Pomiary Automatyka Kontrola

|

2013

|

R. 59, nr 8

781--783

PL

Najnowszy kierunek w projektowaniu kwantowych układów odwracalnych uwzględnia fakt, że interakcje odbywają się tylko na sąsiadujących liniach. Ostatnio zaproponowano wiele algorytmów projektowania takich układów oraz zajmowano się ich optymalizacją. W pracy przedstawiony jest przegląd tych rozwiązań oraz perspektywy rozwoju tej ważnej dziedziny.

EN

Computation is called reversible if it is realized by circuits implementing bijective mappings. It is an emerging research area which has applications in many new areas of computer science, e.g. quantum computing, nanotechnologies, optical computing, digital signal processing, communications, bioinformatics, cryptography as well as low power computation. Quantum computation, which by nature is reversible, constitutes an especially attractive field of research due to a promise of an enormous speed-up of computing processes in the future. However, it has appeared that in some quantum technologies there are intrinsic limitations, namely, physically realizable operations would be only interactions between neighbor lines (also called qubits). As reversible circuits form a subset of quantum circuits there is a need to convert general reversible circuits into the so-called Linear Nearest Neighbor (LNN) architecture. In this architecture any gate operates between adjacent qubits only. Thus, recently there has been a new research objective to develop efficient methods for designing reversible circuits in the LNN architecture. This paper gives an overview of the present advances in this field.

7

Nowe reguły przesuwania bramek w układach odwracalnych

Szyprowski M., Kerntopf P.

Pomiary Automatyka Kontrola

|

2013

|

R. 59, nr 8

787--789

PL

Jedną z możliwości redukcji układów odwracalnych daje przesuwanie bramek. W pracy zaproponowano nowe reguły takich przesunięć dla układów budowanych ze standardowej biblioteki bramek odwracalnych NCT. Umożliwiają one eliminację bramek o dużej liczbie wejść/wyjść, które mają największy tzw. koszt kwantowy. Opracowane przez nas reguły mogą być stosowane dla dowolnej liczby wejść układu. Umożliwia to projektowanie układów odwracalnych o zredukowanym koszcie kwantowym. Podane przez nas przykłady pokazują, że oszczędności w porównaniu z układami publikowanymi w literaturze mogą być znaczne.

EN

Synthesis of reversible logic circuits is the most intensively studied topic of the research area called reversible computation (circuits are reversible if they represent bijective mappings). This new research area has applications in many fields of computer science, e.g. quantum computing, nanotechnologies, optical computing, digital signal processing, communications, bioinformatics, cryptography as well as in low power computation. Recent advances consist in reducing numbers of gates, garbage bits or quantum cost. Some reversible circuit synthesis algorithms generate circuits in which majority of gates have large or even maximal size (i.e. equal to the number of inputs/outputs. However, quantum cost of multi-control generalized Toffoli gates is very high. In this paper it is shown how to reduce the quantum cost of circuits by eliminating most of large gates or even all of them. Namely, a new subset of moving rules useful for reducing the quantum cost is presented. Using this subset, it is possible to reduce the number of maximal-size gates to zero for even functions, and to one for odd functions, according to the known theorem. In the paper substantial savings in the quantum cost are presented for designs taken from recent publications.

8

Odwracalne układy programowalne

Szyprowski M., Kerntopf P.

Pomiary Automatyka Kontrola

|

2012

|

R. 58, nr 7

644-646

PL

Pierwsze próby nawiązania w dziedzinie obliczeń odwracalnych do układów programowalnych pojawiły się w roku 2001, kiedy zademonstrowano zalety ich regularnej struktury do implementacji funkcji boolowskich za pomocą odwracalnych bramek logicznych. Od tego czasu zaproponowano kilka rozwiązań odwracalnych układów programowalnych, które nazywane są Reversible-PLA (R-PLA) i Reversible-FPGA (R-FPGA), oraz zajmowano się optymalizacją i testowaniem takich układów. W pracy przedstawiono przegląd tych rozwiązań oraz perspektywy rozwoju tej ważnej dziedziny.

EN

Reversible computation (i.e. bijective mapping) is an emerging research area. It has applications in many new areas of computer science, e.g. quantum computing, nanotechnologies, optical computing, digital signal processing, communications, bioinformatics, cryptography as well as in low power computation. This paper gives an overview of the present advances in the field of reversible programmable logic gate structures. The first part describes an attempt [8] to construct regular structures of Reversible Programmable Logic Arrays (R-PLAs). The second part focuses on construction of Reversible Field Programmable Gate Arrays [15]. Both presented approaches are based on classic Boolean PLA and FPGA design, where each building block has been constructed from reversible gates. The main drawback of the R-PLA and R-FPGA approaches is the fact that they are based on classic Boolean building blocks, which in case of reversible logic require many additional signal lines to keep the circuit reversibility. Recent advances in this area consist in reducing the number of gates, garbage signal lines and overall quantum cost of the structures. When comparing design of such circuits with known reversible circuit synthesis approaches one might expect a real breakdown in terms of the circuit size and cost when R-PLA and R-FPGA structures will be constructed directly from reversible gates without an intermediate step with classic Boolean building blocks.

9

Modelowanie w FPGA szyfratorów implementowanych w logice odwracalnej

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

Pomiary Automatyka Kontrola

|

2012

|

R. 58, nr 7

620-622

PL

Idea projektowania cyfrowych układów w logice odwracalnej jest wykorzystywana do budowy układów małej mocy. Modelowanie takich układów stało się możliwe dzięki zastosowaniu współczesnych narzędzi symulacyjnych stosowanych do programowania układów FPGA. W niniejszym artykule pokazano wykorzystanie logiki odwracalnej do szyfrowania i przykładową implementację takiego układu. Dla zwiększenia złożoności szyfratora rozbudowano go o programowaną matrycę krosującą zmieniająca kolejność sygnałów wejściowych oraz o układ przekształcania klucza szyfrującego.

EN

A circuit (gate) is called reversible if there is one-to-one correspondence between its inputs and outputs. Research on reversible logic circuits is motivated by advances in quantum computing, nanotechnology and low-power design. Therefore, reversible logic synthesis has been recently intensively studied. The attention is focused mainly on the synthesis of circuits built from the NCT library of gates, i.e. NOT, CNOT and Toffoli gates. Many developers work with design of classical digital devices like registers, adders, processors etc. using reversible circuits. Recently they have also tried to build more complex devices like for example an encryption devices [4, 5, 6, 7], however, only for saving energy. The other point of view, presented in this paper, is to use some features of reversible function. One of them is a big number of functions. For n variables there exist 2n! different function. There are 24 reversible functions for 2 variables, 40320 functions for 3 variables and more than 20x1012 for 4 variables. Synthesis of circuits using 8 variable reversible function is too complicated. We use two cascades using 4 variable reversible function. We consider a 16-gates cascade. Depending on a given reversible function different cascade circuits will be obtained. These circuits correspond to a cryptographic key. Because we assume a 16-gates cascade and there exist 32 various gates we use 80-bit key for a 4-input cascade. Hence, for two cascades a cryptographic key will consist of 160 bits. Modern simulation tools based on FPGAs have enabled modeling of such circuits. In the paper we study application of reversible logic to developing encryption circuits. The results of FPGA-based simulation of a simple encryption circuit implemented built from reversible gates are also presented.

10

Metody konstrukcji optymalnych układów odwracalnych

Szyprowski M., Kerntopf P.

Pomiary Automatyka Kontrola

|

2012

|

R. 58, nr 7

647-649

PL

Dopiero w 2010 roku, po całej dekadzie badań, opracowano pierwszą metodę syntezy optymalnych układów odwracalnych dla dowolnych funkcji czterech zmiennych. Układy te budowane były ze standardowej biblioteki bramek odwracalnych NCT, mających wyłącznie tzw. pozytywne sterowanie. W pracy opisujemy wyniki naszych rozszerzeń tej metody na przypadek minimalizowania kosztu kwantowego dla układów o zadanej liczbie bramek, a także na układy budowane z bramek NCT o mieszanym sterowaniu (tzn. zarówno o pozytywnym, jak i negatywnym).

EN

computation (i.e. bijective mapping). This emerging research area has applications in many new areas of computer science, e.g. quantum computing, nanotechnologies, optical computing, digital signal processing, communications, bioinformatics, cryptography as well as in low power computation. Recent advances consist in reducing numbers of gates, garbage bits or quantum cost. Synthesis of optimal reversible circuits is a very hard problem even for small input/output circuits. In 2010 a method for construction of 4-input/output optimal circuits was developed for circuits constructed using reversible gates from NCT library [5]. In the paper we present a summary of the results of our extensions to this method. We have developed an approach for minimization of quantum cost of the 4-input/output circuits [7]. Our computational experiments have been conducted for two sets of reversible gates: a standard NCT library and extended mixed-polarity NCT library, which consists of gates with both positive and negative control lines. Using our tools we have found circuits for the known reversible benchmarks which have lower quantum cost than any of the best known implementations so far. Based on the data of our experiments we have made a statistical comparison of the optimal circuits built from standard NCT and libraries.

11

Realizacje układów odwracalnych w technologiach półprzewodnikowych

Szyprowski M., Kerntopf P.

Pomiary Automatyka Kontrola

|

2011

|

R. 57, nr 8

911-913

PL

Dziedzina syntezy odwracalnych układów logicznych jest rozwijana bardzo intensywnie. Zaproponowane zostały nawet konstrukcje układów odwracalnych z klasycznych elementów półprzewodnikowych. Wykazują one szereg zalet, m.in. mogą być stosowane jako układy o bardzo małym poborze mocy lub są w stanie realizować pewne klasy algorytmów obliczeń kwantowych. W poniższym referacie przedstawiamy przegląd rozwiązań realizacji układów odwracalnych z wykorzystywaniem klasycznych elementów półprzewodnikowych.

EN

Synthesis of reversible functions (i.e. bijective mappings) is an emerging research area. It is mainly motivated by advances in quantum computing and application of reversible circuits to quantum computing. However, some research has also been done in the area of implementation of reversible circuits in classic semiconductor technologies. Such circuits, built mainly from CMOS transistors, reveal their advantages. They can be successfully applied to the area of low power design. Recently, more attention has also been given to such circuits as they can also be used to implement some classes of quantum algorithms and take the advantage of quantum computing to stretch the limits of the classical computation paradigms. This paper gives an overview of the present advances in the field of reversible circuits built in semiconductor technologies. It describes reversible circuits built from CMOS transistor based switching networks and principles of adiabatic circuits. The last part of the paper presents the foundation of quantum computatiosn that can be realized by reversible circuits with asynchronous feedback.

12

Algorytm syntezy kombinacyjnych układów odwracalnych

Skorupski A., Szyprowski M., Kerntopf P.

Pomiary Automatyka Kontrola

|

2011

|

R. 57, nr 8

858-860

PL

W pracy przedstawiono koncepcję nowego algorytmu syntezy układów odwracalnych. Jest on oparty na oryginalnej reprezentacji zamiany wierszy w tablicy prawdy. Dla układów o trzech wejściach i trzech wyjściach sformułowano kryteria takiego doboru bramek, aby otrzymać układ zbliżony do optymalnego. Następnie podano przykład zastosowania przedstawionego algorytmu do syntezy układów o trzech wejściach i trzech wyjściach z bramek Toffoliego.

EN

A gate or circuit is reversible if there is one-to-one correspondence between its input signals and output signals, i.e. if they implement bijective functions. Research on reversible logic circuits is motivated by advances in quantum computing, nanotechnology and low-power design. Recently, the attention has been focused on the synthesis of reversible circuits built from the NCT library of gates consisting of NOT, CNOT and Toffoli gates. This paper presents a novel algorithm for synthesis of reversible circuits. It is based on a new representation of row exchanges in the truth table. There is described how each possible row exchange determines the set of subsequent gates in a circuit, basing on the newly introduced cube of row exchanges. Next, the criteria for the choice of NCT reversible gates are formulated. For an exemplary function, the presented algorithm generates an optimal reversible circuit with 3 inputs and 3 outputs. It can also be generalized to any number of inputs and outputs.

13

Sekwencyjne odwracalne układy logiczne

Zagniński P., Kerntopf P.

Pomiary Automatyka Kontrola

|

2010

|

R. 56, nr 7

678-680

PL

Układy odwracalne realizują wzajemnie jednoznaczne odwzorowania sygnałów wejściowych na sygnały wyjściowe, tj. nie prowadzące do straty informacji. Badania nad tymi układami prowadzone są bardzo intensywnie. Początkowo zajmowano się głównie syntezą kombinacyjnych układów, dopiero w ostatnich latach liczba publikacji na temat sekwencyjnych układów wzrosła. W pracy przedstawiono układy odwracalnych zatrzasków, które zaproponowano w literaturze, i sformułowano otwarte problemy w tej dziedzinie.

EN

Reversible computations stretch the limits of the classical computa-tions, bounded otherwise by energy loss. They are also the basis for the emerging quantum technologies. Though such designs have succeeded since they are logically equivalent with classical designs, there is still much room for improvement. Reversible logic circuit synthesis received much attention in the past decade from the computer science community due to its, as yet unrivaled, potential to satisfy the requirements for power efficient computations. The initial focus has been given to the combinational logic circuits, as the foundation of a general theory for the reversible circuit synthesis. Recently, more attention is given to sequential circuits as they form the basis of the well known state-based processing of the traditional computers. The research in this field started in 1980 with the pioneering work of Toffoli [3], followed only in 1996 by Picton [7]. Next publications by Chuang and Wang [8], and Rice [9] appeared in the last decade, followed by some very recent publications, e.g. Banerjee and Pathak [10]. This paper gives an overview of the current advances in the field of the sequential reversible logic presenting latches, the most common sequential circuits, and open problems.

14

Porównanie efektywności heurystycznych miar złożoności odwracalnych funkcji boolowskich

Szyprowski M., Kerntopf P.

Pomiary Automatyka Kontrola

|

2009

|

R. 55, nr 8

581-583

PL

Funkcja boolowska jest nazywana odwracalną, gdy jest wzajemnie jednoznaczna. W literaturze zaproponowano kilka heurystyk służących do syntezy odwracalnych układów logicznych, jednak do tej pory nie znaleziono rozwiązania, które dawałoby zadowalające wyniki. Przy pracach nad ulepszaniem tych algorytmów potrzebne jest dobre kryterium oceny jakości poszczególnych heurystyk. W pracy pokazano jak wykorzystać bazę optymalnych układów odwracalnych do oceny działania heurystyk oraz przedstawiono wyniki obliczeń pozwalających na porównanie ich efektywności.

EN

A Boolean logic function is reversible if it is a bijective mapping. Synthesis of such functions is motivated by advances in quantum computing, nanotechnologies and low power design. Several heuristic synthesis algorithms has been proposed, but so far none of them produces circuits of good quality in acceptable time. All of them are based on exploration of the search tree guided by a complexity measure function. Search for better algorithms is important and for this aim a good evaluation criterion of a heuristic complexity measure quality is needed. In this article the comparison of reversible function complexity measures known from the literature is made. Their accuracy is checked on the library of the optimal circuits of 3 inputs/outputs. The results are presented in Table 1. The numeric factor Q is introduced on the basis of calculating the probability of taking a wrong way in the search tree by a synthesis algorithm for every reversible function. This factor was calculated for five heuristic complexity measures and shown in Table 2. According to it the Reed-Muller spectrum based complexity measure gives best synthesis results, however there is still a lot of space for improvements.

15

Decompositions of reversible logic circuits

Szyprowski M., Kerntopf P.

Pomiary Automatyka Kontrola

|

2009

|

R. 55, nr 8

609-611

EN

Results of research on decompositions of reversible circuits into blocks are presented where each block is constructed from one kind of gates. The main contribution of this paper consists in discovering that there exist more decompositions than the only one considered in the literature up to now. Moreover, it is shown that all of these decompositions correspond to circuits having different average minimal cost. This fact can be used in the future to guide heuristics in developing better algorithms for reversible logic circuit synthesis.

PL

Układ logiczny jest odwracalny, gdy liczba wejść jest równa liczbie wyjść, a funkcja realizowana przez ten układ jest wzajemnie jednoznaczna. Do tej pory tylko w jednej publikacji rozważano dekompozycję układów odwracalnych na takie bloki, z których każdy jest złożony z bramek odwracalnych jednego typu. W pracy prezentujemy znalezione przez nas trzy inne dekompozycje układów. Dzięki znalezieniu przez nas wszystkich optymalnych układów o trzech wejściach i trzech wyjściach, pokazaliśmy, że rozpatrywane przez nas nowe dekompozycje prowadzą do układów o mniejszym koszcie niż dla wcześniej rozpatrywanej dekompozycji. Zatem znalezione przez nas dekompozycje mogą mieć duże znaczenie przy konstruowaniu algorytmów syntezy odwracalnych układów logicznych generujących układy o mniejszym koszcie niż opublikowane dotąd algorytmy.

16

Synteza odwracalnych układów logicznych

Kerntopf P.

Pomiary Automatyka Kontrola

|

2007

|

R. 53, nr 7

78-80

PL

Opracowywanie metod syntezy binarnych odwracalnych układów logicznych rozpoczęto niedawno. Artykuł zawiera krótki przegląd publikacji na ten temat, w tym wyniki autora.

EN

The development of synthesis methods for binary reversible logic circuits has started recently. The paper presents a brief survey of publications on the topic including the author's results.

17

Function-driven generalizations of decision diagrams and their applications

Kerntopf P.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2005

|

z. 151

3--109

EN

The monograph is devoted to new generalizations of decision diagrams (DDs) that lead to more compact representations of Boolean and multiple-valued functions. The objective is a scientific contribution to the theory of decision diagrams by offering new possibilities of DD node expansions. In the monograph, we present our original concepts and compare them with those others available in the literature. Binary decision diagrams (BDDs) are the state-of the-art data structure in VLSI CAD and they are widely used in many applications, including formal verification, testing, simulation and logic synthesis of VLSI circuits (e.g. logic synthesis of FPGAs and pass-transistor circuits). They have also found applications outside VLSI CAD. Representations of functions, sets, relations, graphs and matrices using DDs are now successfully used in many areas, like combinatorial problems, artificial intelligence, learning theory, verification of communication protocols, verification of process networks, computer graphics, signal processing, symbolic analysis of large analog circuits, decodingof error-correcting codes, neural nets, reliability analysis, expert systems, etc. A major drawback of all BDD-based systems 8is that the underlying data structure is very sensitive to a chosen variable ordering and, for some functions, no efficient representation even exists, like in the case of the Boolean multiplication. This why several extentions of the basic BDD structure have been proposed and studied recently, including introducing new node expansion types. However, search for new generalisations is still going on. A very promising extension to BDDs are transformed BDDs (TBDDs). They are based on an encodingt of the inputs, while the BDD structure itself remains unchanged. It`s known that some families of Boolean functions can be represented by TBDDs of linear size with respect to the number of variables, while all BDDs for them require exponential size. In this monograph, we introduce new representation called function-driven binary decision diagrams (BDDs). Then we study fBDDs corresponding to arbitrary nonlinear transformations of BDDs and many variants of decision diagrams based on them. a formal framework for generalization of diffrent kinds of binary and multiple-valued diagrams developed up to now is also proposed. Next we present research in the direction of looking for heuristics giving chance of finding smaller DDs than the best known ones. We also provide results of experiments for approaches presented here. An extension of the well-known sifting algorithm nonlinear transformations is presented, based on the combination of three adjacent levels of the decision diagram. Finally , we address synthesis of binary and multi-valued reversible logic circuits by applying function-driven decision diagrams (fDDs) described in this monograph. A synthesis algorithm is based on a new complecit7y measure of reversible circuits depending on sizes of corresponding fDDs. Experimental results of running of the algorithm for reversible circuits with three inputs and three outputs are provided and compared with previously published. Pioneering research on universality and efficiency of reversible gates is also presented.

PL

Niniejsza rozprawa poświęcona jest nowym uogólnieniom diagramów decyzyjnych, które prowadza do zmniejszenia rozmiarów reprezentacji funkcji boolowskich i wielowartościowych w stosunku do standardowych binarnych diagramów decyzyjnych (BDD) wielowartościowych diagramów decyzyjnych (MDD). Jej celem jest opracowanie teorii i zastosowań diagramów decyzyjnych poprzez zaproponowanie nowych możliwości dekompozycji węzłów w tych diagramach. Przedstawione koncepcje są oryginalnym wkładem autora. W pracy zostały one porównane z koncepcjami znanymi w literaturze. Binarne diagramy decyzyjne są obecnie szeroko stosowanymi strukturami danych we wspomaganym komputerowo projektowaniu (ang. CAD) układów VLSI i w wielu zastosowaniach , m.in. w sformalizowanej weryfikacji,testowaniu, symulacji i syntezie logicznej układów VLSI, np.: w syntezie logicznej FPGA (ang. Field Programmable Gate Array) i inntych układów.Znalazły także zastosowania poza dziedzina CAD VLSI. Reprezentacje funkcji, zbiorów, relacji, grafów i macierzy w postaci diagramów decyzyjnych są obecnie z powodzeniem stosowane w wielu dziedzinach, w tym w rozwiązywaniu problemów kombinatorycznych, sztucznej inteligencji, teorii uczenia się, weryfikacji protokołów komunikacyjnych, weryfikacji sieci procesów, grafice komputerowej, przetwarzaniu sygnałow, symbolicznej analizie niezawodnosciowej, systemach eksperckich itd. Jednak słabością wszystkich systemów opartych na BDD jest silna zależność rozmiarów diagramów od wybranego uporządkowania zmiennych, a także brak efektywnych reprezentacji dla pewnych funkcji, jak na przykład dla funkcji wyjściowych układów mnożących i innych układów arytmetycznych. Dlatego zaproponowano i przebadano wiele uogólnień standardowych BDD, m.in. wprowadzając nowe rodzaje dekompozycji węzłów. Tym niemniej poszukiwania nowych uogólnień BDD nadal są prowadzone. Obiecującym uogólnieniem są tzw. Transformowane BDD (TBDD), które oparte są na kodowaniu zmiennych, bez dokonywania zmian w strukturze BDD. Na przykład wiadomo, że dla niektórych rodzin funkcji boolowskich liniowe transformacje prowadza do diagramów TBDD, których rozmiary rosną liniowo, podczas gdy dla tych samych rodzin funkcji rozmiary standardowych BDD rosną wykładniczo. W rozprawie rozpatrzono po raz pierwszy w literaturze nieliniowe transformacje BDD i wiele wariantów diagramów opartych na tych transformacjach. Zaprezentowano tego rodzaju uogólnienia wielu wariantów diagramów znanych z literatury. Przedstawiono badania zmierzające do znalezienia heurystycznych metod dających szanse otrzymywania diagramów decyzyjnych o mniejszych rozmiarach niż znane do tej pory. Podano także wyniki eksperymentów, których celem było sprawdzenie efektywności tego podejścia. Rozpatrzono i zbadano uogólnienie algorytmu dynamicznej redukcji rozmiarów diagramów, znanego pod nazwą Sifting, otrzymane przez dodanie do siftingu nieliniowych transformacji (definiujących sposób przedstawienia węzłów w kolejnych dwóch lub trzech poziomach diagramu). W dalszej części rozprawy wykorzystano wprowadzone we wcześniejszych rozdziałach uogólnienia diagramów decyzyjnych (ang. Function-driven decision diagrams) do opracowania algorytmu syntezy układów logicznych odwracalnych (ang. reversible). Algorytm ten oparty jest na zaproponowanej przez autora nowej koncepcji miary złożoności układów odwracalnych. Został on zaprogramowany, a wyniki eksperymentalne dla układów o trzech wejściach i trzech wyjściach zamieszczono w pracy i porównano je z opublikowanymi wcześniej w literaturze, pokazujac, że przedstawiony tu algorytm daje zmniejszenie kosztów układów. Dwa rozdziały poświęcone są pionierskim badaniom nad uniwersalnością i efektywnością bramek odwracalnych, m.in. podano konstrukcję bramek o maksymalnej efektywności. Wyniki tych prac były już wielokrotnie cytowane w publikacjach innych autorów.