Synthesis of finite state machines for implementation with programmable structures

• Autorzy: Łuba T. , Borowik G. , Kraśniewski A.
• Konferencja: Digital Control Units Design ; 6.03.2009 ; Zielona Góra, Poland
• Języki publikacji: EN

Abstrakty

EN

Sensible application of programmable structures to the realization of digital systems cannot take place without computer aided design systems. It is particularly important when the design is intended for novel programmable structures containing LUT-based cells and embedded memory blocks, since traditional methods for technology mapping are oriented towards gate structures and based on minimization and factorization of Boolean functions. This article focuses on finite state machine synthesis including logic optimization techniques, the technology mapping techniques, and the techniques that provide the resulting circuits with concurrent error detection capability. It is shown that a considerably more effective method of synthesis intended for CPLD and FPGA structures is based on the decomposition scheme.

Słowa kluczowe

EN

decomposition; state encoding; sequential circuit; finite state machine; FPGA; embedded memory block; logic cell; multigraph

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: Electronics and Telecommunications Quarterly
• Rocznik: 2009
• Tom: Vol. 55, No 2
• Strony: 183--200
• Opis fizyczny: Bibliogr. 67 poz., wykr.

Twórcy

autor

Łuba T.

autor

Borowik G.

autor

Kraśniewski A.

• Institute of Telecommunications, Warsaw University of Technology. Poland,

Bibliografia

• [AB06] M. Adamski, A. Barkalov: Architectural and Sequential Synthesis of Digital Devices University of Zielona Góra Press.
• [A1DM06] S. Almukhaizim, P. Drineas, Y. Makristion: Entropy-driven parity-tree selecc for low-overhead concurrent error detection infinite state machines, IEEE Trans. on CAD vol. 25, no. 8, pp. 1547-1554, Aug. 2006,
• [ADN92] P. Ashar, S. Devadas, A. R. Newton: Sequential Logic Synthesis, Kluwer Academic Publishers, 1992, Boston, MA, USA.
• [BMSS00] C. Bolchini, R. Montandon, F. Self-Checking Finite Salice, D. Sciuto: Design of VHDL-Based Totally-State Machine and Data Path Descriptions, IEEE Trans. on VLSI Systems, vol. 8, pp. 98-103, Feb. 2000.
• [BFL07] G. Borowik, B. Falkowski, T. Łuba: Cost-Efficient Synthesis for Sequential Ciruits Implemented Using Embedded Memory Blocks of FPGA's, Proc. of 10th IEEE Workshop on Design and Diagnostics of Electronic Circuits and Systems (2007), Kraków, Poland, -13 April .
• [BL03] J. A. Brzozowski, T. Łuba: Decomposition of Boolean Functions Specified by Cubes, Journal of Multi-Valued Logic and Soft Computing vol. 9 (2003), 377-417, Old City Publishing Inc., Philadelphia 2003.
• [Bor04] G. Borowik: Synthesis of Memory Addressing Circuits in FPGA-based Sequential Machines, Proc. of V International Conference on Computer-Aided Design of Discrete Devices (2004), 31-38, Minsk, Belarus, 16-17 November 2004.
• [Bor08] G. Borowik: Improved State Encoding for FSM Implementation in FPGA Structures with Embedded Memory Blocks, Electronics and Telecommunications Quarterly, vol. 54, no 1, 9-28, March 2008.
• [BW06] A. Barkalov, L. Titarenko: Logic Synthesis for Compositional Microprogram Control Units, Springer, 2008.
• [BW06] A. Barkalov, M. Węgrzyn: Design of Control Units with Programmable Logic, University of Zielona Góra Press, 2008.
• [BoNT93] M. Boudjit, M. Nicolaidis, K. Torki: Automatic generation algorithms, experiments and comparisons of self-checking PLA schemes using parity codes, Proc. European Design Automation Conf., pp. 144-150, 1993.
• [Cohe99] N. Cohen et al.: Soft error considerations for deep-submicron CMOS circuit applications, Dig. IEDM Int. Electron Devices Meeting, pp. 315-318, 1999.
• [CK05] R. Czerwiński, D.: State Assignment for PAL-based CPLDs, Proc. of 8th Euromicro Conference on Digital Systems Design, Architectures, Methods and Tools, IEEE Computer Society, Christophe Wolinski (Ed.) (2005), 127-134, Porto, Portugal, 30 August - 3 September 2005.
• [CKK06] R. Czerwiński, D. Kania, J. Kulisz: FSMs State Encoding Targeting at Logic Level Minimization, Bulletin of the Polish Academy of Sciences vol. 54 (2006), no. 4.
• [CMSH96] S. C. Chang, M. Marek-Sadowska, T. T. Hwang: Technology Mapping for TLU FPGAs Based on Decomposition of Binary Decision Diagrams, IEEE Trans. on CAD vol. 15 (1996), no. 10, 1226-1236, October 1996.
• [Cou98] O. Coudert: A New Paradigm for Dichotomy-based Constrained Encoding, Proc. of Design, Automation and Test in Europe (1998), 830-834.
• [CS96] O. Coudert, C. J. R. Shi: Exact Dichotomy-based Constrained Encoding, Proc. of the Int. Conf. on Computer Design (1996), 426-431.
• [CY92] M. J. Ciesielski, Y. Plade: A Two-stage PLA Decomposition, IEEE Trans. on CAD vol. 11 (1992), no. 8, 943-954.
• [DaTo98] D. Das, N. A. Touba: Synthesis of Circuits with Low-Cost Concurrent Error Detection based on Bose-Lin Codes, Proc. VLSI Test Symp., pp. 309-315, 1998.
• [DBSV85] G. De Micheli, R. K. Brayton A. Sangiovanni-Vincentelli: Optimal State Assignment for Finite State Machines, IEEE Transactions on CAD vol. CAD-4 (1985), no. 3, 269-284.
• [DeM86] G. De Micheli: Symbolic Design of Combinational and Sequentional Logic Circuits Implemented by Low-level Logic Macros, IEEE Transactions on CAD vol. CAD-5 (1986), no. 4, 597-616.
• [DeM94] G. De Micheli: Synthesis and Optimization of Digital Circuits, McGraw-Hill, New York, 1994.
• [DHLN91] X. Du, G. Hachtel, B. Lin, R. A. Newton, MUSE: A Multilevel Symbolic Encoding Algorithm for State Assignment, IEEE Transactions on CAD vol. 10 (1991), no. 1, 28-38.
• [DMNSV88] S. Devadas, H. K. Ma, R. Newton, A. Sangiovanni-Vincentelli: MUSTANG: State Assignment of Finite State Machines Targeting Multilevel Logic Implementations, IEEE Transactions on CAD vol. 7 (1988), no. 12, 1290-1300.
• [DN89] S. Devadas, R. Newton: Decomposition and Factorization of Sequential Finite Stale Machines, IEEE Transactions on CAD vol. 8 (1989), no. 11, 1206-1217.
• [DN91] S. Devadas, R. Newton: Exact Algorithms for Output Encoding, State Assignment and Four-level Boolean Minimization, IEEE Transactions on CAD vol. 10 (1991), no. 1. 13-27.
• [For95] J. Forrest, ODE: Output Direct State Machine Encoding, Proc. of the European Design Automation Conference (1995), 600-605.
• [HK04] E. Hrynkiewicz, D. Kania: Metody syntezy dedykowane dla struktur FPGA typu tablicowego (in Polish), Kwartalnik Elektroniki i Telekomunikacji nr 50, z. 3 (2004). 325-342.
• [HS66] J. Hartmanis, R. E. Stearns: Algebraic Structure Theory of Sequential Machines. Prentice-Hall, New York, 1966.
• [HSB02] S. Hassoun, T. Sasao, R. Brayton (Eds.): Logic Synthesis and Verification. Kluwer Academic Publishers, 2002, New York.
• [IP99] S. Iman, M. Pedram: Logic Synthesis for Low Power VLSI Designs, Kluwer Academic Publishers, 1999.
• [IyKi95] V. S. Iyengar, L. L. Kinney: Concurrent Fault Detection in Microprogrammed Control Units, IEEE Trans. on Computers, vol. C-34, pp. 810-821, Sept. 1985.
• [JC01] L. Jóźwiak, A. Chojnacki: Effective and Efficient FPGA Synthesis through Functional Decomposition Based on Information Relatinship oMeasures, Proc. of Euromicro Symposium on Digital Systems Design (2001), 30-37, Warsaw, Poland, 4-6 September 2001.
• [JSOO] L. Jóźwiak, A. Ślusarczyk: A new state assignment method targeting FPGA implementations, Proc. of the 26th Euromicro Conference vol. 1 (2000), 50-59, Maastricht, The Netherlands, 5-7 September 2000.
• [JSC01] L. Jóźwiak, A. Ślusarczyk, A. Chojnacki: Fast and Compact Sequential Circuits through the Information-Driven Circuit Synthesis, Proc. of Euromicro Symposium on Digital Systems Design (2001), 46-53, Warsaw, Poland, 4-6 September 2001.
• [Kan04] D. Kania: The Logic Synthesis for the PAL-based Complex Programmable Logic Devices (in Polish), Zeszyty Naukowe (2004), 16-19, Politechnika Śląska, Gliwice 2004.
• [Kras97] A. Kraśniewski: Design for Application-Dependent Testability of FPGAs, Proc. Int. Workshop on Logic and Architecture Synthesis, pp. 245-254, Grenoble, Dec. 1977. Self-Testing of Sequential.
• [Kras04a] A. Kraśniewski: Circuits Designed for Implementation in FPGAs with Embedded Memory Blocks, Proc. IEEE Workshop on Design and Diagnostics of Electronics Circuits and Systems, pp. 75-82, Tatranska Lomnica, April 2004.
• [Kras04b] A. Kraśniewski: Concurrent Error Detection in Sequential Circuits Implemented Using FPGAs with Embedded Memory Blocks, Proc. IEEE Int. On-Line Testing Symp., pp. 67-72, Funchal (Madeira), July 2004.
• [Kras05a] A. Kraśniewski: Cost-Free Enhancement of Testability for Sequential Circuits Implemented Using Embedded Memory Blocks of FPGA's, Proc. IEEE Workshop on Design and Diagnostics of Electronics Circuits and Systems, pp. 61-68, Sopron, April 2005.
• [Kras05b] A. Kraśniewski: A Pragmatic Approach to Concurrent Error Detection in Sequential Circuits Implemented Using FPGAs with Embedded Memory, Proc. IEEE Int. On-Line Testing Symp., pp. 197-198, San Raphael, July 2005
• [Kras06] A. Kraśniewski: Low-Cost Concurrent Error Detection for FSMs Implemented Using Embedded Memory Blocks of FPGAs, Proc. IEEE Workshop on Design and Diagnostics of Electronics Circuits and Systems, pp. 180-185, Praha, April 2006. A.
• [Kras08] A Kraśniewski: Concurrent Error Detection for Finite State Machines Implemented with Embedded Memory Blocks of SRAM-Based FPGAs, Microprocessors and Microsystems, vol. 32, no. 5-6, pp. 303-312, August 2008.
• [LeSi99] I. Levin, V. Sinelnikov: Self-checking of FPGA-based control units, Proc. 9th Great Lakes Symposium on VLSI, pp. 292-295, 1999.
• [LOKS06] I. Levin, V. Ostrovsky, O. Keren, V. Sinelnikov: Cascade Scheme for Concurrent Errors Detection, Proc. 10th EUROMICRO Conf. on Digital System Design, pp. 359-368, 2006.
• [LN89] B. Lin, R. A. Newton: Synthesis of Multiple Level Logic Symbolic High-level Description Languages, Proc. of the Int. Conf. on VLSI (1989), 187-196.
• [LPP96] Y. T. Lai, K. R. R. Pan, M. Pedram: OBDD-Based Functional Decomposition: Algorithm and Implementation, IEEE Trans. on CAD vol. 15 (1996), no. 8, 977-990, August 1996.
• [LuS95] T. Luba, H. Selvaraj: General Approach to Boolean Function Decomposition and its Applications in FPGA-based Synthesis. VLSI Design. Special Issue on Decompositions in VLSI Design, vol. 3, Nos. 3-4, 289-300, 1995.
• [PMG99] M. Perkowski, R. Malvi, S. Grygiel, M. Burns, A. Mishchenko: Graph coloring algorithms for Fast Evaluation of Curtis Decompositions, Proc. of Design Automation Conference (1999), 225-230, New Orleans, 1999.
• [Qudd99] W. Quddus, A. Jas, N. A. Touba: Configuration Self-Test in FPGA-Based Reconfigurable Systems. In: Proc. ISCAS'99, 1999, pp. 97-100.
• [Reno03] M. Renovell: Some Aspects of the Test Generation Problem for an Application-Oriented Test of SRAM-Based FPGAs, Journal of Circuits, Systems, and Computers, vol. 12(2003), no. 2, pp. 143-158.
• [RJL01] M. Rawski, L. Jóźwiak, T. Łuba: Functional Decomposition with an Efficent Input Support Selection for Sub-functions Based on Information Relationship Measures, Journal of Systems Architecture 47 (2001), 137-155, Elsevier Science B.V., 2001.
• [RSL05] M. Rawski, H. Selvaraj, T. Łuba: An Application of Functional Decomposition in ROM-based FSM Implementation in FPGA Devices, Journal of Systems Architecture vol. 51 (2005), 424-434, Elsevier 2005.
• [RSLS06] M. Rawski, H. Selvaraj, T. Łuba, P. Szotkowski: Multilevel Synthesis of Finite State Machines Based on Symbolic Functional Decomposition, International Journal of Computational Intelligence and Applications, Vol. 6, No. 2 , June 2006, pp. 257-271, Imperial College Press .
• [SB93] C. J. Shi, J. A. Brzozowski: An Efficient Algorithm for Constrained Encoding and Its Applications, IEEE Trans. on CAD vol. 12 (1993), no. 12, 1813-1826.
• [Sch01] C. Scholl: Functional Decomposition with Application to FPGA Synthesis, Kluwer Academic Publisher, 2001, Boston.
• [SLBG94] G. Sarwary, E. P. Lopes, L. Burgun, A. Greiner: FSM Synthesis on FPGA Architectures, Proc. of 7th Annual IEEE International ASIC Conference and Exhibit (1994), 178-181.
• [Sol97] V. V. Solovjev: Sintez konechnyh avtomatov na programmiruemyh matricah logiki, Avtomatika i Vychislitelnaya Tehnika No. 2 (1997), 65-74.
• [SSL92] E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. R. Stephan, R. K. Brayton, A. Sangiovanni-Vincentelli, SIS: A System for Sequential Circuit Synthesis, Memorandum, no. UCB/ERL M92/41, Electronics Research Laboratory, Department of Electrical Engineering and Computer Science, University of California, Berkley, 1992.
• [SSP01] P. Sapiecha, H. Selvaraj, M. Pleban: Decomposition of Boolean Relations and Functions in Logic Synthesis and Data Analysis, Rough Sets and Current Trends in Computing, Springer Verlag, W. Ziarko, Y. Yao (Eds.) (2001), 487-494, Berlin 2001.
• [SVBSV94] A. Saldanha, T. Villa, R. K. Brayton, A. Sangiovanni-Vincentelli: Satisfaction of Input and Output Encoding Constraints, IEEE Trans. on CAD vol. 13 (1994), no. 5, 589-602.
• [TKBSV98] T. Villa, T. Kam, R. K. Brayton, A. Sangiovanni-Vincentelli: Synthesis of Finite State Machines: Logic Optimization, Kluwer Academic Publishers, Boston, 1998.
• [VSV90] T. Villa, A. Sangiovanni-Vincentelli, NOVA: State Assignment for Optimal Two-level Implementations, IEEE Transactions on CAD vol. 9 (1990), no. 9, 905-924.
• [WKA89] W. Wolf, K. Kautzer, J. Akella: Addendum to A Kernel Finding State Assignment Algorithm for Multilevel Logic, IEEE Transactions on CAD vol. 8 (1989), no. 8, 917-920.
• [Wong83] C. Y. Wong et al.: The Design of a Microprogram Control Unit with Concurrent Error Detection, Proc. Fault Tolerant Computing Symp., pp. 476-483, 1983
• [YSL05] S. N. Yanushkevich, V. P. Shmerko, S. E. Lyshevski: Logic Design of NanoICs, Detection, CRC Press, 2005.
• [ZeSM99] C. Zeng, N. Saxena, E. J. McCluskey: Finite State Machine Synthesis with Concurrent Error Detection, Proc. IEEE Int. Test Conf., pp. 672-679, 1999