A high-level built-in self-test (BIST) synthesis is a process of transforming a behavioral description into a register-transfer level structural description while minimizing BIST overhead. Existing high-level BIST synthesis methods focus on one objective, minimizing either area overhead or test time. Hence, those methods do not render exploration of a large design space, which may result in a local optimum.

In this thesis, we present three methods, which aim to address the problem. The first method tries to find a register assignment for each k-test session in a heuristic manner, where k=1,2,…,N and N is the number of modules of the circuit. Therefore, it offers a range of designs with different figures of merit in area and test time. The second method is based on integer linear programming (ILP). The proposed ILP based method performs the three tasks, assignments of registers, interconnections, and BIST registers, concurrently to yield optimal or near-optimal designs. We describe a complete set of ILP formulations for the three tasks. The ILP based method achieves optimal solutions for most circuits in hardware overhead, but it takes long processing time. The third method, the region-wise heuristic method. It partitions a given data flow graph into smaller regions based on control steps and applies the ILP to each region successively to reduce the processing time.

To measure the performance of BIST accurately and to demonstrate the practicality of our BIST synthesis method, we implemented a DSP circuit; an 8x8 two-dimensional discrete cosine transform (DCT) processor. We implemented two versions of the algorithm, one with incorporation of our BIST method and the other without BIST, to verify the validity of our simplified cost model to estimate BIST area overhead. The two major parts of the circuit, data path and controller, were synthesized using our high-level BIST synthesis tool. All the circuits are implemented and laid out using an ASIC design flow developed at Virginia Tech.

Experimental results show that the three proposed high-level BIST synthesis methods perform better than or comparable to existing BIST synthesis systems. They indeed yield various designs that enable users to trade between area overhead and test time. The region-wise heuristic method reduces the processing time by several orders of magnitude, while the quality of the solution is slightly compromised compared with the ILP-based optimal method. The implementation of DCT circuits demonstrate that our method is applicable to industry size circuits, and the BIST area overhead measured at the layout is close to the estimated one.