Hamming Codes
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 (SECDED), 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 codewords 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.
One of the most discussed hamming code is probably Hamming(7,4) with 7 total bits in total : 3 parity bits and 4 data bits. The reason is that its a lot easier to explain and visualize the functionality with this hamming code size. Arbitrary 2N – 1 lengths can be however constructed. For example, widely used hamming code for ECC RAM memories is the extended hamming code (128,120). This code can be specifically truncated to use only 8 parity bits (Which are necessary) and 64 data bits.
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.