Method of and apparatus for fault detection in digital circuits by comparison of test signals applied to a test circuit and a faultless reference circuit

A fault detection system for electronic circuits is disclosed which comprises a detection circuit in which the crosscorrelation values between the test signal sequence, input to a circuit to be tested, and the output signal sequence from it, with no delay and with delays made in steps to a predetermined time interveral either in the test input signal or in the output sequence, are counted, a reference circuit in which the crosscorrelation values between the test signal sequence input to a faultless reference circuit and the output signal sequence from it, are counted, and a comparator for comparing the crosscorrelation values from both the detection and reference circuit. In one preferred embodiment, one or more of the conventional data compression methods selected from the group of the one's counting, transistion counting, auto-correlation, and C. R. C. methods are incorporated for operation in conjunction with the system.

FIELD OF THE INVENTION 
The present invention relates in general to a system for fault detection in 
electronic circuits and in particular to such a system of the type in 
which a pseudo-random test signal is applied to both a circuit to be 
tested and a faultless reference circuit to compare the outputs from both 
circuits in order to check if there is a difference, indicating an 
abnormality in the various constituent elements of the tested circuit. 
This invention provides far more enhanced efficiency in fault detection 
than any prior art fault detection method. It has been proved to greatly 
reduce residual error rates. 
BACKGROUND OF THE INVENTION 
A well known method of fault detection in digital circuits is to apply a 
sequence of test signals of known value to both a circuit to be tested and 
a reference circuit and to compare the output signals from both circuits. 
However, these conventional methods have been found to demand cumbersome 
efforts on the part of the testers because of the voluminous data arising 
from two sets of signals output from the two circuits. To eliminate this 
problem, several improved methods have been developed in which the 
sequence of output signals is compressed, such as by the one's counting 
method, transistion counting method, cyclic redundancy check (C. R. C.) 
method, and auto-correlation method. 
A problem in these data compression methods, however, is that since all the 
output signals from the tested circuits are not individually subject to 
checking, all possible abnormal states that might be present in the 
circuit are not always detected. 
The undetected error rate for these data compression approaches can be 
computed as follows; 
1. One's counting and auto-correlation methods 
##EQU1## 
2. Transition counting method 
##EQU2## 
3. C. R. C. method 
##EQU3## 
where n: data sequence length 
c: binominal constant 
r: number of stages in the register (for method 3) 
H: step function, providing the value of H(n-r) is either 0, if n&gt;r, or 1, 
if n.ltoreq.r (for method 3) 
Of the above methods, it is known that the C. R. C. method improves 
undetected error rates by increasing the number of stages of the shift 
register. However, this method is not satisfactory in cases where strict 
fault detection is required. 
SUMMARY OF THE INVENTION 
The present invention has for its object to provide a fault detection 
system utilizing the correlation method which can by far markedly improve 
the undetected error rates. 
The basic principle of the present invention can be embodied in two forms 
of fault detection method and apparatus. In the first version, the 
correlation values between the test signal sequence input to a circuit to 
be tested and the output signal sequence from it, with no delay and delays 
made in steps to a predetermined time interval in the input sequence, are 
counted and compared with the similarly counted correlation values between 
the test signal sequence input to and the signal sequence output from a 
faultless reference circuit, also with no delay and delays made in steps 
to a predetermined time in the input sequence time interval. In other 
forms, the correlation values between the sequential test signals input to 
and the sequential signals output from a circuit to be tested, with no 
delay and delays made in steps to a predetermined time interval in the 
output signal sequence are counted and compared with the similarly counted 
correlation values between the test signal sequence input to and the 
signal sequence output from a faultless reference circuit, with no delay 
and delays made in steps to a predetermined time interval in the output 
signal sequence.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
In a fault detection method for digital circuits in which the correlation 
values of the sequential test signals input to and the sequential signals 
output from a circuit being tested are counted and compared, how the 
undetected error rate can be minimized to a greater extent as the input 
test signal sequence is increased in length and the correlation values are 
increased in number, will be described in accordance with the present 
invention. 
In this particular embodiment, the test signal is delayed prior to being 
input to the tested circuit. 
However, it is to be understood that it also applies to an embodiment in 
which the output signal from the tested circuit is delayed, of which 
description is omitted. 
If the sequence of the test signals input to a circuit to be tested is b0, 
b1, - - - , b.sub.n-1 and the sequence of signals output from it is a0, 
a1, - - - , a.sub.n-1, the correlation value R between them is given as 
##EQU4## 
where .sym. represents an exclusive OR. 
1. Fault detection without delaying the input signals: 
In this circuit arrangement, the value of R is related in one-to-one 
correspondence with Q, where 
##EQU5## 
In this case, (ai.sym.bi) is equal to either 1, if ai.noteq.bi, or 0, if 
ai=bi. 
Hence, the probability of the value of Q being a particular value P 
coincides with the probability that the number of the ai's whose 
respective value is not equal to their corresponding bi in the input test 
signal sequence b.sub.0, b.sub.1, - - - , b.sub.n-1 is P. 
It follows that the probability of the correlation value R being R=n-2p is 
nCp/2.sup.n. 
In other words, if the correlation value R for a faultless circuit is 
R=n-2P, while the number of output signal sequences that indicate a 
non-defect state is only one, the number of those whose correlation value 
R being n-2P is nCp, out of all the output signal sequences which might be 
2.sup.n in number. 
Thus, out of the all output signal sequences excluding the one indicating a 
non-defect state, the number of output signal sequences whose respective 
correlation value R is n-2P must be nCp-1. 
This number is substantially the number of defects likely to be left 
undetected at all. 
That is, for a circuit having defects to be otherwise detected, the 
probability of R being n-2p, the value set forth for a faultless circuit, 
is as high as nCp(nCp-1)/{2.sup.n (2.sup.n -1)}. 
The undetected error rate D0 for the sum of all the correlation values is 
##EQU6## 
the value substantially equal to that obtainable with the conventional 
one's counting method. 
2. Fault detection including a delay in the input test signal sequence 
In this method, a cyclic code sequence (so-called M-sequence) may be 
employed as the test signal sequence input to circuits to be tested 
because it is easily generated by a shift register and yet it looks like a 
truly random sequence. It is to be noted that, in this fault detection 
structure, the correlation value for an input signal seqence with a delay 
is not independent from that for an input signal sequence without delay. 
This will be seen clearly from the fact that, for a general input test 
signal sequence other than the M sequence, such as the sequence consisting 
of straight 0's or 1's, whether the sequence has a delay or no delay does 
not affect the correlation value. 
Let the number of 0's or 1's in the input test sequence which transit from 
0 to 1 or from 1 to 0 in one bit time interval be q. 
Then the remaining n-q 0's or 1's do not transmit in one bit time interval. 
As was stated earlier the correlation value R can be calculated by counting 
the number of bi's in the input sequence which differ from ai's in the 
output sequence. 
Therefore, if we take s bits out of the above stated q bits in the input 
sequence, which differ from the corresponding ai's in the output, in the 
case of no delay, the number of such cases is qCs. 
Similarly, if we take t bits out of the above stated n-q bits in the input 
sequence, which differ from the corresponding ai's in the output, in the 
case of no delay, the number of such cases is n-qCt. 
From the above number of ai's equal to t+s, the correlation value R0 for 
the input sequence with no delay can be computed as R0=n-2(t+s). 
On the other hand, for the input sequence with one bit delay, the 
correlation value R1 is n-2(t+q-r). This is because that, while each of 
the above s ai's has the same value as their corresponding bi, the latter 
being transmitted, the remaining (q-s)ai's all take a different value from 
their corresponding bi's. 
Also, from the above equations, it is seen that both R.sub.0 and R.sub.1 
are unconditionally determined by s and t. 
The probability of the correlation value for the input sequence having no 
delay is n-2(t+s) while that for the input sequence with a delay being 
n-2(t+q-s) is obtained as qCs n-qCt/2, in a similar manner as in the 
previous section. 
It follows, consequently, that the probability of a faulty circuit being 
estimated as having the same correlation value of the faultless circuit is 
qCs n-qCt(qCs n-qCt-1)/{2.sup.n (2.sup.n -1)}. 
Since totaling the probabilities for all correlation values is 
substantially the same as summing with respect to the aforesaid numbers of 
ai's, t and s, the total undected error rate D, in case where we use both 
the correlation values R0 and R1, is 
##EQU7## 
3. Fault detection including double delays in the input test signal 
sequence. 
Let us consider the q bits in the test signals that are changed from 0 to 1 
or 1 or 1 to 0 within a one-bit time interval. If the number of those that 
change thereafter to 1 or 0 in a two-bit time interval is p, the number of 
bits that change thereafter to 0 or 1, is consequently q-p. 
On the other hand, of the (n-q) bits in the input signals that changed from 
0 to 0 or 1 to 1 within a one-bit time interval, the number of those that 
change thereafter to 1 or 0 in a two-bit time interval is p. 
Since the cyclic code sequence is employed in this embodiment, the total 
number of bits in the input test signals that change from 0 to 1 or 1 to 0 
within the interval between the first and second delays is also q, so that 
the number of those which change from 0 to 0 then to 1 or 1 to 1 then to 0 
is exactly equal to p, the value obtained by subtracting q-p from q. 
The number of bits in the input signals which transit from 0 to 0 then to 0 
or from 1 to 1 then to 1 is n-q-p, the value obtained by subtracting from 
n-q the above p, q-p, p. 
If, for the input bits that change from 0 to 1 then to 1 or 1 to 0 then to 
0 and from 0 to 0 then to 1 or 1 to 1 then to 0, the numbers of 
corresponding output bits ai's whose respective value differs from the 
paired input bit bi in the input sequence in case of no delay (where no 
transistion takes place), are respectively a and v, and the number of such 
cases are pCs and pCv, respectively. 
Similarly, when, for the input bits that change from 0 to 1 then to 0 or 1 
to 0 then to 1, the number of corresponding output bits ai's whose 
respective value differs from the paired input bit bi in the input 
sequence in case of no delay is t, the number of such cases is q-pCt. 
Furthermore, if, for the input bits that transit from 0 to 0 then to 0 or 1 
to 1 then to 1, the number of corresponding output bits ai's whose 
respective value differs from the paired input bit bi is u, then the 
number of such cases is computed as n-p-qCu. 
Using the above assumed numbers s, t, and u, the correlation values for 
different states of delay are as follows: 
EQU R0=n-2(u+s+v+t)=n-2(s+t+u+v) 
for no delay in the input sequence. 
EQU R1=n-2(u+v+p-s+q-p-t)=n-2(u-t+q+v-s) 
for one bit delay in the input sequence. 
EQU R2=n-2(u+p-s+p-v+t)=n-2(u+t-s-v+2p) 
for two bits delay in the input sequence. 
With respect to R0, the numbers of output bits ai's whose respective value 
differs from that of their corresponding bi in the aforesaid four modes of 
transition are s, t, v, and u, respectively. 
R1 puts these numbers as p-s, q-p-t, v, and u, respectively where there is 
one bit delay in the input sequence. 
R2 with two bits delay in the input sequence gives p-s, t, p-v, and u for 
the number of output bits ai's whose respective value differs from their 
corresponding bi in the four modes of transition. 
Thus, for the above assumed numbers p and q of sequential input bits, the 
probability of the number of unpaired output bits being any of the 
particular values s, t, u, and v, is 
pCs.cndot.pCv.cndot.q-pCt.cndot.n-q-pCu/2.sup.n. 
Of the output sequences excluding the one indicating a non-defect state, 
equal to 2-1, the number of those in which the number of unpaired output 
signals is the same value as above s, t, u or v is estimated as 
pCs.cndot.pCv.cndot.q-pCt.cndot.n-q-pCp-1. 
It follows that the probability for the number of unpaired output signals 
being any of the above particular values s, t, u, and v is 
pCs.cndot.pCv.cndot.q-pCt.cndot.n-q-pCux(pCs.cndot.pCv.cndot.q-pCt.cndot.n 
-q-pCu-1)/{2.sup.n (2.sup.n -1)} 
It is important to note, however, that it can happen that R0, R1, R2 take 
identical values, respectively, even if the individual values for the set 
s, t, u and v are different. 
For example, for an M sequence in which n=7, the values of R0, R1, and R2 
are equally -3, 1, and 1, respectively, when s, t, u, and v are either 1, 
2, 1, and 2 or 2, 1, 2, and 1, respectively. 
Accordingly, in fault detection including up to double delays in the input 
test sequence, the rate of undetected errors is affected, not only by a 
formula summing the above probability with respect to s, t, u, and v, but 
by the fact that these R0, R1, and R2 can take an identical value for the 
different individual values of the set. 
When we describe this effect by multiplying some constant K, the undetected 
error rate D2 for a fault detection system with double delays is 
##EQU8## 
It has been proved that K2 is approximately/.sqroot..pi.n/4. 
The method of fault detection using a two-bits delay gives far more 
decreased undetected error rate compared with the previous fault detection 
method with one bit delay. 
4. Fault detection including triple delays in the input test sequence. 
The same principle as above is used to consider a fault detection system 
with triple delays in the input signal sequence. 
The following equations may be used to give an approximate formula for each 
of the undetected error rates rates D0, D1, and D2 for no delay, one bit 
delay and double bit delays, respectively. 
EQU .SIGMA.nCp=2.sup.n 
EQU .SIGMA.nCp=(2n)!/(n!).sup.n 
##EQU9## 
Since it is granted that D1 and D2 can be based on q.apprxeq.n/2 and 
p.apprxeq.n/4 in the case of an M sequence, 
##EQU10## 
FIG. 2 shows curves plotted to show the undetected error rates for the five 
embodiments of this invention with no delay(r=0), one bit delay(r=1), 
double bit delay(r=2), three bits delay(r=3), and four bits delay(r=4), 
and other conventional data compression method. 
It will be clear from a study of FIG. 2 that the undetected error rate can 
be reduced in steps, and more so if the output signal sequence is 
increased in length according to this invention. 
FIGS. 3(a) and 3(b) are third and fourth embodiments of this invention in 
which the first and second embodiments of FIGS. 1(a) and (b) are combined 
with a data compression circuit 6 according to a conventional method such 
as one's counting, transition counting, auto-correlation, and C. R. C. 
methods. 
In these embodiments, both outputs from the circuit to be detected and the 
faultless circuit are connected to the input of a conventional data 
compression circuit 6. Also, a comparator 5 is provided not only to make 
the same comparison of data described in association with FIGS. 1(a) and 
1(b) but also to perform data comparison according to a conventional 
method. In other words, since the data are compressed in two different 
manners, defects that might be overlooked by one detection system can be 
spotted by the other, reducing the undetected error rate of the overall 
system.