# 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