I'm trying to figure out how to design a Reed-Solomon generator polynomial where $n$ divides $q-1$ (I believe it's denoted by $n|q-1$) but where $n < q-1$. For example, lets say we have a $q=16$ and we want to design a codeword with length 3 and corrects 1 error. so we have the following:

$n = 3$

$l = \frac{q-1}{n} = \frac{15}{3} = 5$

$t=1$ (for correcting 1 error) therefore $\delta = 2t+1$

from here we can get our roots of unity as $\{\alpha^5, \alpha^{10}, \alpha^{15}=\alpha \}$. We then need to choose $\delta -1$ consecutive powers of $\alpha$, but i thought we chose these powers of $\alpha$ from the roots of unity, but there aren't any consecutive roots.

I can solve this for $n=15$ since I will have consecutive roots, however since $n=3$ in this case, i'm not sure how to proceed.


You have the right idea but are missing some of the fine details. A cyclic Reed-Solomon code of length $n$, where $n$ is a proper divisor of $q-1$, is a BCH code and the key property is that if a sequence of $2t$ consecutive $\mathbf{n}$-th roots of unity are roots of the generator polynomial, then the minimum distance is at least $2t+1$. Here, $n = 3$ and $\alpha^5$, $\alpha^{10}$ and $\alpha^{15}=1$ are the three cube roots of unity. So, choose two of them to be roots of $g(x)$ (it doesn't matter which ones because you will always get two consecutive roots in this simple case!) and you are done. If you choose $\beta = \alpha^5$ and $\beta^2 = \alpha^{10}$ as the roots of $g(x)$, then $g(x) = x^2+x+1$, and so all the codewords on this $[3,1,d=3]$ Reed-Solomon code are of the form $\gamma +\gamma x + \gamma x^2, \gamma \in$ GF$(2^4)$, or equivalently $[\gamma, \gamma, \gamma]$, that is, we have a repetition code!

It is also the case here that the cube roots of unity are elements of the subfield GF$(2^2)$ but this is not the case in general. Take $n=5$ which is also a divisor of $q-1=15$ in which case $\alpha^3, \alpha^6, \alpha^9, \alpha^{12}$ and $\alpha^{15}=1$ are the five $5$-th roots of unity which all belong to GF$(2^4)$.

| improve this answer | |
  • $\begingroup$ ahh, so for the $n=5$ case, I can just two $\alpha^3$ and $\alpha^6$ as my consecutive roots, so them my generator becomes $g(x) = (x-\alpha^3)(x-\alpha^6)$ and then just go from there. Is that correct? Thanks for your response! $\endgroup$ – gerrgheiser Nov 16 '17 at 6:06
  • $\begingroup$ Yes, that is correct. If my answer is satisfactory, you can mark it as Accepted, and you could upvote it too if you like. $\endgroup$ – Dilip Sarwate Nov 16 '17 at 15:59
  • $\begingroup$ awesome, thanks for your help with this! it make it much easier to understand! $\endgroup$ – gerrgheiser Nov 16 '17 at 20:42

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.