Hamming codes are a part of Linear Block Codes. They were invented in 1950 and can repair 1 error or detect 2. The most famous code is probably hamming[7,4]. That is a code with a codeword length of 7, which is carrying 4 data bits and 3 parity bits. Hamming codes can be used almost anywhere, although they are mainly used for their simplicity,rather than robustness. They are used for example in GPS as hamming [32,26] – that is an extended hamming code with a minimum hamming distance (r) of 4 unlike the standard hamming codes, whose default is r = 3.

The hamming distance is a minimum number of bits in which 2 codewords differ. For example, given codewords C1 = [0,0,0,0,1,1,1] and C2 = [1,1,1,1,1,1,1], we can see that they differ in a total of 4 bits thus the hamming distance is 4. The number of detectable errors is then given by: n = r-1 and the number of repairable errors is given by n = (r-1)/2. You can easily check for the hamming[7,4] with a distance of r = 3.

For hamming[7,4],we can take a look at the next image showing the process of creating both the Generating matrix G and codewords: 

As we can see, the process of creating both the G-Matrix and the Codeword are quite straightforward. Once we are done, we can simulate any number of errors and attempt to correct them. In order to check a codeword for errors, we need to calculate a so called syndrome. If the syndrome is zero, the codeword is either correct or there were too many errors (3 for Hamming[7,4]). The process of repairing a codeword is shown on the next image:

  • Try setting the number of errors to 1 | 2 | 3 and see what happens.
  • An interesting option is to use 2 errors and attempt repair ;)

 

Share This