Locally Exhaustive Testing of Combinational Circuits Using Linear Logic Circuits

Locally exhaustive testing of multiple output combinational circuits is the test which provides exhaustive pat-terns for each set of inputs on which each output is truly dependent. In this paper, a method for locally exhaustive testing of combinational circuits using linear logic circuits is proposed. The testing scheme consists of a linear combinational circuit and a linear feedback shift register. This scheme can be implemented with smaller amounts of hardware than other existing methods, and can be applied to built-in self testing. The correspondence problem between the outputs of the linear combinational circuit and the inputs of the circuit under test is formalized as a vector assignment problem of hypergraphs. It resembles the coloring problem of graphs and is also proved to be NP-complete. The vector assignment of perfect hypergrahs is shown to be equivalent to the construction of linear codes. Several graph-theoretical properties which can be utilized to reduce the size of hypergraphs are shown. Finally, the length of test sequences is discussed.