Algorytm funkcjonalnej dekompozycji symbolicznej automatów skończonych dla celów implementacji w strukturach FPGA

• Autorzy: Szotkowski P. , Rawski M.

Warianty tytułu

EN

Symbolic Functional Decomposition Algorithm for FSM Implementation in FPGA Structures

• Języki publikacji: PL

Abstrakty

PL

Dotychczasowe podejście do implementacji automatów skończonych w układach FPGA składa sie z dwóch etapów: kodowania stanów automatu oraz mapowania powstałych funkcji w strukturze układu. W przypadku mapowania za pomocą dekompozycji funkcjonalnej trudno jest znaleźć "dobrą" metodę kodowania stanów, szczególnie przy zastosowaniu proce-su syntezy wielopoziomowej. Artykuł opisuje algorytm funkcjonalnej dekompozycji symbolicznej, który zamiast osobnego etapu kodowania wprowadza sukcesywne kodowanie stanów gwarantujące dobrą jakość dekompozycji, oraz przedstawia działanie tego algorytmu na przykładzie wybranego automatu skończonego.

EN

The following paper presents an algorithm of symbolic functional decomposition for implementation of finite state machines in FPGA circuits. The idea of symbolic functional decomposition does not require a separate step of encoding the FSM's states. This method uses a description of the FSM that maintains a symbolic representation of the machine's states and introduces their encoding gradually, during each of the iterations of the decomopsition process; such approach guarantees high quality of the final decomposition. This paper presents an algorithm of symbolic functional decomposition based on blanket algebra. Each of the algorithm's steps is described in detail, as well as presented on an example FSM.

Słowa kluczowe

PL

funkcjonalna dekompozycja symboliczna; automat skończony; FSM; FPGA

EN

symbolic functional decomposition; finite state machine; FSM; FPGA

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2007
• Tom: R. 53, nr 7
• Strony: 48--50
• Opis fizyczny: Bibliogr. 9 poz., rys., wzory

Twórcy

autor

Szotkowski P.

autor

Rawski M.

• Instytut Telekomunikacji, Politechnika Warszawska,

Bibliografia

• [1] J. A. Brzozowski i T. Luba: Decomposition of Boolean Functions Specifed by Cubes, [w:] Journal of Multiple-Valued Logic and Soft Computing, Vol. 9, Old City Publishing Inc., Philadelphia, 2003, s. 377-417.
• [2] M. Rawski, L. Jóźwiak i T. Luba: Functional Decomposition with an Efficient Input Support Selection for Sub-functions Based on Informal Relationship Measures, [w:] Journal of Systems Architecture, 47, 2001, s. 137-155.
• [3] C. Scholl: Functional Decomposition with Application to FP Synthesis, Kluwer Academic Publishers, 2001.
• [4] M. Rawski: The Novel Approach to FSM Synthesis Targeted FPGA Architectures, [w:] Proceedings of IFAC Workshop on Programmable Devices and Systems, PDS 2004, Kraków, s. 169-174.
• [5] M. Rawski, H. Selvaraj, T. Luba i P. Szotkowski: Application of Symbolic Functional Decomposition Concept in FSM Implementation targeting FPGA devices, [w:] Sixth International Conference on Computational Intelligence and Multimedia Applications, ICCIMA 2005, Las Vegas, s. 153-158.
• [6] M. Rawski, H. Selvaraj, T. Luba i P. Szotkowski: Multilevel Synthesis o Finite State Machines Based on Symbolic Functional Decomposition, [w:] International Journal of Computational Intelligence and Applications, w druku.
• [7] G. De Michell, R. K. Brayton i A. Sangiovanni-Vincentelli: Optimal state assignment for finite state machines, [w:] IEEE Trans. on CAD, 1985, s. 269-284.
• [8] T. Villa i A. Sangiovanni-Vincentelli: Nova: state assignment of finite state machines for optimal two-level logic implementation, [w:] IEEE Trans. on CAD, 1990, s. 905-924.
• [9] B. Lin i A. R. Newton: Synthesis of multiple level logic from symbolic high-level description languages, [w:] Proc. of IFIP Int. Conf. on VLSI, s. 187-196.