Title :
An output encoding problem and a solution technique
Author :
Mitra, Subhasish ; Avra, LaNae J. ; McCluskey, Edward J.
Author_Institution :
Dept. of Electr. Eng., Stanford Univ., CA, USA
fDate :
6/1/1999 12:00:00 AM
Abstract :
We present a new output-encoding problem as follows. We are given a specification table, such as a truth table or a finite state machine (FSM) state table, where some of the outputs are specified in terms of ones, zeroes, and don´t cares, and others are specified symbolically. The number of bits for encoding the output symbols may also be specified. We have to 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. In this paper, we develop an exact algorithm to solve the above problem, 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 simple logical combinations of the already specified output columns to facilitate further reduction in the number of output functions
Keywords :
built-in self test; circuit CAD; computational complexity; encoding; finite state machines; logic CAD; BIST; FSM state table; encoding strategy; exact algorithm; finite state machine; output columns compaction; output encoding problem; output functions; solution technique; specification table; symbolic output column; synthesized circuit area reduction; truth table; worst case time complexity; Algorithm design and analysis; Automata; Binary codes; Built-in self-test; Circuit synthesis; Compaction; Digital systems; Encoding; Network synthesis; Signal synthesis;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
