This paper presents a generalized new approach for testing interconnects (for boundary scan architectures) as well as field programmable interconnect chips (FPICs). This approach relies on a structured walking-1 test set in the sense that a structural analysis based on the layout of the interconnect system, is carried out. The proposed structural test method differs from previous approaches as it explicitly avoids aliasing and confounding and is applicable to dense as well as sparse layouts and in the presence of faults in the programmable devices of a FPIC. The proposed method is applicable to both one-step and two-step test generation and diagnosis. Two algorithms with an execution complexity of O(n2), where n is the number of nets in the interconnect, are given. New criteria for test vector compaction are proposed; a greedy condition is exploited to compact test vectors for one-step and two-step diagnosis. For a given interconnect, the two-step diagnosis algorithm requires a number of tests as a function of the number of faults present, while the one-step algorithm requires a fixed number of tests. Simulation results for benchmark and randomly generated layouts show a substantial reduction in the number of tests using the proposed approaches compared with previous approaches. The applicability of the proposed approach to FPICs as manufactured by [1] is discussed and evaluated by simulation.

In this paper, we propose the evolutionary algorithm-based reasoning system and its design methodology. In the proposed design methodology, reasoning rules behind the past cases in each task (in each case database) are extracted through genetic algorithms and are expressed as truth tables (we call them 'evolved truth tables'). Circuits for the reasoning systems are synthesized from the evolved truth tables. Parallelism in each task can be embedded directly in the circuits by the hardware implementation of the evolved truth tables, so that the high speed reasoning system with small or acceptable hardware size is achieved. We developed a prototype system using Xilinx Virtex FPGA chips and applied it to the gene boundary reasoning (GBR) and English pronunciation reasoning (EPR), which are very important practical tasks in the genome science and language processing field, respectively. The GBR and the EPR prototype systems are evaluated in terms of the reasoning accuracy, circuit size, and processing speed, and compared with the conventional approaches in the parallel AI and the artificial neural networks. Fault injection experiments are also carried out using the prototype system, and its high fault-tolerance, or graceful degradation against defective circuits that suits to the hardware implementation using wafer scale LSIs is demonstrated.

We propose the kernel-based pattern recognition hardware and its design methodology using the genetic algorithm. In the proposed design methodology, pattern data are transformed into the truth tables and the truth tables are evolved to represent kernels in the discrimination functions for pattern recognition. The evolved truth tables are then synthesized to logic circuits. Because of this data direct implementation approach, no floating point numerical circuits are required and the intrinsic parallelism in the pattern data set is embedded into the circuits. Consequently, high speed recognition systems can be realized with acceptable small circuit size. We have applied this methodology to the image recognition and the sonar spectrum recognition tasks, and implemented them onto the newly developed FPGA-based reconfigurable pattern recognition board. The developed system demonstrates higher recognition accuracy and much faster processing speed than the conventional approaches.