PDC Live

Hamming Code

Several Teletext packets contain information protected by hamming. This is a method for encoding data such that errors in reception can be detected, and if the error is sufficiently small, corrected. Teletext uses two hamming codes.

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.

8/4 Hamming

The 8/4 code is quite simple; if the input nibble is the 4-bit value:
        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

24/18 Hamming

The more efficient 24/18 code is based on the same principle of interleaved check bits and an overall parity bit as the simpler 8/4 code.

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

This page was created on 12 August 1996. It was last updated 09 September 1998.
Please send comments to Robin O'Leary pdc at ro dot nu
Copyright (C)1996--2004 Robin O'Leary. All rights reserved.