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

I can obviously construct such a linear code, but couldn't find a method to generate cyclic codes with that property. I tried to use the fact that $x^{p-1}-1=(x-1)(x-2)...(x-p+1)$, but I couldn't really use that.

I think it has something to do with the fact that the field of $p$ elements has some primitive element, but I don't really know how to use it.

  • $\begingroup$ Reed-Solomon codes. $\endgroup$ Sep 12, 2012 at 11:49
  • $\begingroup$ Thanks for the reference! That looks like it. I couldn't find a proof for its minimal distance though; is it there? $\endgroup$
    – Harry
    Sep 12, 2012 at 12:13
  • $\begingroup$ Hmm. I didn't see it spelled out in my cursory reading. The idea is that the minimum distance will be at least the prescribed amount because sampling a degree $k-1$ polynomial at $k$ points fully determines the polynomial (so if at least $k$ samples are zero, then all the samples must be zero). The minimum distance cannot be higher, because that would violate the simpleton bound, sorry, I meant the Singleton bound. $\endgroup$ Sep 12, 2012 at 12:23
  • $\begingroup$ That makes sense; I'd have to prove it explicitly but that's definitely the right way. Thanks again! edit: well, looks like only the "classic view" approach is applicable in my homework. So we're not talking about samples, but coefficients. That may make things more complicated, but I hope I'll still manage. $\endgroup$
    – Harry
    Sep 12, 2012 at 12:29


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.