FSM Encoding for BDD Representations

Wilsin Gosti; Tiziano Villa; Alex Saldanha; Alberto Sangiovanni-Vincentelli

doi:10.2478/v10006-007-0011-6

.blurhash-client-img { display: none !important; }

FSM Encoding for BDD Representations

International Journal of Applied Mathematics and Computer Science

Volume 17 (2007): Issue 1 (March 2007)

By: Wilsin Gosti, Tiziano Villa, Alex Saldanha and Alberto Sangiovanni-Vincentelli

Open Access

|Apr 2007

Abstract

We address the problem of encoding the state variables of a finite state machine such that the BDD representing the next state function and the output function has the minimum number of nodes. We present an exact algorithm to solve this problem when only the present state variables are encoded. We provide results on MCNC benchmark circuits.

References

Bern J., Meinel C. and Slobodova A. (1996): Global rebuilding of OBDD's avoiding memory requirement maxima. — IEEE Trans. CAD Int. Circuits Syst., Vol. 15, No. 1, pp. 131-134.10.1109/43.486279
Search in Google Scholar
Brayton R.K., Hachtel G.D., McMullen C.T. and Sangiovanni-Vincentelli A.L. (1984): Logic Minimization Algorithms for VLSI Synthesis. — Kluwer Academic Publishers.10.1007/978-1-4613-2821-6
Search in Google Scholar
Bryant R.E. (1986): Graph-based algorithms for Boolean function manipulation. — IEEE Trans. Comput., Vol. C(35), No. 8, pp. 677-691.10.1109/TC.1986.1676819
Search in Google Scholar
Bryant R.E. (1992): Symbolic Boolean manipulation with ordered binary-decision diagrams. — ACM Comput. Surveys, Vol. 24, No. 3.10.1145/136035.136043
Search in Google Scholar
Buch P., Narayan A., Richard Newton A. and Sangiovanni-Vincentelli A. (1997): Logic synthesis for large pass transistor circuits. — Proc. 1997 IEEE/ACM Int. Conf. Computer-Aided Design, ICCAD '97, Washington, DC, USA, pp. 663-670.10.1109/ICCAD.1997.643609
Search in Google Scholar
Cabodi G., Quer S. and Camurati P. (1995): Transforming Boolean relations by symbolic encoding, In: Proc. Correct Hardware Design and Verification CHARME'95, (P. Camurati and P. Eveking, Edi.), LNCS, Vol. 987, pp. 161-170.10.1007/3-540-60385-9_10
Search in Google Scholar
Drechsler R., Drechsler N. and Gunther W. (2000): Fast exact minimization of BDD's. — IEEE Trans. CAD Int. Circ. Syst., Vol. 19, No. 3, pp. 384-389.10.1109/43.833206
Search in Google Scholar
Drechsler R., Junhao Shi and Görschwin Fey (2004): Synthesis of fully testable circuits from BDDs. — IEEE Trans. CAD Int. Circ. Syst., Vol. 23, No. 3, pp. 440-443.10.1109/TCAD.2004.823342
Search in Google Scholar
Gosti W., Villa T., Saldanha A. and Sangiovanni-Vincentelli A. (1998): An exact input encoding algorithm for BDDs representing FSMs. — Proc. 8-th Great Lakes Symp. VLSI, Lafayette, LA, USA, pp. 294-300.
Search in Google Scholar
Gosti W., Villa T., Saldanha A. and Sangiovanni-Vincentelli A.L. (1997): Input encoding for minimum BDD size: Theory and experiments. — Techn. rep., University of California at Berkeley, No. UCB/ERL M97/22.
Search in Google Scholar
Gunther W. and Drechsler R. (1998): Linear transformations and exact minimization of BDDs. — Proc. 8-th Great Lakes Symp. VLSI, Lafayette, LA, USA, pp. 325-330.10.1109/GLSV.1998.665287
Search in Google Scholar
Gunther W. and Drechsler R. (2000): ACTion: Combining logic synthesis and technology mapping for MUX-based FPGAs. — J. Syst. Archit., Vol. 46, No. 14, pp. 1321-1334.10.1016/S1383-7621(00)00027-8
Search in Google Scholar
Hartrmanis J. and Stearns R.E. (1962): Some dangers in the state reduction of sequential machines. — Inf. Contr., Vol. 5, No. 3, pp. 252-260.10.1016/S0019-9958(62)90588-0
Search in Google Scholar
Lavagno L., McGeer P., Saldanha A. and Sangiovanni-Vincentelli A.L. (1995): Timed Shannon Circuits: A Power-Efficient Design Style and Synthesis Tool. — Proc. 32-th Design Automation Conf., San Francisco, CA, USA, pp. 254-260.10.1109/DAC.1995.250100
Search in Google Scholar
Lee E.B. and Perkowski M. (1984): Concurrent minimization and state assignment of finite state machines. — Proc. IEEE Int. Conf. Syst., Man Cybernetics, Halifax, Nova Scotia, Canada, pp. 248-260.
Search in Google Scholar
Lisanke R. (1989): Logic synthesis benchmark circuits for the International Workshop on Logic Synthesis. — Research Triangle Park, North Carolina, Microelectronics Center of North Carolina.
Search in Google Scholar
Macchiarulo L., Benini L. and Macii E. (2001): On-the-fly layout generation for PTL macrocells. — Proc. Conf. Design, Automation and Test in Europe, DATE '01, pp. 546-551, Piscataway, NJ, USA, IEEE Press.
Search in Google Scholar
Meinel C., Somenzi F. and Theobald T. (2000): Linear sifting of decision diagrams and its application in synthesis. — IEEE Trans. CAD Int. Circ. Syst., Vol. 19, No. 5, pp. 521-533.10.1109/43.845077
Search in Google Scholar
Meinel C. and Theobald T. (1999): On the influence of state encoding on OBDD-representations of finite state machines. — Theoret. Inf. Applic., Vol. 33, No. 1, pp. 21-31.10.1051/ita:1999103
Search in Google Scholar
Meinel Ch. and Theobald T. (1996 a): Local encoding transformations for optimizing OBDD-representations of finite state machines. — Proc. Int. Conf. Formal Methods in Computer-Aided Design, London: Springer, No. 1166, pp. 404-418.10.1007/BFb0031824
Search in Google Scholar
Meinel Ch. and Theobald T. (1996 b): State encodings and OBDD-sizes. — Techn. rep. 96-04, Universität Trier, Germany.
Search in Google Scholar
Rudell R. (1993): Dynamic variable ordering for ordered binary decision diagrams. — Proc. Int. Conf. Computer-Aided Design, San Francisco, CA, USA, pp. 42-47.10.1109/ICCAD.1993.580029
Search in Google Scholar
Saldanha A., Villa T., Brayton R. and Sangiovanni-Vincentelli A. (1994): Satisfaction of input and output encoding constraints. — IEEE Trans. CAD Int. Circ. Syst., Vol. 13, No. 5, pp 589-602.
Search in Google Scholar
Villa T., Kam T., Brayton R. and Sangiovanni-Vincentelli A. (1997): Synthesis of FSMs: Logic Optimization. — Boston: Kluwer.
Search in Google Scholar
Yuan L., Qu G., Villa T. and Sangiovanni-Vincentelli A.L. (2005): FSM re-engineering and its application in low power state encoding. — Proc. 2005 Asia South Pacific Design Automation Conf. (ASP-DAC 2005), Shanghai, China, Vol. 1, pp. 254-259.10.1109/ASPDAC.2005.1466169
Search in Google Scholar

Articles in this issue

DOI: https://doi.org/10.2478/v10006-007-0011-6 | Journal eISSN: 2083-8492 | Journal ISSN: 1641-876X

Journal RSS Feed

Language: English

Page range: 113 - 124

Published on: Apr 5, 2007

Published by: University of Zielona Góra

In partnership with: Paradigm Publishing Services

Publication frequency: 4 issues per year

Keywords:

binary decision diagram,

encoding,

finite state machine,

Related subjects:

© 2007 Wilsin Gosti, Tiziano Villa, Alex Saldanha, Alberto Sangiovanni-Vincentelli, published by University of Zielona Góra
This work is licensed under the Creative Commons License.

Volume 17 (2007): Issue 1 (March 2007)