# Permutation of the columns of an extended binary Hamming code

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)?

-
Hint: For a $[2^m, 2^m-1-1]$ extended Hamming code, how many different values can the $(m+1)$-bit syndrome have? One syndrome value $000\cdots 000$ corresponds to no errors, and $2^m$ to the $2^m$ single bit error patterns $1000\cdots 00, 010\cdots 00, 001\cdots 00, \ldots 000\ldots 01$. Are there enough distinct syndromes to correspond to the $2^m$ different double-adjacent-error patterns including $000\cdots 011$ and $100\cdots 001$ corresponding to the two patterns involving the last digit? –  Dilip Sarwate Sep 13 '12 at 13:08

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.

-