Pseudo-exhaustive self-test technique

Claim 3

The method according to claim 1 characterized in that the step of partitioning the combinational elements into sub-cones by designating test points comprises the steps of: (a) successively examining the output of each combinational element (18 1 ,18 1 ,18 3 ...18 k ) in each cone (14 ; ) to establish a list of the primary inputs of the circuit which feed the combinational element (18 ; ) under examination and which primary outputs of the circuit are fed thereby; (b) rating the examined combinational element output on the basis of (1) the number of cones (if any) which will have the number of their inputs reduced to no more than w (where w is a user- defined integer value) if the examined node is designated as a test point and a sub-cone (14;) is established having such a test point as its output, and (2) the number of inputs reduced in those cones whose total number of inputs is not reduced to less than or equal to w; (c) selecting the highest rated combinational element (18,) output as a test point and thus creating a sub-cone which has the test point as its output; and (d) repeating the steps of (a), (b) and (c) until there remains no cone having more than w inputs.

Claim 4

The method according to claim 1 characterized in that the assignment of inputs is established by the steps of: (a) establishing a priority for the inputs to each of the sub-cones (b) determining if one of the vectors of the set of test vectors can be assigned to the highest priority sub-cone input while maintaining linear independence with all of the vectors (if any) assigned to other inputs of the same sub-cone; (c) assigning the highest priority input to receive the vector so long as linear independence is maintained with the vectors to which the other inputs have been assigned; otherwise, reassigning the inputs to the vectors to maintain linear independence; (d) reducing the priority after the then-highest input is assigned to a test vector; and (e) repeating the steps of (a)-(d) until all of the inputs have been assigned a vector.

Claim 7

The method according to claim 4 characterized in that the response signals produced by sub-cones are successively compacted by exclusively OR-ing the response signal produced by one sub-cone with that of another sub-cone

Claim 8

The method according to claim 4 characterized in that the set of test vectors is generated by the steps of: generating a binary counting sequence to establish w vectors a 1 ,a 2 ...a w , each vector being 2 w bits in length; generating a second sequence of w vectors, b 1 ,b 2 ...b w , each generated in accordance with the relat nship where b; represents a successive one of the second sequence of vectors and a represents a successive one of the vectors in the binary counting sequence.

Claim 9

In combination with a digital integrated circuit (10) containing combinational elements (18 1 ,18 2 ...18 k ) which have been grouped into sub-cones each sub-cone having a single output and a plurality of inputs which receive operating data, a system for pseudo-exhaustively testing the circuit characterized by: means for generating a set of test vectors (74), which when applied to the sub-cones, exhaustively tests them, causing each cone to generate a response for each vector; and means for operating the circuit in a test mode (88) to (1) cease supplying sub-cones with normal operating data and instead provide them with the test vectors such that each sub-cone can be tested exhaustively, and (2) compact the responses produced by the sub-cones upon receipt of the test vectors.

Claim 10

In combination with a digital integrated circuit (10) containing combinational elements (18 1 ,18 2 ...18 k ) which have been grouped into sub-cones each sub-cone having a single output and a plurality of inputs which receive operating data, a system for pseudo-exhaustively testing the circuit characterized by: means for generating a set of test vectors (74), which when applied to the sub-cones, exhaustively tests them, causing each cone to generate a response for each vector; and means for operating the circuit in a test mode (88) to (1) cease supplying sub-cones with normal operating data and instead provide them with the test vectors such that each sub-cone can be tested exhaustively, and (2) compact the responses produced by the sub-cones upon receipt of the test vectors.

Claim 11

The apparatus according to claim 7 characterized in that the vector-generating means comprises: linear feedback shift register means (76) for generating a first exhaustive set of vectors; a parity generator (84) for generating a parity bit in accordance with the parity of the first and last bit generated by the shift register means; and a plurality of exclusive OR gates (82 1 ,82 2 ...82 w ), each serving to generate a separate one of a second set of vectors in accordance with the logical relationship between the parity bit and a separate one of the first set of exhaustive vectors.

Claim 12

The apparatus according to claim 8 characterized in that the means for operating the circuit in the test mode includes a multiplexer for multiplexing the test vectors generated by the test vector-generating means with the normal operating data supplied to the circuit.

Claim 13

The apparatus according to claim 1 characterized by a plurality of test point multiplexers (21), each test point multiplexer being placed between the output of a first sub-cone which feeds the input of the second sub-cone, and the input of the second sub-cone for multiplexing a response produced at the output of the first sub-cone with a test vector to be injected into the second sub-cone.

Claim 14

In combination with a circuit containing groups of combinational elements arranged in groups of sub-cones, each having one output and no more than (w) inputs, the improvement characterized by: means for generating a plurality of independent test vectors (74), which when applied to the inputs of the sub-cones, causes each cone to produce a response indicative of its faults (if any); and a plurality of daisy-chained flip-flop circuits (88), each serving to supply a test vector to the input of a sub-cone, and to compact the response produced by a sub-cone with a signal of an upstream flip-flop in the chain, the flip-flop circuits each including: a flip-flop (90) having a D input and Q and Q outputs; a first multiplexer supplied (94) with an input test vector for receipt at a sub-cone input and with the output signal present at the Q output of the flip-flop, the first multiplexer providing at its output a separate one of its input signals for receipt at the input of a sub-cone; an exclusive NOR (XNOR) (96) gate having a first input coupled to the output of a sub-cone, a second input coupled to an output of the previous flip-flop in the chain, and an output coupled to the D input of the flip-flop; and a second multiplexer (92) having a first input supplied with the output signal of the first multiplexer, and supplied at a second input with the Q output signal of a flip-flop of an upstream flip-flop in the daisy chain, the second multiplexer providing at its output, a separate one of the signals at its input, for receipt at the second input of the XNOR gate.

Claim 15

In combination with a circuit containing groups of combinational elements arranged in groups of sub-cones, each having one output and no more than (w) inputs, the improvement characterized by: means for generating a plurality of independent test vectors (74), which when applied to the inputs of the sub-cones, causes each cone to produce a response indicative of its faults (if any); and a plurality of daisy-chained flip-flop circuits (88), each serving to supply a test vector to the input of a sub-cone, and to compact the response produced by a sub-cone with a signal of an upstream flip-flop in the chain, the flip-flop circuits each including: a flip-flop (90) having a D input and Q and Q outputs; a first multiplexer supplied (94) with an input test vector for receipt at a sub-cone input and with the output signal present at the Q output of the flip-flop, the first multiplexer providing at its output a separate one of its input signals for receipt at the input of a sub-cone; an exclusive NOR (XNOR) (96) gate having a first input coupled to the output of a sub-cone, a second input coupled to an output of the previous flip-flop in the chain, and an output coupled to the D input of the flip-flop; and a second multiplexer (92) having a first input supplied with the output signal of the first multiplexer, and supplied at a second input with the Q output signal of a flip-flop of an upstream flip-flop in the daisy chain, the second multiplexer providing at its output, a separate one of the signals at its input, for receipt at the second input of the XNOR gate.

Claim 16

A test point compactor for compacting a signal received from a first source with a signal received from a second source characterized by: an exclusive OR (112) gate having a first input supplied with the signal from the first source and a second input supplied with the signal from the second source, and an output, and a multiplexer (113) having a first input supplied with the signal from the first source and a second input supplied with the output signal of the exclusive OR gate, the multiplexer selectively passing the signal at a separate one of its first and second inputs in response to the state of a control signal supplied thereto.

Claim 17

A test point compactor for compacting a signal received from a first source with a signal received from a second source characterized by: an exclusive OR (112) gate having a first input supplied with the signal from the first source and a second input supplied with the signal from the second source, and an output, and a multiplexer (113) having a first input supplied with the signal from the first source and a second input supplied with the output signal of the exclusive OR gate, the multiplexer selectively passing the signal at a separate one of its first and second inputs in response to the state of a control signal supplied thereto.