[Math] Cyclic Hamming Code

coding-theory

I know that Hamming codes can be arranged in cyclic form. But my question is how can I proof this.

My idea was to find a generator/primitive polynomial $p(x)$? For example I want to show that the $[15,11]$ Hamming code can be written in a cyclic form. Then the generator polynomial $p(x)$ must divide $x^{15} +1$ . The factorization of this is: $x^{15} +1=(x+1)(x^2 +1)(x^4 +x+1)(x^4 +x^3 +1)(x^4 +x^3 +x^2 +x+1)$ . But what is now my $p(x)$ and why?

And what is the next step in my proof?

Thanks in advance.

Best Answer

The generator polynomial of a cyclic binary $[2^n-1, 2^n-1-n]$ Hamming code is always a primitive polynomial of degree $n$. So, use one of the two primitive polynomials of degree $4$ that you have exhibited as factors of $x^{15}-1$. (Hint: you may need to first figure out which two of the three polynomials of degree $4$ are primitive and which one is nonprimitive).

Thus there are two different cyclic binary $[15,11]$ Hamming codes depending on which primitive polynomial you choose as the generator polynomial. They are related in the sense that if $(C_0, C_1, \ldots, C_{14})$ is a codeword in one code, then $(C_{14}, C_{13}, \ldots, C_1,C_0)$ is a codeword in the other code.

Related Question