Symbolic Minimization of Multilevel Logic and the Input Encoding Problem

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.