improving error-correcting capability of Hamming (7,4) code

Question

The Hamming (7,4) code can correct 1 error, and the extended Hamming (8,4) code can correct 1 error and detect 2 errors. I was wondering if we can modify the Hamming (7,4) code or extended Hamming (8,4) code, so that up to 2 errors can be corrected?

Answer 1

I get the impression that you want to have a binary 4-dimensional code with minimum distance five. The Griesmer bound says that the minimum length of such a code is $\ge11$, so we need to tag at least three extra redundancy bits to the $(8,4)$ extended Hamming code. It is not difficult at all to find a way that works. Consider the following generator matrix $$ G= \left( \begin{array}{l} 11110000\color{red}{100}\\ 11001100\color{red}{010}\\ 00001111\color{red}{100}\\ 10101010\color{red}{001} \end{array} \right). $$ Its eight first columns form a generator matrix of the $(8,4,4)$ extended Hamming code. That code has a single weight 8 word (= the sum of the 1st and 3rd rows), and all the other non-zero words have weight four. Therefore we need to make sure that all those weight 4 words get a non-zero 3-bit tag (colored red in the above generator matrix). By looking at those red bits you see that the only non-trivial way to get all red zeros as a linear combination is to take the sum of rows one and three. But that was precisely the weight eight word of the $(8,4)$-code, so this works. It is, of course, easy to also verify this simply by listing all the 16 words of the code generated by $G$.