Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
1  
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. –  Zahra Jan 26 '12 at 23:25
    
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$? –  Zahra Jan 27 '12 at 10:59
    
@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)$. –  Mark Wildon Jan 27 '12 at 13:17
    
@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? –  Zahra Jan 27 '12 at 13:37
    
@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.) –  Mark Wildon Jan 27 '12 at 13:58
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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