Generator matrix of the extended hamming code

Question

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.

Answer 1

The all $1$'s vector is always in the orthogonal complement of an even-weight, even-length, binary, linear code. The extended Hamming code is such a code.

Since the all $1$'s vector is trivially linearly independent with the three other rows of your parity check (all the other rows are zero on the first column) then by augmenting the parity check with that row, the new parity check still has full rank.

But that's exactly what the parity check matrix for an $(n,k)$ linear code is: a full rank $(n, n-k)$ matrix $H$ such that $GH=0$ where $G$ is a generator matrix for the code.

Answer 2

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.