3
$\begingroup$

I know that Hamming codes can be arranged in cyclic form. But my question is how can I prove 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$

1 Answer 1

5
$\begingroup$

Before answering your question, not every Hamming code is equivalent to some cyclic code. For instance, the ternary $[4,2,3]_3$ Hamming code (aka the tetracode) is not equivalent to any cyclic code.

But it is true that binary Hamming codes can all be seen as cyclic codes. In fact, the $[2^r-1,2^r-r,3]$ Hamming code is the primitive narrow-sense BCH code of length $n = 2^r-1$. More generally, the $q$-ary $[\frac{q^r-1}{q-1},\frac{q^r-1}{q-1}-r,3]_q$ Hamming code with $\gcd(r,q-1)=1$ is the narrow-sense BCH code with its defining set being the $q$-cyclotomic coset $C_1$ of $1$ modulo $n$.

So, if you would like a generator polynomial of the $[15,11,3]$ Hamming code, take the $2$-cyclotomic coset $C_1=\{1,2,4,8\}$ of $1$ modulo $15$. The generator polynomial $p(x)$ you want is the corresponding minimal polynomial

$$\prod_{i\in C_1}(x-\alpha^i),$$

where $\alpha$ is a primitive $15$th root of unity in $\mathbb{F}_{2^4}$.

For instance, take the irreducible polynomial $x^4+x+1$ over $\mathbb{F}_2$. If you regard $\mathbb{F}_{16}$ as $\mathbb{F}_2[x]/(x^4+x+1)$, the element $x$ is a primitive $15$th root of unity. Writing this element as $\alpha$, your $p(x)$ is

$$\begin{align*}p(x) &= \prod_{i\in \{1,2,4,8\}}(x-\alpha^i)\\ &= (x-\alpha)(x-\alpha^2)(x-\alpha^4)(x-\alpha^8)\\ &= x^4+x+1.\end{align*}$$

If you would like the proof that the $[\frac{q^r-1}{q-1},\frac{q^r-1}{q-1}-r,3]_q$ Hamming code with $\gcd(r,q-1)=1$ is the narrow-sense BCH code with defining set $C_1$, assume that $\gcd(r,q-1)=1$. Let $\alpha$ be a primitive element of $\mathbb{F}_{q^r}$, where $\alpha^{q-1}$ is a primitive $n$th root of unity. Construct a cyclic code (actually the narrow-sense BCH code) of length $n=\frac{q^r-1}{q-1}$ by taking the minimal polynomial $M_{\alpha^{q-1}}(x)$ of $\alpha^{q-1}$ as its generator polynomial. The nonzero elements of the subfield $\mathbb{F}_q$ in $\mathbb{F}_{q^r}$ are powers of $\alpha$, where the power is a divisor of $n$. Since $\gcd(r,q-1)=1$, the only element that can be a power of $\alpha^{q-1}$ is the identity. Hence, writing the elements of $\mathbb{F}_{q^r}$ as $r$-tuples in $\mathbb{F}_{q}^r$, no $r$-tuples corresponding to $\alpha^0, \alpha^{q-1}, \dots, \alpha^{(q-1)(n-1)}$ are multiples of another using only elements of $\mathbb{F}_q$, which means that these are simply the points on projective geometry $\operatorname{PG}(r-1,q)$. Hence, the $r \times n$ matrix $H$ in which the columns are the $r$-tuples corresponding to $\alpha^0, \alpha^{q-1}, \dots, \alpha^{(q-1)(n-1)}$ is the parity-check matrix of the $[\frac{q^r-1}{q-1},\frac{q^r-1}{q-1}-r,3]_q$ Hamming code.

$\endgroup$
6
  • $\begingroup$ I think it is really clear. But how do you came from $(x-\alpha)(x-\alpha^2)(x-\alpha^4)(x-\alpha^8)$ to $x^4+x+1$? I only know that $\alpha^{15}=1$ $\endgroup$
    – user41887
    Oct 26, 2013 at 12:01
  • 1
    $\begingroup$ @cl14 I think that particular question about $(x-\alpha)...$ is more of a math.stackexchange-friendly one, but I'll write an answer here as as comments anyway. Do you remember field extension? You can see the finite filed $\mathbb{F}_2^4$ (= $GF(16)$) as the set of $16$ polynomials of degree at most $3$ with coefficients taken from $\mathbb{F}_2$: $\{0,1,x,x+1,\dots,x^3+x^2+x+1\}$. To construct $\mathbb{F}_{16}$ in this form, you take a minimal polynomial of degree $4$. (This degree depends on how much you want to extend the prime field. In our case, it's $4$ because we want $2^4=16$ elements) $\endgroup$ Oct 26, 2013 at 14:50
  • $\begingroup$ An example of minimal polynomials of degree $4$ is $x^4+x+1$. If you pick this guy, computations over the extended field is modulo $x^4+x+1$, which means $x^4+x+1=0$ or equivalently $x^4=x+1$ because coefficients are from $\mathbb{F}_2$. You can show that $x$ is a primitive $15$th root of unity by directly checking $x^i$ are all different for $i=0,1,\dots,14$. Note that because our computation rule is "modulo chosen minimal polynomial," you use the relation $x^4 = x+1$ whenever you get $x^i$ with $i\geq 4$ so that everything is contained in the set $\{0,1,x,x+1,\dots,x^3+x^2+x+1\}$. $\endgroup$ Oct 26, 2013 at 14:50
  • $\begingroup$ From now on, to avoid confusion, we write $x$ as $\alpha$ when talking about $\mathbb{F}_{16}$ (because cyclic codes also use polynomials and we want to use the symbol $x$ for generator polynomials and whatnot). So, if you reduce everything by $\alpha^4 = \alpha+1$, by expanding $(x-\alpha)(x-\alpha^2)(x-\alpha^4)(x-\alpha^8)$ as $(x-\alpha)(x-\alpha^2)(x-\alpha^4)(x-\alpha^8)=(x-\alpha)(x-\alpha^2)(x-\alpha-1)(x-(\alpha+1)^2)=...$, you arrive at $x^4+x+1$. $\endgroup$ Oct 26, 2013 at 14:51
  • $\begingroup$ Also, if you want a simple proof that all binary Hamming codes are cyclic, the proof given in this lecture note (Theorem 7.7) may be a good one. It's exactly the same as what I wrote in the answer except that this one only considers the binary case and the terminology is slightly more elementary. The point is that you don't try to re-arrange columns of $H$ that consists of all $2^r-1$ vectors of $\mathbb{F}_2^r\setminus\{\boldsymbol{0}\}$ into some cyclic form. $\endgroup$ Oct 26, 2013 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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