The simpler and more robust version encodes 4 bits of data in one 8-bit byte. This code is used extensively to protect the fields that have meaning to the Teletext system itself. The more efficient code encodes 18 bits of data in three 8-bit bytes. It is used for to protect some of the data fields inside Teletext packets. Both codes are designed such that any one-bit error can be corrected, and any 2-bit error can be detected.
b3, b2, b1, b0
with b3 being the most significant bit,
then the output hammed byte is the 8-bit value:
b3, b3^b2^b1, b2, !b2^b1^b0, b1, !b3^b1^b0, b0, !b3^b2^b0
where ^ represents bitwise exclusive-or and ! is bitwise not.
This code has the property that every value is four bits different from all other such values. A one-bit error is therefore unambiguously correctable, being only one bit away from a valid code. A two-bit error is detectable but not correctable, being equidistant between two valid codes.
Here is the table of all 16 encoded nibbles:
Data nibble Hammed byte
0 = 0 0 0 0 15 = 0 0 0 1 0 1 0 1
1 = 0 0 0 1 02 = 0 0 0 0 0 0 1 0
2 = 0 0 1 0 49 = 0 1 0 0 1 0 0 1
3 = 0 0 1 1 5E = 0 1 0 1 1 1 1 0
4 = 0 1 0 0 64 = 0 1 1 0 0 1 0 0
5 = 0 1 0 1 73 = 0 1 1 1 0 0 1 1
6 = 0 1 1 0 38 = 0 0 1 1 1 0 0 0
7 = 0 1 1 1 2F = 0 0 1 0 1 1 1 1
8 = 1 0 0 0 D0 = 1 1 0 1 0 0 0 0
9 = 1 0 0 1 C7 = 1 1 0 0 0 1 1 1
A = 1 0 1 0 8C = 1 0 0 0 1 1 0 0
B = 1 0 1 1 9B = 1 0 0 1 1 0 1 1
C = 1 1 0 0 A1 = 1 0 1 0 0 0 0 1
D = 1 1 0 1 B6 = 1 0 1 1 0 1 1 0
E = 1 1 1 0 FD = 1 1 1 1 1 1 0 1
F = 1 1 1 1 EA = 1 1 1 0 1 0 1 0
| | | | | | | | | | | |
b3b2b1b0 b3 |b2 |b1 |b0 |
| | | |
321 !210 !310 !320
Decoding a hammed byte back in to a 4-bit nibble can
be done using the table below, or by a bit-twiddling algorithm.
In the table, the hammed byte value is used to index
the row (most significant 4 bits) and column (least
significant four bits), and the decoded nibble is read
out of the table.
If a single bit error has been detected and corrected,
the nibble is followed by ``!''.
If an uncorrecteable error has occurred, the table
cell is ``.''.
LSB
| 0 1 2 3 4 5 6 7 8 9 A B C D E F |
MSB+------------------------------------------------+---
0 | 1! . 1 1! . 0! 1! . . 2! 1! . A! . . 7!| 0
1 | . 0! 1! . 0! 0 . 0! 6! . . B! . 0! 3! . | 1
2 | . C! 1! . 4! . . 7! 6! . . 7! . 7! 7! 7 | 2
3 | 6! . . 5! . 0! D! . 6 6! 6! . 6! . . 7!| 3
4 | . 2! 1! . 4! . . 9! 2! 2 . 2! . 2! 3! . | 4
5 | 8! . . 5! . 0! 3! . . 2! 3! . 3! . 3 3!| 5
6 | 4! . . 5! 4 4! 4! . . 2! F! . 4! . . 7!| 6
7 | . 5! 5! 5 4! . . 5! 6! . . 5! . E! 3! . | 7
8 | . C! 1! . A! . . 9! A! . . B! A A! A! . | 8
9 | 8! . . B! . 0! D! . . B! B! B A! . . B!| 9
A | C! C . C! . C! D! . . C! F! . A! . . 7!| A
B | . C! D! . D! . D D! 6! . . B! . E! D! . | B
C | 8! . . 9! . 9! 9! 9 . 2! F! . A! . . 9!| C
D | 8 8! 8! . 8! . . 9! 8! . . B! . E! 3! . | D
E | . C! F! . 4! . . 9! F! . F F! . E! F! . | E
F | 8! . . 5! . E! D! . . E! F! . E! E . E!| F
---+------------------------------------------------+---
| 0 1 2 3 4 5 6 7 8 9 A B C D E F |
The algorithmic approach shows what is going on more clearly. Assuming the hammed byte is
h7, h6, h5, h4, h3, h2, h1, h0
with h7 being the most significant bit,
we compute
p = h7 ^ h6 ^ h5 ^ h4 ^ h3 ^ h2 ^ h1 ^ h0
c0 = h7 ^ h5 ^ h1 ^ h0
c1 = h7 ^ h3 ^ h2 ^ h1
c2 = h5 ^ h4 ^ h3 ^ h1
If the parity, p, is correct (equal to 1)
then either 0 or 2 errors occurred.
If all the check bits, c0, c1,
c2 are correct (equal to 1)
then the byte was received intact,
(no errors) otherwise it was damaged beyond repair (two errors).
If p is 0, then there was a single bit error
which can be recovered:
c0 c1 c2 meaning
1 1 1 error in bit h6
1 1 0 error in bit h4
1 0 1 error in bit h2
0 1 1 error in bit h0
0 0 1 error in bit h7
0 1 0 error in bit h5
1 0 0 error in bit h3
0 0 0 error in bit h1
The erroneous bit should be flipped.
Note that there is actually no need to fix errors in bits
h6, h4, h2 and h0
since they are not used in the decoded byte.
After flipping bits if necessary, the decoded byte is then:
h7, h5, h3, h1
Assuming the input bits are:
b17, b16, b15, b14, b13, b12, b11, b10, b9, b8,
b7, b6, b5, b4, b3, b2, b1, b0
with b17 being the most significant bit,
the six hamming check bits are:
c0 = ! b17 ^ b15 ^ b13 ^ b11 ^ b10 ^ b8 ^ b6 ^ b4 ^ b3 ^ b1 ^ b0
c1 = ! b17 ^ b16 ^ b13 ^ b12 ^ b10 ^ b9 ^ b6 ^ b5 ^ b3 ^ b2 ^ b0
c2 = ! b17 ^ b16 ^ b15 ^ b14 ^ b10 ^ b9 ^ b8 ^ b7 ^ b3 ^ b2 ^ b1
c3 = ! b10 ^ b9 ^ b8 ^ b7 ^ b6 ^ b5 ^ b4
c4 = ! b17 ^ b16 ^ b15 ^ b14 ^ b13 ^ b12 ^ b11
c5 = b17 ^ b14 ^ b12 ^ b11 ^ b10 ^ b7 ^ b5 ^ b4 ^ b2 ^ b1 ^ b0
where ^ represents bitwise exclusive-or and ! is bitwise not.
c5 can alternatively and equivalently be computed as
the odd parity of all the other data and check bits.
The output bytes are then:
c3, b3, b2, b1, c2, b0, c1, c0
c4, b10, b9, b8, b7, b6, b5, b4
c5, b17, b16, b15, b14, b13, b12, b11
in byte transmission order, with the most significant bit
of each byte on the left.
To decode a hammed byte triplet:
h7, h6, h5, h4, h3, h2, h1, h0
h15, h14, h13, h12, h11, h10, h9, h8
h23, h22, h21, h20, h19, h18, h17, h16
with h0 being the least significant bit of the first byte
and h23 being the most significant bit of the third byte,
we compute
p = h23 ^ h22 ^ h21 ^ h20 ^ ... ^ h1 ^ h0
c0 = h0 ^ h2 ^ h4 ^ h6 ^ h8 ^ h10 ^ h12 ^ h14 ^ h16 ^ h18 ^ h20 ^ h22
c1 = h1 ^ h2 ^ h5 ^ h6 ^ h9 ^ h10 ^ h13 ^ h14 ^ h17 ^ h18 ^ h21 ^ h22
c2 = h3 ^ h4 ^ h5 ^ h6 ^ h11 ^ h12 ^ h13 ^ h14 ^ h19 ^ h20 ^ h21 ^ h22
c3 = h7 ^ h8 ^ h9 ^ h10 ^ h11 ^ h12 ^ h13 ^ h14
c4 = h15 ^ h16 ^ h17 ^ h18 ^ h19 ^ h20 ^ h21 ^ h22
If the parity, p, is correct (equal to 1)
then either 0 or 2 errors occurred.
If all the check bits, c0, c1,
c2, c3, c4, c5
are correct (equal to 1), then the byte was received intact,
(no errors) otherwise it was damaged beyond repair (two errors).
If p is 0, then there was a single bit error
which can be recovered.
For the check bits which are incorrect (equal to 0), add the
following powers of two together:
if c0 = 0 add 1
if c1 = 0 add 2
if c2 = 0 add 4
if c3 = 0 add 8
if c4 = 0 add 16
The sum gives the bit position 1--24 corresponding to h0--h23
which is in error.
The erroneous bit should be flipped.
Note that there is actually no need to fix errors in bits
h23, h15, h7,
h3, h1 and h0
since they are not used in the decoded byte.
The output data bits, d17--d0 are:
h22, h21, h20, h19, h18, h17, h16, h14, h13, h12,
h11, h10, h9, h8, h6, h5, h4, h2