Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What are known ways to construct linear cyclic codes with minimum distance at least a given number $d$ (and a reasonable rate)?

I could only find two known methods: BCH codes and Quadratic residue codes.

Are there other methods described in books, or papers (or that you're willing to describe here)?

Clarification: I'm interested to know different approaches to constructing cyclic codes in a way that allows us to say something about the distance. It seems like usually it's rather hard to say something about the distance, so I'm interested in collecting examples when we are able to say something about it.

share|cite|improve this question
Reed-Solomon codes are (in one viewpoint) cyclic $(n,k)$ codes over large alphabets with the property that the minimum distance $d$ can be chosen to be anything from $1$ to $n$ as long as you are happy with $k =n-d+1$. RS codes are also BCH codes. For binary cyclic codes, the results are much sparser, and not all distances are achievable. – Dilip Sarwate Sep 4 '13 at 22:25
@DilipSarwate: The result you describe about RS codes cannot be achieved over a fixed ground field, right? We must let the field vary. – user3533 Sep 4 '13 at 22:32
For a given finite field $\mathbb F_q$, linear cyclic RS codes over $\mathbb F_q$ exist for each $n$ that is a divisor of $q-1$ (including $q-1$ itself) and each $k, 1 \leq k \leq n$. But, yes, this result does not extend to lengths larger than $q-1$ (some minor exceptions when $n = q+1$), pretty much like binary codes: For $n > q$, only a few block lengths and distances can be achieved. – Dilip Sarwate Sep 4 '13 at 22:42
A big part of the problem is that for many a length there are relatively few cyclic codes altogether. This happens when there are only few cyclotomic cosets. The cases where $p=2$ is a primitive root are the worst. For example the dimension of a binary cyclic code of length 11 is either 1, 10 or 11. Not much to choose from! We can often say quite a bit about the minimum distance of trace codes. Alas, they tend to have a relatively low rate. – Jyrki Lahtonen Sep 6 '13 at 19:17
@JyrkiLahtonen: This is the first time I hear of trace codes. Can you please give a reference? – user3533 Sep 7 '13 at 23:23

Your Answer


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

Browse other questions tagged or ask your own question.