FSMs state encoding targeting at logic level minimization

• Autorzy: Czerwiński R. , Kania D. , Kulisz J.
• Języki publikacji: EN

Abstrakty

EN

The paper concerns the problem of stale assignment for finite stale machines (FSM), tar-geting at PAL-based CPLDs implementations. Presented in the paper approach is dedicated to stale encoding of fast automata. The main idea is to determine the number of logic levels of the transition function before the stale encoding process, and keep the constraints during the process. The number of implicants of every single transition function must be known while assigning states, so elements of two level minimization based on Primary and Secondary Merging Conditions are implemented in the algorithm. The method is based on code length extraction if necessary. In one of the most basic stages of the logic synthesis of sequential devices, the elements referring to constraints of PAL-based CPLDs are taken into account.

Słowa kluczowe

EN

state assignment; finite state machine (FSM); programmable array logic (PAL); complex programmable logic devices (CPLD)

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2006
• Tom: Vol. 54, nr 4
• Strony: 479--487
• Opis fizyczny: Bibliogr. 17 poz., rys., tab.

Twórcy

autor

Czerwiński R.

autor

Kania D.

autor

Kulisz J.

• Institute of Electronics, Silesian University of Technology, 16 Akademicka Str., 44-100 Gliwice, Poland,

Bibliografia

• [1] G. Saucier, P. Sicard, and L. Bouchet, “Multi-level synthesis on PAL’s”, Proc. European Design Automation Conference, Glasgow, 542–546 (1990).
• [2] G. Saucier, P. Sicard, and L. Bouchet, “Multi-level synthesis on programmable devices in the ASYL system”, Euro ASIC, 136–141 (1990).
• [3] D. Kania, “A technology mapping algorithm for PAL-based devices using multi-output function graphs”, Proc. 26-th Euromicro Conference, 146–153, Maastricht (2000).
• [4] D. Kania, “Logic synthesis of multi-output functions for PALbased CPLDs”, IEEE Int. Conf. Field-Programmable Technology, 429–432, Hong Kong (2002).
• [5] G. De Micheli, R. Brayton, and A. Sangiovanni-Vincentelli, “Optimal state assignment for finite state machines”, IEEE Trans. on CAD/ICAS CAD-4 (3), 269–284 (1985).
• [6] T. Villa and A. Sangiovanni-Vincentelli, “NOVA: State assignment for finite state machines for optimal two-level logic implementation”, IEEE Trans. on Computer-Aided Design 9, 905–924 (1990).
• [7] E. Sentovich, K. Singh, L.Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. Stephan, R. Brayton, and A. Sangiovanni-Vincentelli, “SIS: A system for sequential circuit synthesis”, Proc. Int. Conf. on Computer Design, 328–333 (1992).
• [8] S. Yang and M. Ciesielski. “Optimum and suboptimum algorithms for input encoding and its relationship to logic minimization”, IEEE Trans. on Computer-Aided Design 10, 4–12 (1991).
• [9] S. Devadas, A.R. Newton, and P. Ashar. “Exact algorithms for output encoding, state assignment and four-level boolean minimization”, IEEE Trans. on Computer-Aided Design 10, 13–27 (1991).
• [10] M. Chyzy and W. Kosinski, “Evolutionary algorithm for state assignment of finite state machines”, Proc. of Euromicro Symposium on Digital System Design, 359–362 (2002).
• [11] S. Devadas, H.K. Ma, R. Newton, and A. Sangiovanni-Vincentelli, “MUSTANG: State assignment of finite state machines targeting multilevel logic implementations”, IEEE Trans. on Computer-Aided Design 7 (12), 1290–1300 (1988).
• [12] B. Lin and R. Newton, “Synthesis of multiple level logic from symbolic high-level description languages”, Proc. Int. Conf. on VLSI, 187–206 (1989).
• [13] P. Sicard, M. Crastes, K. Sakouti, and G. Saucier, “Automatic synthesis of boolean functions on xilinx and actel programmable devices”, Proc. Euro ASIC’91, Paris, 1991.
• [14] T. Villa, T. Saldanha, A. Brayton, and A. Sangiovanni-Vincentelli, “Symbolic two-level minimization”, IEEE Trans.on Computer-Aided Design of Integrated Circuits and Systems 16 (7), 692–708 (1997).
• [15] P.K. Lala. “An algorithm for the state assignment of synchronous sequential circuits”, Electronics Letters 14 (6), 199–201 (1978).
• [16] R. Czerwinski and D. Kania, “FSM’s state assignment method based on level of output activity”, RUC’2003, 9–16, Szczecin (2003).
• [17] MCNC, “LGSynth’91 benchmarks”, Collaborative Benchmarking Laboratory, Department of Computer Science, North Carolina State University, http://www.cbl.ncsu.edu/.