PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 17

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  state assignment
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available Finite-state State Machines Minimization by Using of Values of Input Variables at State Assignment
Salauyou V., Ostapczuk M.
Measurement Automation Monitoring
|
2017
|
Vol. 63, No. 5
195--197
EN
In this paper, we propose a method of FSM synthesis on field programmable gate arrays (FPGAs) when input variables are used for state assignment. For this purpose we offer a combined structural model of class A and class E FSMs. This paper also describes in detail algorithms for synthesis a class AE FSM which consists of splitting of internal states for performance of necessary conditions for synthesis of the class E FSM and state assignment of the class AE FSM. It is shown that the proposed method reduces the area for all families of FPGAs by a factor of 1.19…1.39 on average and by a factor of 3.00 for certain families.
2
Content available remote Kodowanie stanów energooszczędnych automatów sekwencyjnych wykorzystujące algorytm Kernighana-Lina
Kajstura K., Kania D.
Przegląd Elektrotechniczny
|
2015
|
R. 91, nr 5
155-158
PL
W artykule przedstawiono oryginalny dekompozycyjny algorytm kodowania stanów wewnętrznych automatów skończonych, który ukierunkowany jest na minimalizację poboru mocy. W kolejnych krokach następuje podział grafu stanowiącego probabilistyczny opis automatu realizowany za pomocą zmodyfikowanego algorytmu Kernighana-Lina. Wyniki eksperymentów wskazują, że opracowana metoda kodowania prowadzi do redukcji poboru mocy oraz zmniejszenia powierzchni układu.
3
Content available remote Algorytm kodowania stanów wewnętrznych automatu skończonego ze zmienną długością kodu do minimalizacji mocy
Salauyou V., Grześ T.
Przegląd Elektrotechniczny
|
2013
|
R. 89, nr 11
101-104
PL
W artykule przedstawiono dwie heurystyczne metody kodowania stanów wewnętrznych automatów skończonych, których celem jest zminimalizowanie poboru energii: ze stałą i ze zmienną długością kodu. Drugie podejście charakteryzuje się małym kosztem obliczeniowym. Badania eksperymentalne wykazują znaczące zmniejszenie poboru energii w przypadku pierwszej metody w porównaniu z algorytmem NOVA średnio o 39%. Druga metoda w porównaniu z pierwszą pozwala na zmniejszenie poboru energii nawet o 34%.
EN
This paper presents two heuristic methods of encoding the internal states of finite state machine to minimize the power consumption: a fixed and a variable code length. The second approach has low computational cost. Experimental researches show a significant reduction in energy consumption in the first method, compared to the algorithm NOVA average of 39%. The second method compared to the first allows you to reduce power consumption by up to 34%.
4
Content available 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ń.
5
Content available remote Dekompozycyjna metoda kodowania stanów wewnętrznych automatu skończonego ukierunkowana na minimalizację mocy
Kajstura K., Kania D.
Przegląd Elektrotechniczny
|
2011
|
R. 87, nr 6
146-149
PL
W artykule przedstawiono metodę kodowania stanów wewnętrznych automatów skończonych ukierunkowaną na minimalizację poboru mocy. Zaproponowano algorytm bazujący na tworzeniu drzewa binarnego, którego węzły powstają na wskutek podziału automatu skończonego. Przeprowadzone badania eksperymentalne wskazują, że proponowany algorytm prowadzi do zmniejszenia poboru mocy, jak również zmniejszenia powierzchni układu w porównaniu do algorytmów kodowania już opracowanych.
EN
This paper presents a state assignment method oriented to reduction of power consumption in Finite State Machines. The proposed algorithm is based on creating a binary tree whose nodes are created by sharing a finite state automaton. The experimental results show that the proposed algorithm leads to the reduction in power consumption compared to the state encoding algorithms have already been developed. The reducing of circuits' area is observed too.
6
Content available Wspólny model automatu skończonego w minimalizacji poboru mocy
Grześ T.
Pomiary Automatyka Kontrola
|
2010
|
R. 56, nr 7
772-774
PL
W artykule przedstawiono wyniki badań algorytmu minimalizacji poboru mocy wykorzystującego wspólny model automatu klas ADE. Nowe modele strukturalne stanowią rozwinięcie klasycznych automatów Mealy'ego i Moore'a. Pozwalają na wykorzystanie szczególnych cech układów programowalnych przy syntezie układów sekwencyjnych. Jedną z możliwości jest zastosowanie przerzutników w buforach wejściowych i wyjściowych w charakterze elementów pamięci. Wyniki badań wykazały bardzo wysoką skuteczność nowego algorytmu.
EN
The paper presents a new algorithm of the power consumption minimisation based on a common model of the finite state machine (FSM) of class ADE. The classic algorithms of the state assignment for power minimisation such as column-based [1], annealing [4], sequential [8] or genetic [2] are based on the general model of FSM (Mealy or Moore). They do not take into account specific features of contemporary programmable logic devices (PLD). The new structural models of FSMs are an extension of Mealy and Moore automata. The proposed algorithm is based on the common model of the finite state machine of class ADE. This paper consists of four paragraphs. The first one is an introduction to the power minimisation problem and shows why the new structural models of FSM can be used as a solution. In the second paragraph there is a detailed description of the common model of FSM of classes ADE (Fig. 1) and discussion on the power dissipation in the common model. The third paragraph describes the algorithm of state assignment that uses the features of the common model of FSM of class ADE. The fourth chapter presents the results of investigations on the new algorithm. These results show very high effectiveness of the new algorithm. In addition, power dissipation depends significantly on the algorithm used for encoding variables ei from the set E as well as increasing number of additional variables ei.
7
Content available Metoda kodowania stanów automatów sekwencyjnych prowadząca do redukcji poboru mocy
Kajstura K., Kania D.
Pomiary Automatyka Kontrola
|
2010
|
R. 56, nr 7
718-720
PL
W artykule przedstawiono algorytm kodowania stanów wewnętrznych automatu skończonego. Istota algorytmu tkwi w minimalizacji poboru mocy synchronicznych układów sekwencyjnych. Algorytm opiera się na tworzeniu drzewa binarnego, którego węzły powstają na wskutek dekompozycji automatu skończonego. Wyniki eksperymentów wskazują, że proponowany algorytm prowadzi do zmniejszenia poboru mocy w porównaniu do algorytmów kodowania już opracowanych. Obserwowane jest również zmniejszenie powierzchni układu.
EN
Power dissipation has become one of the main issues during em-bedded systems design in the recent years, due to the continuous increase of the integration level and the operating frequency. The largest fraction of power consumption in CMOS circuits is caused by signal switches. This paper presents a new algorithm for FSM encoding. The aim of this algorithm is to minimise power consumption of synchronous sequential circuits. The algorithm is based on creating a binary tree whose nodes are created by partitioning a finite state automaton. The algorithm uses the probabilistic model of an FSM to obtain state encoding minimising the number of signal transitions. The algorithm has been applied to the MCNC benchmark circuits and has also been compared to other encoding approaches. The experimental results show that the proposed algorithm leads to the reduction in power consumption compared to the state encoding algorithms already developed. The reduction of the circuit area is observed, too.
8
Content available Algorytm kodowania stanów wewnętrznych automatu skończonego minimalizujący pobór mocy
Kajstura K., Kania D., Kurytnik I.
Pomiary Automatyka Kontrola
|
2010
|
R. 56, nr 8
987-989
PL
W artykule przedstawiono nowy algorytm kodowania stanów wewnętrznych automatu skończonego. Głównym zadaniem przedstawionego algorytmu jest minimalizacja poboru mocy w synchronicznych układach sekwencyjnych. Algorytm opiera się na tworzeniu drzewa binarnego, którego węzły powstają na wskutek podziału automatu skończonego. Wysokość drzewa równa jest liczbie bitów słowa kodowego. Wyniki eksperymentów wskazują, że proponowany algorytm prowadzi do zmniejszenia poboru mocy, jak również zmniejszenia powierzchni układu w porównaniu do algorytmów kodowania już opracowanych.
EN
Power consumption has become one of the main issues during the design of embedded systems and VLSI circuits in the recent years, due to the continuous increase in the integration level and the operating frequency. The largest fraction of power consumption in CMOS circuits is caused by signal switches. This paper presents a new algorithm for FSM encoding. The main task of the presented algorithm is to minimise power consumption in synchronous se-quential circuits. The algorithm is based on creating a binary tree whose nodes are created by sharing a finite state automaton. The tree height is equal to the number of bits of code words. The algorithm uses the FSM probabilistic model to obtain state encoding that minimise the number of signal transitions. The algorithm has been applied to the MCNC benchmark circuits and has also been compared with other encoding approaches. The experiment results show that the proposed algorithm reduces the power consumption, as well as the circuit area compared to the state encoding algorithms already developed.
9
Content available remote Synthesis of finite state machines for CPLDs
Czerwiński R., Kania D.
International Journal of Applied Mathematics and Computer Science
|
2009
|
Vol. 19, no 4
647-659
EN
The paper presents a new two-step approach to FSM synthesis for PAL-based CPLDs that strives to find an optimum fit of an FSM to the structure of the CPLD. The first step, the original state assignment method, includes techniques of two-level minimization and aims at area minimization. The second step, PAL-oriented multi-level optimization, is a search for implicants that can be shared by several functions. It is based on the graph of outputs. Results of experiments prove that the presented approach is especially effective for PAL-based CPLD structures containing a low number of product terms.
10
Modelowanie automatów synchronicznych w języku VHDL pod kątem efektywnego wykorzystania niezależnych narzędzi syntezy
Czerwiński R., Kulisz J.
Elektronika : konstrukcje, technologie, zastosowania
|
2009
|
Vol. 50, nr 2
77-82
PL
Artykuł dyskutuje pewne zagadnienia opisu automatów sekwencyjnych w języku opisu sprzętu VHDL, a w szczególnie problem połączenia syntezy logicznej wykonywanej w narzędziu niezależnym z syntezą fizyczną wykonywaną w oprogramowaniu komercyjnym, dostarczanym przez producenta układów programowalnych. Ze względu na czytelność i przenaszalność najbardziej atrakcyjnym sposobem wprowadzenia projektu po syntezie logicznej do narzędzia komercyjnego powinien być opis w języku opisu sprzętu, dokonany na możliwie najwyższym poziomie abstrakcji. Ponieważ narzędzia komercyjne mogą głęboko ingerować w logiczną strukturę projektu, opis behawioralny, połączony z kodowaniem stanów zdefiniowanym przez projektanta, nie zapewnia optymalnej jakości syntezy. Autorzy proponują styl opisu, który jest przenaszalny i czytelny, a jednocześnie umożliwia efektywne przeprowadzenie syntezy fizycznej w systemach komercyjnych. Wyniki eksperymentów dowodzą, że zaproponowana metoda opisu, wraz z odpowiednią metodą kodowania stanów wewnętrznych, prowadzą do redukcji powierzchni układów CPLD, w których realizowany jest automat sekwencyjny.
EN
The paper discusses certain issues concerning FSM description in an HDL, and in particular the problem of combining logic synthesis performed in vendor-independent tools with physical synthesis performed in commercial tools, supplied by PLD vendors. Because of its clarity and portability, a textual description in an HDL seems to be the most attractive way of porting the project to a commercial tool, after the logic synthesis stage. The description should use the highest possible level of abstraction. Because commercial software can in many cases "destroy" logical structure generated by independent tools, behavioural description combined with user-defined state coding doesn't provide optimal quality of synthesis. The authors propose a style of FSM modelling, that is still portable and readable, and enables effective physical synthesis in commercial tools. The method was verified for CPLD circuits. Experimental results prove that the proposed style of description, combined with an appropriate state coding, leads to more effective synthesis with regards to logic resources used.
11
Content available Algorytmy kodowania stanów wewnętrznych automatu skończonego do minimalizacji poboru mocy
Grześ T., Salauyou V.
Zeszyty Naukowe Politechniki Białostockiej. Informatyka
|
2008
|
Z. 3
53-66
PL
Kodowanie stanów wewęetrznych automatu skończonego jest jednym z ważniejszych procesów podczas syntezy automatu. Zastosowanie odpowiedniego algorytmu pozwala m.in. obnizyć pobór mocy. W artykule skoncentrowano się na algorytmach minimalizujących pobór mocy. Przeprowadzono badania nad algorytmem kodowania kolumnowego, opisanego w pracy [1] oraz nad dwoma algorytmami opracowanymi przez autorów: sekwencyjnym [7] oraz rafinacyjnym. Badania przeprowadzono na standardowych układach testowych, opracowanych w Microelectronics Center of North Carolina [9]. Wyniki badań wykazują znaczące zmniejszenie poboru mocy układów zakodowanych z wykorzystaniem algorytmu sekwencyjnego w porównaniu z poborem z wykorzystaniem algorytmu kodowania kolumnowego (średnio o 12%); zastosowanie algorytmu rafinacyjnego pozwoliło obniżyć moc średnio o kolejny 1%.
EN
State assignment for a finite state machine (FSM) is an important process in logic synthesis of the sequential circuits in programmable devices. Using the proper algorithm provides among other things the reduction of the power dissipation. In this paper we focused on the algorithms that reduce power dissipation. The analysis of the column based algorithm (described in [1]) as well as two algorithms proposed by authors: sequential [7] and iterational was made. Experiments were made on standard benchmarks, researched in Microelectronics Center of North Carolina [9]. Obtained results showed significant reduction of the power dissipation when using the sequential algorithm (12% in comparison with the column-based algorithm). Iterational algorithm improves the results by additional 1%.
12
Content available Zastosowanie grafu niezgodności i dopełnień w procesie kodowania automatów asynchronicznych
Kania D., Kulisz J.
Pomiary Automatyka Kontrola
|
2008
|
R. 54, nr 8
486-488
PL
W artykule przedstawiono przykład zastosowania nowego rodzaj grafu - grafu niezgodności i dopełnień. Specyficzną cechą tego grafu jest to, że zawiera on dwa rodzaje krawędzi: krawędzie skojarzone z relacjami niezgodności oraz krawędzie skojarzone z relacjami dopełniania. Graf może być wykorzystywany w szeregu problemów optymalizacyjnych, w których rozważane są relacje niegodności i dopełniania wzorców bitowych. W artykule zaprezentowano wykorzystanie grafu w procesie kodowania stanów asynchronicznych układów sekwencyjnych. Przedstawiono też odpowiednie algorytmy tworzenia grafu i kolorowania jego wierzchołków.
EN
The paper presents an application of a novel concept of graph - the Incompatibility and Complement Graph. A specific feature of the graph is that it contains two kinds of edges: connecting mutually incompatible nodes, and connecting mutually complementing nodes [3, 4]. The graph can be useful in certain class of optimization problems, in which compatibility of bit patterns in both the true and the complemented form has to be analyzed [5]. An example of such a problem is covering analysis in asynchronous FSM coding. The relevant coding method was presented by Tracey [1]. The method consists of several steps. In one of the steps a Boolean matrix is built, describing partitions of the relevant state set, which are required to provide coding free form critical races. In the subsequent step the Boolean matrix has to be reduced. During this step compatibility of the matrix rows both in the true, and the complemented form has to be analysed. For this purpose the Row Incompatibility and Complement graph can be used. The paper presents a simple example explaining the method. Appropriate algorithms for the graph building (Fig. 3) and colouring (Fig. 4) are also presented.
13
Content available Badania algorytmów kodowania stanów wewnętrznych automatu skończonego zorientowanych na minimalizację poboru mocy
Salauyou V., Grześ T.
Pomiary Automatyka Kontrola
|
2008
|
R. 54, nr 8
499-501
PL
Kodowanie stanów wewnętrznych automatu skończonego jest jednym z ważniejszych procesów podczas syntezy automatu. W artykule skoncentrowano się na algorytmach minimalizujących pobór mocy. Przeprowadzono badania algorytmu kodowania kolumnowego oraz dwóch algorytmów opracowanych przez autorów: sekwencyjnego oraz iteracyjnego. Wyniki badań wykazują znaczące zmniejszenie poboru mocy układów zakodowanych z wykorzystaniem algorytmu sekwencyjnego w porównaniu z algorytmem kodowania kolumnowego (średnio o 12%), natomiast zastosowanie algorytmu iteracyjnego pozwoliło na obniżenie mocy średnio o kolejne 2% (w porównaniu do algorytmu sekwencyjnego).
EN
Finite State Machine (FSM) state assignment is one of the most important activities during the synthesis. In this paper we focused on the low-power design oriented algorithms. We explore column-based algorithm as well as two algorithms researched by authors: sequential and iterational. Experimental results shows the significant reduction of the power dissipation after state assignment using sequential algorithm in comparison with the column-based algorithm (of about 12%). Iterational algorithm increase power reduction of about 2% (in comparison with the sequential algorithm).
14
Content available Synteza logiczna układów sekwencyjnych realizowanych w strukturach CPLD opisanych za pomocą języka VHDL
Czerwiński R., Kania D.
Pomiary Automatyka Kontrola
|
2007
|
R. 53, nr 7
45-47
PL
W artykule przedstawiono problem kodowania stanów wewnętrznych automatów sekwencyjnych ukierunkowany na realizację układu w strukturze matrycowej typu PAL. Opracowano sposób uwzględniania elementów dwupoziomowej minimalizacji oraz elementów dopasowania już na etapie kodowania stanów wewnętrznych. Sporo miejsca poświęcono problemowi opisu automatu w języku opisu sprzętu VHDL pod kątem efektywnego przeprowadzenia syntezy logicznej w systemie Quartus II. Skuteczność metod kodowania i opracowanego opisu potwierdzają uzyskane wyniki eksperymentów.
EN
The paper concerns the problem of state assignment for finite state machines (FSM), targeting at PAL-based CPLDs implementations. The main feature of a PAL-based cell is a limited number of product terms (k AND-gates) that are connected to a single sum (OR-gate). Methods, that do not take into account this limited number of product terms in the process of state assignment, usually lead to multi-cell and multi-level structures. To make allowance for number of product terms the elements of two-level minimization and elements of technology mapping must be taken into account in the process of state assignment. This is possible thanks to Primary and Secondary Merging Conditions and Implicants Distribution Table. The problem of the sequential automata VHDL design is also considered. The VHDL design description of the FSM for Quartus II is proposed. Experimental results consider the efficiency of the proposed methods.
15
Content available Metody kodowania stanów wewnętrznych automatu skończonego minimalizujące pobór mocy
Salauyou V., Grześ T.
Pomiary Automatyka Kontrola
|
2007
|
R. 53, nr 7
112-114
PL
Opisano badania trzech algorytmów kodowania stanów wewnętrznych automatu skończonego: algorytmu kodowania kolumnowego, algorytmu "wyżarzania" oraz algorytmu sekwencyjnego. Głównym zadaniem wymienionych algorytmów jest zakodowanie stanów wewnętrznych automatu skończonego w taki sposób, aby moc pobierana przez automat skończony była jak najmniejsza. Badania eksperymentalne, które przeprowadzono na standardowych układach testowych, potwierdziły wyższość opracowanego przez autorów algorytmu sekwencyjnego.
EN
The reduction of the power dissipation is of extreme importance for mobile, battery-operated systems as well as for increasing the speed and performance of the digital systems. Based on the CMOS gate model we can prove that power dissipation depends on the applied assignment. Thus using the particular state assignment method lead to minimization of the power dissipation. In this paper three algorithms of the FSM internal states assignment were described: column-based, annealing and sequential. The main aim of those algorithms were to minimize the power dissipation in the sequential circuits by assigning the state codes with as minimal Hamming distance as possible. Experimental results show that sequential algorithm can reduce about 10% more power than other discussed algorithms.
16
Kodowanie stanów: minimalizacja liczby warstw z przekodowaniem
Czerwiński R.
Elektronika : konstrukcje, technologie, zastosowania
|
2006
|
Vol. 47, nr 11
26-28
PL
Przedstawiono oryginalny sposób kodowania stanów synchronicznych automatów sekwencyjnych ukierunkowany na minimalizację liczby warstw logicznych bloku przejść. Istota zaproponowanego pomysłu polega na przypisywania odpowiednim parom stanów reprezentacji binarnej o odległości kodowej równej jeden. Idea metody kodowania polega na wydłużaniu długości słowa, co prowadzi do minimalizacji liczby warstw bloku przejść. Wykorzystanie tablicy rozkładu implikantów oraz analiza pierwotnych i wtórnych warunków sklejenia umożliwia dopasowanie struktury układu sekwencyjnego do struktury matrycowego układu programowalnego, którego rdzeń stanowi struktura AND/OR typu PAL.
EN
The paper presents a novel method of FSM state coding. The method is oriented towards logic minimization of the transition block. The essence of the method consists in assigning code words that differ only in one position, to appropriate pairs of states. This way elements of synthesis, supposed to improve logic minimization, are introduced into the coding process. One of the main ideas is also to lengthen the code word, if necessary. The paper introduces the concept of Implicant Distribution Table, and defines Primary and Secondary Merging Conditions. Analysis of the Implicant Distribution Table with the Primary and Secondary Merging Conditions makes it possible to effectively map FSM-s onto PAL-based CPLD-s.
17
Content available remote FSMs state encoding targeting at logic level minimization
Czerwiński R., Kania D., Kulisz J.
Bulletin of the Polish Academy of Sciences. Technical Sciences
|
2006
|
Vol. 54, nr 4
479-487
EN
The paper concerns the problem of stale assignment for finite stale machines (FSM), tar-geting at PAL-based CPLDs implementations. Presented in the paper approach is dedicated to stale encoding of fast automata. The main idea is to determine the number of logic levels of the transition function before the stale encoding process, and keep the constraints during the process. The number of implicants of every single transition function must be known while assigning states, so elements of two level minimization based on Primary and Secondary Merging Conditions are implemented in the algorithm. The method is based on code length extraction if necessary. In one of the most basic stages of the logic synthesis of sequential devices, the elements referring to constraints of PAL-based CPLDs are taken into account.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.