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

• Autorzy: Klimowicz A.

Warianty tytułu

EN

Minimization of finite state machines taking into account the cost of realization in CPLD devices

• Języki publikacji: PL

Abstrakty

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.

Słowa kluczowe

PL

automat skończony; synteza logiczna; minimalizacja; CPLD

EN

finite state machine; logic synthesis; minimization; CPLD

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2013
• Tom: R. 59, nr 8
• Strony: 760--762
• Opis fizyczny: Bibliogr. 10 poz., wzory

Twórcy

autor

Klimowicz A.

• Politechnika Białostocka, Wydział Informatyki, ul. Wiejska 45a, 15-351 Białystok

Bibliografia

• [1] Hallbauer G.: Procedures of state reduction and assignment in one step in synthesis of asynchronous sequential circuits, Proc. of Int. IFAC Symp. Discrete Syst., 1974, pp. 272–282.
• [2] Lee E. B., Perkowski M.: Concurrent minimization and state assignment of finite state machines, Proc. of Int. Conf. Syst., Man, Cybern., 1984, pp. 248–260.
• [3] Avedillo M. J. et al., SMAS: A program for concurrent state reduction and state assignment of finite state machines, Proc. of ISCAS, 1991, pp. 1781–1784.
• [4] Wang K. H. et al., State assignment for power and area minimization, Proc. of ICCD: International Conference on Computer Design, 1994, pp. 250–254.
• [5] Xia Y., Almaini A. E. A.: Genetic algorithm based state assignment for power and area optimization, IEE Proceedings on Computer and Digital Techniques 149 (4) (2002) 128–133.
• [6] Chattopadhyay S., Yadav P., Singh R. K.: Multiplexer Targeted' Finite State Machine Encoding for Area and Power Minimization, Proc. of IEEE India Annual Conference, 2004, pp. 12-16.
• [7] Aiman M., Sadiq S. M., Nawaz K. F.: Finite state machine state assignment for area and power minimization, Proc. of IEEE International Symposium on Circuits and Systems (ISCAS), 2006, 21-24 May 2006, IEEE Inc., pp. 5303-5306.
• [8] Yuan L., Qu G., Villa T., Sangiovanni-Vincentelli A.: An FSM Reengineering Approach to Sequential Circuit Synthesis by State Splitting, IEEE Trans. on CAD, V. 27, No. 6, 2008, pp. 1159-1164.
• [9] Chaudhury S., KrishnaTejaSistla K.T., Chattopadhyay S.: Genetic algorithm-based FSM synthesis with area-power trade-offs, / INTEGRATION, the VLSI journal 42 (2009) 376–384.
• [10] Klimovich А. S., Solov’ev V. V.: Minimization of Mealy finite-state machines by internal states gluing, Journal of Computer and Systems Sciences International, 2012, Vol. 51. No. 2, pp. 244-255.