A computer-aided testing framework for field programmable gate arrays: From verification to configuration

Field programmable gate arrays (FPGAs) are a revolutionary new type of user programmable integrated circuits that provide fast, inexpensive access to customized VLSI. In an FPGA architecture, a Configurable Logic Block (CLB) can be configured to implement different functions and the Programmable Interconnects (PIs) are used to achieve connectivity. FPGA programmability comes in two types: reprogrammable and one-time programmable. This dissertation concentrates on the testing issues in the process of design, including verification, testing and testability of FPGAs, and reconfiguration after testing.; This dissertation first presents a new approach to design verification of digital circuits implemented with FPGAs. The approach utilizes logic simulation and an automatic test pattern generator to establish the equivalence of two designs. Nodes with the same signature make up a so-called equivalent class, which is updated using the simulation results as well as the outcome of the verification process. For the testing of logic resources, this dissertation discusses the traditional logic testing and introduce new approaches to C-testability. It shows the results of fault detection under two multiple fault models: the multiple fault single module (MFSM) and the single fault multiple module (SFMM) models. A new structural approach to full diagnosis (detection and location with no aliasing and confounding) of shorts in interconnects is proposed in the testing of routing resources. The proposed approach utilizes graph coloring techniques and appropriate codes to generate a test set based on the adjacency and continuous assumption. This dissertation also shows that diagnosability can be solved in polynomial time complexity and adjusted within the depth of the fault model. In the reconfiguration of FPGAs, this dissertation proposes a new approach to redesign after implementation. The algorithm is suitable for one-time programmable FPGAs, which are more restrictive.; All the algorithms described in this dissertation are implemented, and experimental results for benchmark circuits or random logic demonstrate the effectiveness of the proposed approaches.