HammingCode

In telecommunication, Hamming codes are a family of linear error-correcting codes that generalize the Hamming(7,4)-code, and were invented by Richard Hamming in 1950. Hamming codes can detect up to two-bit errors or correct one-bit errors without detection of uncorrected errors. By contrast, the simple parity code cannot correct errors, and can detect only an odd number of bits in error. Hamming codes are perfect codes, that is, they achieve the highest possible rate for codes with their block length andminimum distance of three.[1]

In mathematical terms, Hamming codes are a class of binary linear codes. For each integer r ≥ 2 there is a code with block lengthn = 2r − 1 and message length k = 2r − r − 1. Hence the rate of Hamming codes is R = k / n = 1 − r / (2r − 1), which is the highest possible for codes with minimum distance of three (i.e., the minimal number of bit changes needed to go from any code word to any other code word is three) and block length 2r − 1. The parity-check matrix of a Hamming code is constructed by listing all columns of length r that are non-zero, which means that the dual code of the Hamming code is the shortened Hadamard code. The parity-check matrix has the property that any two columns are pairwise linearly independent.

Due to the limited redundancy that Hamming codes add to the data, they can only detect and correct errors when the error rate is low. This is the case in computer memory (ECC memory), where bit errors are extremely rare and Hamming codes are widely used. In this context, an extended Hamming code having one extra parity bit is often used. Extended Hamming codes achieve a Hamming distance of four, which allows the decoder to distinguish between when at most one one-bit error occurs and when any two-bit errors occur. In this sense, extended Hamming codes are single-error correcting and double-error detecting, abbreviated as SECDED.

If more error-correcting bits are included with a message, and if those bits can be arranged such that different incorrect bits produce different error results, then bad bits could be identified. In a seven-bit message, there are seven possible single bit errors, so three error control bits could potentially specify not only that an error occurred but also which bit caused the error.

Hamming studied the existing coding schemes, including two-of-five, and generalized their concepts. To start with, he developed a nomenclature to describe the system, including the number of data bits and error-correction bits in a block. For instance, parity includes a single bit for any data word, so assuming ASCII words with seven bits, Hamming described this as an (8,7) code, with eight bits in total, of which seven are data. The repetition example would be (3,1), following the same logic. The code rate is the second number divided by the first, for our repetition example, 1/3.

Hamming also noticed the problems with flipping two or more bits, and described this as the "distance" (it is now called the Hamming distance, after him). Parity has a distance of 2, so one bit flip can be detected, but not corrected and any two bit flips will be invisible. The (3,1) repetition has a distance of 3, as three bits need to be flipped in the same triple to obtain another code word with no visible errors. It can correct one-bit errors or detect but not correct two-bit errors. A (4,1) repetition (each bit is repeated four times) has a distance of 4, so flipping three bits can be detected, but not corrected. When three bits flip in the same group there can be situations where attempting to correct will produce the wrong code word. In general, a code with distance k can detect but not correct k − 1 errors.

Hamming was interested in two problems at once: increasing the distance as much as possible, while at the same time increasing the code rate as much as possible. During the 1940s he developed several encoding schemes that were dramatic improvements on existing codes. The key to all of his systems was to have the parity bits overlap, such that they managed to check each other as well as the data.

General algorithm[edit]

The following general algorithm generates a single-error correcting (SEC) code for any number of bits.

• 1. Number the bits starting from 1: bit 1, 2, 3, 4, 5, etc.

  2. Write the bit numbers in binary: 1, 10, 11, 100, 101, etc.

  3. All bit positions that are powers of two (have only one 1 bit in the binary form of their position) are parity bits: 1, 2, 4, 8, etc. (1, 10, 100, 1000)

  4. All other bit positions, with two or more 1 bits in the binary form of their position, are data bits.

  5. Each data bit is included in a unique set of 2 or more parity bits, as determined by the binary form of its bit position.

The form of the parity is irrelevant. Even parity is simpler from the perspective of theoretical mathematics, but there is no difference in practice.

This general rule can be shown visually:

 parity bits, it can cover bits from 1 up to . If we subtract out the parity bits, we are left with  bits we can use for the data. As varies, we get all the possible Hamming codes:

TAKE NOTES:

From the above Table we could easily determine how many Parity Bits is needed to be transmitted with a total of K Data Bits.  Using the Equations from the Table above, m is the required number of PARITY BITS needed to be transmitted with the (K) DATA BITS.  If the TOTAL BITS to be TRANSMITTED is 

) TOTAL Bits such that K <=  or  >= K Data Bits.

Hence from the Table, we could easily determine the required Number of PARITY BITS knowing the Number of K DATA BITS.  So id we want to send 3 DATA BITS, we need 3 PARITY BITS making a Total BITS of (3+3) or 6 bits.  Another example, if we want to send 7 DATA BITS. we need 4 PARITY BITS making a Total Bits of 11.

The PARITY BITS can be determined such that Pn = 2n   where n =0, 1, 2, 3, 4, ....n

 Hence a 4 BIT PARITY will be P0, P1, P2 and P3.  So if we want to send a 15 DATA BITS that will require a 5 PARITY BITS making a TOTAL BITS of 20.  Referring to the Table above we could see the format of our BITS TRANSMISSION as shown below.

Also from the Table we could easily determine the Values of each PARITY BIT using the Logic XOR operation on the DATA BITS.

P1 = XOR (D1, D2, D4, D5, D7, D9, D11, D12, D14)

P2 = XOR (D1, D3, D4, D6, D7, D10, D11, D13, D14)

P4 = XOR (D2, D3, D4, D8, D9, D10, D11, D15)

P8 = XOR (D5, D6, D7, D8, D9, D10, D11)

P16 = XOR (D12, D13, D14, D15)

The value of each of the PARITY BITS will depend if you are using ODD PARITY or EVEN PARITY check.

Now let us see how this HAMMING CODE could do its ERROR-CORRECTING Process. TO determine the Error and Correct it, the procedure is almost the same as determining the value of the PARITY BITS.  TO detect the ERROR all we need to do is to EXOR all the DATA BITS with its PARITY BIT and save the result as value Rn,

R1   =  XOR (P1, D1, D2, D4, D5, D7, D9, D11, D12, D14)

R2   =  XOR (P2, D1, D3, D4, D6, D7, D10, D11, D13, D14)

R4   =  XOR (P3, D2, D3, D4, D8, D9, D10, D11, D15)

R8   =  XOR (P4, D5, D6, D7, D8, D9, D10, D11)

R16 =  XOR (P5, D12, D13, D14, D15)

If Rn > 0, then there is an ERROR in the Transmission of the DATA BITS. and To detect which specific DATA BIT is ERROR for CORRECTION could be Determine by getting the corresponding Binary Value for R16 R8 R4 R2 R1.

EXAMPLES:

DETERMINING THE PARITY BITS.

Let us now see  how the  HAMMING Code will  determine the PARITY BITS needed for the TRANSMISSION of K DATA BITS of information.

Let us see how  7 BITS of DATA will be TRANSMITTED with its PARITY BITS.  Here K = 7, which is the number of DATA BITS.  To determine how many PARITY BITS are needed we compute for the m from the equation 

 >= K and the computed value for  m is equal to 4. This value of m can also easily be determined by referring to the TABLE above.

Next, we determine how these 7 DATA BITS together with their 4 PARITY BITS are ENCODED during TRANSMISSION.   The Total number of BITS to be transmitted is 11 BITS ( 7 DATA BITS + 4 PARITY BITS).  Below Figures show how the Data BIts and Parity BIts are Encoded.

Let's assume that our 7 BITS DATA D1D2D3D4D5D6D7 = 1010111

Next, we determine the values of each specific PARITY BITS.  The PARITY BITS can be determined such that Pn = 2n   where n =0, 1, 2, 3, 4, ....n  From this There are 4 Parity Bits Pn namely, P1, P2, P4 and P8.

From the Table above, we could now compute for the VALUES of each PARITY BITS.  Assume EVEN PARITY BITS.

P1 = XOR (D1, D2, D4, D5, D7) =  XOR(1, 0, 0, 1, 1) = 1

P2 = XOR (D1, D3, D4, D6, D7) = XOR(1, 1, 0, 1, 1) = 0

P4 = XOR (D2, D3, D4) = XOR(0, 1, 0) = 1

P8 = XOR (D5, D6, D7) = XOR(1, 1, 1) = 1

So the required DATA TRANSMISSION IS  10110101111. The Details are shown below.