Introduction

In this paper, the checksum is used with a different meaning. Under our approach, for each output, its checksum represents the number of either 00s or 10s corresponding to the given input setting. In fact, such a checksum would cover a (contiguous) range of inputs and involve a distinct count for each output. It will be able to detect and also to locate stuck-at-0 and stuck-at-1 faults. Figure 1 illustrates our new scheme for checksum testing.

A pair of inputs, called enumerated signals, specifies a test range for the circuit under test (CUT), together with a vector of counters for each output to accumulate the number of either 00s or 10s encountered. At the end of each testing, the accumulated counters are compared with the expected checksums from the cache, generated apriori by a software checksum calculator. The comparison between the algorithm and the testing machine should be efficiently real-time coordinated. Section IV discusses the cases which might appear in practice, depending whether the testing machine and the checksum algorithm can be synchronized, or one of them is faster than the other. Any mismatch with the checksums indicates a definite fault, while a match on the checksums increases our confidence on the circuit’s correctness. Each checksum test plan can either be computed before hand and stored, or generated on the fly. Compared to the pairwise approach to testing, the storage requirement of checksums is considerably smaller. For example, 2¹⁶ expected results for the pairwise approach will require 64K x 4 bytes memory involving 32 bit input and output, while checksum results need only 32x2 bytes cache

The Counting Algorithm

Step 1. As we wrote in the Introduction, the number of test patterns can be controlled, before starting the effective test pattern generation, according to the memory limitations of the testing machine. To do so, we split the set of inputs, Vinp, into two disjoint sets: variables (V¹_inp), and constants (V²_inp), namely V_inp = V¹_inp U V²_inp and V¹_inp Ç V²_inp = Æ. The set V¹_inp is called the current frame of our test plan. A set of frames is called a frame test and the process of doing a frame test is a test pattern generation (Figure 3). However, we can design a series of test frames which slides through the entire input set, such that all the inputs are present as variables in one or more of the test frames. A full frame test consists of a set of frames such that any input variable appears unbounded in at least one frame of the frame test. We say that a frame is complete if it contains all inputs, namely V¹_inp = V_inpVinp and V²_inp= Æ. As expected, for large combinational circuits, the testing of the complete frame is impracticable .

Application how-to:
Apply the input assignments to the combinational circuit specification (frame approach):

Step 2. The CNF formula of a combinational circuit is the conjunction of the CNF formulas for each gate output, where the CNF formula of each gate denotes the valid input-output assignments to the gate (Table 1).

Step 3. The algorithm Input: A CNF formula F over V corresponding to a combinational circuit, a checksum testing machine able to test a combinational circuit, and N the number of frames; Output: “The chip has a stuck-at-0/1 leading to output x.”, for some x.

1. split V_inp into two disjoints sets, V^1,i_inp and V^1,i_inp, that is V_inp = V^1,i_inp U V^2,i_inp and V^1,i_inp Ç V^2,i_inp;
2. make some settings for the variables of V^2,i_inp, and denote the corresponding clausal formula by Fⁱ_inp;
3. (tester task) let mc₀[x] be the measured checksum provided by the checksum testing machine corresponding to the input given by V^1,i_inp and V^2,i_inp and to the output x bounded to 0. Then mc₁[x] = 2^|V^1,i_inp - mc₀[x];
4. F' = F U Fⁱ_inp; det_V(F') = 2(|V_inp| - |V^2,i_inp| ;
5. for (any x Î V_out) {
6.     det_V (F' U {¬x}) = det_V (F')+ inc_V ({¬x}, F');
7.     det_V (F' U {x}) = det_V (F')+ inc_V ({x}, F');

8.     if (det_V (F' U {¬x}) != mc₀[x]) print “The chip has a stuck-at-0 leading to output x.”
9.     if (det_V (F' U {x}) != mc₁[x]) print “The chip has a stuck-at-1 leading to output x.” }

Application how-to:
Apply the counting algorithm to the given clausal formula.

	input	output
java testing	<clausal formula>	<expected checksum>

Real-time execution coordination

Let F be a arbitrary frame, and let T_m(F), T_a(F) be the times spend by the testing machine and the checksum algorithm, respectively, in order to measure the two checksums. To have an agreement between the two time values, we denote by ad the accepted delay. If ad is “small enough”, then it is very likely that the testing machine and the checksums algorithm can be mutually synchronized one to the other. Depending on these time values, we have two general cases:

• If |T_m(F) - T_a(F)| < ad, for all frames F, then we say that the testing machine correlates with the checksums algorithm (|x| means the absolute value of x);
• Otherwise, we may distinguish three situations:
  • For all frames F, we have T_m(F) £ T_a(F), that is, the testing machine is faster than the algorithm. Then the proposed solution is to store in a memory array all the measured checksums corresponding to the testing machine. When the algorithm provides a determinant, this will be checked with the already saved checksums.
  • For all frames F, we have T_m(F) ³ T_a(F), that is, the testing machine is slower than the algorithm. Then the algorithm should have the posibility of storing in a memory array all the determinants corresponding to the frame F. When the testing machine provides a measured checksum, this will be checked with the already saved determinants.
  • For some frames F₁, we get T_m(F1) £ T_a(F₁), whereas for other frames F₂, we get T_m(F₂) ³ T_a(F₂), that is, the testing machine execution time may vary compared with the checksum algorithm execution time, from one frame to a different frame. In other words, for some frames, the testing machines is faster than the checksum algorithm, whilst for other frames the converse holds. In tihs case, we need to store in memory for each frame the measured checksums and the determinants for later comparisons, respectively.