2
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Thinking.... This question might be better on the Signal Processing SE because this is more about information theory than circuit design. \$\endgroup\$ – KingDuken Feb 18 '18 at 22:07
  • \$\begingroup\$ @KingDuken. This is about digital communications, so it is ok here, but Hamming Code is stretching the limits. \$\endgroup\$ – Sparky256 Feb 18 '18 at 22:49
  • \$\begingroup\$ Note that your second and third bullets are entirely pointless. Interleaving the bit order has no effect on hamming distance. \$\endgroup\$ – Ben Voigt Feb 19 '18 at 4:40
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks much for the response!. I am trying to comprehend your answer. Can you please help me understand "no two data bits can have the same pattern of appearance in the parity bits" by providing an example. I am having difficulties in grasping it. \$\endgroup\$ – Vivek Maran Feb 19 '18 at 23:18
  • 1
    \$\begingroup\$ @VivekMaran: Let's say that all parity bit equations contain either $$d_0 \oplus d_1$$ or neither of these data bits. Then for any valid codeword $$(d_0, d_1, d_2, d_3, p_1, p_2, p_3)$$, the codeword $$(\overline{d_0}, \overline{d_1}, d_2, d_3, p_1, p_2, p_3)$$ is also valid, and the distance between these is only 2. You need at least one bit that depends on d_0 but not d_1 or at least one that depends on d_1 but not d_0. \$\endgroup\$ – Ben Voigt Feb 19 '18 at 23:39
  • \$\begingroup\$ Thanks, so in general 1. Ensure that there each data bit should affect 'n' parity bits, where 'n' should be greater than (or) equal to 'reqd_min_hamming_dist' 2. Ensure that no two data bits appear in the same pattern in the parity equation. So, I got what you are saying :). But I am worried that it is easy for me to overlook any other special cases that I might have to handle in similar problems. Thanks for the response.Will upvote and accept. \$\endgroup\$ – Vivek Maran Feb 19 '18 at 23:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.