Article

Free access

Multi-level logic optimization of FSM networks

Authors:

Huey-Yih Wang,

Robert K. BraytonAuthors Info & Claims

ICCAD '95: Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design

Pages 728 - 735

Published: 01 December 1995 Publication History

PDF eReader

References

[1]

A. Aziz, E Balarin, R. K. Brayton, and A. Sangiovanni-Vincentelli. Sequential Synthesis using S1S. In IEEE International Conference on Computer-Aided Deign, November 1995.

Digital Library

Google Scholar

[2]

R. Brayton, R. Rudell, A. Sangiovarmi-Vincentelli, and A. Wang. MIS: Multiple- Level Logic Optimization System. In IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, pages 1062-1081, November 1987.

Google Scholar

[3]

R.K. Brayton and E Somenzi. Boolean Relations and the Incomplete Specification of Logic Networks. In VLSI'89, August 1989.

Google Scholar

[4]

R.E. Bryant. Graph Based Algorithms for Boolean Function Manipulation. IEEE Transactions on Computers, C-35(8):677-691, August 1986.

Digital Library

Google Scholar

[5]

K.-T. Cheng. On Removing Redundancy in Sequential Circuits. In 28th ACM/IEEE Design Automation Conference, pages 164-169, June 1991.

Digital Library

Google Scholar

[6]

H. Cho, G. D. Hachtel, and F. Somenzi. Redundancy Identification/Removal and Test Generation for Sequential Circuits Using Implicit State Enumeration. In IEEE Transactions on Computer Aided Design of integrated Circuits and Systems, pages 935-945, July 1993.

Google Scholar

[7]

O. Coudert, C. Berthet, and J. C. Medre. Verification of Sequential Machines Based on Symbolic Execution. In Proceedings of the Workshop on Automatic Verification Methods for Finite State Systems, Grenoble, France, 1989.

Digital Library

Google Scholar

[8]

M. Damiani. Nondeterministic Finite State Machines and Sequential Don't Cares. In The European Design and Test Conference, pages 192-198, February 1994.

Crossref

Google Scholar

[9]

S. Devadas. Optimizing Interacting Finite State Machines Using Sequential Don't Cares. In IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, pages 1473-1484, December 1991.

Google Scholar

[10]

X. Du, G. D. HachteI, B. Lin, and A. R. Newton. MUSE : A Multilevel Symbolic Encoding Algorithm for State Assignment. In IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, pages 28-38, January 1991.

Google Scholar

[11]

L. Entrena and K.-T. Chang. Sequential Logic Optimization By Redundancy Addition and Removal. In IEEE International Conference on Computer-Aided Design, pages 310-315, Novembes 1993.

Digital Library

Google Scholar

[12]

G. D. Hachtel, J. K. Rho, F. Sornenzi, and R. Jacoby. Exact and Heuristic Algorithms for the Minimization of Incompletely Specified State Machines. In The European Conference on Design Automation, 1991.

Digital Library

Google Scholar

[13]

J. E. Hopcroft. An nlog(n) Algorithm for Minimizing the States in a Finite Automaton. In The Theory of Machines and Computation, ed. Z. Kohavi, 1971.

Google Scholar

[14]

T. Kam, T. Villa, R. K. Brayton, and A. Sangiovanni-Vincentelli. A Fully Implicit Algorithm for Exact State Minimization. In 31st ACM/IEEE Design Automation Conference, pages 683-690, June 1994.

Digital Library

Google Scholar

[15]

T. Kam, T. Villa, R. K. Brayton, and A. Sangiovanni-Vincentelli. Implicit State Minimization of Non-Deterministic FSM's. In International Workshop on Logic Synthesis, May 1995.

Google Scholar

[16]

J. Kim and M. M. Newborn. The Simplification of Sequential Machines With Input Restrictions. In IEEE Transactions on Computers, pages 1440-1443, December 1972.

Google Scholar

[17]

B. Lin, G. de Jong, and Kolks T. Modeling and Optimization of Hierarchical Synchronous Circuits. In The European Desgin and Test Conference, pages 144- 149, Paris, March 1995.

Digital Library

Google Scholar

[18]

B. Lin and A. R. Newton. A Generalized Approach to the Constrained Cubical Imbedding Problem. In International Conference on Computer Design, October 1989.

Google Scholar

[19]

B. Lin and A. R Newton. Implicit Manipulation of Equivalence Classes Using Binary Decision Digrams. In International Workshop on Logic Synthesis, 1991.

Google Scholar

[20]

B. Lin, H. Touati, and A. R. Newton. Don't Care Minimization of Multi-Level Sequential Logic Networks. In IEEE International Conference on Computer-Aided Design, pages 414-417, November 1990.

Crossref

Google Scholar

[21]

S. Muroga, Y. Kambeyashi, H. C. Lai, andJ. N. Culliney. The Transduction Method - Design of Logic Networks Bases on Permissible Functions. In IEEE Transactions on Computers, October 1989.

Digital Library

Google Scholar

[22]

M. Rabin and D. Scott. Finite Automata and Their Decision Problems. In IBM Journal of Research and Development, pages 114-125,1959.

Digital Library

Google Scholar

[23]

J. K. Rho, G. D. Hachtel, and E Somenzi. Don't Care Sequences and the Optimization of Interacting Finite State Machines. In IEEE International Conference on Computer-Aided Design, pages 418-421, November 1991.

Google Scholar

[24]

H. Savoj and R. K. Brayton. Observability Relations and Observability Don't Cares. In IEEE International Conference on Computer-Aided Design, pages 518- 521, November 1991.

Digital Library

Google Scholar

[25]

H. Savoj, R. K. Brayton, and H. Touati. Extracting Local Don't Cares for Network Optimization. In IEEE International Conference on Computer-Aided Design, pages 514-517, November 1991.

Crossref

Google Scholar

[26]

H. Savoj, H.-Y. Wang, and R. K. Brayten. Improved Scripts in MIS-II for Logic Minimization of Combinational Circuits. In International Workshop on Logic Synthesis, May 1991.

Google Scholar

[27]

E. M. Sentovich, K. J. Singh, L. Lavagno, R. Moon, C. Murgai, A. Saldanha, H. Savoj, P. R. Stephan, R. K. Brayton, and A. Sangiovann/-Vincentelli. SIS: A System for Sequential Circuit Synthesis. Technical Report Memorandum UCB/ERL M92/41, University of California, Berkeley, May 1992.

Google Scholar

[28]

H. Touati, H. Savoj, B. Lin, R. K. Brayton, and A. Sangiovanni-Vincentelli. Implicit State Enumeration of Finite State Machines using BDD's. In IEEE International Conference on Computer-Aided Design, pages 130-133, November 1990.

Crossref

Google Scholar

[29]

T. Villa and A. Sangiovanni-Vincentelli. NOVA: State Assignmeant for Optimal Two-level Logic Implementations. In IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, pages 905-924, September 1990.

Google Scholar

[30]

H.-Y. Wang and R. K. Brayton. Input Don't Care Sequences in FSM Networks. In IEEE International Conference on Computer-Aided Design, pages 321-328, November 1993.

Digital Library

Google Scholar

[31]

H.-Y. Wang and R. K. Brayton. Permissible Observability Relations in FSM Networks. In 31st ACM/IEEE Design Automation Conference, pages 677-683, June 1994.

Digital Library

Google Scholar

[32]

H.-Y. Wang and R. K. Brayton. Multi-level Logic Optimization of FSM Networks. Technical Report UCB/ERL M95/66, University of California, Berkeley, August 1995.

Google Scholar

[33]

Y. Watanabe and R. K. Brayton. The Maximum Set of Permissible Behaviors for FSM Networks. In IEEE International Conference on Computer-Aided Design, pages 316-320, November 1993.

Digital Library

Google Scholar

[34]

Y. Watanabe and R. K. Brayton. State Minimization of Pseudo Non-Deterministic FSM's. In The European Design and Test Conference, pages 184-191, February 1994.

Crossref

Google Scholar

Cited By

View all

Harris IGielen G(2006)A coverage metric for the validation of interacting processesProceedings of the conference on Design, automation and test in Europe: Proceedings10.5555/1131481.1131763(1019-1024)Online publication date: 6-Mar-2006
https://dl.acm.org/doi/10.5555/1131481.1131763
Ferrandi FFummi FMacii EPoncino MSciuto DPennino TYoffa E(1996)Symbolic optimization of FSM networks based on sequential ATPG techniquesProceedings of the 33rd annual Design Automation Conference10.1145/240518.240607(467-470)Online publication date: 1-Jun-1996
https://dl.acm.org/doi/10.1145/240518.240607

Index Terms

Multi-level logic optimization of FSM networks
1. Hardware
  1. Electronic design automation
    1. Logic synthesis
      1. Circuit optimization
2. Theory of computation
  1. Formal languages and automata theory

Recommendations

Multi-level logic optimization of FSM networks
ICCAD '95: Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design

Abstract: Current approaches to compute and exploit the flexibility of a component in an FSM network are all at the symbolic level. Conventionally, exploitation of this flexibility relies on state minimizers for incompletely specified FSMs (ISFSMs) or ...
Fuzzy Logic-Based Sink Selection and Load Balancing in Multi-Sink Wireless Sensor Networks

Using multiple sink nodes in wireless sensor networks can greatly improve the lifetime and throughput of the network. One of the important issues in multi-sink wireless sensor networks is the congestion problem in sink nodes which reduces the ...
Fuzzy Logic-Based Clustering Algorithm for Multi-hop Wireless Sensor Networks

To prolong the life of wireless sensor networks(WSNs) and reduce energy consumption, a clustering protocol based on fuzzy logic for Multi-hop WSNs(FLCMN) is proposed. The algorithm considers the residual energy of nodes, the number of neighbor nodes and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICCAD '95: Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design

December 1995

748 pages

ISBN:0818672137

Chairman:
Richard Rudell
Synopsys, Inc., Mountain View, CA

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 December 1995

Check for updates

Qualifiers

Article

Conference

ICCAD '95

Sponsor:

SIGDA
IEEE-CS

ICCAD '95: International Conference on Computer Aided Design

November 5 - 9, 1995

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
204
Total Downloads

Downloads (Last 12 months)30
Downloads (Last 6 weeks)4

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Harris IGielen G(2006)A coverage metric for the validation of interacting processesProceedings of the conference on Design, automation and test in Europe: Proceedings10.5555/1131481.1131763(1019-1024)Online publication date: 6-Mar-2006
https://dl.acm.org/doi/10.5555/1131481.1131763
Ferrandi FFummi FMacii EPoncino MSciuto DPennino TYoffa E(1996)Symbolic optimization of FSM networks based on sequential ATPG techniquesProceedings of the 33rd annual Design Automation Conference10.1145/240518.240607(467-470)Online publication date: 1-Jun-1996
https://dl.acm.org/doi/10.1145/240518.240607

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Multi-level logic optimization of FSM networks

Fuzzy Logic-Based Sink Selection and Load Balancing in Multi-Sink Wireless Sensor Networks

Fuzzy Logic-Based Clustering Algorithm for Multi-hop Wireless Sensor Networks