7
$\begingroup$

X. Kai and S. Zhu in the paper "On cyclic self-dual codes", AAECC, vol. 19, pp. 509-525, 2008, at page 510 in line 6 said that, It is well Known that there are no cyclic self-dual codes over $F_q$ when $q$ is odd.

I know that W. Cary Huffman and V. Pless in the book "Fundamentals of error correcting codes" proved that there are no self-dual cyclic codes of length $n$ over $F_q$ when $gcd(n,q)=1$.

Also Y. Jia, S. Ling and C. Xing in the paper with name "On self-dual cyclic codes over finite fields" at 2011 proved that there exist at least one self-dual cyclic code of length $n$ over $F_q$ if and only if $q$ is a power of $2$ and $n$ is even.

My questions are:

1) Where can I find the proof of the claim that introduced in my first paragraph?

2) Generally, how can I find some good sources about self-dual (self-orthogonal) cyclic codes, precisely about the existence of these codes over finite fields?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

I think (1) is straightforward: suppose $C$ is a cyclic code of length $n$ with generator polynomial $f(x) \in F_q[x]$. Let $C'$ be the code with generator polynomial $g(x) = (x^n-1)/f(x)$. As I understand the definition of duality for cyclic codes (following page 84 of van Lint, Introduction to Coding Theory, 3rd edition), the dual of $C$ is $C'$. Hence, if $C$ is self-dual then $f(x) = g(x)$ and so $x^n-1 = f(x)^2$. This is impossible when $q$ is odd.

I can't help with (2), except to say that a quick Google search found several papers that look relevant, e.g. Self-dual cyclic codes by N.J.A Sloane and J.G. Thompson and On the Minimal Distance of Binary Self-Dual Cyclic Codes by Bas Heijne and Jaap Top.

Edit: as Zahra's comment says, with the other definition of duality for cyclic codes, the generator polynomial for $C^\bot$ is a multiple of $h(x) = g(x^{-1})x^{\deg g}$. The roots of $h(x)$ are the reciprocals of the roots of $g(x)$, counted with multiplicities. Suppose that $1$ is a root of $x^n-1$ with multiplicity $m$. If $1$ has multiplicity $r$ as a root of $f(x)$, then $1$ has multiplicity $m-r$ as a root of $g(x)$ and $h(x)$. Hence, if $C$ is self-dual then $f(x) = h(x)$, and $m-r = r$. Therefore $m$ is even, and again this is impossible when $q$ is odd.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Dear Mark, thanks for your contribution. But, if $C$ be a cyclic code of length $n$ with generator polynomial $f(x)$ and $g(x)=(x^n-1)/f(x)$, then the generator polynomial of its dual is $f^{\perp}(x)={g_0}^{-1}x^{deg(g(x))}g(x^{-1})$, where $g_0$ is the constant term of $g(x)$. Therefor, I think your proof can't be true. $\endgroup$
    – Zahra Taheri
    Commented Jan 26, 2012 at 23:25
  • $\begingroup$ Dear Mark, thanks for your new proof. I understand from your proof that for a self-dual cyclic code $C$ with the generator polynomial $f(x)$, always we have $(x-1)|f(x)$, because $m \neq 0$ and $m=2r$. Is this true in general for self-dual cyclic codes over $F_q$? $\endgroup$
    – Zahra Taheri
    Commented Jan 27, 2012 at 10:59
  • $\begingroup$ @Zahra: in your second comment do you mean $m \not= 2r$? I assume your question is about the case where $q$ is a power of $2$. Suppose that $C$ is a self-dual cyclic code over $F_q$ of length $n$ with generator polynomial $f(x)$. If $n = 2^e b$ where $b$ is odd, then $x^n-1 = (x^b-1)^{2^e}$. The polynomial $x^b-1$ is separable so the multiplicity of $1$ as a root of $x^n-1$ is $2^e$. Hence $e \ge 1$ and by my answer above, the multiplicity of $1$ as a root of $f$ is $2^{e-1}$. So in fact $(x-1)^{2^{e-1}}$ divides $f(x)$. $\endgroup$
    – Mark Wildon
    Commented Jan 27, 2012 at 13:17
  • $\begingroup$ @Mark: I agree with your last comment and because of your proof, I know that $m=2r$. You said in your proof that: " and again this is impossible when $q$ is odd". Would you please explain the reason of this claim? $\endgroup$
    – Zahra Taheri
    Commented Jan 27, 2012 at 13:37
  • $\begingroup$ @Zahra: suppose that $q$ is a power of the prime $p$. If $n = p^e b$, where $p$ does not divide $b$, then $x^n-1 = (x^b-1)^{p^e}$. The polynomial $x^b-1$ is separable, so has distinct roots. Hence every root of $x^n-1$ has multiplicity $p^e$. In particular $1$ has odd multiplicity. (If you have any other questions, perhaps it would be best to email me.) $\endgroup$
    – Mark Wildon
    Commented Jan 27, 2012 at 13:58
1
$\begingroup$

Suppose CSD(n,q) is a cyclic self-dual code over $\mathbb{F}_q$ with length n , and its generator polynomial $g(x) = g_0 + g_1 x + ··· + x^{n−k}$.

So $x^n − 1 = g(x)h(x) = (g_0 + g_1 x + ··· + x^{n−k}) (h_0 + h_1 x + ··· + x^k )$.

We have $g_0 h_0 = −1$.

Because $g^⊥(x)$(generator polynomial of $C^⊥$) = $h_0^{−1} (1 + h_{k−1} x + ··· + h_1 x^{k−1} + h_0 x^k $), $C = C^⊥$ if and only if $g(x) = g^⊥(x)$. It deduces $h_0^{−1}=g_0, k = n/2$.
So $1 = −1$.

'There exist at least one self-dual cyclic code of length n over F q if and only if q is a power of 2 and n is even.'

To (2), suppose $gcd(n,q) = 1$, there exist at least one CSO(n,q) (cyclic self-orthogonal)if and only if n to q and 1 is 'bad'.

It means: $n > 2$, and $ord_n (q)$ is odd or $n\nmid q ^{ord_n (q)/2} + 1$.

$Ord_n (q)$ is the ord of q in $\mathbb{Z}_n$ (unit group).

For ' n to q and 1 is 'bad'', please read P. Moree, On the Divisors of $a^k +b^ k$ , Acta Arithmetica, 1997, LXXX.3: 197-212.

Improve this answer
$\endgroup$

You must log in to answer this question.

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