Hamming Codes

by | Jan 18, 2016 | QUICK

Hamming codes are basic Linear Block Codes. The most common configuration is Hamming [7,4] with 3 parity bits, 4 data bits and 7 bits total. The codeword length can be increased however to any arbitrary 2N – 1 as the algorithm is generic. The code can detect and repair 1 error or detect two errors. This is bound by the hamming distance, which is 3 for standard hamming codes, but can be extended to 4 in case of extended hamming codes, which enhances the ratio by being able to correct 1 error and detect 2 errors. The hamming distance specifies minimum amount of bits in which 2 codewrods differ. Amount of detectable errors is given by n = r – 1 and the amount of correctable errors is given by n = (r-1)/2, where r is the hamming distance. An example of constructing the Hamming [7,4] is given below:

The most important part is to properly design the generator matrix G. Note that some articles refer to [ p1 | p2 | d1 | p3 | d2 | d3 | d4 ] while some other articles might use [d1 | d2 | d3 | d4 | p1 | p2 | p3 ]. Those codes are however equivalent with exact same properties. Given the generator matrix G,one can precompute the syndromes – which are zero in case no error has been detected.  Each bit error is then assigned a unique syndrome. Correcting the error therefore refers to looking-up into the precompute table and figuring out the bit index that caused the error. The process is shown below:

Try to play around with the Matlab Demo and different amount of errors, most notably:  [1 2 3]. Try to repair with these settings and observe what happens. The package is freely available ➡️ HERE ⬅️ . As an RTL designer, I would just point out that Matrix – Vector Multiply can be computed with logic AND and summation (modulo %2 ) with XOR. Hamming codes are simple, reliable, doesn’t require many resources and can be utilized with ease in systems with low bit error rate.