Wyniki wyszukiwania - BazTech

1

The Algorithm for Reversible Circuits Synthesis

Skorupski Andrzej, Gracki Krzysztof

International Journal of Electronics and Telecommunications

|

2020

|

Vol. 66, No. 2

281--286

EN

In this paper the new synthesis method for reversible networks is proposed. The method is suitable to generate optimal circuits. The examples will be shown for three variables reversible functions but the method is scalable to larger number of variables. The algorithm could be easily implemented with high speed execution and without big consuming storage software. Section 1 contains general concepts about the reversible functions. In Section 2 there are presented various descriptions of reversible functions. One of them is the description using partitions. In Section 3 there are introduced the cascade of the reversible gates as the target of the synthesis algorithm. In order to achieve this target the definitions of the rest and remain functions will be helpful. Section 4 contains the proposed algorithm. There is introduced a classification of minterms distribution for a given function. To select the successive gates in the cascade the condition of the improvement the minterms distribution must be fulfilled. Section 4 describes the algorithm how to improve the minterms distributions in order to find the optimal cascade. Section 5 shows the one example of this algorithm.

2

The Transforming Method Between Two Reversible Functions

Skorupski Andrzej, Gracki Krzysztof

International Journal of Electronics and Telecommunications

|

2019

|

Vol. 65, No. 1

33--38

EN

This paper presents an original method of designing some special reversible circuits. This method is intended for the most popular gate set with three types of gates CNT (Control, NOT and Toffoli). The presented algorithm is based on two types of cascades with these reversible gates. The problem of transformation between two reversible functions is solved. This method allows to find optimal reversible circuits. The paper is organized as follows. Section 1 and 2 recalls basic concepts of reversible logic. Especially the two types of cascades of reversible function are presented. In Section 3 there is introduced a problem of analysis of the cascades. Section 4 describes the method of synthesis of the optimal cascade for transformation of the given reversible function into another one.

3

The Method of Reversible Circuits Design with One-gate Prediction

Skorupski A.

International Journal of Electronics and Telecommunications

|

2018

|

Vol. 64, No. 4

535--540

EN

This paper presents an original method of designing reversible circuits. This method is destined to most popular gate set with three types of gates CNT (Control, NOT and Toffoli). The presented algorithm based on graphical representation of the reversible function is called s-maps. This algorithm allows to find optimal or quasi-optimal reversible circuits. The paper is organized as follows. Section 1 recalls basic concepts of reversible logic. Especially the cascade of the gates as realization of reversible function is presented. In Section 2 there is introduced a classification of minterms distribution. The s-maps are the representation of the reversible functions where the minterms distribution is presented. The choice of the first gate in the cascade depends on possibility of improving the distribution. Section 3 describes the algorithm, namely how to find the optimal or quasi-optimal solutions of the given function.

4

Graphical Method of Reversible Circuits Synthesis

Skorupski A.

International Journal of Electronics and Telecommunications

|

2017

|

Vol. 63, No. 3

235--240

EN

This paper presents a new approach to designing reversible circuits. Reversible circuits can decrease energy dissipation theoretically to zero. This feature is a base to build quantum computers. The main problem of reversible logic is designing optimal reversible circuits i.e. circuits with minimal gates number implementing the given reversible function. There are many types of reversible gates. Most popular library is a set of three types of gates so called CNT (Control, NOT and Toffoli). The method presented in this paper is based only on the Toffoli gates. A graphical representation of the reversible function called s-maps is introduced in the paper. This representation allows to find optimal reversible circuits. The paper is organized as follows. Section 1 recalls basic concepts of reversible logic. In Section 2 a graphical representation of the reversible functions is presented. Section 3 describes the algorithm whereby all optimal solutions of the given function could be obtained.

5

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.

6

A hybrid PSO-GA algorithm for Reversible Circuits Synthesis

Podlaski K.

Pomiary Automatyka Kontrola

|

2014

|

R. 60, nr 7

474--476

EN

In the domain of Reversible Circuits there is still lack of good synthesis algorithms. There are many heuristic propositions, unfortunately, their results for a given reversible function usually are circuits far from optimal implementations. There are some propositions of using Particle Swarm Optimization (PSO) and Genetic Algorithms (GA) for this purpose. In this paper a new hybrid PSO-GA algorithm is proposed. Comparison of the proposed algorithm with the existing ones gives promising results.

PL

W dobie poszukiwania układów cyfrowych o niskim zużyciu energii układy odwracalne stanowią ciekawą alternatywę dla aktualnie stosowanych układów cyfrowych. Jednym z najistotniejszych zagadnień w dziedzinie budowy układów cyfrowych jest synteza układu reprezentującego zadaną funkcję. Niestety do dzisiaj nie ma dobrych rozwiązań w dziedzinie syntezy układów odwracalnych, istniejące rozwiązania są bardzo czasochłonne bądź generują układy o dużej redundancji. Ciekawą alternatywą dla obecnie stosowanych metod heurystycznych jest wykorzystanie algorytmów ewolucyjnych np. Particle Swarm Optimization (PSO) lub algorytmów genetycznych (GA). W niniejszym artykule zaproponowano nowy hybrydowy algorytm PSO-GA dostosowany do syntezy odwracalnych układów cyfrowych. Stworzony algorytm zastosowano do syntezy układów dla wybranych funkcji testowych (tzw. benchmarków) a wyniki porównano z wynikami otrzymywanymi za pomocą algorytmów heurystycznych. Wygenerowane układy okazały się mniej redundantne niż układy otrzymane w syntezie metodami heurystycznymi.

7

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.

8

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.

9

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.

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

Fault modeling and analysis of short defects in CMOS based reversible circuits

Amaricai A., Boncalo O.

International Journal of Microelectronics and Computer Science

|

2010

|

Vol. 1, nr 2

175-179

EN

This paper presents a SPICE based analysis of reversible circuits affected by the short defects: the gate oxide defect and the source-drain defect. The simulations are performed using realistic transistor models (the BSIM4 model) and take into account the resistive nature of the gate oxide and the source drain shorts. We aim at determining dependence between the short's resistance and the output voltage. Furthermore, we analyze the timing characteristics of reversible circuits affected by such faults. The goal is to develop logic and delay fault models for CMOS based reversible gates. This way, Boolean test strategies and logic level fault tolerant mechanisms and strategies can be devised for reversible circuits.