Multi valued Logic Synthesis Robert K Brayton Sunil P Khatri University of California Berkeley CA 94720 fbrayton linusg ic eecs berkeley edu Abstract We survey some of the methods used for manipulating representing and optimizing multi valued logic with the view of both building a better understanding of the more specialized binary valued logic as well as motivating re search towards a true multi valued multi level optimization package 1 Introduction Logic design is normally thought of in terms of binary sig nals however for higher level design it is natural to think of variables with symbolic values For example it is easier to conceive of a traf c light processor with a signal light tak ing on three values red yellow and green rather than deal ing with light0 1 light1 0 to stand for the light being red The process of converting these multi valued variables to binary signals is called encoding In many cases the en coding is done initially mostly arbitrarily and then binary valued logic synthesis is applied to the resulting circuit An alternative is to rst manipulate and optimize the logic di rectly as multi valued logic Then the resulting form of the network can be used possibly intelligently to select a good encoding Once the encoding is done further optimizations not possible in the purely multi valued form can be applied to the resulting binary network The intelligent encoding should take into account this additional optimization which will depend on the nal binary codes selected However this alternative approach is not used often be cause cid 15 The encoding problem is hard for large circuits since it is dif cult to see how an encoding decision ultimately affects the logic that results after powerful logic opti mizations are applied Multi valued logic is a generalization One advantage in dealing with generalizations is that it can lead to increased insight into the specialized problem A generalization helps differentiate the special properties from the general ones Often a property that is known for the special case can be a general property in disguise or a specialization of a more general property When this is understood frequently there is a sense of oh is that what I was really doing Thus the attempt to generalize helps understand the special case better In this paper we survey several of the concepts algo rithms and optimizations that have found extensions from binary to multi valued logic We rst deal with two level logic where most of the concepts directly generalize Then we look at several methods for representing multi valued logic sum of products SOPs multi valued decision di agrams MDDs and multi level multi valued networks MV networks We look at algorithms for manipulating Boolean networks decomposition factorization using ker nels and extensions of don t cares SPFDs and see their generalizations to MV networks We discuss extensions to a popular RTL language Verilog to MV variables and use this to build a front end to VIS an MV logic optimization and veri cation package Finally the state assignment prob lem is revisited and we conclude the paper with a discussion of some open problems and work for the future 2 Notation cid 15 There is no good multi valued multi level logic op timization package for a multi valued logic network such as SIS for binary networks cid 15 Although many of the algorithms in logic synthesis have been generalized to multi valued logic a com plete suite of algorithms has not been developed De nition 1 A multi valued variable Xi can take on val ues from Pi fa 0 a 1 cid 1 cid 1 cid 1 a jPij cid 0 1g Since each symbolic value a i can be associated with a unique integer i we henceforth only consider multi valued variables with integer values for uniformity and Pi f0 1 cid 1 cid 1 cid 1 j Pi j cid 0 1g Authorized licensed use limited to INESC Downloaded on February 4 2009 at 10 42 from IEEE Xplore Restrictions apply X1 X2 F 1 0 0 2 0 1 1 1 0 1 1 1 0 2 0 2 2 1 Figure 1 A Multi valued Function of 2 vari ables De nition 2 A vertex is a point in the space P1 cid 2 P2 cid 2 cid 1 cid 1 cid 1 cid 2 Pn positional notation De nition 3 A multi valued function F is a function which maps vertices in P1 cid 2 P2 cid 2 cid 1 cid 1 cid 1 cid 2 Pn to PF formally F P1 cid 2 P2 cid 2 cid 1 cid 1 cid 1 cid 2 Pn 7 PF An example of a multi valued function is shown in Fig ure 1 Assume that P1 f0 1 2g P2 f0 1g and PF f0 1 2g If PF f0 1 cid 3 g F is a multi valued function with a binary valued output If a vertex minterm is mapped to the 1 value it is said to be in the on set of F mapped to 0 in the off set and to cid 3 in the don t care set The binary ideas of implicants prime implicants covers and prime covers can be extended to multi valued functions for functions F with binary valued outputs De nition 4 A multi valued literal X ci i of the form is a logic function i Xi g 1 cid 1 cid 1 cid 1 Xi g k where g X ci j 2 ci cid 18 Pi De nition 5 A cube c c1 cid 2 c2 cid 2 cid 1 cid 1 cid 1 cid 2 cn can be written as a product of MV literals in the form X c1 1 X c2 2 cid 1 cid 1 cid 1 X cn n Note that if ci Pi we can omit X Pi i from the expression of the cube since X Pi i 1 If variable Xi is binary valued the literal Xi can be written in the new notation as X f1g Similarly the literal Xi can be written as X f0g If the variable Xi takes on both its values also written as a this is written as X f0 1g i i The next four de nitions apply speci cally to binary val i ued functions of multi valued inputs De nition 6 An implicant is a cube c such that for all ver tices v 2 c F v 6 0 De nition 7 A prime implicant is an implicant c such that there is no implicant d such that d cid 27 c De nition 8 A cover of F is a set of implicants whose union contains every point in the onset of F and no points in the offset De nition 9 A prime cover of F is a cover each of whose elements is prime The multi valued function in Figure 1 can be written in the form of a sum of cubes for each of its values One such cover for F is Ff0g X f2g Ff1g X …