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

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.

3

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.

4

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.

5

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.

6

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.

7

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.

8

Synteza i implementacja układu sterowania w strukturze FPGA opisanego językiem SFC zgodnego z IEC61131

Milik A., Pułka A.

Elektronika : konstrukcje, technologie, zastosowania

|

2014

|

Vol. 55, nr 12

17-20

PL

Artykuł przedstawia opracowany całościowy proces syntezy wielokontekstrowego sprzętowego układu sterowania implementowanego w strukturach FPGA. Dedykowana struktura sprzętowa pozwala na zdecydowane zredukowanie czasu przetwarzania w porównaniu z rozwiązaniami programowymi. Program podlegający syntezie jest opisany językiem SFC zgodnie z normą IEC61131-3. W procesie syntezy wykorzystano oryginalną grafową metodę reprezentacji postaci pośredniej programu sterowania. Metoda konstruowania postaci pośredniej zachowuje własności przetwarzania, ujawniając zadania równoległe. Opracowano również metodę odwzorowania technologicznego dla tablicowych układów FPGA. W celu porównania przedstawiono rezultaty implementacji opracowanej metody oraz bezpośredniego odwzorowania postaci grafowej.

EN

The paper presents the synthesis and implementation algorithms of multiple context logic controller implemented in a FPGA. A massively parallel hardware execution of control algorithms is utilized that significantly reduces the throughput time. The input program is written in the SFC according to the IEC61131-3 standard. An originally developed intermediate representation based on data flow graph has been used for processing. The graph building algorithm maintains sequential dependencies and reveals parallel tasks in program. Developed method of scheduling and mapping is dedicated for LUT based FPGA devices. The paper is concluded with exemplary implementation comparison of greedy direct mapping and developed FPGA architecture optimized method.

9

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.

10

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.

11

Analiza porównawcza narzędzi syntezy Altera Quartus II i Synthagate

Węgrzyn M., Karatkiewicz A.

Przegląd Elektrotechniczny

|

2013

|

R. 89, nr 12

380-383

PL

W artykule przedstawiono analizę porównawczą skuteczności działania przemysłowego narzędzia syntezy układów cyfrowych FPGA (na przykładzie systemu Altera Quartus II), a narzędzia syntezy o pochodzeniu akademickim (Synthagate). Eksperymenty przeprowadzono z wykorzystaniem szeregu przykładów opisujących automaty skończone. Przedyskutowano wpływ sposobu opisu automatów na wyniki syntezy. Stwierdzono, że system Synthagate daje na ogół lepsze wyniki pod względem wykorzystania zasobów układów programowalnych oraz działa znacznie szybciej, niż narzędzie przemysłowe.

EN

The paper presents comparison between efficiency of an industrial FPGA design software tool Altera Quartus II and similar design software tool Synthagate by Syntezza company of an academic origin. The experiments were performed using a series of examples describing the Moore finite state machines; one-hot state encoding was used in all cases. Area (number of used logical blocks) was the main parameter used for the comparison. Influence of the way of FSM description (in VHDL language) on the quality of synthesis was studied. The obtained results show that Synthagate in almost all cases performs synthesis more efficiently and essentially quicker than Altera Quartus. Section 1 presents motivation of the research; Section 2 describes problems which had to be solved to provide correctness of experimental comparison. In Section 3, the experimental results are presented. Section 4 describes still existing problems related to the comparison, which have to be solved. Section 5 presents the conclusions.

12

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.

13

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ń.

14

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.

15

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.

16

Strategia dekompozycji ukierunkowana na minimalizację warstw logicznych

Kubica M, Kania D, Opara A

Elektronika : konstrukcje, technologie, zastosowania

|

2013

|

Vol. 54, nr 12

96-99

PL

Artykuł koncentruje się wokół dekompozycji wielokrotnej i sposobów jej realizacji z wykorzystaniem BDD. Jego celem jest przedstawienie strategii dekompozycji prowadzącej do minimalizacji liczby warstw logicznych. Zaproponowana strategia dekompozycji wykorzystuje dekompozycję wielokrotną pozwalającą na wyszukiwanie w jednym kroku dekompozycji kilku bloków związanych. W artykule przedstawiono wyniki eksperymentów uzyskanych przedstawioną metodą i porównano je z wynikami otrzymanymi wykonując dekompozycję innymi akademickimi narzędziami programowymi.

EN

The article relates to the problem of partition of the combinational circuit between LUT blocks which are included inside the FPGA structure. Decomposition is the mathematical model of such a partition. The authors focus on one of the complex decomposition – multiple decomposition. According to the authors of the article, the strategy based on multiple decomposition should lead to obtain logic structures which have relatively small number of logic levels. Therefore, the main goal of the article is to present a decomposition strategy leading to gain the structures with good dynamic properties. The paper also focuses on the techniques of acquiring multiple decomposition using BDD. Function representation, in the form of BDD, leads to the minimalization of the synthesis time. The article presents the results of the experiments for described decomposition strategy.

17

Zastosowanie dekompozycji w projektowaniu układów cyfrowych

Borowik G., Łuba T., Ogorzałek R.

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2012

|

nr 6

548-552

PL

Przedstawiono narzędzie wspomagające dekompozycję układów logicznych z użyciem oprogramowania uniwersyteckiego Demain i Spark. Narzędzie znacznie skraca czas potrzebny do przeprowadzenia pojedynczego badania przez wygenerowanie gotowego kodu źródłowego w języku opisu sprzętu. Wynikowy kod źródłowy umożliwia bezpośrednią syntezę układu cyfrowego za pomocą systemów komercyjnych.

EN

The paper examines the usefulness of the university tools by the decomposition of example logic functions and analyzes various strategies of the decomposition of truth tables using the notion of r-admissibility. Subsequently, statistically optimal management strategy for the Spark software have been established. Final results have been compared with the Altera Quartus II system.

18

Application of Modified Distributed Arithmetic Concept in FIR Filter Implementations Targeted at Heterogeneous FPGAs

Staworko M., Rawski M.

Przegląd Elektrotechniczny

|

2012

|

R. 88, nr 6

240-246

EN

Distributed arithmetic is a very efficient method for implementing digital FIR filters in FPGA structures. In this approach general purpose multipliers of traditional MAC implementations are replaced by combinational LUT blocks. Since LUT blocks can be of considerable size thus, the quality of digital filter implementation highly depends on efficiency of logic synthesis algorithm that maps it into FPGA resources. Modern FPGAs have heterogeneous structure, there is a need for quality algorithms to target these structures and the need for flexible architecture exploration aiding in appropriate mapping. The paper presents an application of modified distributed arithmetic concept that allows for very efficient implementation of FIR filters in heterogeneous FPGA architectures.

PL

Arytmetyka rozproszona jest bardzo wydajną metodą implementacji filtrów SOI w układach FPGA. Pozwala na zastąpienie kosztowych układów mnożących tablicami prawdy (LUT). Dla filtrów wysokich rzędów tablice LUT osiągają wielkie rozmiary, dlatego jakość implementacji filtru zależy głównie od jakości dekompozycji tej tablicy. Artykuł przedstawia nową metodę dekompozycji tablic LUT filtrów SOI dedykowaną do heterogenicznych stukrur rekonfigurowalnych.

19

Zastosowanie wspólnego modelu automatów Mealy'ego i Moore'a do realizacji układów sekwencyjnych w układach programowalnych

Klimowicz A., Salauyou V.

Pomiary Automatyka Kontrola

|

2012

|

R. 58, nr 7

653-655

PL

W pracy opisano syntezę automatów skończonych na bazie programowalnych układów logicznych (PLD). Cechą szczególną metody jest zastosowanie wartości zmiennych wyjściowych w charakterze części kodu stanów wewnętrznych automatu. W celu rozwiązania zadania został zastosowany wspólny model automatów Mealy'ego i Moore'a, przy czym automat nie podlega żadnym przekształceniom związanym ze zwiększeniem liczby stanów wewnętrznych i liczby przejść. W pracy opisano też metodę syntezy wspólnego modelu automatów skończonych klas AC.

EN

This paper describes the problem of synthesis of finite automata on programmable logic devices. A special feature of the method is the application of the values of output variables as a code or the part of a code of internal states of finite automata. In order to solve the problem, a common model of Mealy [4] and Moore [5] machines is used. The main difference of this approach in relation to known methods [1-3, 6, 7, 9] is that the finite state machine does not undergo any transformation associated with a increase in the number of internal states and the number of transitions of a finite automaton. In this paper three models of finite state machines are considered (classes: A, B and C). They are applied to realization of a FSM on programmable logic. The paper presents the necessary conditions for the possibility of using the values of output variables as a code of internal states of a finite automaton. In the paper there is described the method for synthesis of a common model for the finite state machine of AC class. The idea of the proposed approach is to find such sets of the values of output variables which are formed at all transitions from the corresponding states and satisfy the conditions of realization. It also aims at doing a special coding of the internal states, where the sets of values of the output variables are used as a part of the code of the internal states. There are given possible directions for future research in the area of synthesis of new structural models of finite state machines.

20

Rozproszony system sterowania o architekturze GALS projektowany z wykorzystaniem sieci Petriego

Bukowiec A.

Pomiary Automatyka Kontrola

|

2012

|

R. 58, nr 6

502-505

PL

W artykule omówiona została architektura rozproszonego systemu sterowania zbudowanego z konfigurowalnych struktur FPGA. System specyfikowany jest z wykorzystaniem sieci Petriego. Następnie poddawany jest dekompozycji na składowe automatowe z wykorzystaniem algorytmów kolorowania sieci Petriego. Każda składowa implementowana jest niezależnie w oddzielnym układzie FPGA. Aby umożliwić komunikację pomiędzy poszczególnymi składowymi zastosowano architekturę globalnie asynchroniczną lokalnie synchroniczną (GALS). Każda podsieć synchronizowana jest lokalnym sygnałem zegarowym. Komunikacja pomiędzy poszczególnymi podsieciami zrealizowana jest asynchronicznie z wykorzystaniem dodatkowych sygnałów.

EN

The paper presents a new architecture of the distributed specific control system built with FPGA devices. The control algorithm specification is made with use of the control interpreted Petri net. It allows specifying parallel processes in easy way. Next, such a Petri net is decomposed into a set of state-machine type subnets. For this purpose there are applied algorithms of coloring of Petri nets. In this case, each subnet represents one parallel process. Each subnet is independently implemented in different FPGA device. To ensure communication between all subnets, there is used globally asynchronous locally synchronous (GALS) architecture of the whole control system. Each subnet is synchronized by a local clock signal. The global communication between components is buffer-based via additional signals. These signals are generated in particular subnets and they are distributed to other ones. During the synthesis process places of each state-machine subnet are encoded by a minimal-length binary vector. This encoding allows a realization of a microoperation decoder with use of embedded memory blocks of the FPGA device. It leads to balanced usage of all kinds of logic resources of the FPGA device.