Symbolic Minimization of Multilevel Logic and the Input Encoding Problem

Sharad Malik, Luciano Lavagno, Robert K. Brayton, Alberto Sangiovanni-Vincentelli

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


This paper presents techniques for the optimization of multilevel logic with multiple-valued input variables. The motivation for this is to tackle the input encoding problem in logic synthesis, where binary codes need to be found for the different values that a symbolic input variable can take. Multilevel multiple-valued optimization is used to generate constraints that are then used to determine the codes. Output encoding is also an important problem. However, presently, we do not have a solution to this. State assignment involves the encoding of inputs and outputs subject to constraints that impose the same encoding for the state input and output variables. However, in cases where the output logic dominates the next state logic, state assignment can be approximated as an input encoding problem by ignoring the next state field. Common factor extraction is an important step in multilevel optimization, and thus far it has not been clear how this could be done with multiple-valued variables. This paper presents a novel technique for extracting common factors with multiple-valued variables. It is then shown how the other multilevel optimization techniques are easily extended with multiple-valued variables. These ideas have been implemented as algorithms in the program MIS-MV. The practical issues involved in the implementation of these ideas are discussed here, and results of using MIS-MV for input encoding on benchmark examples presented.

Original languageEnglish (US)
Pages (from-to)825-843
Number of pages19
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number7
StatePublished - Jul 1992

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'Symbolic Minimization of Multilevel Logic and the Input Encoding Problem'. Together they form a unique fingerprint.

Cite this