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 should return . 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 . 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 , 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 -bit words. Bit has its own full adder, which takes the operand bits and and the carry from the stage below, and produces a sum bit and a carry for the stage above. Read as integers, the three inputs and two outputs of every full adder satisfy
So is the low bit of a three-way count and is its high bit. The carry into bit 0 is normally 0, and out of the top stage is the carry-out, which sits above the sum bits as bit of the result.
Take and . In bit 3 both operands hold a 1, so and . Bits 4 to 14 of are all 1, so each of those stages writes 0 and passes the carry upward, until it comes to rest as . The sum is , and twelve carries, to , are 1 along the way.
Now hold the wire at 0. Stage 4 sees , so it writes and passes no carry, and every stage above does the same. The adder returns . Figure 1 lines up both results bit by bit, and bits 4 to 15 of the faulty sum are all wrong.
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 has twelve ones, so , and , which predicts a sum of parity 1. The correct sum has a single 1, so the check passes it. The faulty sum 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 the operand parities XOR to 0, but the sum 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 and so follow , not .
The useful measure of the error is its size, . A single flipped bit in a stored word has the same shape, adding or subtracting .
So , and because , though 7 has three ones. Eleven needs three terms whichever way it is written, so . The number has eight ones but arithmetic weight 2, and so does . 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 never see the line , so they produce the same sum bits and the same carry as in a healthy adder. Let and be the low bits of the operands and let be the number those low sum bits form, so that . Stages to are a healthy adder for the high parts and with carry-in , so the high sum bits and the carry-out together hold . The faulty result is therefore , while . Subtracting gives , and since and are bits, the difference is , or .
In the 16-bit example , and , so the error is , as computed. The script checks the theorem on a 6-bit adder with each carry from to 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 . Exactly half are wrong because, for each line, one of its two stuck values is wrong on every operand pair.
02.AN Codes
Choose and store every number as , so is stored as . Since , the adder needs no change. If a carry fault adds 4, the adder returns 19, and shows the error.
Avizienis compared the cost and effectiveness of such arithmetic codes for real arithmetic units, singling out multipliers of the form whose remainders are cheap to compute [1].
Not every multiplier works. With , the value is stored as 20, and the error gives 24, which is a multiple of 4, so the error slips through. In remainder terms, . The trouble is that 4 divides the error.
Proof. A received word is a multiple of exactly when divides . The only divisors of are powers of two, and an odd is not one, so .
An even multiplier with odd also detects every single error, but its codewords end in zeros that carry nothing, and does all the work. The useful multipliers are the odd ones.
Proof. The largest codeword for is . It is at least , because when , and it is below , so it needs exactly bits. An AN code that adds at most one bit needs , so , which leaves only . That multiplier is a power of two and misses the error , since .
The script tries every 8-bit data value with , whose codewords have 10 bits, against each of the 20 errors 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 , and since , the remainder equals . 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, distinct nonzero remainders must fit among the nonzero values, so .
The multiplier protects 4 data bits. Its largest codeword is , so , 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 , 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 | ||
|---|---|---|
| 0 | 1 | 18 |
| 1 | 2 | 17 |
| 2 | 4 | 15 |
| 3 | 8 | 11 |
| 4 | 16 | 3 |
| 5 | 13 | 6 |
| 6 | 7 | 12 |
| 7 | 14 | 5 |
| 8 | 9 | 10 |
Source: reproduced by ch22_arithmetic_codes_and_checking_logic.py.
At 10 bits the code fails, because , which is the remainder of . The errors and then look alike. The next theorem says where such a collision first appears, using the order of 2, the least with . Groups and Cosets defined the order of an element, and Euler's theorem from Integers and Modular Arithmetic guarantees that it exists, because whenever is odd. For the order is 18, and .
Proof. Since is odd, 2 has an inverse modulo , so no power of 2 is 0 and every remainder is nonzero. Two plus signs collide, with , exactly when , that is when divides , so the values are distinct exactly when , and the same holds for the values . A plus and a minus collide, with , exactly when . The case would need , which is impossible. If no power of 2 is , nothing more can collide and . Otherwise let be the least exponent with . Then , so divides . Since for , does not divide , and because would otherwise be a smaller solution. With and , the only choice is . Now for only at , so a plus and a minus collide exactly when some difference equals , which first happens at .
An odd order cannot equal , so when is odd, is never a power of 2 and . For the order is 3, so the longest correctable word has 3 bits. For the order is 11 and the longest word has 11 bits. The script checks the theorem against a direct search for every odd below 100.
The smallest multiplier for data bits is the least odd whose reaches the length 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 the order of 2 modulo 47 is 23, which is odd, so 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 | Multiplier | Length | Check bits | Order of 2 | |
|---|---|---|---|---|---|
| 4 | 19 | 9 | 5 | 18 | 9 |
| 8 | 29 | 13 | 5 | 28 | 14 |
| 12 | 37 | 18 | 6 | 36 | 18 |
| 16 | 47 | 22 | 6 | 23 | 23 |
| 32 | 79 | 39 | 7 | 39 | 39 |
Source: reproduced by ch22_arithmetic_codes_and_checking_logic.py.
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 signed errors where the Hamming code tells apart bit flips. AN codes also suit a multiplier poorly, since must be divided by before it is a codeword again. The next code avoids that.
03.Residue Codes
Take and . Both leave remainder 1 on division by 3. Their sum 35 leaves 2, which is , and their product 286 leaves 1, which is . 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 and with . Then differs from by a multiple of , and differs from by a multiple of . Numbers that differ by a multiple of leave the same remainder.
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 , 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 , and only equals . Since , the carry-out adds to the residue of , which costs one more mod-3 adder. Comparing alone would raise a false alarm on all 2,147,450,880 operand pairs that carry out, nearly half of the 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 generator for a general modulus is a divider, which is far too costly to sit beside an adder. A modulus of the form needs only additions.
Proof. Since , it follows that , and so for every . Each term is therefore congruent to , and the sum to the sum. A carry out of an -bit adder has weight , so adding it back at bit 0 keeps the total congruent.
Take and , the case of mod 3, since . The 2-bit chunks, lowest first, are 1, 1, 3 and 2, which sum to 7. Folding 7 the same way gives , and folding 4 gives , which is . With the chunks are 5 and 11, which sum to 16, and folding 16 gives 1, which is . The script checks the fold for , 3 and 4 on every 12-bit word.
One detail needs care. In -bit arithmetic modulo the all-ones pattern also means zero, so for mod 3 the chunk stands for 3, which is 0. A hardware generator first reduces each 2-bit chunk to the range 0 to 2 with a small block , which computes , and . For the chunks , and , passes them through unchanged, and for it gives and hence .
Two reduced residues and then go to a mod-3 adder. With , which is 1 exactly when , and likewise, the outputs are and . The bit is 1 for the sums , and , and is 1 for , and . The output never reads , 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.
Figure 4 assembles the generator for a 16-bit word. Its eight chunks need eight 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 block is two gate levels deep and each adder three, NOR then AND then OR, so the three adder levels give a depth of . 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 to at 0 and at 1 gives six faults, and over all 256 operand pairs they make 1,536 cases, 768 of them wrong. For with stuck at 0 the adder returns 2, whose residue 2 differs from the predicted . 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 data bits the number of zeros in , written as a binary number [3]. Write for the number of ones in an -bit word and for its Berger symbol, which is . 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 in a 4-bit adder. With and , the sum bits are and the carry-out is . The carries to are . Counting ones, , and the carries hold 3. The combination is exactly the number of ones in the sum bits .
Proof. Add the relation Equation 1 over . The left side gives , and the carry sum equals . The right side gives . Setting the two equal and solving for gives , which is the claim.
The carry chain has outputs, to , so write for its zeros. Replacing every count of ones by minus a count of zeros turns the theorem into the Berger prediction.
For this reads , and the sum bits 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 obeys Equation 1 with the values on the lines. Stage obeys it with in place of the line value , so it obeys the line-value form with an extra on its right side. Adding the stages as in the previous proof gives , where and are read from the lines. The predictor computes everything but the last term, so the two counts differ by , which is when and 0 otherwise. By Equation 2 the result is wrong exactly when .
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, , and XOR is associative and commutative, so the following holds.
Proof. XOR the relations over and regroup the right side into the operand bits, the other operand's bits and the carries.
For the parities are , and , which predicts 1, and the sum bits have parity 1. The prediction is the ones count of Equation 6 read modulo 2, since enters that count twice and vanishes, while 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 , 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 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 to differ between the chains. The 16-bit fault from the start of the chapter changes twelve carries, to , 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 never escape the duplicated chain, because among to only 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
| Fault | Wrong | Mod-3 residue | Parity, shared carries | Parity, duplicated chain | Duplicated chain and compare | Berger prediction |
|---|---|---|---|---|---|---|
| stuck at 0 | 64 | 64 | 0 | 48 | 64 | 64 |
| stuck at 1 | 192 | 192 | 0 | 144 | 192 | 192 |
| stuck at 0 | 96 | 96 | 0 | 48 | 96 | 96 |
| stuck at 1 | 160 | 160 | 0 | 80 | 160 | 160 |
| stuck at 0 | 112 | 112 | 0 | 112 | 112 | 112 |
| stuck at 1 | 144 | 144 | 0 | 144 | 144 | 144 |
| All six | 768 | 768 | 0 | 576 | 768 | 768 |
Source: reproduced by ch22_arithmetic_codes_and_checking_logic.py.
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 -out-of- 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 and meaning no error and and meaning error.
The basic building block takes two two-rail signals and , healthy when and , and produces one two-rail signal with
Figure 6 draws the cell. Four AND gates form , , and , and two OR gates combine them in pairs. For the code inputs , , and the outputs are , , and , so is the XNOR of and and is its complement.
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 then and , the same value, so . The case 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 and , turning or into or . For self-testing, each AND gate is 1 on exactly one code input, on , on , on and on . On that input the other gate feeding the same OR is 0, because and are never both 1 and neither are and , 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.
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 the five are stuck at 0, the branches of and into stuck at 0, the branch of into stuck at 1 and the branch of into stuck at 1. With and stuck at 1, the output becomes , 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 | Output | Faults detected | Faults only it detects |
|---|---|---|---|
| 00 | 10 | 13 | 5 |
| 01 | 01 | 13 | 5 |
| 10 | 01 | 13 | 5 |
| 11 | 10 | 13 | 5 |
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 from the first and the complemented parity from the second. That takes six gates, four XOR gates at the first level, one XOR gate for and one XNOR gate for , and fourteen lines, the eight inputs, the four first-level outputs, and .
Proof. Let and be the parities of the two halves, so that and . An even word has , so is a two-rail codeword. An odd word has , so , a non-codeword. The two trees share no line, so a single fault changes at most one of and , and the output is either correct or or . 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 is therefore exposed by any code word on which that line holds , and the three code words below make every line take both values.
The three words , and , written to 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 takes the values 0, 0, 1 and 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 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
Append to a row holding its column sums, , and append to a column holding its row sums, . Multiplying the extended matrices gives
whose last column holds the row sums of , whose last row holds its column sums and whose corner holds , 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 . The top-right is , the bottom-left is and the corner is , each by associativity of the matrix product. Multiplying a matrix by on the right adds up each of its rows, and by on the left adds up each of its columns.
Now suppose the computation goes wrong at one entry, and comes out as 9 instead of 4, as in Figure 7. The recomputed row sums of 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 .
Proof. The entry appears in exactly one row sum, that of row , and in exactly one column sum, that of column . Each of those sums is off by , and every other row and column sum is untouched.
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 entries of products each, against entries for , so the extra work is a fraction of the product, about .
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]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]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]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]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]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]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]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.