1
$\begingroup$

Let $Ham$ be the $[7,4,3]_2$ Hamming code.

It is known that $\{w(c):c\in Ham\}\subseteq\{0,3,4,7\}$, where $w(c)$ is the Hamming weight of the word $c$.

A code $C$ of length $n$ is called cyclic if $\forall c=(c_0,\dots,c_{n-1})\in C:(c_{n-1},c_0,\dots,c_{n-2})\in C$.

A straight forward extension for $Ham$ to an $[8,4,4]_2$ code $C$ is a code which is restricted to the $7$ first coordinates is $Ham$ and the last (new) coordinate is a parity bit for the first (original) $7$ ones.

This is true since $C$ is of length $8$ which is $7$ for the first $Ham$ coordinates and another $1$ for the parity bit. Also we end up with the same number of codewords, so the dimension is still $4$. But, now $\{w(c):c\in C\}\subseteq\{0,4,8\}$.

The question is whether $C$ is a cyclic code? and a more general one is what are all the $[8,4]_2$ cyclic codes (I mean is there a certain criterion)?

I know that $Ham$ is cyclic.

I can also say that in $Ham$ we can look at the zero codeword, the all $1$'s codeword and two other codewords $x,y$ with all their cyclic movements this gives us $1+1+7+7=16$ codewords.

|cite|improve this question
$\endgroup$
  • $\begingroup$ You can write the code explicitly and try all possible orderings of the 8 coordinates up to rotation and reflection (so only 7!/2=360). For each one, you can check whether the resulting code is cyclic or not. $\endgroup$ – Yuval Filmus Feb 10 '18 at 10:55
  • $\begingroup$ @YuvalFilmus I now think that a better approach is from the polynomial codes point of view. Since the codes described are all linear, they are cyclic iff their generating polynomial divides $x^8-1$. But the dimension of the code is $4$ so the generating polynomial should be of degree $8-4=4$. Now, $x^8-1=(x^4+1)(x^4-1)$, so the generating polynomial of a cyclic $[8,4]_2$ code is $x^4+1\equiv x^4-1$ but such a code will have distance $2$ and not $4$... Is it right? $\endgroup$ – Don Fanucci Feb 10 '18 at 15:28
  • $\begingroup$ Yes, sounds convincing. How do you know you found all degree 4 factors? $\endgroup$ – Yuval Filmus Feb 10 '18 at 17:16
  • $\begingroup$ @YuvalFilmus I think it's because the final decomposition is $x^8-1=(x-1)^8$? $\endgroup$ – Don Fanucci Feb 10 '18 at 17:28
  • $\begingroup$ So there is only one degree 4 factor, $x^4+1$. $\endgroup$ – Yuval Filmus Feb 10 '18 at 17:54

Your Answer

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

Browse other questions tagged or ask your own question.