On the relationship between input encoding and logic minimization

A theoretical formulation of the input encoding problem is presented, based on the concept of compatibility of dichotomies. Three possible techniques to solve the problem are discussed, based on: techniques borrowed from classical logic minimization (generation of prime dichotomies and solving the covering problem); graph coloring applied to the graph of incompatibility of dichotomies; and extraction of essential prime dichotomies followed by graph coloring. Extracting essential prime dichotomies serves the same purpose as the extraction of essential prime implicants in logic minimization, in the sense that it reduces the size of the covering/graph coloring problem. The conditions of optimality of the encoding problem are discussed. The method can be applied to the input encoding of combinational logic and the state assignment of finite state machines in both two-level and multilevel implementations