Permutation of the columns of an extended binary Hamming code

296 Views Asked by At

Let $C$ be a binary cyclic Hamming code; we add a parity check at the end of every code word and get an extended (not necessarily cyclic) code.

It is possible to show this code can fix any single error, and any double error occurring in two adjacent position, excluding the final (parity) digit.

Is it possible to permutate the order of the columns in the code's parity check matrix, so that the code (well, an equivalent code) will be able to fix any single error and every double errors in adjacent places (including the two pairs containing the last digit)?

1

There are 1 best solutions below

0
On

As the previous response noted, there are not enough syndromes to cover no errors, the 8 single errors, and the 8 cyclic adjacent error patterns. On the other hand, the even weight subcode (i.e., add the all-ones vector to H) of the cyclic Hamming code does allow one to correct all single errors and all adjacent double errors.

Another interesting question is whether or not the original construction is possible if one neglects the boundary [1 0 0 0 0 0 0 1] error pattern. In this case, there are just enough syndromes. But, a near exhaustive search has convinced me this is also impossible.

Perhaps it is possible with a length-8 nonlinear code with 16 codewords.