Given a check matrix $H$ of the $Ham(3,2)$ code, so $$H = \begin{bmatrix}
1&1&1&1&0&0&0\\
1&1&0&0&1&1&0\\
1&0&1&0&1&0&1
\end{bmatrix}$$
Then, the heck matrix for the extended Hamming code can be done by adding a row of$1s$ at the bottom and a columns of $0s$ like so; $$ H' = \begin{bmatrix}
0&1&1&1&1&0&0&0\\
0&1&1&0&0&1&1&0\\
0&1&0&1&0&1&0&1\\
1&1&1&1&1&1&1&1
\end{bmatrix}$$
Why is this true? I know that the extended code adds an extra bit such that the resulting codeword is of even weight. So it'll be $1$ if the codeword has odd weight and $0$ if it has even weight.
Best Answer
The check matrix indicates which parity-check equations all the codewords must satisfy. $[c_1, c_2, \ldots, c_7]$ is a codeword in the original Hamming code if and only if \begin{align} c_1 +c_2 +c_3 + c_4 &= 0\\ c_1 + c_2 + c_5 + c_6 &= 0\\ c_1 + c_3 + c_5 + c_7 &= 0 \end{align} Now, the codewords in the extended Hamming code are of the form $[c_0, c_1, \ldots, c_7]$ where \begin{align} c_1 +c_2 +c_3 + c_4 &= 0\\ c_1 + c_2 + c_5 + c_6 &= 0\\ c_1 + c_3 + c_5 + c_7 &= 0 \end{align} and $$ c_0 + c_1 + c_2 +c_3 + c_4 + c_5 + c_6 + c_7= 0, $$ that is, the subcodeword $[c_1, \ldots, c_7]$ of the extended Hamming codeword $[c_0, c_1, \ldots, c_7]$ must be a codeword of the original Hamming code, but the extended Hamming codeword also has this pesky bit $c_0$ that doesn't appear in any other parity-check equation. Now, $c_0 + c_1 + c_2 +c_3 + c_4 + c_5 + c_6 + c_7= 0$ holds only when an even number of the $c_i$ have value $1$, and so, if $[c_1, \ldots, c_7]$ is a codeword in the original Hamming code and we stick a $c_0$ in front where $c_0$ is chosen so as to make sure that an even number of the $c_i, 0 \leq i \leq 7,$ have value $1$, then we constructed a codeword of the extended Hamming code from a codeword of the original Hamming code. Now, here comes the tricky part: if $[c_1, \ldots, c_7]$ has an odd number of ONEs in it, set $c_0 = 1$ while if $[c_1, \ldots, c_7]$ has an even number of ONEs in it, set $c_0 = 0$. $c_0$ thus is an overall parity check symbol; it forces all the codewords of the extended Hamming code to have even Hamming weight.