# Generate hamming code-words with given minimum distance

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

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

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.

• 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. – Vivek Maran Feb 19 '18 at 23:18
• @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. – Ben Voigt Feb 19 '18 at 23:39
• 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. – Vivek Maran Feb 19 '18 at 23:57