It is apparent that F Y R, Y R, and Y R, where the shows an exclusive-OR (XOR) operation or an exclusive-NOR (XNOR) operation, are also solutions that satisfy Eq. 12:24 . Proof of Theorem 12.13 From Lemma 12.5 the following relation satis es Eq. 12:20 : fF yi yi ri : By Eqs. 12:21 and 12:26 , ri can be obtained such that ri yi ai bi : Modulo-2 addition with respect to i for both sides of Eqs. 12:21 and 12:26 produces the relations ! k 1 k 1 X X fF yi ai bi pA pB ;

12:26

ri :

ri :

This satis es Eq. 12:22 . On the other hand, from Lemma 12.5 the following relation also satis es Eq. (12.21): fF yi yi ri : In the same manner, for ri yi ai bi, the predicted parity bit p0Y can be obtained as Eq. 12:23 . Q.E.D. From the de nition of the Boolean difference, Eq. 12:20 demonstrates that an error in yi is always propagated to the output of the function fF yi . Equations 12:20 and 12:21 are important from the point of producing the predicted parity bits as well as giving the condition for propagating an error in yi to the output of fF yi . Table 12.3 shows the function ri for the basic arithmetic and logic operations, where R is de ned as follows. R rk 1 rk 2 . . . r1 r0 : Theorem 12.14 describes the parity checking for an arbitrary ALU operation using the predicted parity bit p0Y shown in Eq. (12.22).

TABLE 12.3 Function r i ri Operation F AND OR XOR XNOR ADD yi a1 \ bi ai [ bi ai bi ai bi ai bi XOR ai [ bi ai \ bi 0 1 ci 1 XNOR " " ai \ bi " " ai [ bi 1 0 ci 1

Theorem 12.14 For inputs A and B, each having k bits, the parity checking (i.e., syndrome generation) for an ALU operation F is performed as SF pY p0Y where fF yi yi ri ai bi ; SF 1 : error detected; SF 0 : error free: Figure 12.46 shows the parity-checking scheme for an ALU operation F. Theorem 12.15 The parity-checking scheme shown in Fig. 12.46 detects any single errors in input A or B, if there exist no faults in both ALU and checker. Proof Equation 12:27 can be also written as SF Therefore we have dSF 1 dai and dSF 1: dbi Q.E.D.

) pA pB 12:27

pA pB ;

pA pB ! pA pB :

Figure 12.46 Parity-checking scheme for arbitrary operation F. Source: [FUJI81]. 1981IEICE Japan.

Next we consider an error correction of ALU operation based on the foregoing principle. Parity checking is performed according to the check group indicated by the H matrix row. That is, the check group is de ned as a set of input data determined by the row pattern of H. There exist n k r check bits in the n; k code H He j Ir r n : Here He is an r k encoding matrix and Ir is an r r identity matrix. Two input codewords are shown as A; CA and B; CB , where CA and CB are check-bit vectors, such that CA cA;0 cA;1 . . . cA;r 1 ; CB cB;0 cB;1 . . . cB;r 1 : We also de ne C such that C CA CB ; C c0 c1 . . . cr 1 ; ci cA;i cB;i ; i 0; 1; . . . ; r 1:

The output of ALU is shown as Y; CY , where CY is a check-bit vector for output Y: CY cY;0 cY;1 . . . cY;r 1 : Recall that an error correction procedure consists of three main steps: (1) syndrome generation, (2) determination of error location (syndrome decoding), and (3) inversion of the erroneous bit. For syndrome generation for output Y, we have the following sequence of steps: Step 1. Check-bit generation, CY Y HT : e Step 2. Check-bit prediction, Cp R HT C; e Cp cp;0 cp;1 . . . cp;r 1 : Step 3. Syndrome generation, S CY Cp Y HT R HT C e e FF HT C; e where FF Y R:

The error location is determined from the syndrome, such that w S 0 : No error: w S 1 : Error in check-bit part Cp : w S ! 2 : Error in ALU output Y; where w S means the weight of syndrome S. Location of the erroneous bits, especially the erroneous bits in the output Y, is determined precisely by the column vectors of the H matrix. An error pointer E EY ; Ec speci es the error pattern to be corrected, where EY is the ^ ^ output Y error and Ec the check-bit error. The corrected output Y; CY is obtained by the error pointer such that ^ Y Y EY ; ^ CY Cp Ec : Figure 12.47 shows an error correction circuit EC for ALU. Note particularly that the circuit EC0 in EC, enclosed by the broken line, is the same error decoding circuit as that for the high-speed memories. Therefore any type of error detecting / correcting parity-based code, that is, any linear code, can be applied to an error detection / correction in ALU operations. In [FUJI81],