An output encoding problem and a solution technique

We present a new output encoding problem as follows: Given a specification table, such as a truth table or a finite state machine state table, where some of the outputs are specified in terms of 1s, 0s and don´t cares, and others are specified symbolically, and assuming that the minimum number of bits are used to encode the symbolic outputs ([log/sub 2/] bits for n symbolic outputs), determine a binary code for each symbol of the symbolically specified output column such that the total number of output functions to be implemented after encoding the symbolic outputs and compacting the columns is minimum. There are several applications of this output encoding problem, one of which is to reduce the area overhead while implementing scan or pseudo-random BIST in a circuit with one-hot signals. We develop an exact algorithm to solve the above problem and present experimental data to validate the claim that our encoding strategy helps to reduce the area of a synthesized circuit.