Synthesis of finite state machines for CPLDs

Robert Czerwiński; Dariusz Kania

International Journal of Applied Mathematics and Computer Science (2009)

  • Volume: 19, Issue: 4, page 647-659
  • ISSN: 1641-876X

Abstract

top
The paper presents a new two-step approach to FSM synthesis for PAL-based CPLDs that strives to find an optimum fit of an FSM to the structure of the CPLD. The first step, the original state assignment method, includes techniques of twolevel minimization and aims at area minimization. The second step, PAL-oriented multi-level optimization, is a search for implicants that can be shared by several functions. It is based on the graph of outputs. Results of experiments prove that the presented approach is especially effective for PAL-based CPLD structures containing a low number of product terms.

How to cite

top

Robert Czerwiński, and Dariusz Kania. "Synthesis of finite state machines for CPLDs." International Journal of Applied Mathematics and Computer Science 19.4 (2009): 647-659. <http://eudml.org/doc/207963>.

@article{RobertCzerwiński2009,
abstract = {The paper presents a new two-step approach to FSM synthesis for PAL-based CPLDs that strives to find an optimum fit of an FSM to the structure of the CPLD. The first step, the original state assignment method, includes techniques of twolevel minimization and aims at area minimization. The second step, PAL-oriented multi-level optimization, is a search for implicants that can be shared by several functions. It is based on the graph of outputs. Results of experiments prove that the presented approach is especially effective for PAL-based CPLD structures containing a low number of product terms.},
author = {Robert Czerwiński, Dariusz Kania},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {logic synthesis; FSM; state assignment; logic optimization; CPLD},
language = {eng},
number = {4},
pages = {647-659},
title = {Synthesis of finite state machines for CPLDs},
url = {http://eudml.org/doc/207963},
volume = {19},
year = {2009},
}

TY - JOUR
AU - Robert Czerwiński
AU - Dariusz Kania
TI - Synthesis of finite state machines for CPLDs
JO - International Journal of Applied Mathematics and Computer Science
PY - 2009
VL - 19
IS - 4
SP - 647
EP - 659
AB - The paper presents a new two-step approach to FSM synthesis for PAL-based CPLDs that strives to find an optimum fit of an FSM to the structure of the CPLD. The first step, the original state assignment method, includes techniques of twolevel minimization and aims at area minimization. The second step, PAL-oriented multi-level optimization, is a search for implicants that can be shared by several functions. It is based on the graph of outputs. Results of experiments prove that the presented approach is especially effective for PAL-based CPLD structures containing a low number of product terms.
LA - eng
KW - logic synthesis; FSM; state assignment; logic optimization; CPLD
UR - http://eudml.org/doc/207963
ER -

References

top
  1. Baranov, S. (1994). Logic Synthesis for Control Automata, Kluwer Academic Publishers, Dordrecht. Zbl0806.68009
  2. Barkalov, A., Titarenko, L. and Chmielewski, S. (2007). Reduction in the number of PAL macrocells in the circuit of a Moore FSM, International Journal of Applied Mathematics and Computer Science 17(4): 565-575. 
  3. Chattopadhyay, S. (2001). Low power state assignment and flipflop selection for finite state machine synthesis-A genetic algorithmic approach, IEE Proceedings-Computers and Digital Techniques 148(45): 147-151. 
  4. Chyży, M. and Kłosiński, W. (2002). Evolutionary algorithm for state assignment of finite state machines, Proceedings of the Euromicro Symposium on Digital System Design, Dortmund, Germany, pp. 359-362. 
  5. Czerwiński, R. and Kania, D. (2005). State assignment for PALbased CPLDs, Proceedings of the 8-th Euromicro Symposium on Digital System Design, DSD2005, Porto, Portugal, IEEE Computer Society Press, Porto, pp. 127-134. 
  6. Czerwiński, R., Kania, D. and Kulisz, J. (2006). FSMs state encoding targeting at logic level minimization, Bulletin of the Polish Academy of Sciences 54(4): 479-487. Zbl1203.03055
  7. Czerwiński, R. and Kulisz, J. (2009). State machine description oriented towards effective usage of vendor-independent synthesis tool, IFAC Workshop on Programmable Devices and Embedded Systems, PDES'2009, Roznov and Radhostem, Czech Republic, pp. 27-32. 
  8. Czerwiński, R. (2006). The FSMs State Assignment for PALBased Matrix Programmable Structures, Ph.D. thesis, Silesian University of Technology, Gliwice, (in Polish). 
  9. De Micheli, G. (1994). Synthesis and Optimization of Digital Circuits, McGraw-Hill Inc., New York, NY. 
  10. Devadas, S. and Newton, A. R. (1991). Exact algorithms for output encoding, state assignment and four-level boolean minimization, IEEE Transactions on Computer-Aided Design 10(1): 13-27. 
  11. Jóźwiak, L. and Volf, F. (1995). Efficient decomposition of assigned sequential machines and boolean functions for PLD implementations, Proceedings of Electronic Technology Directions to the Year 2000, Adelaide, Australia, pp. 258-266. 
  12. Kania, D. (2003). An efficient approach to synthesis of multi-output boolean functions on PAL-based devices, IEE Proceedings on Computer and Digital Techniques 150(3): 143-149. 
  13. Kania, D. (2004). The Logic Synthesis for the PAL-based Complex Programmable Logic Devices, Silesian University of Technology, Gliwice, (in Polish). 
  14. MCNC (1991). LGSynth'91 benchmarks, Collaborative Benchmarking Laboratory, Department of Computer Science at North Carolina State University, Raleigh, NC, http://www.cbl.ncsu.edu/. 
  15. Mengibar, L., Entrena, L., M.G.Lorenz and E.S.Millan (2005). Patitioned state encoding for low power in FPGAs, Electronics Letters 41(17): 948-949. 
  16. Park, S., Yang, S. and Cho, S. (2000). Optimal state assignment technique for partial scan designs, Electronics Letters 36(18): 1527-1529. 
  17. Salauyou, V., Klimowicz, A., Grzes, T., Dimitrova-Grekow, T. and Bulatowa, I. (2006). Experimental Studies of Finite State Machines Synthesis Methods Implemented in Package ZUBR, Pomiary, Automatyka, Kontrola 52(6 bis): 44-46, (in Polish). 
  18. Sentovich, E., Singh, K., Moon, C., Savoj, H., Brayton, R. and Sangiovanni-Vincentelli, A. (1992). SIS: A system for sequential circuit synthesis, Technical report, University of California, Berkeley, CA. 
  19. Sharma, K. (1998). Programmable Logic Handbook, PLDs, CPLDs, & FPGAs, McGraw-Hill, New York, NY. 
  20. Villa, T., Kam, T., Brayton, R. and Sangiovanni-Vincentelli, A. (1997). Synthesis of Finite State Machines: Logic Optimization, Kluwer Academic Publishers, Boston, MA. Zbl0876.94057
  21. Villa, T. and Sangiovanni-Vincentelli, A. (1990). NOVA: State assignment for finite state machines for optimal two-level logic implementation, IEEE Transactions on ComputerAided Design 9(9): 905-924. 
  22. Yang, S. and Ciesielski, M. (1991). Optimum and suboptimum algorithms for input encoding and its relationship to logic minimization, IEEE Transactions on Computer-Aided Design 10(1): 4-12. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.