← Academy·Codes: BCD, Gray, ASCII, Parity and Hamming
⌗Core~35 min
Codes: BCD, Gray, ASCII, Parity and Hamming
The same bits can mean different things. Codes that suit displays, sensors, text and error checking.
Bits mean what we agree they mean
The pattern 0100 0001 has no meaning of its own. It could be the number 65, the letter A, or two decimal digits. A code is an agreement about what patterns stand for. Plain binary is best for arithmetic, but other jobs suit other codes.
BCD and Excess-3
Binary-coded decimal (BCD) stores each decimal digit in its own 4 bits. It's handy wherever numbers go straight to a display, such as clocks, meters and calculators, because each digit can drive its own display without any conversion.
Decimal 59 as…
Bits
Size
BCD
0101 1001
8 bits
Plain binary
111011
6 bits
BCD costs more bits. The patterns 1010 to 1111 are never used.
BCD arithmetic needs a correction. Adding 7 + 5 in binary gives 1100, which isn't a valid digit. If a digit goes above 9, add 6 to skip the six unused patterns: 1100 + 0110 = 1 0010, which reads as 1 and 2, or 12. Chapter 12 builds this as a circuit.
Excess-3 is BCD with 3 added to each digit, so 59 becomes 1000 1100. Its useful property is that it's self-complementing: inverting all the bits gives the code for 9 minus that digit. For example, 2 is 0101 and inverting gives 1010, which is the code for 7. That makes decimal subtraction easier to build.
Digit
BCD (8421)
2421
Excess-3
0
0000
0000
0011
1
0001
0001
0100
2
0010
0010
0101
3
0011
0011
0110
4
0100
0100
0111
5
0101
1011
1000
6
0110
1100
1001
7
0111
1101
1010
8
1000
1110
1011
9
1001
1111
1100
8421 and 2421 are named after the weights of their bits. Excess-3 has no fixed weights. 2421 is also self-complementing.
Gray code
In plain binary, going from 3 (011) to 4 (100) flips three bits at once. Real signals never switch at exactly the same moment, so for an instant a sensor could read anything, like 111 or 000. Gray code fixes this by making only one bit change between neighbours.
You can build it by reflecting. Take the list for n bits, write it again in reverse below, then put 0 in front of the top half and 1 in front of the bottom half.
Decimal
Binary
Gray
0
000
000
1
001
001
2
010
011
3
011
010
4
100
110
5
101
111
6
110
101
7
111
100
Each Gray code differs from the one above it in one bit, and the last wraps around to the first with one bit too.
Converting uses XOR, which outputs 1 when its two inputs differ. The top bit stays the same in both directions.
Binary to Gray: each Gray bit is the XOR of that binary bit and the one to its left. 1011 → 1110.
Gray to binary: each binary bit is the XOR of that Gray bit and the binary bit you just found to its left. 1110 → 1011.
> Loading the circuit…
Binary to Gray with three XOR gates. Both displays are in hex.
Set bin to B (1011). The output is E (1110), as in the rule above.
Count up and write down the outputs in binary. Only one bit changes per step.
> Loading the animation…
You'll meet Gray code again in rotary position sensors, in FIFO pointers that cross between clocks, and in K-maps, whose rows and columns follow Gray order so that neighbouring cells differ by one variable. That's what lets you spot simplifications at a glance. Here's a preview of Chapter 7:
Grouping
maj = bc + ac + ab
The majority function: the output is 1 when at least two inputs are 1. The columns run 00, 01, 11, 10, so neighbours differ in one bit, and each loop is one simple term.
ASCII: bits as text
ASCII gives each English letter, digit and symbol a 7-bit code. Unicode's UTF-8 encoding, used across the web today, keeps ASCII unchanged as its first 128 codes.
Character
Decimal
Hex
Binary
A
65
0x41
100 0001
a
97
0x61
110 0001
0
48
0x30
011 0000
The codes were arranged with care. Upper and lower case differ in one bit (0x20), so flipping that bit changes case. A digit character's value is its code minus 48, so the character '7' is 55 and 55 − 48 = 7.
Watch outA keypad or serial port sending the character 7 sends 55, not 7. Forgetting to subtract 48 is one of the most common bugs in serial projects.
Parity: spotting an error
Bits get flipped by noise on long wires and by radiation in memories. The simplest check adds one parity bit, chosen so that the total count of 1s is always even (even parity) or always odd (odd parity). The receiver counts the 1s, and a wrong count means something flipped.
The parity bit is just the XOR of the data bits, since XOR outputs 1 when the number of 1s at its inputs is odd.
> Loading the circuit…
An even parity generator for 4 data bits. The light turns on when the data has an odd number of 1s, making the total even.
Set the data to 1011. It has three 1s, so the parity bit is 1.
Flip any one switch. The parity bit always changes, which is how one flipped bit gets noticed.
NoteParity catches any odd number of flipped bits, but it misses an even number, because two flips leave the count even. It also can't tell you which bit is wrong.
Richard Hamming's idea was to use several parity bits, each checking a different group of positions, so that the pattern of failed checks spells out where the error is. Parity bits sit at positions that are powers of 2: 1, 2, 4, and so on. Each one covers every position whose number has that bit set.
Parity bit
Covers positions
Why
p1
1, 3, 5, 7
Numbers with bit 0 set
p2
2, 3, 6, 7
Numbers with bit 1 set
p4
4, 5, 6, 7
Numbers with bit 2 set
Worked example: Encode 1011 with Hamming(7,4)
Protect the data bits d1 d2 d3 d4 = 1 0 1 1, which go in positions 3, 5, 6 and 7.
p1 makes positions 1, 3, 5, 7 even: 1 + 0 + 1 is two 1s, so p1 = 0.
p2 makes positions 2, 3, 6, 7 even: 1 + 1 + 1 is three 1s, so p2 = 1.
p4 makes positions 4, 5, 6, 7 even: 0 + 1 + 1 is two 1s, so p4 = 0.
Write positions 1 to 7 in order: p1 p2 d1 p4 d2 d3 d4.
Answer:0110011
To check a received word, recompute all three parities. Each result, called c4, c2 and c1, is 0 if its group is still even. Read together as a binary number, c4c2c1 is the position of the wrong bit, and 000 means no single-bit error.
> Loading the circuit…
A Hamming(7,4) checker. The switches are the received bits and the display gives the position of the wrong one, or 0 if the word is fine.
Enter the codeword from above: p1=0, p2=1, d1=1, p4=0, d2=0, d3=1, d4=1. The display shows 0.
Now flip d2, which is position 5. The display shows 5.
Flip it back, then flip any other switch. The display always names the switch you flipped.
Worked example: Finding an error
You sent 0110011 and received 0110111. Which bit is wrong?
c1 checks positions 1, 3, 5, 7: 0, 1, 1, 1 has three 1s, so c1 = 1.
c2 checks positions 2, 3, 6, 7: 1, 1, 1, 1 has four 1s, so c2 = 0.
c4 checks positions 4, 5, 6, 7: 0, 1, 1, 1 has three 1s, so c4 = 1.
c4c2c1 = 101, which is 5.
Answer:Position 5 is wrong. Flip it to get back 0110011.
How many parity bits do you need? With m data bits and p parity bits, the checks must be able to name each of the m + p positions, plus "no error":
2ᵖ ≥ m + p + 1
For m = 4, p = 3 works because 8 ≥ 8. For m = 8 you need p = 4 because 16 ≥ 13, while p = 3 gives only 8.
Hamming distanceGATE: fine to skip at first
The Hamming distance between two words is the number of positions where they differ. The distance of a code, d, is the smallest distance between any two of its valid codewords. It sets what the code can do:
To…
You need
Detect up to s errors
d ≥ s + 1
Correct up to t errors
d ≥ 2t + 1
Simple parity has d = 2, so it detects 1 error and corrects none. Hamming(7,4) has d = 3, so it detects 2 errors or corrects 1. Memory chips with error correction commonly add one more overall parity bit, for d = 4: correct 1 error and also detect 2.
Practice · GATE-style
What is the minimum number of parity bits needed to correct a single-bit error in 11 data bits?
Practice · GATE-style
A code's codewords are 00000, 01011, 10101 and 11110. How many errors can it correct?