Presents an approach for fault detection in programmable wiring networks (PWNs). A comprehensive fault model which includes faults in the nets (open, stuck-at and shorts) as well as in the switches (stuck-off, stuck-on and programming faults) is assumed at both the physical and behavioral levels. In a PWN, the most important issue is to find the minimal number of configurations (or programming phases) as the dominant figure of merit of testing. Through the construction of different graphs, it is shown that this process corresponds to finding the node-disjoint path-sets such that each switch is turned on/off at least once and adjacencies in the nets for possible bridge faults (shorts) are verified. To account for 100% fault coverage of bridge faults, a post-processing algorithm may be required.

An approach is proposed to test FPGA logic blocks, including part of the configuration memories used to control them. The proposed AND tree and OR tree-based testing structure is simple and the conditions for constant testability can easily be satisfied. Test generation for only a single logic block is sufficient. We do not assume any particular fault model. Any number of faulty blocks in the chip can be detected. Members of the Xilinx XC3000, XC4000, and XC5200 families were studied. The proposed AND/OR approach was found to reduce the number of FPGA reprogrammings needed for testing by up to a factor of seven versus direct methods of multiple faulty block detection.

This paper presents a method to diagnose faults in FPGA interconnection resources. A single fault model is given. Under the given model, a diagnosing method is proposed. At most five programming steps in the proposed method is required if adaptive testing scheme is used. For non-adaptive test, eight programming steps is required to diagnose all the possible faults under the given single fault model. The accuracy of the fault diagnosing is one segment for a segment stuck-at or stuck-open fault, a segment pair for a bridge fault, a switch for switch stuck-on or stuck-off fault.

In this paper, a novel architecture for built-in self test (BIST) and different designs for both the control and data test pattern generators (CTPG and DTPG) are proposed for interconnect testing using the IEEE standard 1149.1. A general and complete procedure to implement this architecture is also presented. For the DTPG design, the complementary counting sequence (as an example of a maximal independent test set) is used for fault detection. One of the main features of this design is its independence with respect to the type of cell in the chain. A novel design is proposed for the CTPG to avoid damage to the circuit as well as to guarantee 100% fault coverage with low hardware overhead and time complexity.

This paper presents a procedure to diagnose single faults in SRAM based FPGAs. The procedure is nonadaptive and requires six programming steps to give the exact position and type of any single fault in a FPGA. It is proved that the number of programming steps required for the procedure is minimal for a non-adaptive procedure with the given interconnect model.

This paper presents a novel fault tolerant approach for SRAM-based FPGAs. The proposed approach includes a fault tolerant architecture and its related routing procedure. In the approach, both the overheads for CLBs and interconnects are considered. The fault tolerant routing procedure under this novel approach is simple and less time-consuming. We provide the simulation results and show that the proposed approach has lower overhead than previous methods found in technical literature.

We present a novel approach for detecting faults in tristate system environments-e.g., in multiple board systems. These environments are made of an interconnect and drivers/receivers with tristate features. We present a comprehensive fault model that includes faults in terminals (drivers/receivers) and nets. Under this fault model, physical faults (stuck-at and short), as well as functional faults (dominance, permanently enabled or permanently disabled driver modes), are taken into account. We show that, for a single net with L drivers, 2L tests are necessary and sufficient for fault detection. This is independent of the number of receivers. We extend this result to a system environment with N nets and where K is the maximal number of drivers for a net. Under the proposed fault model, any number of faults of any type can be detected in a system environment using any types that can be detected in a system environment using max (2K, P) tests, where P is the minimal integer that satisfies C/sub /2//sup P//spl ges/N. If only the traditional (wired-AND or wired-OR) model is assumed, then the test set required for fault detection can be further reduced. We provide simulation results and show that the proposed approach outperforms previous methods found in the technical literature.

This paper presents a five-step programming method to diagnose faults in FPGA interconnection resources. A single and a multiple fault model are given. The accuracy of fault location is a single segment for a segment stuck-at fault or a segment open fault, a segment pair or terminal pair for bridge fault or switch stuck-off fault under the single fault assumption. Similar accuracy can be achieved under the multiple fault assumption.

We present a new technique for testing field programmable gate arrays (FPGA's) based on look-up tables (LUT's). We consider a generalized structure for the basic FPGA logic element (cell); it includes devices such as LUT's, sequential elements (flip-flops), multiplexers and control circuitry. We use a hybrid fault model for these devices. The model is based on a physical as well as a behavioral characterization. This permits detection of all single faults (either stuck-at or functional) and some multiple faults using repeated FPGA reprogramming. We show that different arrangements of disjoint one-dimensional (l-D) cell arrays with cascaded horizontal connections and common vertical input lines provide a good logic testing regimen. The testing time is independent of the number of cells in the array (C-testability), We define new conditions for C-testability of programmable/reconfigurable arrays. These conditions do not suffer from limited I/O pins. Cell configuration affects the controllability/observability of the iterative array. We apply the approach to various Xilinx FPGA families and compare it to prior work.

This paper presents a novel approach for testing and diagnosing configurable field programmable gate arrays (FPGAs). The proposed approach is row-based and uses a two-session procedure. The approach arranges some logic blocks to be programmed as XOR-tree (or chain, or cascade) in the first session. The XOR-tree is effectively used as test vehicle for observability. The roles of the CLBs are inverted in the second session. It is shown that the proposed testing arrangement requires a number of tests independent of the number of CLBs in the FPGA (i.e. C-testability is accomplished). Routing is kept local, and compatibility for a CAD implementation is also accomplished.

No abstract available.

This paper considers the diagnosis of field programmable interconnect systems (FPIS) in which programmable grids made of switches are included. For this type of interconnects, the number of times the grid must be programmed and the programming sequence of the switches an two of the most important figures of merit for full diagnosis (defection and location with no aliasing and confounding). A hierarchical approach to diagnosis is proposed and fully characterized. The application of this technique to commercially available FPIS such as FPGAs, is discussed. It is shown that the proposed diagnostic technique can be applied to the general purpose interconnect of the FPGAs in the 3000 family by Xilinx.

This paper presents a new general technique for testing field programmable gate arrays (FPGAs) by fully exploiting their programmable and configurable characteristics. A hybrid fault model is introduced based on a physical and behavioral characterization; this permits the detection of a single fault, as either a stuck-at or a functional fault. A general approach which regards testing as can application for the reconfigurable FPGA, is then proposed. It is shown that different arrangements of disjoint one-dimensional arrays with unilateral horizontal connections and common vertical input lines provide a very good solution. A further feature that is considered for array testing, is the relation between the configuration of the logic blocks and the number of I/O pins in the chip. As an example, the proposed approach is applied for testing the Xilinz 4000 family of FPGAs.

This paper presents a methodology for production-time testing of (uncustomized) segmented channel field programmable gate arrays (FPGAs) such as those manufactured by Actel. The principles of this methodology are based on configuring the uncommitted modules (made of sequential and combinational logic circuits) of the FPGA as a set of disjoint one-dimensional arrays similar to iterative logic arrays (ILAs). These arrays can then be tested by establishing appropriate conditions such as constant testability (C-testability). A design approach is proposed. This approach is based on adding a small circuitry (consisting of two transistors) between each pair of uncustomized modules in a row for establishing the ILA configuration as a one-dimensional unilateral array. It also requires the addition of a further primary pin. Features such as number of test vectors and hardware requirements (measured by the number of additional transistors and primary input/output pins) are analyzed; it is shown that the proposed design approach requires a considerably smaller number of test vectors (a reduction of more than two orders of magnitude) and hardware overhead for the testing circuitry (a reduction of 13.6%) than the original FPGA configuration of [1]. The proposed approach requires 8+2nf vectors for testing the uncommitted FPGA of [1], where nf is the number of flip-flops (equal to the number of sequential modules for the FPGA of [1]) in a row of the FPGA.

An algorithm for fault diagnosis (detection and location) of baseline interconnection networks in the presence of multiple faults is presented. This algorithm requires 2(1+log/sub 2/ N) tests, where log/sub 2/ N is the number of stages. Multiple fault diagnosis is possible provided: (a) there exists no logically erroneous and unidentified outputs in each faulty switching element and (b) multiple link faults (of the type stuck-at-0 stuck-at-1) do not exist in the network. Fault location is accomplished using an iterative process which checks each stage of the multistage interconnection network. A new functional description of the network is introduced to facilitate fault location.>

A novel approach for the diagnosis of baseline interconnection networks with a fan-in/fan-out of 2 is presented. The totally exhaustive combinatorial fault model with single fault assumption is used in the analysis. Some new characteristics of baseline interconnection networks are proved. A characterization for the fault location and the fault type of the one-response fault are given. This characterization is used in proving that baseline interconnection networks with fan-in/fan-out of 2 can be diagnosed with a constant number of tests independent of the network size. The maximum number of tests is 12.>

An extension of a previous approach to fault detection and C-testability of orthogonal iterative arrays is presented. The state transition table of a basic cell is analyzed. Five new states are added to it. It is proved that even though the number of additional states in the proposed approach is greater than previous approaches, (five states compared to four), the required number of test vectors is considerably reduced (by a factor of approximately 4/9). An approach to implement the proposed C-testability approach into logic design is also presented. Complexity of this implementation is analyzed.>

Two approaches for the repair of large random access memory (RAM) devices in which redundant rows and columns are added as spares are presented. These devices, referred to as redundant RAMs, are repaired to achieve acceptable yield at manufacturing and production times. The first approach, the faulty line covering technique, is a refinement of the fault-driven approach. This approach finds the optimal repair solution within a smaller number of iterations than the fault-driven algorithm. The second approach exploits a heuristic criterion in the generation of the repair solution. This heuristic criterion permits a fast repair. The criterion is based on the calculation of efficient coefficients for the rows and columns of the memory. Simulation results are presented. Comparison of the proposed heuristic approaches with the fully exhaustive approach shows that repair can be accomplished in most cases. A considerable reduction in processing and complexity (number of records generated in the repair process for finding the optimal repair solution) is accomplished.>

An improved version of the C-testability approach for orthogonal iterative arrays presented by H. Elhuni et al. (see ibid., vol.CAD-5, p.573-81, 1986) is described. C-testability is defined by those criteria which characterize the complexity of the testing process as independent of the dimensions of the array and of the erroneous states of the cells. The proposed approach is based on a cellular automata characterization under single faulty assumption. This characterization analyzes the state transition table of a basic cell and adds new states to it. These states are used to reproduce internally to the array the test input and propagate the faulty state to the output pins of a chip. This process is analyzed exhaustively. The characteristics of the additional states are presented. The conditions of C-testability are fully proved. Complexity of the testing process (number of test vectors) is discussed. It is proved that the proposed approach has a lower complexity than that of Elhuni et al.>