Electronic – Generate hamming code-words with given minimum distance

codecommunicationdigital-communicationserror correctionnetworking

My understanding of hamming code (adding this as it might help someone in future):

Description: Hamming code is basically an extended parity check code. Message is divided into blocks, and multiple parity bits are added in each block of message (by the transmitter) in a way that these bits indicate the position of the error bit in that block.

Code-word: Each block (message + parity bits) forms a code word. The list of valid code words is known both to the transmitter and the receiver. Whenever a block is found not to match the list of code words, it is considered as error, and a correction is applied.

Hamming distance: It is the number of bits that differ between a pair of valid codewords. The minimal distance among the all possible pairs of valid codes is called the minimal hamming distance.

Questions:

Currently am using parity method to generate hamming codes. As an an example, I will do the following to generate a (7,4) hamming code

  • Define positions 1-7 for the 7 bits of block.
  • Designate position {1,2,4} , which are powers of 2, for parity bits.
  • Designate other positions {3,5,6,7} for data bits
  • Compute parity bits which will be a function of data bits present in the subset of the above positions and form the code.

Will the above algorithm guarantee the code-words generated will have a minimal hamming distance of 3? If not which algorithm I should use to solve the problem of generating hamming codes with the given (or specified) minimal distance?

Note: Since it was a laborious task to find the minimal distance of the generated 7 bit code-words, I am posting this question here to know the general procedure for generating hamming codes with the given (or specified) minimal distance

Best Answer

To have a minimum distance of 3, it's necessary that a single change to a data bit changes at least two parity bits as well. Therefore, each data bit must appear in the equations of either 2 or 3 parity bits.

Additionally, no two data bits can have the same pattern of appearance in the parity bits, or else changing both those two data bits would result in a second valid codeword at a distance of only 2.

As there are four data bits, and $$\left ( \array{3 \\ 2} \right) + \left( \array{3 \\ 3} \right) = 3 + 1 = 4$$

all combinations of 2 and 3 parity bits must appear.

Thus the generation matrix is

$$\left[ \array{1 & 0 & 0 & 0\\0 & 1 & 0 & 0\\0 & 0 & 1 & 0\\0 & 0 & 0 & 1\\1 & 0 & 1 & 1\\1 & 1 & 0 & 1\\1 & 1 & 1 & 0} \right]$$

and all other valid standard-form generation matrices are just permutations.

All the code words can then be generated by matrix multiplication using a finite field, commonly designated GF(2), where the additive operation is XOR and the multiplicative operation is AND.

$$\left[ \array{1 & 0 & 0 & 0\\0 & 1 & 0 & 0\\0 & 0 & 1 & 0\\0 & 0 & 0 & 1\\1 & 0 & 1 & 1\\1 & 1 & 0 & 1\\1 & 1 & 1 & 0} \right] \left[ \array{d_0 \\ d_1 \\ d_2 \\ d_3} \right ] = \left[ \array{d_0 \\ d_1 \\ d_2 \\ d_3 \\ d_0 \oplus d_2 \oplus d_3 \\ d_0 \oplus d_1 \oplus d_3 \\ d_0 \oplus d_1 \oplus d_2} \right]$$

If your bullet points are requirements rather than a plan, reorder the rows to place the parity bits in the specified positions.

Related Topic