1
$\begingroup$

I know this kind of question have been asked before, here: Constructing a cyclic code with a given minimum distance, but i couldn't understand the answer there.

The question is:

Let $p$ a prime number; I want to prove that for every $d≤p−1$ there exists some cyclic code $C$ with words' length $p−1$ over the field $GF(p)$, such that $d(C)=d$.

Hint: there exist a primitive element in $GF(p)$.

I tried two ways to get to solution, and neither of them was satisfaying.

My first attempt was to create these codes cyclic. I easily constructed a cyclic code with $d=p-1$, for example the code with the generator matrix (which have $p-1$ columns):

$G= \left( \begin{array}{ccc} 1 & ... & 1 \\ \end{array} \right) $

And of course, i found some less trivial example. If $\alpha\in GF(p)$ is the primitive element, so this generator matrix have also $d=p-1$, and the code it's generates is also cyclic:

$G= \left( \begin{array}{ccc} \alpha & \alpha^{2} & ... & \alpha^{p-1} \\ \end{array} \right) $

But my problem is that i haven't find a way to reduce these codes minimal distance below $p-1$ and still keep the cyclic, so this is not helpful at all.

Another thing I try is to create the codes with the desired parameters, and afterward prove they are cyclic. According to my book (A First Course in Coding Theory by Raymond Hill), the following parity check matrix have minimum distance d (Because each d-1 columns of it are linery independent, cause they forming a Vandermonde matrix):

$H= \left( \begin{array}{ccc} 1& 1 & ... & 1 \\ 1 & 2 & ... & p-1 \\ 1 & 2^{2} & ... & (p-1)^{2} \\ ... \\ 1 & 2^{d-2} & ... & (p-1)^{d-2} \\ \end{array} \right) $

So i can find a parity check matrix for a code of length p-1 with every $d≤p-1$, but here i have a problem too: I can't think of a way proving that these code are cyclic. So this is a major problem that i can't overcome.

Is there anyway to solve my problems? Is there another way for proving it?

Thank you very much :)

edit: The answer, if anyone wants to know, is, if $\alpha\in GF(p)$ is the primitive element:

$H= \left( \begin{array}{ccc} \alpha^{p-1}& \alpha^{p-1} & ... & \alpha^{p-1} \\ \alpha^{p-1} & \alpha^{p-2} & ... & \alpha \\ (\alpha^{p-1})^2 & (\alpha^{p-2})^2 & ... & (\alpha)^2 \\ ... \\ (\alpha^{p-1})^{d-2} & (\alpha^{p-2})^{d-2} & ... & (\alpha)^{d-2} \\ \end{array} \right) $

And i got to give credit for Jyrki Lahtonen, his comment really helped me understand the answer.

$\endgroup$
3
  • 1
    $\begingroup$ Look up Reed-Solomon codes. They give you the answer. Essentially using your $H$ but sorted in the order of powers of a primitive element as opposed to the linear order. $\endgroup$ Sep 2, 2013 at 20:07
  • $\begingroup$ Thank you. I haven't found a lot of information about Reed-Solomon code, but your explanation and some hard work led me to the answer, using the elements in order of powers of the primitive element was just brilliant. Thanks a lot and sorry for the inconvinient. $\endgroup$
    – or523
    Sep 2, 2013 at 22:00
  • $\begingroup$ You could post it as an answer. That improves the site hygiene by a small amount, because it removes one question from the unanswered queue. You may also get a few upvotes, and more importantly feedback from other users :-) $\endgroup$ Sep 4, 2013 at 3:46

1 Answer 1

2
$\begingroup$

The answer, if anyone wants to know, is, if $\alpha\in GF(p)$ is the primitive element:

$H= \left( \begin{array}{ccc} \alpha^{p-1}& \alpha^{p-1} & ... & \alpha^{p-1} \\ \alpha^{p-1} & \alpha^{p-2} & ... & \alpha \\ (\alpha^{p-1})^2 & (\alpha^{p-2})^2 & ... & (\alpha)^2 \\ ... \\ (\alpha^{p-1})^{d-2} & (\alpha^{p-2})^{d-2} & ... & (\alpha)^{d-2} \\ \end{array} \right) $

And i got to give credit for Jyrki Lahtonen, his comment really helped me understand the answer.

$\endgroup$

Your Answer

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

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