Hamming code of length $8$ self dual

Question

I'm reading a paper by N.J.A Sloane on self dual codes, and he introduces the binary Hamming code of length $8$ with generator matrix $$ G = \begin{bmatrix} 1&1&1&1&1&1&1&1\\ 0&1&1&1&0&1&0&0\\ 0&0&1&1&1&0&1&0\\ 0&0&0&1&1&1&0&1 \end{bmatrix}$$

Where if we assign labels to the columns from left to right; $\infty, 0,1,2,3,4,5,6$, then the second row has $1's$ where the column is labelled by a quadratic residue mod $7$. Then we cyclic shift to get the remaining rows.

What is being done here? I assume we just ignore the first row and first column as this just extends the matrix. I've looked in to quadratic residue codes but I can't seem to find the link between them and this generator matrix? Could anyone explain what's being done here?

The paper I'm referring to can be found here; https://arxiv.org/abs/math/0612535.

Answer 1

There is a quadratic residue (QR) code of length $p$ over the finite field $GF(m)$ whenever $p$ and $m$ are primes, $p$ is odd, and $m$ is a quadratic residue modulo $p$.

It just happens that the (7,4,3) Hamming Code, and the (23,12,7) Golay Code, both over $GF(2)$ (thus $m=2$) can also be expressed as QR codes.

As $p$ increases, QR codes are no longer very efficient, with their minimum distance asymptotically $O(\sqrt{p})$ but for short lengths they produce the above two perfect codes.

Edit: The online magma calculator is quite useful for computations in coding theory. You can access it here.

Entering

QRCode(GF(2),7); HammingCode(GF(2),3);

gives

[7, 4, 3] "Quadratic Residue code" Linear Code over GF(2)

and

[7, 4, 3] "Hamming code (r = 3)" Linear Code over GF(2)

and displays the same generator matrix for both.

Answer 2

The code is self-dual. The generator matrix is also the parity check matrix. If you consider the matrix $G$ as parity check matrix, then deleting the first row and the first column gives the parity check matrix of the 7,4,3 Hamming code.