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, b0with

`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^b0where ^ 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 !320Decoding 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, h0with

`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 ^ h1If 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 h1The 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, b0with

`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 ^ b0where ^ 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, b11in 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, h16with

`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 ^ h22If 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 16The 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

This page was created on 12 August 1996. It was last updated 09 September 1998.

Please send comments to Robin O'Leary

Copyright (C)1996--2004 Robin O'Leary. All rights reserved.