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

Volume

18

Issue

6

fYear

1999

fDate

6/1/1999 12:00:00 AM

Firstpage

761

Lastpage

768

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;

fLanguage

English

Journal_Title

Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.766726

Filename

766726