How a Galois Field is used to construct a Hamming Parity Matrix

Question

I'm trying to understand how Matlab is generating their Hamming parity matrix. The default according to the documentation is GF(2^m), where m=3.

Hamming(7, 4) parity matrix from Matlab

>> hammgen(3)

ans =

     1     0     0     1     0     1     1
     0     1     0     1     1     1     0
     0     0     1     0     1     1     1

Galois primitive polynomial output

>> gfprimdf(8)

ans =

     1     0     1     1     1     0     0     0     1

How does the Galois field govern the arrangement of the Hamming parity matrix?

Answer 1

As the docs say,

The binary primitive polynomial used to produce the Hamming code is the default primitive polynomial for $GF(2^m)$, represented by gfprimdf(m).

So, in our case we have $m=n-k=8-4=3$. Hence, we must compute the default primitive polynomial for $GF(2^3)$, by doing gfprimdf(3), which gives $[ 1 1 0 1]$ or $p(X)=1+X+X^3$. Indeed, the cyclic $(7,4)$ code generated by this polynomial is a Hamming code. To understand the details you need to read about how polynomial codes work, specifically how the binary codewords can be mapped to polynomials in $GF(2)$ - this particular case (Hamming codes seen as cyclic codes) is treated in detail in Lin & Costello, chapter 4