Richard Hamming invented Hamming codes in 1950, and they are still utilized today. Applications where the bit error rate is low, but errors cannot be tolerated, Hamming codes provide an computationally efficient encoding and decoding. Hamming codes are used for improving RAM reliability, and in error resiliency in the Tactical Secure Voice Cryptographic Interoperability Specification (TSVCIS).
Hamming codes are a class of linear block codes. For any positive integer >= 3, a Hamming code exists where the code length, n, is 2^m – 1, the number of information bits,k, is 2^m – m – 1, and number of parity bits is n – k. Hamming codes have a minimum distance of 3, and provides an error correction capability of 1. Minimum distance is the number of bits that need to be flipped to go from one codeword to another.
The encoding of the information bits is performed by multiplication of the 1 x k vector by the k x n generator matrix. The decoding of Hamming received codeword is performed by the multiplication of the 1xn codeword by the transpose of the n x (n-k) parity matrix. The resulting 1 x (n-k) vector is referred to as the syndrome of the decoder. The syndrome determines the location of the bit error. The main operations of a Hamming encoder and decoder are implemented via bitwise and-ing and xor-ing operations. The finding the location of the bit position from the syndrome can be implemented via a lookup table. The figure below shows an example of the decoding operation, where there was an error introduced into the 0th bit.
The rows of the transposed parity matrix correspond to the bit in which contains the error bit, from the bottom up. So, the resulting [0 0 1], corrects the error. Again, Hamming codes are only designed to correct single bit errors, so it important to know the bit error rate of the system. Adding an additional parity bit to a Hamming code increases the minimum distance to 4 and creates a class of codes called Single Error Correction Double Error Detecting (SECDED) codes. VOCAL has 35 plus experiencing developing software modules for signal processing algorithms. Hamming codes and other forward error correction (FEC) codes, such as Reed-Solomon and BCH codes are part of VOCAL software solutions. Please contact us to learn more.