Algorytm kodowania stanów wewnętrznych automatu skończonego minimalizujący pobór mocy

• Autorzy: Kajstura K. , Kania D. , Kurytnik I.

Warianty tytułu

EN

Finite state machine state assignment algorithm for low power dissipation

• Języki publikacji: PL

Abstrakty

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.

Słowa kluczowe

PL

kodowanie stanów; pobór mocy; automat skończony

EN

state assignment; power dissipation; finite state machine

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2010
• Tom: R. 56, nr 8
• Strony: 987--989
• Opis fizyczny: Bibliogr. 12 poz., rys., tab., wzory

Twórcy

autor

Kajstura K.

autor

Kania D.

autor

Kurytnik I.

• Akademia Techniczno-Humanistyczna, Katedra Elektrotechniki i Automatyki, ul. Willowa 2, 43-309 Bielsko-Biała,

Bibliografia

• [1] Cirit M. A.: Estimating dynamic power consumption of CMOS circuits. Proc. IEEE Int. Conf. CAD, Nov. 1987, pp. 534-537.
• [2] Kentzer K., Ghosh A., Devadas S., White J.: Estimation of average switching activity in combinational and sequential circuits. Proc. Design Automation Conf., June 1992, pp. 253-259.
• [3] Benini L., DeMicheli G.: State Assignment for Low Power Dissipation. In IEEE Journal on Solid-state Circuits, Vol. 30, No 3, 1995.
• [4] Freitas A. T., Oliveira A. L.: Implicit Resolution of the Chapman-Kolmogorov Equations for Sequential Circuits: An Application in Power Estimation. Proceedings of DATE, 2003.
• [5] Surti P., Chao L. F.: Lower Power FSM Design Using Huffman-Style Encoding. IEEE EDTC-97, 1997, pp. 521-525.
• [6] Nőth W., Kolla R.: Spanning Tree Based State Encoding for Lower Power Dissipation. Technical Report, University of Wűrzburg, 1998.
• [7] Roy K., Prasad S. C.: Circuit Activity Based Logic Synthesis for Low Power Reliable Operations. Trans. on VLSI Systems, Vol. 1, No 4, 1993.
• [8] Venkataraman G., Reddy S. M., Pomeranz I.: GALLOP: Genetic Algorithm Based Lowe Power FSM Synthesis by Simultaneous Partitioning and State Assignment. 6th Intl. on VLSI Design, 2003.
• [9] Baccheta P., L. Daldoss, D. Sciuto, C. Silvano: Lower-Power State Assignment Techniques for Finite State Machines. IEEE International Symposium on Circuits and Systems (ISCAS’00), 2000.
• [10] Salauyou V., Grześ T.: Badania algorytmów kodowania stanów wewnętrznych automatu skończonego zorientowanych na minimalizację poboru mocy. Pomiary, Automatyka, Kontrola, 2008, R. 54, nr 8.
• [11] Yang S.: Logic Synthesis and Optimization Benchmarks User Guide: Version 3.0. Technical Report, Microelectronics Center of North Carolina, 1991.
• [12] Sentovich, E. M., Singh, K. J., Lavango, L., Moon, C., Muragi, R., Saldhana, A., Savoj, H., Stephen, P., Brayton, R., Sangiovanni-Vincentelli A.: SIS: A System for Sequential Circuit Synthesis. Technical Report UCB/ERL M92/41, University of California, Berkeley, 1992.