Article

Free access

State assignment using a new embedding method based on an intersecting cube theory

Authors:

F. PoirotAuthors Info & Claims

DAC '89: Proceedings of the 26th ACM/IEEE Design Automation Conference

Pages 321 - 326

https://doi.org/10.1145/74382.74436

Published: 01 June 1989 Publication History

Abstract

The controller state assignment methodology proposed here features two improvements over existing methods. First, a larger set of predictive minimizations in the control flowgraph is performed. Secondly, the embedding phase uses a new theory of intersecting cubes in the Boolean lattice. Practical results using the VLSI Technology Logic-Synthesizer on both PLA and multi-level logic demonstrate the effectiveness of the approach.

References

[1]

D.B. Armstrong : ~A ProgrammeO Algontltm tor Assigning Internal Codes to Sequential Machines", IEEE Trans. on Elec. Comp., pp. 466-472, August 1962

[2]

A.J. Coppola : "An Implementation of a State Assignment Heuristic", 23rd DAC, pp. 643-649, July 1986

Digital Library

[3]

S. Devadas et ad. : "MUSTANG : State Assignment of Finite State Machines for Optimal Multi-level Logic Implementations", ICCAD 87, pp. 16-19

[4]

G. de Micheli : "Computer-Aided Synthesis of PLA-based Finite State Machines", ICCAD 83, pp. 154-156

[5]

G. de Micheli, A. Sangiovani-Vincentelli, R.K. Brayton "Optimal State Assignment of Finite State Machines", IEEE Trans. on CAD, July 1985, pp. 269-285

Digital Library

[6]

K. Keutzer et al. : "A Kernel-Finding State Assignment Algorithm for Multi-Level Log, 25th DAC, pp. 433-438, June 1988

Digital Library

[7]

J. Hartmanis, R.E. Stearns : "Algebraic Structure, Theory of Sequential Machines", Prentice Hall, 1966

Digital Library

[8]

C.N. Liu : "A State Variable Assignment Method for Asynchronous Sequential Switching Circuits", ACM, April 63

Digital Library

[9]

W. Rosenstiel et al. : "Datapath and Control Synthesis in the CADDY System", international Workshop on logic and architecture synthesis for silicon compilers, Grenoble, France, May 88

[10]

G. Saucier : "Encoding of Asynchronous Sequential Networks", IEEE Trans. on E.C., vol 16, pp. 365- 369

[11]

G. Saucier : "State Assignment of Asynchronous Sequential Machines using Graph Techniques", IEEE trans, on Comp, March 1972

[12]

G. Saucier : "Next State Equations of Asynchronous Sequential Machines", IEEE trans on Comp., November 1972

[13]

G. Saucier et a_l. : "ASYL : A Rule-Based System for Controller Synthesis", IEEE Trans on CAll), November 1987

[14]

S.FI. Unger : "A Row Assignment for Delay-Free Realizations of Flow Tables Without Essential Hazards", IEEE Trans. on E.C. Vol 17, pp. 146-151

Digital Library

[15]

Portable 1.5~t CMOS Standard Ceil Library, V1.1, VLSI Technology Inc., 1988

Cited By

Semeria LDe Micheli G(2006)Resolution, optimization, and encoding of pointer variables for the behavioral synthesis from CIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.90844220:2(213-233)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.908442
Goldberg EVilla TBrayton RSangiovanni-Vincentelli A(2006)Theory and algorithms for face hypercube embeddingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.70382917:6(472-488)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.703829
Villa TSaldanha ABrayton RSangiovanni-Vincentelli A(2006)Symbolic two-level minimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.64403116:7(692-708)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.644031
Show More Cited By

Index Terms

State assignment using a new embedding method based on an intersecting cube theory

Recommendations

A State Assignment Approach to Asynchronous CMOS Circuit Design

Present a new algorithm for state assignment in asynchronous circuits so that for each circuit state transition, only one (secondary) state variable switches. No intermediate unstable states are used. The resultant circuits operate at optimum speed in ...
A Universal STT State Assignment Method for Pulse Input Asynchronous Sequential Circuits

Methods to realize race-free asynchronous sequential circuits by using appropriate single transition time (STT) state assignments have been described in the literature. This paper deals with that restricted class of asynchronous circuits (called pulse-...
Optimum State Assignment for the D Flip-Flop

This correspondence is a modification of the basic SHR-optimal¹ state assignment procedure for the D flip-flop. Under the minimum sum-of-products (MSOP) constraint, a sequential machine with n D flip-flops has 2ⁿ times as many distinct state assignments ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '89: Proceedings of the 26th ACM/IEEE Design Automation Conference

June 1989

839 pages

ISBN:0897913108

DOI:10.1145/74382

Chairman:
Donald E. Thomas
Carnegie Mellon Univ., Pittsburgh, PA

Copyright © 1989 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

IEEE-CS\TCDA: TC Design Automation
SIGDA: ACM Special Interest Group on Design Automation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC89

Sponsor:

IEEE-CS\TCDA
SIGDA

DAC89: The 26th ACM/IEEE-CS Design Automation Conference

June 25 - 28, 1989

Nevada, Las Vegas, USA

Acceptance Rates

DAC '89 Paper Acceptance Rate 156 of 465 submissions, 34%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
246
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)9

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Semeria LDe Micheli G(2006)Resolution, optimization, and encoding of pointer variables for the behavioral synthesis from CIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.90844220:2(213-233)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.908442
Goldberg EVilla TBrayton RSangiovanni-Vincentelli A(2006)Theory and algorithms for face hypercube embeddingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.70382917:6(472-488)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.703829
Villa TSaldanha ABrayton RSangiovanni-Vincentelli A(2006)Symbolic two-level minimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.64403116:7(692-708)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.644031
Papachristou CPandya A(2006)A design scheme for PLA-based control tables with reduced area and time-delay costIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.551789:5(453-472)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.55178
Saldanha AVilla TBrayton RSangiovanni-Vincentelli A(2006)Satisfaction of input and output encoding constraintsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.27763213:5(589-602)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.277632
Shi CBrzozswski J(2006)An efficient algorithm for constrained encoding and its applicationsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.25114512:12(1813-1826)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.251145
Mueller-Wipperfuerth TScharinger JPichler F(2005)FSM shift register realization for improved testabilityComputer Aided Systems Theory — EUROCAST '9310.1007/3-540-57601-0_55(254-267)Online publication date: 31-May-2005
https://doi.org/10.1007/3-540-57601-0_55
Goldberg EVilla TBrayton RSangiovanni-Vincentelli AOtten RYasuura H(1997)A fast and robust exact algorithm for face embeddingProceedings of the 1997 IEEE/ACM international conference on Computer-aided design10.5555/266388.266495(296-303)Online publication date: 13-Nov-1997
https://dl.acm.org/doi/10.5555/266388.266495
Goldberg Villa Brayton Sangiovanni-Vincentelli (1997)A fast and robust exact algorithm for face embeddingProceedings of IEEE International Conference on Computer Aided Design (ICCAD) ICCAD-9710.1109/ICCAD.1997.643534(296-303)Online publication date: 1997
https://doi.org/10.1109/ICCAD.1997.643534
Rochet RLeveugle RSaucier G(1995)Efficiency comparison of signature monitoring schemes for FSMsProceedings of ASP-DAC'95/CHDL'95/VLSI'95 with EDA Technofair10.1109/ASPDAC.1995.486391(705-710)Online publication date: 1995
https://doi.org/10.1109/ASPDAC.1995.486391
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten