Article

Free access

A State-Machine Synthesizer—SMS

Author:

Douglas W. BrownAuthors Info & Claims

DAC '81: Proceedings of the 18th Design Automation Conference

Pages 301 - 305

Published: 29 June 1981 Publication History

PDF eReader

Abstract

Much of the work in implementing a state machine involves tedious calculations that require no creativity. This report describes the development of a digital-circuit synthesis program that helps reduce the tedium. SMS accepts a high-level description of a state machine and returns equations for implementation that assume a sum-of-products next-state and output functions and that also assume JK or D flip-flops for memory.

References

[1]

Christopher R. Clare, Designing Logic Systems Using State Machines, (McGraw-Hill Book Company, New York, 1973).

Google Scholar

[2]

D.L. Dietmeyer, "Connection arrays from equations," Journal of Design Automation and Fault-Tolerant Computing, vol. 3, pp. 109-125, (April 1979).

Google Scholar

[3]

D.L. Dietmeyer and M.H. Doshi, "Automated PLA synthesis of the combinational logic of a DDL description," Journal of Design Automation and Fault-Tolerant Computing, vol. 3, pp. 241-257, (Winter 1979).

Google Scholar

[4]

Per Brinch Hansen, The Architecture of Concurrent Programs, (Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1977), ch. 1.

Digital Library

Google Scholar

[5]

S.J. Hong, R.G. Cain, D.L. Ostapko, "MINI: A heuristic approach for logic minimization," IBM Journal of Research and Development, pp. 443-458, (September, 1974).

Google Scholar

[6]

A. Svoboda, "Fast multiple output logical circuit minimization." Svoboda died before he could publish this work. Douglas W. Brown, the author of this paper, has the preliminary version of Svoboda's final report on PRESTO to Tektronix, Inc. This preliminary version is based on: A. Svoboda, "The concept of term exclusiveness and its effect on the theory of boolean functions," Journal of the Association of Computing Machinery, vol. 22, no. 3, pp. 425-440, (July 1975) and on R.C. DeVries and A. Svoboda, "Multiple output minimization with mosaics of boolean functions," IEEE Transactions on Computers, vol. C-24, no. 8, pp. 777-785, (August 1975).

Digital Library

Google Scholar

[7]

A. Svoboda and Donnamaie E. White, Advanced Logical Circuit Design Techniques, (Garland Press, New York, 1979), ch. 4 and 5.

Google Scholar

Cited By

View all

de Pablo SMartínez FHerrero LCebrián JCáceres SLindh L(2010)Recent advances in ASM++ methodology for FPGA designProceedings of the 7th FPGAworld Conference10.1145/1975482.1975488(49-59)Online publication date: 6-Sep-2010
https://dl.acm.org/doi/10.1145/1975482.1975488
Sasao TButler J(2001)Worst and Best Irredundant Sum-of-Products ExpressionsIEEE Transactions on Computers10.1109/12.95450850:9(935-948)Online publication date: 1-Sep-2001
https://dl.acm.org/doi/10.1109/12.954508
Kamath AKarmarkar NRamakrishnan KResende M(1992)A continuous approach to inductive inferenceMathematical Programming: Series A and B10.5555/2794494.311271657:1-3(215-238)Online publication date: 1-May-1992
https://dl.acm.org/doi/10.5555/2794494.3112716
Show More Cited By

Index Terms

A State-Machine Synthesizer—SMS
1. Hardware
  1. Integrated circuits
    1. Logic circuits
      1. Combinational circuits

Recommendations

Novel state minimization and state assignment in finite state machine design for low-power portable devices

In this paper, we present a comprehensive method consisting of efficient state minimization and a comprehensive method of state assignment techniques to synthesize finite state machines (FSMs) to optimize power, area, and delay for ''next-state'' logic ...
Synthesis of Testable Finite State Machine Through Decomposition
ATS '05: Proceedings of the 14th Asian Test Symposium on Asian Test Symposium

This paper reports an efficient state encoding scheme for synthesis of large FSMs with enhanced BIST quality. A metric, referred to as degree-of-freedom (DOF) [5] in FSM states has been employed to quantify the BIST quality. Analysis of DOF enables ...
The design of an asynchronous VHDL synthesizer
DATE '98: Proceedings of the conference on Design, automation and test in Europe

This paper presents a straightforward approach for synthesizing a standard VHDL description of an asynchronous circuit from a behavioral VHDL description. The asynchronous circuit style is based on "micropipelines", a style currently used to develop ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '81: Proceedings of the 18th Design Automation Conference

June 1981

899 pages

Publisher

IEEE Press

Publication History

Published: 29 June 1981

Check for updates

Qualifiers

Article

Acceptance Rates

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

16
Total Citations
View Citations
204
Total Downloads

Downloads (Last 12 months)25
Downloads (Last 6 weeks)8

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

de Pablo SMartínez FHerrero LCebrián JCáceres SLindh L(2010)Recent advances in ASM++ methodology for FPGA designProceedings of the 7th FPGAworld Conference10.1145/1975482.1975488(49-59)Online publication date: 6-Sep-2010
https://dl.acm.org/doi/10.1145/1975482.1975488
Sasao TButler J(2001)Worst and Best Irredundant Sum-of-Products ExpressionsIEEE Transactions on Computers10.1109/12.95450850:9(935-948)Online publication date: 1-Sep-2001
https://dl.acm.org/doi/10.1109/12.954508
Kamath AKarmarkar NRamakrishnan KResende M(1992)A continuous approach to inductive inferenceMathematical Programming: Series A and B10.5555/2794494.311271657:1-3(215-238)Online publication date: 1-May-1992
https://dl.acm.org/doi/10.5555/2794494.3112716
Malik ABrayton RNewton ASangiovanni-Vincentelli ASmith R(1991)Reduced offsets for two-level multi-valued logic minimizationProceedings of the 27th ACM/IEEE Design Automation Conference10.1145/123186.123279(290-296)Online publication date: 3-Jan-1991
https://dl.acm.org/doi/10.1145/123186.123279
Wey CChang TShaklee DNewton A(1988)PLAYGROUNDProceedings of the 25th ACM/IEEE Design Automation Conference10.5555/285730.285798(421-426)Online publication date: 1-Jun-1988
https://dl.acm.org/doi/10.5555/285730.285798
Nguyen LPerkowdki MGoldstein N(1987)PALMINI—fast Boolean minimizer for personal computersProceedings of the 24th ACM/IEEE Design Automation Conference10.1145/37888.37985(615-621)Online publication date: 1-Oct-1987
https://dl.acm.org/doi/10.1145/37888.37985
Koseki YYamada TOfek HO'Neill L(1985)PLAYERProceedings of the 22nd ACM/IEEE Design Automation Conference10.5555/317825.317983(766-769)Online publication date: 1-Jun-1985
https://dl.acm.org/doi/10.5555/317825.317983
van Laarhoven PAarts EDavio MOfek HO'Neill L(1985)PHIPLA—a new algorithm for logic minimizationProceedings of the 22nd ACM/IEEE Design Automation Conference10.5555/317825.317973(739-743)Online publication date: 1-Jun-1985
https://dl.acm.org/doi/10.5555/317825.317973
Dagenais MAgarwal VRumin NOfek HO'Neill L(1985)The McBOOLE logic minimizerProceedings of the 22nd ACM/IEEE Design Automation Conference10.5555/317825.317961(667-673)Online publication date: 1-Jun-1985
https://dl.acm.org/doi/10.5555/317825.317961
Rowen CHennessey JOfek HO'Neill L(1985)SWAMIProceedings of the 22nd ACM/IEEE Design Automation Conference10.5555/317825.317853(169-175)Online publication date: 1-Jun-1985
https://dl.acm.org/doi/10.5555/317825.317853
Show More Cited By

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

Novel state minimization and state assignment in finite state machine design for low-power portable devices

Synthesis of Testable Finite State Machine Through Decomposition

The design of an asynchronous VHDL synthesizer