2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Okay... Using the Magma Calculator, I think that $f_1(x)=(x^4+x+1)$ and $f_2(x)=(x^4+x^3+1)$ are primitive polynomials of degree 4, because then I have Parituy Check Matrices with all independent column vectors. $\endgroup$ – cl14 Oct 20 '13 at 18:12
  • $\begingroup$ But how can I proof that all $[2^n-1,2^n-1-n]$ are equivalent to a cyclic (Hamming) Code? Thus not for the case that $n=4$ but for all $n$? $\endgroup$ – cl14 Oct 20 '13 at 18:18
  • $\begingroup$ The columns of the $n \times (2^n-1)$ parity check matrix of any binary Hamming code are the $2^n-1$ nonzero binary vectors. Permute the columns so that they occur in the order in which they are found in the parity check matrix of your choice of cyclic Hamming code $\endgroup$ – Dilip Sarwate Oct 20 '13 at 18:23
  • $\begingroup$ But what is the 'normal' order of the columns in the parity check matrix, before you permute it in the way you want? And how can I proof that there is Always such a permutation? $\endgroup$ – cl14 Oct 20 '13 at 18:30
  • 1
    $\begingroup$ There is no normal order; there are $(2^n-1)!$ different orders in which you can list the $2^n-1$ nonzero binary vectors of length $n$. Each such order gives a different binary Hamming code. Some of these Hamming codes are cyclic. So, pick one of the cyclic Hamming codes and look at its parity check matrix. Can you find two or more identical columns? Yes? No? If not, the columns are all distinct and are just the $2^n-1$ nonzero binary vectors of length $n$ in a specific order. Now prove that there is a permutation of columns that changes one matrix into the pther. $\endgroup$ – Dilip Sarwate Oct 20 '13 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.