Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: reversible logistic gates

Sortuj według:

Ogranicz wyniki do:

Function-driven generalizations of decision diagrams and their applications

Kerntopf P.

Prace Naukowe Politechniki Warszawskiej. Elektronika

2005

z. 151

3--109

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.

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.