Koszt implementacji w strukturach CPLD i FPGA jako kryterium wyboru stanów przy minimalizacji automatu skończonego

• Autorzy: Klimowicz A.

Warianty tytułu

EN

Cost of implementation in CPLD and FPGA structures as the criterion of state selection for minimization of finite state machines

• Języki publikacji: PL

Abstrakty

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.

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: 2014
• Tom: R. 60, nr 7
• Strony: 480--482
• Opis fizyczny: Bibliogr. 10 poz., tab.

Twórcy

autor

Klimowicz A.

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

Bibliografia

• [1] 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.
• [2] Yuan L., Qu G., Villa T., Sangiovanni-Vincentelli A.: An FSM Reengineering Approach to Sequential Circuit Synthesis by State Splitting, IEEE Trans. on CAD, Vol. 27, No. 6, 2008, pp.1159-1164.
• [3] Czerwiński R., Kania D.: Synthesis of finite state machines for CPLDs, Int. J. Appl. Math. Comput. Sci., 2009, Vol. 19, No. 4, pp. 647–659.
• [4] Chaudhury S., KrishnaTejaSistla K.T., Chattopadhyay S.: Genetic algorithm-based FSM synthesis with area-power trade-offs, INTEGRATION, the VLSI journal, 2009, Vol. 42, pp. 376–384.
• [5] Liu Z., Arslan T., Erdogan A. T.: An embedded low power reconfigurable fabric for finite state machine operations. Proc. of the International Symposium on Circuits and Systems, 2006, pp. 4374–4377.
• [6] Shiue W.T.: Novel state minimization and state assignment in finite state machine design for low-power portable devices. INTEGRATION, the VLSI journal, 2005, Vol. 38, pp. 549–570.
• [7] Klimovich А.S., Solov’ev V.V.: Minimization of Incompletely Specified Mealy Finite-State Machines by Merging Two Internal States, Journal of Computer and Systems Sciences International, 2013, Vol.52, No.3, pp. 400-409.
• [8] Luba T. Selvaraj H.: A general approach to Boolean function decomposition and its application in FPGA-based synthesis, 1995, VLSI DESIGN, Vol.3, Issue:3-4, pp. 289-300.
• [9] Yang S.: Logic Synthesis and Optimization Benchmarks User Guide; Microelectronics Center of North Carolina, Research Triangle Park, NC, 1991.
• [10] Rho J.K., Hachtel G., Somenzi F., Jacoby R., Exact and heuristic algorithms for the minimization of incompletely specified state machines, IEEE Trans. Computer-Aided Design, Vol. 13, 1994, pp. 167–177.