Binary Codes: BCD, Gray and Excess-3

A binary code assigns a bit pattern to each symbol of a set (decimal digits, angles of a shaft encoder, and so on). Pure binary is efficient for arithmetic, but other codes are built for decimal I/O, for single-bit-change sequencing, or for self-complementing digit arithmetic. This note covers three widely used codes: BCD (8421), Gray code, and Excess-3.

Binary codes are not named as a separate item in the GATE CS syllabus; they sit under number representation because decimal and positional encodings appear inside representation and combinational-design questions.

Binary-Coded Decimal encodes each decimal digit $0..9$ as its 4-bit binary value:

Patterns $1010$ to $1111$ are invalid in 8421 BCD. A multi-digit decimal number concatenates digit codes: $59_{10} = 0101\,1001_{\text{BCD}}$.

Weighted. BCD is a weighted code with weights 8, 4, 2, 1. Other decimal codes (2421, 84-2-1) exist; unless a question names them, "BCD" means 8421.

Cost of BCD. An $n$-digit decimal number takes $4n$ bits in BCD but only $\lceil n \lg 10 \rceil$ bits in pure binary: three digits (0 to 999) need 12 BCD bits against 10 binary bits. Only 10 of the 16 nibble patterns are used.

In 84-2-1 the weights are $8, 4, -2, -1$: $0111 = 4 - 2 - 1 = 1$. In 2421 some digits have two weighted forms (5 could be $0101$ or $1011$); the table uses the standard choice, which makes the code self-complementing. Both columns are self-complementing: the bitwise complement of digit $d$'s code is the code of $9 - d$.

The 7-bit ASCII code assigns $2^7 = 128$ symbols. Three useful ASCII facts are: digit characters run from $\texttt{0} = 48 = 30_{16}$ to $\texttt{9} = 57 = 39_{16}$, so the low nibble of a digit character is its BCD value; $\texttt{A} = 65 = 41_{16}$; and $\texttt{a} = 97 = 61_{16}$. Upper and lower case differ only in bit 5 (value 32).

Each decimal digit $d$ is encoded as the 4-bit binary of $d+3$:

Self-complementing. The 9's complement of a digit is the bitwise complement of its XS-3 code. Example: digit 2 is $0101$; digit 7 ($9-2$) is $1010 = \overline{0101}$. That property simplifies decimal subtraction hardware.

Invalid XS-3 patterns include $0000, 0001, 0010, 1101, 1110, 1111$.

A reflected Gray code of $n$ bits lists all $2^n$ patterns so that successive codes (including the wrap from last to first) differ in exactly one bit. The standard binary-reflected construction:

Conversion formulas (standard binary-reflected Gray):

Bit-by-bit example. Gray $1011$ to binary: $b_3 = 1$; $b_2 = 1 \oplus 0 = 1$; $b_1 = 1 \oplus 1 = 0$; $b_0 = 0 \oplus 1 = 1$. So Gray $1011$ is binary $1101 = 13$. Equivalently, each binary bit is the XOR (parity) of all Gray bits at or to its left.

Add BCD digits as binary. If the 4-bit sum exceeds 9, or a carry out of the nibble occurs, add correction $0110$ (six) and propagate the carry to the next digit. Full BCD adder design is a combinational exercise; the correction rule is what exams test.

Why six? A nibble holds 16 values but a decimal digit only 10. Adding 6 skips the six unused codes, so the nibble wraps exactly when the decimal digit should carry.

Correction as a Boolean function. With binary digit sum $K\,Z_8 Z_4 Z_2 Z_1$ ($K$ the carry out of the 4-bit adder), the decimal carry and correction signal is

The terms $Z_8 Z_4$ and $Z_8 Z_2$ are 1 exactly for the sums 10 to 15; $K$ covers 16 to 19 (the largest digit sum is $9 + 9 + 1 = 19$).

Example. $58 + 67$ in BCD:

Example: carry without a large nibble. $9 + 9 = 18$: $1001 + 1001 = 1\,0010$. The nibble $0010$ looks legal, but $K = 1$, so add six: $0010 + 0110 = 1000$, carry 1. Result $0001\,1000 = 18$.

In a shaft encoder, adjacent Gray positions differ in one bit, reducing ambiguous transitions caused by skew when several binary bits would change (for example, binary 7 to 8 changes all four bits). Karnaugh-map axes use Gray order for a different reason: adjacent cells then differ in exactly one Boolean variable, permitting that variable to be eliminated when cells are grouped. See Karnaugh Maps.

Costs for an $n$-bit word, counting loop iterations:

Unit-distance property. A code is a Gray code when the Hamming distance between codes of consecutive integers (mod $2^n$) is 1. The reflected construction yields a Hamiltonian path on the $n$-dimensional hypercube that also closes into a cycle.

Self-complementing codes. For a weighted decimal code with weights $w_3 w_2 w_1 w_0$, complementing every bit of the code of $d$ gives a pattern of weight $\sum w_i - d$. So $\sum w_i = 9$ is necessary for a weighted code to be self-complementing; it is sufficient only when the codeword choice is consistent, as in the standard 2421 and 84-2-1 tables (8421 has $\sum w_i = 15$ and is not self-complementing). Excess-3 is self-complementing even though it is unweighted: the code of $d$ is $d + 3$, its complement is $15 - (d + 3) = (9 - d) + 3$, which is the code of $9 - d$.

Gray parity. The XOR of all bits of the Gray code of $b$ equals $b_0$, the LSB of $b$. So Gray codes of even numbers have even parity and those of odd numbers have odd parity, which is a useful parity consistency check, not a proof of unit distance. For the latter, if incrementing binary $b$ flips its $t$ trailing ones and the preceding zero, then $d=b\mathbin{\mathrm{XOR}}(b+1)=2^{t+1}-1$. Hence $g(b)\mathbin{\mathrm{XOR}}g(b+1)=d\mathbin{\mathrm{XOR}}(d\gg1)=2^t$, exactly one set bit. The reflected construction also establishes the cyclic wrap-around.

Bit changes per cycle. Counting once round all $2^n$ values and back to 0, a Gray counter changes exactly one bit per step, $2^n$ changes in total. A binary counter changes bit $i$ $2^{n-i}$ times, $2^{n+1} - 2$ changes in total: for $n = 3$, 8 changes in Gray against 14 in binary. Fewer simultaneous changes means fewer glitches and lower switching power.

For $b = 13 = 1101_2$: $\textit{gray} = 1101 \oplus 0110 = 1011$. Applying GRAY-TO-BIN recovers 13. Checking all $0..15$ confirms a bijection.

Gray codes of 4 and 5 are $0110$ and $0111$ (for 4-bit): XOR $0001$, Hamming weight 1. Codes of 15 and 0: $1000$ and $0000$, weight 1 (wrap-around).

Digit 4 is $0111$; complement $1000$ is digit 5, and $4+5=9$. Digit 0 is $0011$; complement $1100$ is digit 9.

The 4-bit Gray code of 10 ($1010_2$) is $1010 \oplus 0101 = 1111$. Going back, $1111$ gives $b_3 = 1$, $b_2 = 0$, $b_1 = 1$, $b_0 = 0$, that is 10.

A table encodes 3 as $0110$ and 6 as $1001$. In BCD 3 is $0011$; in XS-3 it is $0110$, and XS-3 of 6 is $1001$. The two codes are complements, as XS-3 self-complementation predicts for digits that sum to 9.

Common misconceptions.