BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CSL-TR-98-761
       ENTRY:: August 12, 1998
ORGANIZATION:: Stanford University, Computer Systems Laboratory
       TITLE:: An Output Encoding Problem and A Solution Technique
        TYPE:: Technical Report
      AUTHOR:: Mitra, Subhasish
      AUTHOR:: LaNae, J. Avra
      AUTHOR:: McCluskey, Edward J.
        DATE:: November 1997
       PAGES:: 30
    ABSTRACT:: 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, 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 output 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.  This algorithm 
can also be used as a pre-processing step during FSM state encoding.
In this paper, we develop an exact algorithm to solve the above
problem, prove its correctness, analyze the worst case time complexity
of the algorithm and present experimental data to validate the claim that our
encoding strategy helps to reduce the area of a synthesized circuit.  In
addition, we have investigated the possibility of using elementary gates to
facilitate further merging of the output functions generated by the 
encoding bits with the output functions generated by the elementary gates.
       NOTES:: [Adminitrivia V1/Prg/19980121]
         END:: STAN//CSL-TR-98-761