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.

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.

Tri-state buses and pass transistor logic are used in many complex applications to achieve high performance and small area. Such circuits often contain logic requiring one-hot signals. In a scan-based design, one-hot values on these signals may not be maintained during the scan-in and scan-out operations. Also, the presence of faults, the existence of don't care conditions and the use of random patterns for testing the circuit in a scan or BIST environment may lead to non-one-hot values on these one hot signals, resulting in abnormal circuit behavior and possible circuit damage. In this paper, we present new techniques for synthesizing scan-based designs so that one-hot values are maintained on the one-hot signals during all modes of operation. One of our synthesis techniques often generates designs with no area overhead-the designs are smaller than those that do not ensure safe scan operation. In addition, we propose a scan path design that has no performance overhead during the normal mode of operation and ensures that only valid states appear on the bistables during test mode, thus guaranteeing safe scan operations.

This paper introduces new design and synthesis techniques that reduce the area and performance overhead of built-in self-test (BIST) architectures such as circular BIST and parallel BIST. Our goal is to arrange the system bistables into scan paths such that some of the BIST and scan logic is shared with the functional logic. Logic sharing is possible when scan dependence is introduced in the design. Other BIST design techniques attempt to avoid scan dependence because it can reduce the fault coverage of embedded, multiple input signature registers (MISRs). We show that introducing certain types of scan dependence in embedded MISRs can result in reduced overhead and improved fault coverage. We present our results for benchmark circuits that have been synthesized to take advantage of scan dependence in a circular BIST architecture.>

This paper describes a technique and program for automatically synthesizing a self-testable data path structure given a scheduled data flow description of a design. The resulting data path structure is combinationally self-testable when the registers are reconfigured as either pseudo-random pattern generators or parallel signature analyzers. The synthesis procedure consists of first mapping the data flow description onto a register conflict graph. The nodes of the graph are then colored using a node coloring algorithm that is guided by design implementation costs such as interconnection area and multiplexer size. Finally, the colored graph is mapped to hardware. A simple constraint imposed on the conflicl. graph guarantees combinational self-testability of the data path. In addition, new methods for mapping the data flow description to the conflict graph are incorporated to allow the procedure maximum flexibility in synthesizing arr efficient hardware implementation.