Performance-driven synthesis of controller circuits is very important and challenging task in digital systems design. The clock frequency of a synchronous sequential logic circuit is dependent in a large part on the maximum propagation delay through its combinational block. The paper presents a new method for FPGA-based design of high-speed Algorithmic State Machine (ASM) controllers. The proposed approach is based on the introduction of additional states of the state machine in order to simplify transition and output logical functions to implement them in the single-level structures. The proposed technique is applied at the stage of converting the ASM chart to the finite state machine description and allows obtaining such an HDL specification that provides an increase in the designed system speed. Experimental results show that our approach achieves an average performance gain of 22.24% to 29.72% (for various FPGA devices) compared with the conventional synthesis method.
In this paper we present an indoor mapping algorithm based on sonar sensor. The overall object detection and mapping experiment is based on small scale local spatial information which has been accomplished in a 2D geometrical map. Considering all drawbacks and pluses of ultrasonic sensors, we present an innovative mapping approach, applying the Otsu’s method and Hit-or-Miss for sonar-data processing. The collected data are treated as a gray-scale picture. For its binarization, we applied the well-known for vision-based systems threshold calculation. Then also the morphology effect, what rises additionally the mapping accuracy, as is shown at the end of the paper. The robot is based on the education construction set LEGO Mindstorms EV3 intelligent brick on ev3dev - a Debian Linux-based operating system and Python 2.0 have been used for programming. The results are evaluated and compared with the real space.
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.
This paper presents a design method of high-speed digital comparators on FPGA/SoC by means of hierarchical structures. A synthesis technique of hierarchical structures for comparators is offered. In this technique, the comparator best hierarchical structure is empirically found for a certain FPGA family. The proposed method allows reducing a delay for 256-bits comparators by 1.245 to 2.516 times as compared with a traditional approach, and for 512-bits comparators by 3.399 times. The method also allows reducing an area by 40.2% on occasion.
The paper presents a method for minimization of finite state machines (FSMs) with unspecified values of output variables. The proposed method is based on merging of two states. In addition to reduction of the FSM states, the method also allows reducing the number of FSM transitions and FSM input variables. This method enables reducing the number of internal states of the initial FSM by 1.22 times on the average, and by 2.75 times on occasion. An average reduction of the number of FSM transitions makes up 1.32 times, and on occasion may amount to 2.27 times. The comparison of the method with the program STAMINA shows that the offered method allows decreasing the number of FSM transitions by 1.55 times on the average, and by 3.92 times on occasion.
A method of finite state machine (FSM) minimization for low power by merging FSM internal states is considered. The general algorithm for the minimization of FSM power consumption by means of merging two states is presented. The algorithm of the merging possibility of two states and the actual algorithm merging of two states for incompletely specified Mealy FSMs are given. In the conclusions, the possible directions of development of this approach are specified.
Artykuł przedstawia badania efektywności zarządzania układami mobilnymi przez Internet oraz testowanie skuteczności algorytmu śledzenia robota sterowanego zdalnie. Eksperymenty zostały przeprowadzone na zrealizowanym do tego celu systemie - serwis internetowy oferujący przeprowadzanie gry pomiędzy dwoma, zdalnie sterowanymi robotami. Do wykonania powyższych założeń wykorzystany został statystyczny algorytm śledzenia punktu oparty o rozszerzony filtr Kalmana. Przeprowadzono szereg testów.
EN
The paper presents an analysis of the effectiveness of mobile system management via the Internet [1] and testing of the effectiveness of the tracking algorithm robot controlled remotely [2, 3]. A object tracking algorithm based on the Extended Kalman Filter is implemented into a game for two robots (Fig. 1). The project proves the efficiency of the robot control and the EKF accuracy by observing and analyzing the work of the internet service, which allows two remote-controlled robots to take a part in the game [8]. Similar examples are in medicine [5] as well as international research and education [6]. All of them use advanced robotics technologies [4, 7, 9]. The robot used in the experiments is an educational robot Mindstorms NXT and in this paper we prove that it also gives many possibilities to achieve interesting results in robot remote-control and human-robot interaction (Fig. 2). In the case of tests for the reaction time of the robot on request, one can draw positive conclusions. In situations where no response is required from the server, the response time of the systems to commands from the remote computers is instant. The effectiveness of the tracking algorithm for the remote-controlled robot was tested by conducting a series of tests. They showed a proportional dependency between the velocity of the robots and the coordinate errors (Figs. 3 and 4). A possible direction of development of the system may be the use of more advanced Internet technologies, which could accelerate communication between a client and a server.
Praca poświęcona jest problematyce syntezy komparatorów binarnych w strukturach CPLD/FPGA. Opracowano metody opisu komparatorów w postaci piramidalnych struktur hierarchicznych. Do budowy komparatorów wykorzystano język Verilog i edytor graficzny. Badania eksperymentalne wykonano dla komparatorów 64-bitowych w środowisku Quartus II firmy Altera. Przeprowadzone badania wykazały, że istnieją struktury hierarchiczne, które są bardziej efektywne od wbudowanej funkcji lpm_compare pakietu Quartus II. W najlepszym przypadku uzyskano zmniejszenie maksymalnego czasu propagacji o 44%.
EN
The paper deals with the problem of binary comparator synthesis in CPLD/FPGA structures. Comparators were built with the usage of the Verilog language and the Quartus II graphics editor [10]. Section 1 describes the notion of a digital comparator, its basic usage [1-4] and research directions [6-10]. Section 2 presents the general hierarchical structure of the comparator (Fig. 2). Section 3 describes the method of building new hierarchical structures of 64-bit comparators. Section 4 presents the results of experimental research. Comparators were built and tested in the Altera Quartus II environment. In the experimental research, the 64-bit hierarchical comparators were compared with the 64-bit comparator built with the direct usage of the lpm_compare library function of the Quartus II package. The research was conducted on three CPLD families (MAX 3000 A, MAX II and MAX V) and two FPGA families (Cyclone III and Arria II GX). Three parameters were compared: implementation cost, maximum propagation delay and overall power dissipation. The conducted research demonstrates the existence of hierarchical structures which are better than the in-built lpm_compare function. For the MAX 3000 A family, the implemented hierarchical methods of comparator synthesis show the improved results: 32% in the implementation cost, 44% in the maximum propagation delay and 18% in the overall power dissipation. The improved results for Arria II are as follows: 17% in the implementation cost and 26% in the maximum propagation delay.
Praca dotyczy syntezy komparatorów binarnych w strukturach CPLD/FPGA. Do budowy komparatorów wykorzystano struktury hierarchiczne i równoległo-szeregowe metody syntezy. Badania eksperymentalne wykonano dla komparatorów 128-bitowych oraz 256-bitowych w środowisku Quartus II firmy Altera. Wybrane parametry porównano z wynikami uzyskanymi za pomocą funkcji lpm_compare. Dla komparatorów 128-bitowych uzyskano zmniejszenie kosztu realizacji o 13% oraz zmniejszenie ich maksymalnego czasu propagacji do 38%. W przypadku komparatorów 256-bitowych uzyskano zmniejszenie kosztu realizacji o 19% oraz zmniejszenie ich maksymalnego czasu propagacji do 54%.
EN
The paper deals with the problem of a binary comparator synthesis in CPLD/FPGA structures. The comparators were built with the usage of the Verilog language and the Quartus II graphics editor [10]. Section 1 describes the notion of a digital comparator, its basic usage [1-4] and research directions [6-10]. Section 2 presents the general hierarchical structure of the comparator (Fig. 1). Section 3 describes the parallel-serial method of the comparator synthesis [10]. This method was used in the first level comparator synthesis in hierarchical structures of 128-bit and 256-bit comparators. Section 4 presents the results of experimental research. The comparators were built and tested in the Altera Quartus II environment. In the experimental investigations, hierarchical comparators (128-bit and 256-bit) were compared with the comparators (128_lpm and 256_lpm) built with the direct usage of the lpm_compare library function of the Quartus II package. The research was conducted on two CPLD families (MAX II and MAX V) and on four FPGA families (Cyclone III, Arria II GX, Arria V GZ and Stratix III). Two parameters, the implementation cost and the maximum propagation delay, were compared. For 128-bit comparators, the implementation cost was reduced by 13% and the maximum propagation delay was reduced up to 38% (depending on the family of FPGA structures). For 256-bit comparators, the implementation cost was reduced by 19% and the maximum propagation delay was reduced up to 54% (depending on the family of FPGA structures).
Opracowana została metoda syntezy układów sekwencyjnych o obniżonym poborze mocy, algorytmy sterowania których opisywane są za pomocą sieci działań. Metoda syntezy polega na dekompozycji sieci działań na fragmenty realizowane w postaci oddzielnych automatów połączonych w dwupoziomową strukturę hierarchiczną. Zmniejszenie poboru mocy osiąga się przez odłączenie sygnału synchronizacji od nieaktywnych w danym momencie automatów. Zaproponowano schemat bramkowania sygnału synchronizacji z wykorzystaniem sygnałów struktury hierarchicznej. Opracowany został algorytm dekompozycji sieci działań na fragmenty realizowane jako komponenty struktury hierarchicznej. Przeprowadzone badania potwierdziły efektywność zaproponowanej metody.
EN
In this paper a method for low-power design of hierarchical structures of sequential circuits specified by the Algorithmic State Machine (ASM) charts is presented. The proposed method uses a decomposition of the original sequential circuit into the smaller automata which are connected in a two-level hierarchical structure topology (Fig.1). A clock-gating approach [4, 5] is used to reduce power consumption of the sequential circuit. Due to this approach the power can be saved by clocking only one automaton of hierarchical structure at a time while the clock to the other automata is gated. As a result, only one automaton of hierarchical structure is active at any time while the others are idle, thus reducing the switching activity and minimizing the power dissipation. The algorithm of decomposition of the ASM chart into the fragments, which are implemented as components of a hierarchical structure, has been developed. The clockgating circuit (Fig. 2) which uses the control signals generated by the hierarchical structure is proposed. The power simulation method used to estimate the power consumption for original and decomposed circuits is described. Experimental results show that the proposed partitioning technique can reduce power consumption, on average 20.31%, over the original undecomposed circuit. An additional power saving is available by using special state encoding which reduces the switching activity of sequential circuits.
11
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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%.
Zbadane sposoby opisu układów kombinacyjnych automatów skończonych w języku Verilog, a problem wyboru najlepszego opisu z punktu widzenia kosztów realizacji. Problem został rozwiązany empirycznie. Zaproponowano siedem konstrukcji języka Verilog dla opisu układów kombinacyjnych, z których zostały wybrane dwie najlepsze konstrukcje. Pokazano, że wybór sposobu opisu pozwala zmniejszyć koszt realizacji średnio w 2,71 razy, a dla niektórych przypadków - w 3,40 razy. Praca ma duże znaczenie praktyczne.
EN
In the paper techniques of combinational circuit specifications in the Verilog language at synthesis of finite state machines (FSMs) are examined. The problem of the best specification choice for minimization of an FSM cost is considered. This task was empirically solved by performing a great many experimental researches. There were proposed seven Verilog language constructions for specification of the FSM combinational circuits, four with the statement if and three with the statement case, from which two best constructions were chosen on a basis of the experimental investigations. For different methods of the FSM description the comparison of the maximum and minimum cost of implementation was made. It was shown that the choice of the specification technique allowed reducing the FSM cost by a factor of 2.71 on the average and sometimes even by a factor of 3.40. This approach is of great practical importance, since it allows reducing the FSM realization cost and raising the FSM speed essentially without any special efforts from designers and application of any special synthesis methods.
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.
Przedstawiono metodę syntezy hierarchicznych struktur automatów mikroprogramowalnych, algorytmy sterowania których opisywane są za pomocą sieci działań. Metoda syntezy umożliwia realizację złożonych układów sterowania w postaci sieci hierarchicznie podporządkowanych automatów. Opracowany został algorytm dekompozycji sieci działań na fragmenty realizowane jako komponenty struktury hierarchicznej. Przeprowadzono badania wpływu parametrów sieci działań na możliwość oraz koszt realizacji struktury hierarchicznej.
EN
In this paper a method for synthesis of hierarchical structures of microprogram automata specified by the Algoritmic State Machine (ASM) charts [4] is presented. The proposed method enables the synthesis of complex control systems as a network of hierarchically subordinated automata (Fig. 1), each of which can be implemented on a separate PLD device with limited parameters. Two-level hierarchical structure can also be used to implement control algorithms with repeated fragments [6]. In this approach each repeated section is implemented in the structure only once, and is called many times during the algorithm execution. Additionally, a modified hierarchical structure that allows parallel execution of algorithm fragments is proposed (Fig. 4). The algorithm of decomposition of the ASM chart into fragments which are implemented as components of a hierarchical structure was developed. The synthesis algorithm considers limitations on the fragments size and minimizes the number of links between the different automata. The conditions the expediency of ASM decomposition into fragments to be implemented in a separate automata of the hierarchical structure are taken into consideration, too. A prerequisite for implementation of the method is decomposition of the ASM to fragments having only one input and one output, which is not always possible to fulfill. The experimental results show how the possibility of realization and the cost of implementation of the microprogram automata hierarchical structures depend on the parameters of the ASM charts.
W pracy przedstawiono badania nad wykorzystaniem wejść specjalizowanych w układach programowalnych (Programmable Logic Devices - PLDs). Opisano sposób wykorzystania ich jako wejścia logiczne. Wejścia dedykowane (dedicated inputs) pozwalają na skrócenie czasu przesyłania sygnału z wejścia na wyście układu. W badaniu użyliśmy 3 klas PLD: SPLD (rodzina CLASSIC), CPLD (rodzina MAX) i FPGA (rodzina FLEX oraz ACEX) firmy Altera. Jako urządzenie do projektowania wykorzystaliśmy oprogramowanie MAX+PLUS II. Po wykonania badań eksperymentalnych, zostały otrzymane następujące wyniki: 1) ręczne przypisanie wyjść sygnałom logicznym, nie zmniejszyło czasu propagacji sygnału w rodzinie CLASSIC, 2) w rodzinach MAX, FLEX, ACEX dla niektórych układów udało się znaleźć wyjścia, które zmniejszają czas rozchodzenia się sygnałów.
EN
The paper presents a study on the use of specialized inputs in the control system programmable (Programmable Logic Devices - PLDs). It describes how to use them as a logical entry. Dedicated inputs allow to reduce the time of the signal sending from input to output system. In the study we used 3 classes PLD: SPLDs (Family CLASSIC), CPLD (family MAX) and FPGA (FLEX and ACEX family) by Altera. As a device to design used software MAX + PLUS II. After the implementation of experimental studies, were obtained the following results: a) hand signals a logical assignment to output, not decreased the signal propagation time in the family CLASSIC, b) in families, MAX, FLEX, ACEX for some systems, managed to find the exit, which reduce the time propagation signals, c) manual pick feet, in most cases provides much better time results, because the compiler algorithm for MAX + PLUS II, find the optimal solution with some approximation. The results of our study allowed us to achieve even better results, in some cases the shortening of time transfer signal from input to output PLD reaches 50%.
W artykule przedstawiono nowy algorytm kodowania stanów wewnętrznych automatu skończonego o obniżonym poborze mocy. Zastosowano w nim wspólny model automatu klas ADE co pozwoliło to na zmniejszenie ilości przerzutników przechowujących kod stanu. Badania symulacyjne przeprowadzone z wykorzystaniem standardowych układów testowych potwierdziły skuteczność kodowania z wykorzystaniem proponowanego algorytmu w porównaniu z algorytmami JEDI oraz NOVA, jak i zawartymi we wcześniejszych pracach autorów.
EN
In this paper there is addressed the problem of power minimisation of the finite state machine (FSM). Power reduction is of great importance in design of digital systems as it can improve the speed and extend the time between recharging the batteries in mobile systems. In the common model of the FSM of class ADE (Section 2) the set A of internal states consists of three subsets: AA, AD, and AE. AA is the set of internal states of the FSM of class A, AD is the set of internal states of the FSM of class D (the output vector is identical to the next state code), and AE is the set of internal states of the FSM of class E (the input vector is identical to the next state code) [12]. The common model of the FSM of class ADE requires an additional register used for storing the input and output vector values. These registers are present in modern programmable logic devices. In Section 3 there is proposed a new algorithm of the FSM state assignment that makes use of the common model. The assigned code consists of three parts: G - input vector, Z - output vector and E - state code. G and Z are stored in the input and output registers, respectively. With this algorithm it is possible to assign codes that are shorter than those assigned with use of classical methods, and thus less power is dissipated in registers storing the current state code during every transition. The experimental results (Section 4, Tables 1 and 2) show the significant reduction (of 13 to 51%) in power dissipation compared to classic (JEDI, NOVA, column-based) and recent (sequential and iterating) algorithms.
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%.
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).
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.
Artykuł opisuje stan obecnych badań w dziedzinie metod obliczania mocy układów cyfrowych. Obliczanie (estymacja) mocy ma zasadnicze znaczenie podczas projektowania systemów cyfrowych o niskim poborze mocy. Przeprowadzono analizę technik stosowanych do obliczania mocy zarówno dla układów kombinacyjnych jak i sekwencyjnych na różnych poziomach abstrakcji, jak również metody mające zastosowanie do układów FPGA.
EN
The state of contemporary researches in digital circuit power calculation was described in this paper. Power calculation (estimation) has great meaning during low power digital circuits designing. Analysis of techniques used in power calculating was made, either for combinational or sequential circuits on different levels of abstraction, as well as methods used for calculation of power in FPGA structures.
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ć.