Wyniki wyszukiwania - BazTech

1

Synteza logiczna – aktualne trendy i perspektywy

Mazurkiewicz Tomasz

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2021

|

nr 3

88--92

PL

Synteza logiczna jest gałęzią nauki, która rozwija się nieprzerwanie od kilkudziesięciu lat. Pozornie można odnieść wrażenie, że ze względu na dużą dojrzałość zaproponowanych metod w zakresie tej tematyki nie dzieje się nic nowego. Jednakże ostatnie prace, publikowane również na łamach Przeglądu Telekomunikacyjnego i Wiadomości Telekomunikacyjnych, zdają się przeczyć tej tezie. W artykule przedstawiono najważniejsze – zdaniem autora – kierunki rozwoju metod syntezy logicznej. Wskazano również technologie, których rozwój w najbliższych latach najbardziej może przyczynić się do wzmożonego zainteresowania opracowaniem nowatorskich metod.

EN

Logic synthesis is a branch of science that has been developing for several decades. It is possible to get the impression that nothing new is happening in this field due to the high maturity of the already proposed methods. However, recent works, also published in this journal, seem to contradict this thesis. This article presents the most interesting directions (in the author's opinion) in the development of logic synthesis methods. Moreover, the technologies, which progress in the coming years may contribute most to the increased interest in this field, are indicated.

2

Application of Graph Theory Algorithms in Non-disjoint Functional Decomposition of Speciﬁc Boolean Functions

Mazurkiewicz Tomasz

Journal of Telecommunications and Information Technology

|

2020

|

nr 3

67--74

EN

Functional decomposition is a technique that allows to minimize Boolean functions that cannot be optimally minimized using other methods, such as variable reduction and linear decomposition. A heuristic method for ﬁnding nondisjoint decomposition has been proposed lately. In this paper, we examine how the usage of diﬀerent graph theory techniques affects the computation time and the quality of the solution obtained. In total, six dfferent approaches were analyzed. The results presented herein prove the advantages of the proposed approaches, showing that results obtained for standard benchmark M-out-of-20 functions are better than those presented in previous publication. Results obtained for randomly generated functions prove that time complexity and scalability are signiﬁcantly better when using the heuristic graph coloring algorithm. However, quality of the solution is worse, in general.

3

Technology mapping oriented to adaptive logic modules

Kubica M., Kania D.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2019

|

Vol. 67, nr 5

947--956

EN

This paper presents an innovative method of technology mapping of the circuits in ALM appearing in FPGA devices by Intel. The essence of the idea is based on using triangle tables that are connected with different configurations of blocks. The innovation of the proposed method focuses on the possibility of choosing an appropriate configuration of an ALM block, which is connected with choosing an appropriate decomposition path. The effectiveness of the proposed technique of technology mapping is proved by experiments conducted on combinational and sequential circuits.

4

Speed Targeted Minimization of Finite State Machines for CPLDs

Klimowicz A.

Measurement Automation Monitoring

|

2018

|

Vol. 64, No. 1

5--7

EN

A method of the minimization finite state machines (FSM) is proposed. In this method, such optimization criterion as the critical delay path is taken into account already at the stage of minimizing internal states. The method is based on sequential merging of two internal states including the optimization criteria. The critical path is estimated for CPLD devices. In addition, the proposed method allows one to minimize the number of transitions and input variables of the FSM. Experimental results shows, that the maximum clock frequency of minimized FSMs is higher by 17% comparing to initial FSM.

5

On Transformation of a Logical Circuit to a Circuit with NAND and NOR Gates Only

Baranov S., Karatkevich A.

International Journal of Electronics and Telecommunications

|

2018

|

Vol. 64, No. 3

373--378

EN

In the paper we consider fast transformation of a multilevel and multioutput circuit with AND, OR and NOT gates into a functionally equivalent circuit with NAND and NOR gates. The task can be solved by replacing AND and OR gates by NAND or NOR gates, which requires in some cases introducing the additional inverters or splitting the gates. In the paper the quick approximation algorithms of the circuit transformation are proposed, minimizing number of the inverters. The presented algorithms allow transformation of any multilevel circuit into a circuit being a combination of NOR gates, NAND gates or both types of universal gates.

6

Optimization on the complementation procedure towards efficient implementation of the index generation function

Borowik G.

International Journal of Applied Mathematics and Computer Science

|

2018

|

Vol. 28, no. 4

803--815

EN

In the era of big data, solutions are desired that would be capable of efficient data reduction. This paper presents a summary of research on an algorithm for complementation of a Boolean function which is fundamental for logic synthesis and data mining. Successively, the existing problems and their proposed solutions are examined, including the analysis of current implementations of the algorithm. Then, methods to speed up the computation process and efficient parallel implementation of the algorithm are shown; they include optimization of data representation, recursive decomposition, merging, and removal of redundant data. Besides the discussion of computational complexity, the paper compares the processing times of the proposed solution with those for the well-known analysis and data mining systems. Although the presented idea is focused on searching for all possible solutions, it can be restricted to finding just those of the smallest size. Both approaches are of great application potential, including proving mathematical theorems, logic synthesis, especially index generation functions, or data processing and mining such as feature selection, data discretization, rule generation, etc. The problem considered is NP-hard, and it is easy to point to examples that are not solvable within the expected amount of time. However, the solution allows the barrier of computations to be moved one step further. For example, the unique algorithm can calculate, as the only one at the moment, all minimal sets of features for few standard benchmarks. Unlike many existing methods, the algorithm additionally works with undetermined values. The result of this research is an easily extendable experimental software that is the fastest among the tested solutions and the data mining systems.

7

Decomposition of multi-output functions oriented to configurability of logic blocks

Kubica M., Kania D.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2017

|

Vol. 65, nr 3

317--331

EN

The main goal of the paper is to present a logic synthesis strategy dedicated to an LUT-based FPGA. New elements of the proposed synthesis strategy include: an original method of function decomposition, non-disjoint decomposition, and technology mapping dedicated to configurability of logic blocks. The aim of all of the proposed synthesis approaches is the sharing of appropriately configured logic blocks. Innovation of the methods is based on the way of searching decomposition, which relies on multiple cutting of an MTBDD diagram describing a multi-output function. The essence of the proposed algorithms rests on the method of unicoding dedicated to sharing resources, searching non-disjoint decomposition on the basis of the partition of root tables, and choosing the levels of diagram cutting that will guarantee the best mapping to complex logic blocks. The methods mentioned above were implemented in the MultiDec tool. The efficiency of the analyzed methods was experimentally confirmed by comparing the synthesis results with both academic and commercial tools.

8

Optimization problems in the synthesis of multiple-valued logic networks

Deniziak S., Wiśniewski M., Kurczyna K.

Measurement Automation Monitoring

|

2016

|

Vol. 62, No. 5

166--168

EN

The paper discusses some aspects of FPGA-oriented synthesis of multiple-valued logic (MVL) network, i.e. a network of modules connected by multiple-valued signals. MVL networks are built during high-level synthesis, as a source specification of logical systems or during re-synthesis of gate-level circuits. FPGA-oriented synthesis of MVL is based on decomposing modules into smaller ones, each fitting in one logic cell. In this paper, we show that the order, according to which the modules are decomposed, has a great influence on the efficiency of the synthesis. This paper presents the case study which demonstrates the above problem as well as some experimental results and conclusions.

9

SMTBDD : New Form of BDD for Logic Synthesis

Kubica M., Kania D.

International Journal of Electronics and Telecommunications

|

2016

|

Vol. 62, No. 1

33--41

EN

The main purpose of the paper is to suggest a new form of BDD - SMTBDD diagram, methods of obtaining, and its basic features. The idea of using SMTBDD diagram in the process of logic synthesis dedicated to FPGA structures is presented. The creation of SMTBDD diagrams is the result of cutting BDD diagram which is the effect of multiple decomposition. The essence of a proposed decomposition method rests on the way of determining the number of necessary ‘g’ bounded functions on the basis of the content of a root table connected with an appropriate SMTBDD diagram. The article presents the methods of searching non-disjoint decomposition using SMTBDD diagrams. Besides, it analyzes the techniques of choosing cutting levels as far as effective technology mapping is concerned. The paper also discusses the results of the experiments which confirm the efficiency of the analyzed decomposition methods.

10

Dual synthesis of Petri net based application specific logic controllers with increased safety

Tkacz J., Bukowiec A., Adamski M.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2016

|

Vol. 64, nr 3

467--478

EN

In the paper, design flow of the application specific logic controllers with increased safety by means of Petri nets is proposed. The controller architecture is based on duplicated control unit and comparison results from both units. One specification of control algorithm is used by means of Petri net for both units. The hardware duplication is obtained during dual synthesis process. This process uses two different logic synthesis methods to obtain two different hardware configurations for both control units. Additionally, the dual verification is applied to increase reliability of the control algorithm. Such design flow simplifies the process of realization of control systems with increased safety.

11

Efektywna procedura uzupełnienia funkcji boolowskich i jej zastosowanie w eksploracji danych

Borowik G., Kowalski K.

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2015

|

nr 2-3

55--63

PL

Podsumowano badania nad algorytmem uzupełnienia funkcji boolowskich. Wskazano rozwiązania, zaproponowane w czasie badan, w tym analizę istniejącej implementacji algorytmu oraz wykorzystane i proponowane sposoby przyśpieszenia obliczeń. Badania zostały zakończone wydajną implementacją współbieżną algorytmu. Wykonano zestawienie czasów obliczeń istniejących systemów analizy i eksploracji danych z autorską implementacją. Wynikiem prac jest łatwo rozszerzalne eksperymentalne oprogramowanie - najszybsze z testowanych rozwiązań i systemów eksploracji danych.

EN

The paper provides three-year research summary related to the Boolean function complement algorithm. It contains computational issues of the algorithm, the analysis of existing implementations, and solutions that have been considered during the research including both proposed and implemented enhancements to reduce the calculation time. As a result of the research new algorithm has been developed that has finally been implemented as efficient concurrent procedure. At last, the computation time comparison of existing data mining systems to the authors' implementation has been shown. These studies have resulted in experimental software that is the most effective of the tested solutions and data mining systems.

12

Dekompozycja kolumnowa zespołu funkcji opisanego za pomocą MTBDD ukierunkowana na użycie elementu XOR

Białas M., Kania D.

Elektronika : konstrukcje, technologie, zastosowania

|

2015

|

Vol. 56, nr 10

89-94

PL

Elementem składowym układów CPLD są bloki logiczne typu PAL. W blokach tych występuje element XOR, który umożliwia efektywne wykorzystanie zasobów struktury programowalnej. W artykule przedstawiono oryginalną metodę dekompozycji zespołu funkcji opisanego za pomocą MTBDD ukierunkowaną na wykorzystanie elementu XOR. Istota dekompozycji polega na modyfikacji pierwotnej postaci diagramu MTBDD polegającej na wprowadzeniu atrybutów negacji w obszarze krawędzi znajdujących się na poziomie linii cięcia diagramu. Pozwala to na ograniczenie liczby węzłów odciętych, co prowadzi do zmniejszenia liczby wyjść bloku związanego.

EN

Most CPLD’s PAL type macrocells include XOR element which is able to use programming resources more efficiently. This paper shows the original decomposition of multi-output functions described by MTBDD oriented to XOR element. The idea of decomposition is based on the modification of the initial MTBDD and the supplementation of negation attribute within the area of edges leveled in the cutting area line. It enables to reduce the number of cut nodes and bound set outputs. The negation of suitable edges related to the negation attribute is realized in the proposed solution with the use of XOR element.

13

Koszt implementacji w strukturach CPLD i FPGA jako kryterium wyboru stanów przy minimalizacji automatu skończonego

Klimowicz A.

Pomiary Automatyka Kontrola

|

2014

|

R. 60, nr 7

480--482

PL

W pracy opisano heurystyczną metodę minimalizacji automatów skończonych, która pozwala na etapie minimalizacji stanów uwzględniać parametry bazy technologicznej oraz metodę kodowania stanów. Opisano kryteria minimalizacji liczby stanów ze względu na koszt ich realizacji w strukturze CPLD, gdzie głównym parametrem wpływającym na realizację jest liczba termów podłączonych do jednej makrokomórki i liczba elementarnych koniunkcji w opisie SOP (Sum of Products) funkcji logicznej oraz FPGA, gdzie głównym parametrem jest liczba wejść elementu logicznego i liczba argumentów realizowanej funkcji logicznej. Przedstawiono także wyniki badań opracowanych algorytmów i porównanie ich z innymi metodami minimalizacji stanów.

EN

In the paper a heuristic method of minimization of incompletely specified finite state machines is described. This method allows taking into account the parameters of technological base, the method of state assignment and realization costs. The presented method is focused on realization of FSM in CPLD and FPGA structures. The method is based on operation of merging two states. In addition to reducing internal states this method minimizes the number of FSM transitions and FSM input variables. In contrast to the previously developed methods, in each step of the algorithm there is considered not only one, but the entire set of all pairs of states for which it is permissible to merge. Then from the set there is selected the pair of states which best matches the criteria of minimizing. The paper describes the criteria for minimizing the number of states of the machine because of the cost of their implementation in the CPLD. The main parameter influencing the implementation is a number of terms connected to one macrocell and FPGA structures, where the main parameter is the number of LUT inputs and the number of logic function arguments. The results of implementation of the minimized FSMs in programmable devices showed that the proposed method allowed building FSMs at lower cost and higher speed than STAMINA program for CPLD and FPGA devices.

14

Badania metody minimalizacji nie w pełni określonych automatów skończonych realizowanej w oparciu o sklejanie dwóch stanów

Klimowicz A.

Pomiary Automatyka Kontrola

|

2014

|

R. 60, nr 5

297--300

PL

W pracy opisano badania eksperymentalne metody minimalizacji nie w pełni określonych automatów skończonych. Proponowana metoda bazuje na operacji sklejania dwóch stanów. W pracy pokazano warunki konieczne łączenia dwóch stanów oraz przypadek tworzenia się stanów oczekiwania. Opisana metoda pozwala na redukcję liczby stanów średnio 1,16 razy i liczby przejść automatu 1,27 razy. Pozwala także na redukcję liczby przejść w stosunku do programu STAMINA średnio 1,40 razy. Przedstawiono także wyniki implementacji zminimalizowanych automatów w strukturach CPLD i FPGA, które potwierdziły skuteczność metody.

EN

This paper presents experiments on a heuristic method for minimization of an incompletely specified finite state machine with unspecified values of output variables. The proposed method is based on two states merging. In addition to reduction of the finite state machine (FSM) states, the method also allows reducing the number of FSM transitions and input variables. In contrast to the previously developed methods, in each step of the algorithm there is considered not only one, but the entire set of all pairs of states for which it is permissible to merge. Then from the set there is selected the pair of states which best matches the criteria of minimizing. In the paper, the conditions of state equivalence are presented. Two FSM states can be merged only if they are equivalent. It should be noted that the wait states can be formed at the merging of FSM states. This method allows reducing the number of internal states of the initial FSM by 1.16 times on the average, and by 2.75 times on occasion. An average reduction of the number of FSM transitions makes up 1.27 times. The comparison of the proposed method with the program STAMINA shows that the offered method does not reduce the number of FSM states, however it allows reducing the number of FSM transitions by 1.40 times on the average. The results of implementation of the minimized FSMs in programmable devices showed that the proposed method allowed building FSMs at lower cost and higher speed than the STAMINA program for CPLD and FPGA devices.

15

Ocena efektywności dopasowania technologicznego dla struktur FPGA

Kubica M., Kania D., Opara A.

Elektronika : konstrukcje, technologie, zastosowania

|

2014

|

Vol. 55, nr 2

59-62

PL

Tematem artykułu jest dopasowanie technologiczne do bloków LUT, zawartych wewnątrz struktury FPGA na etapie dekompozycji. Problem ten został sprowadzony do doboru konfiguracji liczby wejść bloku LUT. Dobór liczby wejść jest skojarzony z doborem odpowiedniej liczności zbiorów związanych podczas dekompozycji. Dla reprezentacji funkcji w postaci diagramów BDD liczność odpowiednich zbiorów zależy od doboru linii cięcia. W artykule zaproponowano nową technikę wyznaczania efektywności dopasowania technologicznego (wybór linii cięcia), poprzez wprowadzenie parametru δ zależnego od liczności zbioru związanego, liczby funkcji wiążących oraz liczby niezbędnych bloków LUT. Dobór odpowiedniej dekompozycji jest uzależniony od wartości uzyskiwanego parametru δ. Artykuł zawiera wyniki eksperymentów ukazujące przydatność opisywanych metod.

EN

The topic of the article is concerned with technological mapping for LUT blocks included inside the FPGA structure during decomposition. This problem focuses on the configuration choice of the number of inputs of a LUT block. The choice of the number of inputs is connected with the choice of appropriate number of bound sets while carrying out decomposition. For function representation in the form of BDD diagrams, the number of appropriate sets depends on the choice of cutting lines. The authors have suggested an innovative technique of determining efficiency of technological mapping (the choice of a cutting line). It can be carried out by introducing δ parameter which depends on the number of a bound set, the amount of bound functions, and the number of essential LUT blocks. The choice of an appropriate decomposition makes it conditional on the value of an obtained δ parameter. The article includes the results of the experiments showing the effectiveness of presented methods. The results were compared with other algorithms known from literature as far as the number of necessary logic blocks for carrying out of the structure and the numbers of levels obtained are concerned.

16

Zastosowanie metody syntezy wielopoziomowych układów kombinacyjnych do realizacji części kombinacyjnej wspólnego modelu automatów skończonych Mealy’ego i Moore’a

Klimowicz A.

Przegląd Elektrotechniczny

|

2013

|

R. 89, nr 11

105-108

PL

Praca dotyczy problemu syntezy układu sekwencyjnego w oparciu o programowalne układy logiczne. Cechą szczególną zastosowanej metody jest wykorzystanie wartości zmiennych wyjściowych jako kodu lub części kodu stanów wewnętrznych automatu skończonego. Do uproszczenia funkcji wyjść i funkcji wzbudzeń elementów pamięci automatu zastosowano metodę syntezy wielopoziomowych układów kombinacyjnych wykorzystującą sprzężenia zwrotne układu programowalnego. Praca zawiera także wyniki badań eksperymentalnych metody.

EN

In this paper, a problem of synthesis of sequential circuit on programmable logic device was presented. A special feature of the method is application of values of output variables as a code or as a part of code of internal states of a finite automata. The synthesis method of multilevel combinational circuits, which uses feedbacks of PLD macrocells to synthesis of finite state machines was applied to simplification of combinational part of state machine. The experimental results of synthesis of the improved method are presented in the paper.

17

Dekompozycyjne metody syntezy w projektowaniu systemów cyfrowych dla heterogenicznych struktur programowalnych

Rawski M.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2013

|

z. 191

5--154

PL

Od wielu lat możliwość nowoczesnych technologii mikroelektronicznych w dziedzinie układów scalonych wzrastają znacznie szybciej, niż zdolność projektantów (wspomaganych narzędziami CAD) do ich wykorzystania. Powoduje to konieczność ciągłego doskonalenia metod projektowania i opracowywania nowych narzędzi wspomagających ten proces w taki sposób, aby było możliwe wykorzystanie w jak największym stopniu możliwości nowoczesnej mikroelektronik. W dziedzinie systemów cyfrowych głównym kierunkiem badań obejmuje opracowanie efektywnych metod opisu projektowego układu na poziomie systemu (System Level), które zapewniają ujednolicone modelowanie zarówno jego części sprzętowej, jak i programowej. Należy jednak pamiętać, że ostatecznie – w celu realizacji projektowanego urządzenia cyfrowego – niezbędna jest translacja opisu części sprzętowej z poziomu systemu do poziomu przesłań międzyrejestrowych RTL. Na tym poziomie układ cyfrowy jest reprezentowany jako sieć bloków kombinacyjnych, automatów FSM, rejestrów i struktur, takich jak pamięć RAM, sumatory, układy mnożące itp. Jakość odwzorowania tak reprezentowanego systemu w zasobach logicznych docelowej architektury w ogromnej mierze zależy od efektywności algorytmów zastosowanych na etapie syntezy logicznej. Jest to szczególnie widoczne w przypadku struktur programowalnych FPGA, które dzięki postępowi mikroelektroniki maja obecnie budowę heterogeniczną – składają się z elementów logicznych różnego typu. Niestety, rozwój metod syntezy logicznej nie nadąża za rozwojem układów FPGA. Istniejące algorytmy, oparte na koncepcji dekompozycji funkcjonalnej, nie są w stanie w pełni wykorzystać zalet heterogenicznej budowy nowoczesnych struktur programowalnych. W niniejszej pracy zaprezentowano dekompozycyjne metody syntezy logicznej, umożliwiające efektywne wykorzystanie heterogenicznej struktury nowoczesnych układów FPGA.

EN

For many years possibilities delivered by modern microelectronic technology grow much faster than abilities of designers to utilize them. This necessitates continuous improvement of design methods and development of new tools to assist design process in such a way, that the possibilities of modern microelectronics are utilized I most possible degree. In the area of digital systems the main direction of research includes the development of effective methods of description of the proposed system at a system level, that provides a unified modeling of both the hardware and software. However in order to implement hardware part of the designed digital device the system level description has to be translated to register transfer level (RTL). At this level digital circuit is represented as a network of combinational blocks, FSMs, registers and modules, such as RAMs, adders, multipliers, etc. The quality of mapping of RTL description in the logic resources of target architecture largely depends on the efficiency of the algorithms used in logic synthesis stage. This is particularly evident in the case of FPGA programmable structures which, due to the improvements in microelectronics, have heterogeneous architecture – are built of different types of logic elements. Unfortunately, the development of logic synthesis methods cannot keep up with the development of FPGA devices. Existing algorithms based on the concept of functional decomposition are not able to fully exploit the advantages of heterogeneous architecture of modern programmable structures. Un this work synthesis methods based on functional decomposition concept are presented, that enable the efficient us o heterogeneous structure of modern FPGAs.

18

Synthesis of Finite State Machines with use of pseudoequivalent states

Barkalov A.

Pomiary Automatyka Kontrola

|

2013

|

R. 59, nr 11

1198--1202

EN

A new two-stage method of FSMs synthesis for PAL-based CPLD is proposed. It is based on both wide fan-in of PAL cells and existence of the classes of pseudoequivalent states of Moore FSM. The first step aims at decreasing the number of PAL cells used for implementing the input memory functions. The purpose of the second step is decrease in the number of PAL cells in the block of microoperations. An example of application of the proposed method as well as the results of experiments carried out for standard benchmarks are given.

PL

W artykule przedstawiono metody syntezy mikroprogramowalnego układu sterującego z użyciem wbudowanych bloków pamięci. Postęp w technologii półprzewodnikowej powoduje pojawienie się coraz to bardziej złożonych układów cyfrowych VLSI, takich jak złożone programowalne układy cyfrowe CPLD, gdzie funkcje logiczne są implementowane przy użyciu programowalnych bloków logicznych PAL. Obecnie jedną z istotnych kwestii w przypadku implementowania automatów FSM przy zastosowaniu układów CPLD jest zmniejszenie liczby zużycia makrokomórek PAL. Proponowane metody są ukierunkowane na zmniejszenie rozmiaru układu sterującego poprzez zastosowanie transformacji kodów klas pseudorównoważnych w pamięci. Podejście takie pozwala uzyskać uproszczoną formę funkcji przejścia części adresowej układu, dzięki któremu możliwa jest redukcja zasobów sprzętowych potrzebnych do implementacji jednostki sterującej w układach programowalnych typu CPLD bez zmniejszenia wydajności systemu cyfrowego. W artykule zamieszono wprowadzenie teoretyczne, przykład oraz wyniki badań uzyskanych podczas syntezy testowych sieci działań.

19

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.

20

Minimalizacja automatów skończonych z uwzględnieniem ich kosztu realizacji w układach programowalnych o strukturze CPLD

Klimowicz A.

Pomiary Automatyka Kontrola

|

2013

|

R. 59, nr 8

760--762

PL

W pracy opisano heurystyczną metodę minimalizacji nie w pełni określonych automatów skończonych, która pozwala już na etapie minimalizacji stanów wewnętrznych uwzględniać parametry bazy technologicznej, metodę kodowania stanów oraz optymalizować koszt realizacji automatu w strukturze programowalnej. Opisano kryteria minimalizacji liczby stanów automatu ze względu na koszt ich realizacji w strukturze CPLD, gdzie głównym parametrem wpływającym na realizację jest liczba termów podłączonych do makrokomórki. Dodatkowym efektem działania metody jest minimalizacja liczby przejść automatu.

EN

In the paper a heuristic method of minimization of incompletely specified finite state machines is described. This method allows taking into account parameters of technological base, the method of state assignment and realization costs. The presented method is focused on realization of an FSM in the CPLD structure. The method is based on an operation of merging two states. In addition to reducing internal states, this method minimizes the number of FSM transitions and FSM input variables. In contrast to the previously developed methods, in each step of the algorithm there is considered not only one, but the entire set of all pairs of states for which it is permissible to merge. Then the pair of states which best matches the criteria of minimizing is selected from the set. Two FSM states can be merged if they are equivalent. FSM behavior does not change after the states are merged, if the transition conditions from these states that lead to different states are orthogonal. If there are transi-tions from the states that lead to the same states, the transition conditions for such transitions should be equal. Moreover, the output vectors generated in these states should not be orthogonal. It should be noted that wait states can be formed at the merging of FSM states. This paper describes the criteria for minimizing the number of states of the machine because of the cost of their implementation in the CPLD structure, where the main parameter influencing the implementation is a number of terms connected to one macrocell.