# Design of Reed-Solomon Code where $n < q-1$

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)$.
• 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! – gerrgheiser Nov 16 '17 at 6:06