Binary Codes: BCD, Gray, Excess-3 and ASCII

1 Weighted Codes: 8421, 2421 and 5211

A code is weighted if each bit position carries a fixed numerical weight and the decimal digit is the sum of the weights where a 1 appears. This is the same weighted-sum idea as Chapter 2, except that the weights no longer have to be powers of a base — they are chosen by whoever designed the code.

The most familiar is 8421 BCD, whose weights are the ordinary binary ones, so each decimal digit is written exactly as it would be in four-bit binary. Only 0000 through 1001 are used; the six patterns 1010 to 1111 are invalid and, if they appear, indicate a fault or an uncorrected arithmetic result of the kind Chapter 3 dealt with. A reading of 947 is stored as three separate groups, 1001 0100 0111, and not as the binary number 947, which is 1110110011. The two are different things.

Two other weighted codes appear in syllabuses and are worth being able to decode on sight. The 2421 code (also called the Aiken code) has weights 2, 4, 2 and 1. The digit 5 is 1011, since \(2+2+1 = 5\); the digit 8 is 1110, since \(2+4+2 = 8\). Because the weights sum to 9 rather than 15, some digits could be written more than one way — 5 is also \(4+1\), which is 0101 — and the code fixes the ambiguity by a rule: digits 0 to 4 take the pattern with a 0 in the leading position and digits 5 to 9 take the pattern with a 1 there. Section 2 shows what that rule buys.

The 5211 code has weights 5, 2, 1 and 1. Here 7 is 1011, since \(5+1+1 = 7\), and 3 is 0101, since \(2+1 = 3\). Its practical attraction is that the leading bit is 1 for exactly the digits 5 to 9, so a single wire divides the decade in half — useful in a counter that must round or divide by two.

Packed BCD stores two digits in one byte, which is why a real-time clock returns 0x59 for fifty-nine seconds rather than 0x3B. Reading that register as ordinary binary gives 89.

2 Unweighted Codes and the Self-Complementing Property

An unweighted code assigns patterns to digits by a rule that is not a weighted sum at all. The two that matter here are Excess-3 and Gray.

Excess-3 is the plain binary value of the digit plus three, so 0 is 0011 and 9 is 1100. No set of four weights reproduces that table — in particular any weighted code must give 0000 for zero, and Excess-3 does not. The offset looks arbitrary until you notice what it does to complements.

A code is self-complementing if inverting every bit of the pattern for a digit \(D\) produces the pattern for \(9-D\). Test Excess-3 on \(D = 2\): the pattern is 0101, its bitwise inverse is 1010, and 1010 is the Excess-3 pattern for 7, which is indeed \(9-2\). The reason is algebraic rather than lucky. The stored value is \(D+3\); inverting a four-bit value \(v\) gives \(15-v\), so the inverse holds \(15-(D+3) = 12-D\), and \(12-D = (9-D)+3\), which is precisely the Excess-3 pattern for \(9-D\). The offset of 3 is what makes the arithmetic close.

The test fails immediately for 8421. Take \(D = 4\), pattern 0100; its inverse is 1011, which is not a valid BCD pattern at all, let alone the pattern for 5. It succeeds for 2421 on every row, and that is the whole reason the awkward duplicate-pattern rule of the previous section was chosen the way it was: \(D=4\) is 0100, whose inverse 1011 is the 2421 pattern for 5. The 5211 code passes on some digits and fails on others — \(D=1\) is 0001, whose inverse 1110 is not the 5211 pattern for 8, which is 1101 — and a code that works on only some rows is of no use, because the hardware cannot know which row it is holding.

Converting between codes is a small combinational design problem. Excess-3 from BCD is simply “add 0011” — a four-bit adder with a constant, or four gates once minimised. Chapter 20 designs these converters properly, using the technique of Chapter 8, where the six unused BCD patterns become don't-care conditions that shrink the result considerably.

3 The Gray Code and Its Conversions

The Gray code, also called the reflected binary code, orders the \(2^n\) patterns so that any two consecutive entries differ in exactly one bit. That single property is the whole point of it; the code carries no useful weights and you cannot do arithmetic in it.

It is built by reflection, which is where the other name comes from. Start with the one-bit list 0, 1. To extend to \(n+1\) bits: write the \(n\)-bit list, then write it again underneath in reverse order, and prefix 0 to every entry in the first half and 1 to every entry in the second. The mirror line guarantees that the two entries straddling it differ only in the new leading bit, and every other adjacent pair inherits its single-bit difference from the shorter list. Three bits give 000, 001, 011, 010, 110, 111, 101, 100 — and the last entry differs from the first in one bit too, so the sequence is cyclic, which is what a rotating shaft needs.

That ordering will reappear in Chapter 8: the rows and columns of a Karnaugh map are labelled in Gray order precisely so that physically adjacent cells differ in one variable, which is what makes grouping them a valid simplification.

Reflection is fine for building a table but useless for converting one number. For that there are two formulas, and both are pure exclusive-OR. Writing the binary word as \(B_{n-1}\ldots B_0\) and the Gray word as \(G_{n-1}\ldots G_0\):

The two look almost identical but behave very differently in hardware. In the first, every output depends only on the original inputs, so all the gates work at once and the conversion costs one gate delay. In the second, each output depends on the output above it, so the gates form a chain \(n-1\) deep.

4 Why the Gray Code Exists: The Shaft Encoder

An absolute shaft encoder reports the angular position of a rotating shaft. A disc fixed to the shaft carries \(n\) concentric tracks of conducting and insulating sectors, and \(n\) brushes or optical sensors read one bit from each. Three tracks divide the disc into eight sectors.

Pattern the tracks in natural binary and the encoder works perfectly — as long as the shaft never moves. The trouble is at the boundaries. Going from position 3 to position 4, the code goes from 011 to 100 and all three bits change. No mechanical assembly aligns three brushes to better than a fraction of a sector, so for a brief interval one track has already switched and another has not. The reading during that interval is neither 3 nor 4 but whatever combination the misalignment produces — possibly 000, which is 0, or 111, which is 7.

That is not a small inaccuracy but a wrong answer at the far end of the range, arriving briefly and repeatedly at one particular angle. A control loop reading such an encoder receives a violent spurious error every revolution, in the same place each time, and will act on it.

Figure 4.1 makes the comparison directly. At the 3 → 4 boundary the binary tracks change from 011 to 100, three simultaneous transitions; the Gray tracks change from 010 to 110, one transition on the outermost track. Every boundary behaves that way, including the wrap from 7 back to 0.

The price is that the encoder delivers a number the rest of the system cannot use directly, so a Gray-to-binary converter sits immediately after it — the cascade in the lower half of Figure 4.2, developed as a standard code converter in Chapter 20. The same single-bit-change argument recurs later: it is why the Johnson counter of Chapter 26 decodes without glitches, and it underlies the hazards of Chapter 11, where a circuit misbehaves precisely because two inputs did not change at quite the same instant.

5 ASCII and Error Detection by Parity

Text needs a code too. ASCII, the American Standard Code for Information Interchange, assigns a seven-bit pattern to each of 128 characters: 95 printable ones and 33 control codes — enough for the Latin alphabet in both cases, the digits, punctuation, and the control characters a teleprinter needed.

Three regularities make the table worth understanding rather than memorising. The digits 0 to 9 occupy 0x30 to 0x39, so the low four bits of a digit character are its BCD value and converting between the two is a matter of adding or subtracting 0x30. Upper-case letters run from 0x41 (A) to 0x5A (Z) and lower-case from 0x61 (a) to 0x7A (z), so the two cases differ in exactly one bit, \(b_5\); changing case is one XOR with 0x20, not a table lookup. And the control codes occupy 0x00 to 0x1F, which is why carriage return is 0x0D and line feed 0x0A.

A seven-bit character sits awkwardly in an eight-bit byte, and the spare bit was traditionally used for a parity bit. In even parity it is chosen so that the total number of 1s in the transmitted word is even; in odd parity, odd. Chapter 17 builds the generator and the checker — both are a tree of exclusive-OR gates, because an XOR of many inputs is 1 exactly when an odd number of them are 1.

What parity cannot do is as important as what it can. A single parity bit detects any odd number of bit errors and is completely blind to any even number: if two bits flip, the count changes by zero, two or minus two, and its parity is unaltered. Nor can parity say which bit is wrong, so the only recovery is to ask for the message again. Where retransmission is impossible — a memory read, a signal already in flight from a spacecraft — detection is not enough, and the next section shows what more redundancy buys.

6 The Hamming Code: Locating a Single Error

Parity gives a single yes-or-no answer. Hamming's idea is to use several parity bits, each covering a different overlapping subset of the word, so that the pattern of failed checks identifies the guilty bit — and if the subsets are chosen well, that pattern is the bit's position number written in binary.

Start with how many check bits are needed. With \(k\) check bits there are \(2^k\) possible patterns of check results. One of them must mean “no error”, and each of the \(m+k\) positions in the code word needs one of the rest. So

For \(m=4\) data bits, \(k=3\) satisfies it (\(8 \ge 8\)), giving the classic (7, 4) code. For \(m=8\), \(k=3\) fails (\(8 < 12\)) but \(k=4\) works (\(16 \ge 13\)), giving a 12-bit word. For \(m=16\), \(k=5\); for \(m=32\), \(k=6\) — the overhead falls as the word grows, which is why memory error correction is applied to wide words.

The placement is what makes the scheme work. Number the positions of the code word from 1 on the left, and put the check bits at the positions that are powers of two — 1, 2, 4, 8 — leaving every other position for data. Check bit \(P_p\) then covers every position whose number has a 1 in bit \(p\), including its own. So \(P_1\) covers 1, 3, 5, 7, 9, 11; \(P_2\) covers 2, 3, 6, 7, 10, 11; \(P_4\) covers 4, 5, 6, 7, 12; and \(P_8\) covers 8, 9, 10, 11, 12. Each check bit is set so that its group has even parity.

Now suppose exactly one bit is corrupted, at position \(e\). Every check whose group contains position \(e\) fails; every check whose group does not, passes. By construction the checks that contain \(e\) are exactly those whose bit is 1 in the binary expansion of \(e\). Assemble the results as \(C_8C_4C_2C_1\), taking 1 for a failed check, and the number you have written is \(e\) itself. That word is the syndrome. A syndrome of zero means no single error was present.

The limits follow from counting. A Hamming code has a minimum distance of 3 between valid code words, so it corrects one error or detects two, but not both at once — two errors produce a non-zero syndrome that points confidently at an innocent third position. Adding one more overall parity bit over the whole word raises the distance to 4 and gives the SECDED code (single error correction, double error detection) used in server memory, where the extra bit distinguishes “one error, corrected” from “two errors, give up and report”. Chapter 27 returns to this when it discusses what a memory subsystem does about soft errors.

7 Summary and Key Results

8 Common Mistakes

9 Chapter Review