Self correcting codes are constructed by combining data bits with a number of redundant check-bits, which together are referred to as codewords.  By adding a single bit (as in Parity Checking) along with a given number of data-bits, half of the possible codewords become valid and half invalid.  This is referred to as a code that has Hamming Distance 2 (two single bit flips are required to get from one calid code to another).  This is insufficient for correcting invalid codes since it is impossible to determine whether the original valid codeword was the valid codeword one bit difference preceding the invalid one or one bit difference following the invalid one.  In codes with Hamming Distance 3, every valid codeword has two unique invalid codewords exactly one bit different from itself.  No valid codeword shares one-bit different invalid codes with any other valid code.  Because of this, any given invalid codeword can be assumed (if we assume the possibility of only one bit-error per codeword) to be representative of the corresponding valid codeword with a single bit error.  This particular approach, using Haming Distance 3, is the minimum requirement for self-error correction and is commonly referred to as a Hamming Code.

    In 1948, Claude Shannon, of Bell Laboratories, published his paper "Mathematical Theory of Communication" and opened the door to the problem of digital communication error.  Shortly afterward Richard Hamming, also of Bell Laboratories, discovered and implemented a concise and efficient algorithm for single-bit error correction codes.  A decade later, among others, Irving Reed and Gustave Solomon, discovered algorithms which could be used for multiple error correction.  Since that time, further research was made into multiple-bit error detection and recovery and it was discovered that some of these algorithms are in fact variations of some of Euclid's findings from 300 BC.

Firstly, the minimum number of check-bits required to implement a Hamming Code is given by the inequality

d + c + 1 <= 2c

where d is the number of data-bits per codeword and c is the number of check-bits.
A codeword which satisfies the equation

d + c + 1 = 2c

is know as a perfect Hamming Code and represents the most efficient combination of data-bits and check-bits which provide Hamming Distance 3.

Constructing a Hamming Codeword

We'll proceed by outlining how we construct a Hamming codeword with 11 data-bits and 4 check-bits (a perfect codeword).  This specific combination of data and check bits is referred to as a (15,11) code for its 15 total bits of which 11 are real data.  (Note that the choice of a (15:11) code is completely arbitrary and that this algorithm can be used for any number of data bits)

1) We label the check-bits with increasing powers of two:
       C₁, C₂, C₄, and C₈
       and interleave these with the given data-bits, giving:
       C₁, C₂, D₃, C₄, D₅, D₆, D₇, C₈, D₉, D₁₀, D₁₁, D₁₂, D₁₃, D₁₄, D₁₅

2) Each check bit is assigned the even parity value of the set of bits formed in the following way:
        - given that p is the label of the particular check-bit
        - including the first p-1 bit(s) starting with bit p+1, excluding the next p bit(s), including the next p bit(s), etc...

C₁ = D₃  D₅   D₇   D₉   D₁₁  D₁₃  D₁₅
C₂ = D₃  D₆   D₇   D₁₀  D₁₁  D₁₄  D₁₅
C₄ = D₅  D₆   D₇   D₁₂  D₁₃  D₁₄  D₁₅
C₈ = D₉  D₁₀  D₁₁  D₁₂  D₁₃  D₁₄  D₁₅

        (where  is the exclusive-or operator)

For example, the codeword for the data-bits 10010110011 would constructed as follows:
 

C1

C2

D3

C4

D5

D6

D7

C8

D9

D10

D11

D12

D13

D14

D15

?

?

1

?

0

0

1

?

0

1

1

0

0

1

1

C₁ = 1  0  1  0  1  0  1 = 0
C₂ = 1  0  1  1  1  1  1 = 0
C₄ = 0  0  1  0  0  1  1 = 1
C₈ = 0  1  1  0  0  1  1 = 0

The codeword is then:

C1	C2	D3	C4	D5	D6	D7	C8	D9	D10	D11	D12	D13	D14	D15
0	0	1	1	0	0	1	0	0	1	1	0	0	1	1

Verifying a Hamming Codeword

This is where it pays of to have formed the codeword in such a specific manner.
The following is first calculated:

S₁ = D₃  D₅  D₇  D₉  D₁₁  D₁₃  D₁₅  C₁
S₂ = D₃  D₆  D₇  D₁₀  D₁₁  D₁₄  D₁₅  C₂
S₃ = D₅  D₆  D₇  D₁₂  D₁₃  D₁₄  D₁₅  C₄
S₄ = D₉  D₁₀  D₁₁  D₁₂  D₁₃  D₁₄  D₁₅  C₈

If  S₁=S₂=S₃=S₄=0, the codeword is valid, otherwise the number formed by taking S₁ through S₄ indicates the bit position of the bit which cause the codeword to be invalid.  Obviously by complementing this bit, we form the original valid codeword (again assuming that only a single bit-error was possible).

For example, the full codeword 001100100110011 of the previous example is verified by the following:
 

C1	C2	D3	C4	D5	D6	D7	C8	D9	D10	D11	D12	D13	D14	D15
0	0	1	1	0	0	1	0	0	1	1	0	0	1	1

S₁ = 1  0  1  0  1  0  1  0 = 0
S₂ = 1  0  1  1  1  1  1  0 = 0
S₃ = 0  0  1  0  0  1  1  1 = 0
S₄ = 0  1  1  0  0  1  1  0 = 0

Since all S's are 0, the codeword is deemed valid.

If we flip one of the bits in the full codeword, we'll see that the code is invalid and that the offending bit can be identified.
We'll take, for example, the codeword 001100100100011 (in which we flipped bit 11 from the previous example):
 

C1	C2	D3	C4	D5	D6	D7	C8	D9	D10	D11	D12	D13	D14	D15
0	0	1	1	0	0	1	0	0	1	0	0	0	1	1

S₁ = 1  0  1  0  0  0  1  0 = 1
S₂ = 1  0  1  1  0  1  1  0 = 1
S₃ = 0  0  1  0  0  1  1  1 = 0
S₄ = 0  1  0  0  0  1  1  0 = 1

This indicates an error.  Furthermore, since S=1011 indicates position 11, we should flip bit 11.  Making the correction gives us 001100100110011, the correct original codeword.

It should be noted that this algorithm works only for single-bit errors.  Two-bit errors would be incorrectly mapped to a different original codeword and a three-bit error would not be cought.  However, a two bit-error is detected (just not corrected properly), therefore this algorithm could be used for single and two-bit error detection (but not correction).  To provide detection and correction for more bit errors, a code of higher Hamming Distance must be chosen and implemented accordingly.

---

Links to related material

1. David A. Patterson & John L. Hennessy. Computer Organization & Design. Morgan Kaufmann Publishers, Inc, 1998: B34-B35.

A concise description of Hamming Codes and other error detection mechanisms
2. L. R. Verman. Elements of Algebraic Coding Theory. Chapman & Hall, 1996: Ch 3.

Description and examples of forming Hamming codewords.
3. A. D. Houghton. The Engineer's Error Coding Handbook. Chapman & Hall, 1997: 35-38, 53-60.

Description of various error detecting/correcting codes.
4. R. W. Hamming. Coding and Information Theory. Prentice-Hall,1986

History, Description and comparison of various error-correction techniques with emphasis on Hamming Codes

---

Web page creators

Any comments or criticisms are welcome.