Encoding multi-valued functions for symmetry
Abstract
In high-level designs, variables are often naturally represented in a symbolic multi-valued form. Binary encoding is an essential step in realizing these designs in Boolean circuits. This paper poses the encoding problem with the objective of maximizing the degree of symmetry, which has many useful applications in logic optimization, circuit rewiring, functional decomposition, etc. In fact, it is guaranteed that there exists a full symmetry encoding with respect to every input multi-valued variable for all multi-valued functions. We propose effective computation for finding such encoding by solving a system of subset-sum constraints. Experiments show unique benefits of symmetry encoding.
References
[1]
P. Ashar, S. Devadas, and R. Newton. Sequential Logic Synthesis, Kluwer Academic Publishers, 1992.
[2]
Berkeley Logic Synthesis and Verification Group. ABC: A system for sequential synthesis and verification. http://www.eecs.berkeley.edu/~alanmi/abc/
[3]
R. K. Brayton and S. P. Khatri. Multi-Valued Logic Synthesis. Proc. Int'l Conf. on VLSI Design, pp. 196--205, 1999.
[4]
R. K. Brayton. C. McMullen, G. D. Hachtel and A. Sangiovanni-Vincentelli. Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers, 1984.
[5]
C.-W Chang, C.-K, Cheng, P. Suaris, M. Marek-Sadowska. Fast Post-placement Rewiring Using Easily Detectable Functional Symmetries. In Proc. Design Automation Conference, pp. 286--289, 2000.
[6]
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, MIT Press, 2001.
[7]
K.-H. Chang, I. L. Markov, V. Bertacco. Post-placement Rewiring and Rebuffering by Exhaustive Search for Functional Symmetries. In Proc. Int'l Conf. on Computer-Aided Design, pp. 56--63, 2005.
[8]
G. De Micheli, R. K. Brayton, and A. Sangiovanni-Vincentelli. Optimal State Assignment for Finite State Machines. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 4(3): 269--285, 1985.
[9]
G. De Micheli. Synthesis and Optimization of Digital Circuits, McGraw-Hill, 1994.
[10]
M. Gao, J.-H. Jiang, Y. Jiang, Y. Li, S. Sinha, and R. K. Brayton. MVSIS. In Proc. Int'l Workshop on Logic Synthesis, 2001.
[11]
Y.-J. Jiang and R. K. Brayton. Don't Cares and Multi-Valued Logic Network Minimization. In Proc. Int'l Conf. on Computer-Aided Design, pp. 520--525, 2000.
[12]
J.-H. Jiang, Y.-J. Jiang, and R. K. Brayton. An Implicit Method for Multi-Valued Network Encoding. In Proc. Int'l Workshop on Logic Synthesis, 2001.
[13]
J.-H. Jiang, A. Mishchenko, and R. K. Brayton. Reducing Multi-Valued Algebraic Operations to Binary. In Proc. Design, Automation, and Test in Europe, pp. 10752--10757, 2003.
[14]
M.-Y. Li. Pseudo-Boolean Constraint Formulation of Symmetry Boolean Encoding for Multi-Valued Functions. Master Thesis, National Taiwan Univeristy, 2011.
[15]
L. Lavagno, S. Malik, R. K. Brayton, and A. L. Sangiovanni-Vincentelli. MIS-MV: Optimization of Multi-level Logic with Multiple-valued Inputs. In Proc. Int'l Conf. on Computer-Aided Design, pp. 560--563, 1990.
[16]
R. Murgai, R. K. Brayton, and A. Sangiovanni-Vincentelli. Optimum Functional Decomposition Using Encoding. Proc. Design Automation Conference, pp. 408--414, 1994.
[17]
A. Mishchenko. Fast Computation of Symmetries in Boolean Functions. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 22(11):1588--1593, Nov. 2003.
[18]
C. Scholl, D. Moller, P. Molitor, and R. Drechsler. BDD Minimization Using Symmetries. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 18(2): 81--100, Feb. 1999.
[19]
T. Villa and A. L. Sangiovanni-Vincentelli. NOVA: State Assignment of Finite State Machines for Optimal Two-Level Logic Implementation. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 9(9): 905--924, Sep. 1990.
[20]
K.-H. Wang, C.-M. Chan, and J.-C. Liu. Simulation and SAT-based Boolean Matching for Large Boolean Networks. In Proc. Design Automation Conference, pp. 396--401, 2009.
Index Terms
- Encoding multi-valued functions for symmetry
Recommendations
Multi-Input Variable-Threshold Circuits for Multi-Valued Logic Functions
ISMVL '00: Proceedings of the 30th IEEE International Symposium on Multiple-Valued LogicIn this paper, two-types of Multi-Input Variable-Threshold (M-I V-T) circuits and their applications to Multi-Valued Logic (MVL) are proposed. M-I V-T circuits are extensions of binary CMOS NAND and NOR gates to multi-valued logic. First, definitions of ...
Basic circuits for multi-valued sequential logic
Multi-valued logic circuits were presented as an alternative to well known binary logic. It has the potential of reducing the number of active elements and interconnection lines. More data may be transferred trough a single wire using logic signals ...
Realization of NMAX and NMIN Functions with Multi-Valued Voltage Comparators
ISMVL '01: Proceedings of the 31st IEEE International Symposium on Multiple-Valued LogicIn this paper, realization of three fundamental functions, NOT, negated MAX and negated MIN functions, in the voltage-mode quaternary logic is presented. First, the high-performance NOT circuits with the down literal circuits are composed. The proposed ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
Publisher
IEEE Press
Publication History
Published: 18 November 2013
Check for updates
Qualifiers
- Research-article
Conference
ICCAD'13
Sponsor:
ICCAD'13: The International Conference on Computer-Aided Design
November 18 - 21, 2013
California, San Jose
Acceptance Rates
ICCAD '13 Paper Acceptance Rate 92 of 354 submissions, 26%;
Overall Acceptance Rate 457 of 1,762 submissions, 26%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 54Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)1
Reflects downloads up to 20 Dec 2024
Other Metrics
Citations
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