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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented 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$
    – Yuichiro Fujiwara
    Commented 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$
    – Yuichiro Fujiwara
    Commented 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$
    – Yuichiro Fujiwara
    Commented 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$
    – Yuichiro Fujiwara
    Commented Oct 26, 2013 at 15:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .