Cited By
View all- Kraus OPadeffke M(2003)XBM2PLAProceedings of the conference on Design, Automation and Test in Europe - Volume 110.5555/789083.1022868Online publication date: 3-Mar-2003
A new paradigm for dichotomy-based constrained encoding
Author: 
O. CoudertAuthors Info & Claims
Abstract
One essential step in sequential logic synthesis consists of finding a state encoding that meets some requirements, such as optimal implementation, or correctness in the case of asynchronous FSMs. Dichotomy-based constrained encoding is more general than other constrained encoding frameworks, but it is also more difficult to solve. This paper introduces a new formalization of this problem, which leads to original exact and heuristic algorithms. Experimental results show that the resulting exact solver outperforms the previous approaches.
References
[1]
D. Brelaz, "New Methods to Color Vertices of a Graph", Comm. of the ACM, 22-4, pp. 251-256, 1979.
[2]
O. Coudert, C.-J. Richard Shi, "Exact Dichotomybased Constrained Encoding", ICCD'96, Oct. 1996.
[3]
S. Devadas, A. R. Newton, "Exact Algorithms for Output Encoding, State Assignment, and Four-level Boolean Minimization", IEEE Trans. CAD, 1-10, pp. 13-27, Jan. 1991.
[4]
S. Devadas, A. R. Wang, A. R. Newton, A. L. Sangiovanni-Vincentelli, "Boolean Decomposition of Programmable Logic Arrays", CICC'88, 1988.
[5]
R. M. Fuhrer, B. Lin, S. M. Nowick, "Symbolic Hazardfree Minimization and Encoding of Asynchronous Finite State Machines", ICCAD'95, Nov. 1995
[6]
L. Lavagno, C. W. Moon, R. K. Brayton, A. L. Sangiovanni-Vincentelli, "An Efficient Heuristic Procedure for Solving the State Assignment Problem for Event-based Specification", IEEE Trans. CAD, 14-1, pp. 45-60, Jan. 1995.
[7]
G. D. Micheli, R. K. Brayton, A. L. Sangiovanni- Vincentelli, "Optimal State Assignment for Finite State Machines", IEEE Trans. CAD, 4-3, July 1985.
[8]
G. D. Micheli, "Symbolic Design of Combinational and Sequential Logic Circuits Implemented by Two-level Logic Macros", IEEE Trans. CAD, 5-1, Oct. 1986.
[9]
G. D. Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill, 1994.
[10]
R. L. Rudell, A. L. Sangiovanni-Vincentelli, "Multiple- Valued Minimization for PLA Optimization", IEEE Trans. CAD, 6-5, pp. 727-750, Sept. 1987.
[11]
A. Saldanha, T. Villa, R. K. Brayton, A. L. Sangiovanni-Vincentelli, "Satisfaction of Input and Output Encoding Constraints", IEEE Trans. CAD, 13- 5, pp. 589-602, May 1994.
[12]
J. H. Tracey, "Internal State Assignment for Asynchronous Sequential Machines" IEEE Trans. Elec. Comp., pp. 551-560, Aug. 1966.
[13]
S. H. Unger, Asynchronous Sequential Switching Circuits, John Wiley & Sons, Inc., 1969.
[14]
T. Villa, A. L. Sangiovanni-Vincentelli, "NOVA: State Assignment of Finite State Machines for Optimal Twolevel Logic Implementation", IEEE Trans. CAD, 9-9, pp. 905-924, Sept. 1990.
[15]
S. Yang, M. J. Ciesielski, "Optimum and Suboptimum Algorithms for Input Encoding and its Relationship to Logic Minimization", IEEE Trans. CAD, 10-1, pp. 4- 12, Jan. 1991.
Index Terms
- A new paradigm for dichotomy-based constrained encoding
Recommendations
Exact Dichotomy-based Constrained Encodi
ICCD '96: Proceedings of the 1996 International Conference on Computer Design, VLSI in Computers and ProcessorsConstrained encoding has several applications in the synthesis of finite state machines (FSMs). E.g., it can be used to generate asynchronous FSM state assignment that guarantees a critical hazard-free implementation, or to generate synchronous FSM ...
A new line of attack on the dichotomy conjecture
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computingThe well known dichotomy conjecture of Feder and Vardi states that for every finite family Γ of constraints CSP(Γ) is either polynomially solvable or NP-hard. Bulatov and Jeavons reformulated this conjecture in terms of the properties of the algebra Pol(...
A Dichotomy for Real Weighted Holant Problems
Holant is a framework of counting characterized by local constraints. It is closely related to other well-studied frameworks such as the counting constraint satisfaction problem (#CSP) and graph homomorphism. An effective dichotomy for such frameworks ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright © 1998 IEEE. All Rights Reserved.
Sponsors
Publisher
IEEE Computer Society
United States
Publication History
Published: 23 February 1998
Check for updates
Author Tags
Qualifiers
- Article
Conference
DATE98
Sponsor:
DATE98: Design, Automation & Test in Europe
February 23 - 26, 1998
Le Palais des Congrés de Paris, France
Acceptance Rates
Overall Acceptance Rate 518 of 1,794 submissions, 29%
Upcoming Conference
DATE '25
- Sponsor:
- sigda
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 111Total Downloads
- Downloads (Last 12 months)15
- Downloads (Last 6 weeks)7
Reflects downloads up to 09 Mar 2025
Other Metrics
Citations
Cited By
View all- Kraus OPadeffke M(2003)XBM2PLAProceedings of the conference on Design, Automation and Test in Europe - Volume 110.5555/789083.1022868Online publication date: 3-Mar-2003
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in