Paper
Part IILinear Block Codes

Arithmetic Codes and Checking Logic

November 15, 202649 min readbeginner

One stuck carry can flip twelve sum bits yet move the value by a single power of two. The chapter builds AN and residue codes, Berger and parity prediction, totally self-checking checkers and checksums for matrix products.

An adder asked for 32760+832760 + 8 should return 3276832768. Suppose that inside a 16-bit ripple-carry adder the wire carrying the carry out of bit 3 is stuck at 0. The adder then returns 3275232752. Twelve of its sixteen sum bits are wrong, so by the count every earlier chapter used this is a twelve-bit error, far beyond the two-bit errors that the codes of SECDED and Hsiao Codes are built to detect. Yet the value is off by exactly 1616, a single power of two. Measured the way arithmetic measures it, one bad wire made one error.

This chapter builds codes that measure errors the way an adder makes them. AN codes multiply every number by a constant and read errors from the remainder, and residue codes carry that remainder beside the data. Berger check prediction and parity prediction work out from the operands and the carries what the check symbol of a sum has to be. Self-checking circuits answer the question of what checks the checker, and checksums for matrix products carry the idea from one addition up to a whole algorithm.

Every number in the chapter is recomputed by ch22_arithmetic_codes_and_checking_logic.py in the python/ folder of the companion repository ecc-book-lab, and the charts are drawn by ch22_charts.py in the same folder. The GNU Octave twin ch22_arithmetic_codes_and_checking_logic.m prints the same lines, as The Octave Route explains.

01.When the Adder Is Wrong

The adder is a ripple-carry adder, the simplest way to add two nn-bit words. Bit ii has its own full adder, which takes the operand bits xix_i and yiy_i and the carry cic_i from the stage below, and produces a sum bit sis_i and a carry ci+1c_{i+1} for the stage above. Read as integers, the three inputs and two outputs of every full adder satisfy

xi+yi+ci=si+2 ci+1.x_i + y_i + c_i = s_i + 2\,c_{i+1} .
(1)

So si=xi⊕yi⊕cis_i = x_i \oplus y_i \oplus c_i is the low bit of a three-way count and ci+1c_{i+1} is its high bit. The carry c0c_0 into bit 0 is normally 0, and cnc_n out of the top stage is the carry-out, which sits above the sum bits as bit nn of the result.

Take x=32760=0x7FF8x = 32760 = \texttt{0x7FF8} and y=8=0x0008y = 8 = \texttt{0x0008}. In bit 3 both operands hold a 1, so s3=0s_3 = 0 and c4=1c_4 = 1. Bits 4 to 14 of xx are all 1, so each of those stages writes 0 and passes the carry upward, until it comes to rest as s15=1s_{15} = 1. The sum is 0x8000=32768\texttt{0x8000} = 32768, and twelve carries, c4c_4 to c15c_{15}, are 1 along the way.

Now hold the wire c4c_4 at 0. Stage 4 sees x4+y4+0=1x_4 + y_4 + 0 = 1, so it writes s4=1s_4 = 1 and passes no carry, and every stage above does the same. The adder returns 0x7FF0=32752\texttt{0x7FF0} = 32752. Figure 1 lines up both results bit by bit, and bits 4 to 15 of the faulty sum are all wrong.

Adding 0x7FF8 and 0x0008 in a 16-bit ripple-carry adder. Fault-free, the carry into bits 4 to 15 is 1 and the sum is 0x8000. With the carry c4 stuck at 0, every carry is 0 and the sum is 0x7FF0, so the twelve sum bits from 4 to 15 are wrong, marked in red, while the arithmetic error is only -16, one power of two. 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 bit x = 0x7FF8 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 y = 0x0008 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 carry in, fault-free 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 carry in, c4 stuck at 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 sum, fault-free = 0x8000 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 sum, c4 stuck at 0 = 0x7FF0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 With c4 stuck at 0 no carry ripples, so sum bits 4 to 15 all come out wrong. 12 of 16 bits differ, yet 32752 − 32768 = −16, a single power of two.
Figure 1. Adding 32760 and 8 in a 16-bit ripple-carry adder. With the carry c4 stuck at 0 no carry ripples upward, so sum bits 4 to 15 all come out wrong, yet the result 32752 is only 16 below the right sum 32768.

A tempting check XORs the parity bits of the two operands and compares the result with the parity of the sum, the way a parity bit guards a stored word. Here xx has twelve ones, so P(x)=0P(x) = 0, and P(y)=1P(y) = 1, which predicts a sum of parity 1. The correct sum 3276832768 has a single 1, so the check passes it. The faulty sum 3275232752 has eleven ones and parity 1 as well, so the check passes it too. Twelve flipped bits is an even number, which parity cannot see.

The check is wrong even with no fault. For 1+11 + 1 the operand parities XOR to 0, but the sum 2=1022 = 10_2 has parity 1. Parity follows XOR, and addition is XOR plus carries. The memory codes of the earlier chapters fail for the same reason, since their check bits are linear over GF(2)\mathrm{GF}(2) and so follow x⊕yx \oplus y, not x+yx + y.

The useful measure of the error is its size, 32752−32768=−16=−2432752 - 32768 = -16 = -2^4. A single flipped bit in a stored word has the same shape, adding or subtracting 2i2^i.

So wA(16)=1w_A(16) = 1, and wA(7)=2w_A(7) = 2 because 7=8−17 = 8 - 1, though 7 has three ones. Eleven needs three terms whichever way it is written, so wA(11)=3w_A(11) = 3. The number 4080=4096−164080 = 4096 - 16 has eight ones but arithmetic weight 2, and so does 255=256−1255 = 256 - 1. The ordinary binary expansion is always one such sum, so the arithmetic weight never exceeds the Hamming weight, and a long run of ones costs only two terms.

Proof. Stages 0 to j−1j-1 never see the line cjc_j, so they produce the same sum bits and the same carry cj∗c_j^{*} as in a healthy adder. Let xlox_{\mathrm{lo}} and yloy_{\mathrm{lo}} be the low jj bits of the operands and let LL be the number those low sum bits form, so that xlo+ylo=L+2jcj∗x_{\mathrm{lo}} + y_{\mathrm{lo}} = L + 2^j c_j^{*}. Stages jj to n−1n-1 are a healthy adder for the high parts xhi=⌊x/2j⌋x_{\mathrm{hi}} = \lfloor x / 2^j \rfloor and yhi=⌊y/2j⌋y_{\mathrm{hi}} = \lfloor y / 2^j \rfloor with carry-in vv, so the high sum bits and the carry-out together hold xhi+yhi+vx_{\mathrm{hi}} + y_{\mathrm{hi}} + v. The faulty result is therefore L+2j(xhi+yhi+v)L + 2^j (x_{\mathrm{hi}} + y_{\mathrm{hi}} + v), while x+y=xlo+ylo+2j(xhi+yhi)=L+2j(xhi+yhi+cj∗)x + y = x_{\mathrm{lo}} + y_{\mathrm{lo}} + 2^j(x_{\mathrm{hi}} + y_{\mathrm{hi}}) = L + 2^j(x_{\mathrm{hi}} + y_{\mathrm{hi}} + c_j^{*}). Subtracting gives (v−cj∗) 2j(v - c_j^{*})\,2^j, and since vv and cj∗c_j^{*} are bits, the difference is 00, 2j2^j or −2j-2^j. ■\blacksquare

In the 16-bit example j=4j = 4, v=0v = 0 and c4∗=1c_4^{*} = 1, so the error is −16-16, as computed. The script checks the theorem on a 6-bit adder with each carry from c1c_1 to c6c_6 stuck at 0 and at 1, over all 4,096 operand pairs. Of the 49,152 cases, 24,576 give a wrong result, every one off by exactly ±2j\pm 2^j. Exactly half are wrong because, for each line, one of its two stuck values is wrong on every operand pair.

02.AN Codes

Choose A=3A = 3 and store every number NN as 3N3N, so N=5N = 5 is stored as 15=01111215 = 01111_2. Since 3N1+3N2=3(N1+N2)3N_1 + 3N_2 = 3(N_1 + N_2), the adder needs no change. If a carry fault adds 4, the adder returns 19, and 19 mod 3=119 \bmod 3 = 1 shows the error.

Avizienis compared the cost and effectiveness of such arithmetic codes for real arithmetic units, singling out multipliers of the form 2a−12^a - 1 whose remainders are cheap to compute [1].

Not every multiplier works. With A=4A = 4, the value N=5N = 5 is stored as 20, and the error +4+4 gives 24, which is a multiple of 4, so the error slips through. In remainder terms, (20+4) mod 4=0(20 + 4) \bmod 4 = 0. The trouble is that 4 divides the error.

Proof. A received word y=AN±2iy = AN \pm 2^i is a multiple of AA exactly when AA divides 2i2^i. The only divisors of 2i2^i are powers of two, and an odd A>1A > 1 is not one, so y mod A≠0y \bmod A \ne 0. ■\blacksquare

An even multiplier A=2tA′A = 2^t A' with odd A′>1A' > 1 also detects every single error, but its codewords end in tt zeros that carry nothing, and A′A' does all the work. The useful multipliers are the odd ones.

Proof. The largest codeword for A=3A = 3 is 3(2k−1)=3⋅2k−33(2^k - 1) = 3 \cdot 2^k - 3. It is at least 2k+12^{k+1}, because 2k≥32^k \ge 3 when k≥2k \ge 2, and it is below 2k+22^{k+2}, so it needs exactly k+2k + 2 bits. An AN code that adds at most one bit needs A(2k−1)<2k+1A(2^k - 1) < 2^{k+1}, so A<2+2/(2k−1)A < 2 + 2/(2^k - 1), which leaves only A=2A = 2. That multiplier is a power of two and misses the error +2+2, since 2N+2=2(N+1)2N + 2 = 2(N + 1). ■\blacksquare

The script tries every 8-bit data value with A=3A = 3, whose codewords have 10 bits, against each of the 20 errors ±2i\pm 2^i on those 10 positions. Of the 5,120 errors, none goes undetected.

Correction asks the decoder to tell the errors apart. A received word is y=AN+ey = AN + e, and since AN≡0(modA)AN \equiv 0 \pmod{A}, the remainder y mod Ay \bmod A equals e mod Ae \bmod A. Like a syndrome, it depends on the error and never on the data, so if each single error leaves its own remainder, the decoder looks the error up and subtracts it.

Proof. If the remainders are nonzero and distinct, a remainder of 0 means no error and every other remainder names exactly one error, which the decoder subtracts. If one error leaves remainder 0, the decoder cannot tell it from no error. If two errors leave the same remainder, the decoder must make the same correction for both, so it gets one of them wrong. Finally, 2m2m distinct nonzero remainders must fit among the A−1A - 1 nonzero values, so 2m≤A−12m \le A - 1. ■\blacksquare

The multiplier A=19A = 19 protects 4 data bits. Its largest codeword is 19⋅15=28519 \cdot 15 = 285, so m=9m = 9, and Table 1 lists the eighteen remainders. They are all different and all nonzero, so every nonzero remainder modulo 19 names exactly one single error. Since 19=2⋅9+119 = 2 \cdot 9 + 1, the code meets the bound with equality, an arithmetic counterpart of the perfect codes of Hamming Codes and Perfect Codes.

Table 1. The remainders of the eighteen single errors of the AN code with A = 19 on 9-bit codewords, each nonzero remainder appearing once

Position ii+2i mod 19+2^i \bmod 19−2i mod 19-2^i \bmod 19
0118
1217
2415
3811
4163
5136
6712
7145
8910

Source: reproduced by ch22_arithmetic_codes_and_checking_logic.py.

At 10 bits the code fails, because 29 mod 19=182^9 \bmod 19 = 18, which is the remainder of −20-2^0. The errors +512+512 and −1-1 then look alike. The next theorem says where such a collision first appears, using the order of 2, the least e≥1e \ge 1 with 2e≡1(modA)2^e \equiv 1 \pmod{A}. Groups and Cosets defined the order of an element, and Euler's theorem from Integers and Modular Arithmetic guarantees that it exists, because 2φ(A)≡1(modA)2^{\varphi(A)} \equiv 1 \pmod{A} whenever AA is odd. For A=19A = 19 the order is 18, and 29≡−12^9 \equiv -1.

Proof. Since AA is odd, 2 has an inverse modulo AA, so no power of 2 is 0 and every remainder is nonzero. Two plus signs collide, 2i≡2j2^i \equiv 2^j with i>ji > j, exactly when 2i−j≡12^{i-j} \equiv 1, that is when ee divides i−ji - j, so the mm values 2i2^i are distinct exactly when m≤em \le e, and the same holds for the values −2i-2^i. A plus and a minus collide, 2i≡−2j2^i \equiv -2^j with i≥ji \ge j, exactly when 2i−j≡−12^{i-j} \equiv -1. The case i=ji = j would need 2i+1≡02^{i+1} \equiv 0, which is impossible. If no power of 2 is −1-1, nothing more can collide and L(A)=eL(A) = e. Otherwise let hh be the least exponent with 2h≡−12^h \equiv -1. Then 22h≡12^{2h} \equiv 1, so ee divides 2h2h. Since −1≢1-1 \not\equiv 1 for A>2A > 2, ee does not divide hh, and h<eh < e because 2h−e≡−12^{h - e} \equiv -1 would otherwise be a smaller solution. With 0<2h<2e0 < 2h < 2e and e∣2he \mid 2h, the only choice is 2h=e2h = e. Now 2d≡−12^d \equiv -1 for 0≤d<e0 \le d < e only at d=hd = h, so a plus and a minus collide exactly when some difference i−ji - j equals e/2e/2, which first happens at m=e/2+1m = e/2 + 1. ■\blacksquare

An odd order cannot equal 2h2h, so when ee is odd, −1-1 is never a power of 2 and L(A)=eL(A) = e. For A=7A = 7 the order is 3, so the longest correctable word has 3 bits. For A=23A = 23 the order is 11 and the longest word has 11 bits. The script checks the theorem against a direct search for every odd AA below 100.

The smallest multiplier for kk data bits is the least odd AA whose L(A)L(A) reaches the length mm of its own codewords. Table 2 gives it for five word lengths, and Figure 2 plots it for every length from 1 to 32. At k=16k = 16 the order of 2 modulo 47 is 23, which is odd, so L(47)=23L(47) = 23 and the 22-bit codewords fit with one position to spare.

Table 2. The smallest multiplier A whose AN code corrects every single arithmetic error, with codeword length m, check bits, the order of 2 modulo A and the longest correctable length

Data bits kkMultiplier AALength mmCheck bitsOrder of 2L(A)L(A)
41995189
8291352814
12371863618
16472262323
32793973939

Source: reproduced by ch22_arithmetic_codes_and_checking_logic.py.

The smallest A that corrects every single arithmetic error, for data words of 1 to 32 bits 0 15 30 45 60 75 90 0 4 8 12 16 20 24 28 32 data bits k smallest correcting A A = 19, 5 check bits A = 29, 5 check bits A = 37, 6 check bits A = 47, 6 check bits A = 79, 7 check bits values the chapter states the remaining k from 1 to 32
Figure 2. The smallest odd multiplier whose AN code corrects every single arithmetic error, for data words of 1 to 32 bits. The check bits grow slowly with the word length, as a Hamming code's do. Data: computed by ch22_charts.py in the companion repository.

SECDED and Hsiao Codes tabulates the Hamming cost of single-error correction for 4, 8, 16 and 32 data bits as 3, 4, 5 and 6 check bits. An AN code pays one or two bits more, because it must tell apart 2m2m signed errors where the Hamming code tells apart mm bit flips. AN codes also suit a multiplier poorly, since AN1⋅AN2=A2N1N2AN_1 \cdot AN_2 = A^2 N_1 N_2 must be divided by AA before it is a codeword again. The next code avoids that.

03.Residue Codes

Take x=22x = 22 and y=13y = 13. Both leave remainder 1 on division by 3. Their sum 35 leaves 2, which is (1+1) mod 3(1 + 1) \bmod 3, and their product 286 leaves 1, which is (1⋅1) mod 3(1 \cdot 1) \bmod 3. A tiny unit working only on remainders can therefore predict the remainder of the result, and comparing that prediction with the remainder of the actual result checks the full-width unit.

Proof. Write x=qA+rx = qA + r and y=q′A+r′y = q'A + r' with 0≤r,r′<A0 \le r, r' < A. Then x+y=(q+q′)A+(r+r′)x + y = (q + q')A + (r + r') differs from r+r′r + r' by a multiple of AA, and xy=(qq′A+qr′+q′r)A+rr′xy = (qq'A + qr' + q'r)A + rr' differs from rr′rr' by a multiple of AA. Numbers that differ by a multiple of AA leave the same remainder. ■\blacksquare

This is the theorem Congruence respects addition and multiplication from Integers and Modular Arithmetic, and the script confirms it for every modulus from 2 to 16 on every pair of 6-bit operands. A mod-3 residue code catches every single carry fault for the reason the odd multiplier did. The error is ±2j\pm 2^j, and 3 never divides a power of two, so the remainder of the faulty result differs from the prediction. The check must read the carry-out too. A 16-bit adder returns the 17-bit result r=c16 216+sr = c_{16}\, 2^{16} + s, and only rr equals x+yx + y. Since 216≡1(mod3)2^{16} \equiv 1 \pmod 3, the carry-out adds c16c_{16} to the residue of ss, which costs one more mod-3 adder. Comparing s mod 3s \bmod 3 alone would raise a false alarm on all 2,147,450,880 operand pairs that carry out, nearly half of the 2322^{32} pairs. Peterson showed that a check built independently of the adder must use residue-class check symbols, and how to handle them when the sum overflows [2]. Figure 3 shows the arrangement.

A residue-checked adder. The data path adds x and y into the sum s and the carry-out c16. The check path, in green, reduces x, y and the 17-bit result r made of c16 and s modulo 3, adds the two operand residues in a small mod-3 adder to predict the residue of r, and raises error when the prediction and r mod 3 differ. x y 16-bit adder s c16 mod 3 mod 3 mod 3 x mod 3 y mod 3 mod-3 adder predicted r mod 3 equal? error check path data path
Figure 3. An adder checked by a mod-3 residue code. The carry-out c16 joins s in the residue of the result. The check path works only on 2-bit residues, so it is small, and it shares no gate with the adder it checks.

A residue generator for a general modulus is a divider, which is far too costly to sit beside an adder. A modulus of the form 2a−12^a - 1 needs only additions.

Proof. Since 2a=(2a−1)+12^a = (2^a - 1) + 1, it follows that 2a≡12^a \equiv 1, and so 2at=(2a)t≡12^{at} = (2^a)^t \equiv 1 for every tt. Each term Xt 2atX_t\, 2^{at} is therefore congruent to XtX_t, and the sum to the sum. A carry out of an aa-bit adder has weight 2a≡12^a \equiv 1, so adding it back at bit 0 keeps the total congruent. ■\blacksquare

Take x=181=101101012x = 181 = 10110101_2 and a=2a = 2, the case of mod 3, since 4≡1(mod3)4 \equiv 1 \pmod 3. The 2-bit chunks, lowest first, are 1, 1, 3 and 2, which sum to 7. Folding 7 the same way gives 3+1=43 + 1 = 4, and folding 4 gives 0+1=10 + 1 = 1, which is 181 mod 3181 \bmod 3. With a=4a = 4 the chunks are 5 and 11, which sum to 16, and folding 16 gives 1, which is 181 mod 15181 \bmod 15. The script checks the fold for a=2a = 2, 3 and 4 on every 12-bit word.

One detail needs care. In aa-bit arithmetic modulo 2a−12^a - 1 the all-ones pattern also means zero, so for mod 3 the chunk 1111 stands for 3, which is 0. A hardware generator first reduces each 2-bit chunk p1p0p_1 p_0 to the range 0 to 2 with a small block CC, which computes t=p1⊕p0t = p_1 \oplus p_0, c1=p1∧tc_1 = p_1 \wedge t and c0=p0∧tc_0 = p_0 \wedge t. For the chunks 0000, 0101 and 1010, tt passes them through unchanged, and for 1111 it gives t=0t = 0 and hence 0000.

Two reduced residues a=a1a0a = a_1 a_0 and b=b1b0b = b_1 b_0 then go to a mod-3 adder. With za=a1∨a0‾z_a = \overline{a_1 \vee a_0}, which is 1 exactly when a=0a = 0, and zbz_b likewise, the outputs are r0=zab0∨a0zb∨a1b1r_0 = z_a b_0 \vee a_0 z_b \vee a_1 b_1 and r1=zab1∨a1zb∨a0b0r_1 = z_a b_1 \vee a_1 z_b \vee a_0 b_0. The bit r0r_0 is 1 for the sums 0+10 + 1, 1+01 + 0 and 2+2=4≡12 + 2 = 4 \equiv 1, and r1r_1 is 1 for 0+20 + 2, 2+02 + 0 and 1+11 + 1. The output never reads 1111, so it can feed the next adder directly. Each adder takes two NOR gates, six AND gates and two three-input OR gates, ten gates in all.

A tree that computes a 16-bit word modulo 3. Each 2-bit chunk enters a block C that maps the pair 11 to 00, since 3 is 0 modulo 3, using one XOR gate and two AND gates as the inset shows. Seven mod-3 adders in three levels combine the eight residues into x mod 3, 94 gates in all. x1 x0 C x3 x2 C x5 x4 C x7 x6 C x9 x8 C x11 x10 C x13 x12 C x15 x14 C add add add add add add add x mod 3 inside one C block p1 p0 t c1 c0 C block, 1 XOR and 2 AND gates add block, a mod-3 adder of 10 gates whole tree, 94 gates, 11 levels deep
Figure 4. A mod-3 residue generator for a 16-bit word. Each C block reduces a 2-bit chunk to the range 0 to 2, and a tree of seven mod-3 adders sums the eight chunks. The whole tree is 94 gates and 11 levels deep.

Figure 4 assembles the generator for a 16-bit word. Its eight chunks need eight CC blocks and a tree of seven adders, which comes to 8 XOR gates, 58 AND gates, 14 NOR gates and 14 OR gates, 94 gates in all. A CC block is two gate levels deep and each adder three, NOR then AND then OR, so the three adder levels give a depth of 2+3⋅3=112 + 3 \cdot 3 = 11. The script runs the gate-level tree on all 65,536 inputs and finds no wrong residue.

A 4-bit ripple-carry adder makes a small test bench. Holding each internal carry c1c_1 to c3c_3 at 0 and at 1 gives six faults, and over all 256 operand pairs they make 1,536 cases, 768 of them wrong. For 3+13 + 1 with c1c_1 stuck at 0 the adder returns 2, whose residue 2 differs from the predicted (0+1) mod 3=1(0 + 1) \bmod 3 = 1. The mod-3 check catches all 768 wrong results, as Table 3 records below.

04.Berger Check Prediction

The section The Berger Code in Beyond SECDED defined the Berger code, which appends to kk data bits uu the number z(u)z(u) of zeros in uu, written as a binary number [3]. Write N(w)N(w) for the number of ones in an nn-bit word ww and B(w)=n−N(w)B(w) = n - N(w) for its Berger symbol, which is z(w)z(w). Counting the zeros of a computed sum says nothing about whether it is right, since a wrong sum has its own valid count. What helps is to predict that count from the operands and the carries.

Take 11+6=1711 + 6 = 17 in a 4-bit adder. With x=10112x = 1011_2 and y=01102y = 0110_2, the sum bits are 00010001 and the carry-out is c4=1c_4 = 1. The carries c1c_1 to c4c_4 are 0,1,1,10, 1, 1, 1. Counting ones, N(x)=3N(x) = 3, N(y)=2N(y) = 2 and the carries hold 3. The combination 3+2−3+0−1=13 + 2 - 3 + 0 - 1 = 1 is exactly the number of ones in the sum bits 00010001.

Proof. Add the relation Equation 1 over i=0,…,n−1i = 0, \ldots, n-1. The left side gives N(x)+N(y)+(c0+c1+⋯+cn−1)N(x) + N(y) + (c_0 + c_1 + \cdots + c_{n-1}), and the carry sum equals c0+Nc−cnc_0 + N_c - c_n. The right side gives N(s)+2NcN(s) + 2N_c. Setting the two equal and solving for N(s)N(s) gives N(x)+N(y)+c0+Nc−cn−2NcN(x) + N(y) + c_0 + N_c - c_n - 2N_c, which is the claim. ■\blacksquare

The carry chain has nn outputs, c1c_1 to cnc_n, so write Bc=n−NcB_c = n - N_c for its zeros. Replacing every count of ones by nn minus a count of zeros turns the theorem into the Berger prediction.

B(s)=B(x)+B(y)−Bc−c0+cn.B(s) = B(x) + B(y) - B_c - c_0 + c_n .
(7)

For 11+611 + 6 this reads 1+2−1−0+1=31 + 2 - 1 - 0 + 1 = 3, and the sum bits 00010001 do have three zeros. The script checks the ones count and the prediction on all 512 inputs of a 4-bit adder, carry-in 0 and 1 included. In hardware the predictor adds the stored symbols to a zero count of the carry lines. Lo, Thanawastien, Rao and Nicolaidis built a whole arithmetic and logic unit around this prediction [4].

Proof. Every stage except stage j−1j - 1 obeys Equation 1 with the values on the lines. Stage j−1j - 1 obeys it with cj∗c_j^{*} in place of the line value vv, so it obeys the line-value form with an extra 2(cj∗−v)2(c_j^{*} - v) on its right side. Adding the stages as in the previous proof gives N(s)=N(x)+N(y)−Nc+c0−cn+2(v−cj∗)N(s) = N(x) + N(y) - N_c + c_0 - c_n + 2(v - c_j^{*}), where NcN_c and cnc_n are read from the lines. The predictor computes everything but the last term, so the two counts differ by 2(v−cj∗)2(v - c_j^{*}), which is ±2\pm 2 when v≠cj∗v \ne c_j^{*} and 0 otherwise. By Equation 2 the result is wrong exactly when v≠cj∗v \ne c_j^{*}. ■\blacksquare

The factor 2 in Equation 1 is what makes this work, since a carry counts twice on one side and once on the other. In the 4-bit experiment the Berger check catches all 768 wrong results, each by a discrepancy of exactly 2.

05.Parity Prediction

Parity is cheaper than a zero count, and the carries repair the broken check from the first section. For the sum bits, si=xi⊕yi⊕cis_i = x_i \oplus y_i \oplus c_i, and XOR is associative and commutative, so the following holds.

Proof. XOR the relations si=xi⊕yi⊕cis_i = x_i \oplus y_i \oplus c_i over i=0,…,n−1i = 0, \ldots, n-1 and regroup the right side into the operand bits, the other operand's bits and the carries. ■\blacksquare

For 11+611 + 6 the parities are P(x)=1P(x) = 1, P(y)=0P(y) = 0 and P(c0,…,c3)=P(0,0,1,1)=0P(c_0, \ldots, c_3) = P(0, 0, 1, 1) = 0, which predicts 1, and the sum bits 00010001 have parity 1. The prediction is the ones count of Equation 6 read modulo 2, since cnc_n enters that count twice and vanishes, while c0c_0 moves into the list of carries. That observation also says where the trouble lies. The discrepancy a carry fault leaves in the ones count is 2(v−cj∗)2(v - c_j^{*}), and an even number is 0 modulo 2.

So if the parity predictor takes its carries from the same lines the sum bits use, every relation si=xi⊕yi⊕cis_i = x_i \oplus y_i \oplus c_i still holds with the faulty line values, the prediction still matches, and the check passes every wrong result. In the 4-bit experiment it catches 0 of the 768.

The fix is to build the carries twice. A second chain of separate gates computes the carries, and the predictor reads those, so a single fault in the main chain leaves the prediction equal to the parity of the correct sum. The two parities then differ exactly when an odd number of the carries c0c_0 to cn−1c_{n-1} differ between the chains. The 16-bit fault from the start of the chapter changes twelve carries, c4c_4 to c15c_{15}, an even number, so even the duplicated chain misses it. In the 4-bit experiment the duplicated chain catches 576 of the 768 wrong results and lets 192 through.

The remaining step is to compare the two carry chains directly and flag any difference. A fault that changes the result changes at least the stuck carry, so the comparison catches every one, 768 of 768. Nicolaidis analyzed adders and arithmetic units that pair parity prediction with such a check on the carries [5]. Table 3 gives the count for every fault and every check, and Figure 5 draws the totals. The faults on c3c_3 never escape the duplicated chain, because among c0c_0 to c3c_3 only c3c_3 itself can differ.

Table 3. Wrong results of a 4-bit ripple-carry adder under each single carry fault, over all 256 operand pairs, and how many each check catches

FaultWrongMod-3 residueParity, shared carriesParity, duplicated chainDuplicated chain and compareBerger prediction
c1c_1 stuck at 064640486464
c1c_1 stuck at 11921920144192192
c2c_2 stuck at 096960489696
c2c_2 stuck at 1160160080160160
c3c_3 stuck at 01121120112112112
c3c_3 stuck at 11441440144144144
All six7687680576768768

Source: reproduced by ch22_arithmetic_codes_and_checking_logic.py.

Of 768 wrong sums from a 4-bit adder with one stuck carry, how many each check catches 0 192 384 576 768 mod-3 residue check 768 of 768 parity, shared carries 0 of 768 parity, duplicated carry chain 576 of 768 duplicated chain and compare 768 of 768 Berger check prediction 768 of 768 wrong results caught 4-bit adder, carries c1 to c3 stuck at 0 or 1, all 256 operand pairs
Figure 5. Wrong sums caught by five checks on a 4-bit ripple-carry adder with each of the carries c1 to c3 stuck at 0 and at 1, over all 256 operand pairs. Data: computed by ch22_charts.py in the companion repository.

06.Self-Checking Circuits

Every check so far ends in a comparator. The parity checker of Lab: A First Hardware Checker has a single output wire, and a fault holding that wire at its no-error value looks like a healthy checker reading clean data, so the first real error after the fault goes through unseen. A checker has to be built so that its own faults show up.

The definitions concern a circuit whose inputs are meant to be codewords of an input code and whose outputs should be codewords of an output code. The faults considered are the single stuck-at faults on its lines, where a line is a gate output, a primary input or one branch of a wire that fans out to several gates.

A checker must be code-disjoint, so that bad data reaches its output as a non-codeword, and totally self-checking, so that ordinary data exposes its own faults. These definitions follow Anderson and Metze, who used them to design totally self-checking checkers for mm-out-of-nn codes [6]. They also explain why a checker needs two output wires. If a single output reads 0 for every code input, a fault holding it at 0 never changes the output on a code input, so the checker cannot be self-testing. The usual choice is a two-rail output, with 0101 and 1010 meaning no error and 0000 and 1111 meaning error.

The basic building block takes two two-rail signals (a,a′)(a, a') and (b,b′)(b, b'), healthy when a′=a‾a' = \overline{a} and b′=b‾b' = \overline{b}, and produces one two-rail signal (z,z′)(z, z') with

z=ab∨a′b′,z′=ab′∨a′b.z = a b \vee a' b' , \qquad z' = a b' \vee a' b .

Figure 6 draws the cell. Four AND gates form g1=abg_1 = ab, g2=a′b′g_2 = a'b', g3=ab′g_3 = ab' and g4=a′bg_4 = a'b, and two OR gates combine them in pairs. For the code inputs ab=00ab = 00, 0101, 1010 and 1111 the outputs are 1010, 0101, 0101 and 1010, so zz is the XNOR of aa and bb and z′z' is its complement.

The two-rail checker cell. Inputs arrive as two pairs (a, a') and (b, b'), each a code word when its rails differ. Four AND gates g1 to g4 and two OR gates form z = ab + a'b' and z' = ab' + a'b. On the four code inputs the outputs are 10, 01, 01 and 10, always a code word, and any non-code input gives z equal to z'. a a' b b' g1 g2 g3 g4 z z' z = ab + a'b' z' = ab' + a'b code inputs a b z z' 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 0 a non-code input, a = a' or b = b', gives z = z'
Figure 6. A two-rail checker cell built from four AND gates and two OR gates. Healthy two-rail inputs give a two-rail output, and any input with a = a' or b = b' gives z = z', which the next stage reads as an error.

Proof. The lines are the four input stems, the eight branches into the AND gates, the four AND outputs and the two OR outputs, 18 in all. For code-disjointness, if a=a′=ua = a' = u then z=ub∨ub′=u(b∨b′)z = ub \vee ub' = u(b \vee b') and z′=ub′∨ubz' = ub' \vee ub, the same value, so z=z′z = z'. The case b=b′b = b' is the same with the roles swapped. For fault-security, a fault on an input stem, whenever it changes the line, makes a non-code input, and code-disjointness then gives a non-code output. Every other line lies in the cone of only one output, since each branch feeds one AND gate and each AND gate feeds one OR gate, so the fault changes at most one of zz and z′z', turning 0101 or 1010 into 0000 or 1111. For self-testing, each AND gate is 1 on exactly one code input, g1g_1 on 1111, g2g_2 on 0000, g3g_3 on 1010 and g4g_4 on 0101. On that input the other gate feeding the same OR is 0, because g1g_1 and g2g_2 are never both 1 and neither are g3g_3 and g4g_4, so a stuck-at-0 on the gate or on either of its input branches drops the OR output. A gate output stuck at 1 shows on the two code inputs where its OR gate should give 0. A branch stuck at 1 shows on the code input where the gate's other input is 1 and the branch itself is 0, since the gate then turns on while its partner stays off. The two OR outputs each take both values over the code inputs, and each stem takes both values and turns a code input into a non-code one when it is wrong. ■\blacksquare

Table 4 shows what each code input contributes. Every one of the four detects 13 of the 36 faults, and every one is the only test for 5 of them, so all four code inputs are needed. For ab=11ab = 11 the five are g1g_1 stuck at 0, the branches of aa and bb into g1g_1 stuck at 0, the branch of b′b' into g3g_3 stuck at 1 and the branch of a′a' into g4g_4 stuck at 1. With ab=10ab = 10 and g1g_1 stuck at 1, the output becomes 1111, an error signal. A checker in service sees all four code inputs often, so its faults surface quickly.

Table 4. The four code inputs of the two-rail cell, the output each produces, how many of the 36 single stuck-at faults each detects and how many only it detects

Code input ababOutput zz′z z'Faults detectedFaults only it detects
0010135
0101135
1001135
1110135

Source: reproduced by ch22_arithmetic_codes_and_checking_logic.py.

Cells combine into trees that check any number of two-rail pairs, such as each carry of the duplicated chain paired with its complemented twin.

A parity checker can be made totally self-checking in a similar way. Split an 8-bit even-parity word into two halves, and compute f=(x0⊕x1)⊕(x2⊕x3)f = (x_0 \oplus x_1) \oplus (x_2 \oplus x_3) from the first and the complemented parity g=(x4⊕x5)⊕(x6⊕x7)‾g = \overline{(x_4 \oplus x_5) \oplus (x_6 \oplus x_7)} from the second. That takes six gates, four XOR gates at the first level, one XOR gate for ff and one XNOR gate for gg, and fourteen lines, the eight inputs, the four first-level outputs, ff and gg.

Proof. Let p1p_1 and p2p_2 be the parities of the two halves, so that f=p1f = p_1 and g=p2‾g = \overline{p_2}. An even word has p1=p2p_1 = p_2, so (f,g)=(p1,p1‾)(f, g) = (p_1, \overline{p_1}) is a two-rail codeword. An odd word has p1≠p2p_1 \ne p_2, so g=p2‾=p1=fg = \overline{p_2} = p_1 = f, a non-codeword. The two trees share no line, so a single fault changes at most one of ff and gg, and the output is either correct or 0000 or 1111. An XOR or XNOR gate passes a change in either input to its output, so a change on any line reaches the output of its tree. A line stuck at vv is therefore exposed by any code word on which that line holds v‾\overline{v}, and the three code words below make every line take both values. ■\blacksquare

The three words 0000000000000000, 0101010101010101 and 1011101110111011, written x0x_0 to x7x_7 from left to right, form a complete test. Every input is 0 in the first word and 1 in the second or the third. The four first-level outputs are all 0 in the first word and all 1 in the second, and across the three words ff takes the values 0, 0, 1 and gg the values 1, 1, 0. No two code words can do it. Each input must take both values, so the second word would have to be the complement of the first, and complementing both inputs of an XOR leaves its output unchanged, so the line x0⊕x1x_0 \oplus x_1 would hold the same value in both. The script confirms this by trying every fault on every code word, and finds that no pair of code words covers all 28 faults.

07.Checksums for Matrix Products

The same thinking scales up from gates to algorithms. Take the integer matrices

A=[210131024],B=[102310211],C=AB=[51412431464].A = \begin{bmatrix} 2 & 1 & 0 \\ 1 & 3 & 1 \\ 0 & 2 & 4 \end{bmatrix} , \qquad B = \begin{bmatrix} 1 & 0 & 2 \\ 3 & 1 & 0 \\ 2 & 1 & 1 \end{bmatrix} , \qquad C = A B = \begin{bmatrix} 5 & 1 & 4 \\ 12 & 4 & 3 \\ 14 & 6 & 4 \end{bmatrix} .

Append to AA a row holding its column sums, 3,6,53, 6, 5, and append to BB a column holding its row sums, 3,4,43, 4, 4. Multiplying the extended matrices gives

[5141012431914642431111153],\begin{bmatrix} 5 & 1 & 4 & 10 \\ 12 & 4 & 3 & 19 \\ 14 & 6 & 4 & 24 \\ 31 & 11 & 11 & 53 \end{bmatrix} ,

whose last column holds the row sums of CC, whose last row holds its column sums and whose corner holds 3⋅3+6⋅4+5⋅4=533 \cdot 3 + 6 \cdot 4 + 5 \cdot 4 = 53, the sum of every entry. Huang and Abraham introduced this scheme, which they called algorithm-based fault tolerance, for matrix operations on arrays of processors [7].

Proof. Multiply in blocks. The top-left block is ABAB. The top-right is A(Be)=(AB)eA(B\mathbf{e}) = (AB)\mathbf{e}, the bottom-left is (eTA)B=eT(AB)(\mathbf{e}^{\mathsf T} A) B = \mathbf{e}^{\mathsf T}(AB) and the corner is (eTA)(Be)=eT(AB)e(\mathbf{e}^{\mathsf T} A)(B \mathbf{e}) = \mathbf{e}^{\mathsf T}(AB)\mathbf{e}, each by associativity of the matrix product. Multiplying a matrix by e\mathbf{e} on the right adds up each of its rows, and by eT\mathbf{e}^{\mathsf T} on the left adds up each of its columns. ■\blacksquare

Now suppose the computation goes wrong at one entry, and c22c_{22} comes out as 9 instead of 4, as in Figure 7. The recomputed row sums of CC are 10, 24 and 24 against the stored 10, 19 and 24, and the column sums are 31, 16 and 11 against 31, 11 and 11. The gaps are 0, 5, 0 for the rows and 0, 5, 0 for the columns. Only row 2 and column 2 fail, so the wrong entry is where they cross, and both gaps say it is 5 too large. Subtracting gives 9−5=49 - 5 = 4.

The full checksum matrix of a 3-by-3 product with one wrong entry. The stored checksum column holds the row sums 10, 19 and 24 and the checksum row the column sums 31, 11 and 11. Entry (2, 2) reads 9 instead of 4, so row 2 now sums to 24 against 19 and column 2 to 16 against 11. Both are off by 5, which names the entry and the size of its error. 1 2 3 check 1 2 3 check 5 1 4 10 12 9 3 19 14 6 4 24 31 11 11 53 sum now 10 24 24 19 stored, off by 5 sum now 31 16 11 11 stored, off by 5 Row 2 and column 2 each miss their checksum by 5. The entry where they cross is the wrong one, and 9 − 5 = 4 restores it.
Figure 7. Locating a wrong entry of a matrix product from its checksums. Row 2 and column 2 each miss their checksum by 5, so the entry where they cross is the wrong one, and subtracting 5 restores the value 4.

Proof. The entry cijc_{ij} appears in exactly one row sum, that of row ii, and in exactly one column sum, that of column jj. Each of those sums is off by δ\delta, and every other row and column sum is untouched. ■\blacksquare

The script places the error at each of the nine positions in turn and locates and corrects it every time. If instead exactly one row check fails and no column check does, the fault lies in the checksum column itself, and the product is fine. The cost is small for large matrices. The extended product has (n+1)2(n + 1)^2 entries of nn products each, against n2n^2 entries for CC, so the extra work is a fraction (2n+1)/n2(2n + 1)/n^2 of the product, about 2/n2/n.

08.Looking Ahead

Every check in this chapter was judged against single faults. A code that catches every single error still lets through the multiple errors that carry one codeword onto another. The next chapter, Weight Distributions and Undetected Errors, counts the codewords of a linear code at each weight, turns those counts into the probability that a random error goes undetected, and proves the MacWilliams identity, which reads the weight distribution of a code off that of its dual.

09.Worked Examples

10.Exercises

References

  1. [1]Avizienis, Algirdas (1971). “Arithmetic Error Codes: Cost and Effectiveness Studies for Application in Digital System Design.” IEEE Transactions on Computers, C-20(11), pp. 1322–1331. doi:10.1109/T-C.1971.223134
  2. [2]Peterson, W. W. (1958). “On Checking an Adder.” IBM Journal of Research and Development, 2(2), pp. 166–168. doi:10.1147/rd.22.0166
  3. [3]Berger, J. M. (1961). “A Note on Error Detection Codes for Asymmetric Channels.” Information and Control, 4(1), pp. 68–73. doi:10.1016/S0019-9958(61)80037-5
  4. [4]Lo, Jien-Chung and Thanawastien, Suchai and Rao, T. R. N. and Nicolaidis, Michael (1992). “An SFS Berger Check Prediction ALU and Its Application to Self-Checking Processor Designs.” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 11(4), pp. 525–540. doi:10.1109/43.125100
  5. [5]Nicolaidis, Michael (2003). “Carry Checking/Parity Prediction Adders and ALUs.” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 11(1), pp. 121–128. doi:10.1109/TVLSI.2002.800526
  6. [6]Anderson, D. A. and Metze, G. (1973). “Design of Totally Self-Checking Check Circuits for m-Out-of-n Codes.” IEEE Transactions on Computers, C-22(3), pp. 263–269. doi:10.1109/T-C.1973.223705
  7. [7]Huang, Kuang-Hua and Abraham, Jacob A. (1984). “Algorithm-Based Fault Tolerance for Matrix Operations.” IEEE Transactions on Computers, C-33(6), pp. 518–528. doi:10.1109/TC.1984.1676475

— Anirban

Hardware–software at the seam where compilers meet microcode.

FeedbackBook modePaper
error-correction-codinglinear-block-codes