What is so special about the generator chosen for Reed solomon Codes?

Question

I am a bit confused about the Reed Solomon codes which we are dealing with in our course right now. We first had linear codes than cyclic codes and at the end we had the Reed Solomon codes.

First I would like to tell you what I have understanded until now.

Cyclic Codes

Let $C$ be a $(n,k)$-cyclic code with $C \subset \mathbb{F}_q^n$ for $q$ prime.

$(c_0,c_1,\ldots,c_{n-1}) \leftrightarrow c_0+c_1x+\ldots+c_{n-1}x^{n-1} \in \mathbb{F}_q[x]/(x^n-1)$

Under these circumstances the set of all these polynomials constructed by the codewords of $C$, we call it $C[x]$, forms a principal ideal, since $\mathbb{F}_q[x]$ is a principal ideal ring. So there is an element in $C[x]$ which generates this ideal and this generator is, as far as I understood, crucial for the decoding process. I know that this generator $g(x)$ is a divisor of $x^n-1$ in $\mathbb{F}_q[x]$. My first question here is:

Is this generator unique and what is the best way to calculate it?

If a have messages of length $k$ than the message polynomials have degree $k-1$ and so the generator polynomial needs to have degree $n-k$. Would it be possible to factor $x^n-1$ and than just use a product of these factors so that I get a polynomial of degree $n-k$ ? Would this polynomial be a generator which fulfills my needs ?

After finding the generator we can construct a decoding technique. Let $r(x)$ be my received polynomial. We divide $r(x)$ by $g(x)$ and if the remainder is zero, than there was no error. But if it is not, than we just look at our syndrom table of remainders which completely depends on the error polynomial. So when we know the remainder we know exactly where the error happened.

Reed Solomon Codes

So now we are discussing the Reed Solomon Code. Here my professor first specifies the minimum distance as $d = 2t + 1$ so that we can correct $t$ errors. From what I know Reed Solomon Codes also fulfill the singleton bound("in the best way"). It is $d = n-k+1$. So if we know $k$, what we usually do and we want to correct $t$ errors than $n = k+2t$. So now here comes the thing that I don't really understand. Reed Solomon Codes are cyclic codes and so we also need some generator polynomial and here my professor just states:

$g(x) = (x-\alpha)(x-\alpha^2)\cdot\ldots\cdot(x-\alpha^{2t})$, where $\alpha$ is a primitve Element of $\mathbb{F}_q$.

It would be good to know what the point of choosing the generator like this is. I know that for Reed Solomon Codes we use another method for decoding. From what I understanded we use the fact, that we exatly know the zeros of our generator. If I have a received message $r(x) = c(x) + e(x)$, than I know that:

$r(\alpha^i) = c(\alpha^i)+e(\alpha^i) = e(\alpha^i)$, $i\in\{1,\ldots,2t\}$

As far as I understand, we now try to find the error polynomial through this system of equations, which seems to be the hardest part compared to the other steps. I am asking myself why we are considering this special generator. We maybe could have used some other generator where we also know the zeros and proceed in the same way.

Answer 1

Is this generator unique?

The generator polynomial is unique if $q=2$ but not if $q>2$. This because if $g(x)$ is a generator polynomial, then so is $\alpha g(x)$ a generator polynomial for any nonzero $\alpha \in \mathbb F_q$. Usually, but not always, the generator polynomial is defined as the monic polynomial of least degree in $\mathbb{F}_q[x]/(x^n-1)$ which makes it unique.

With regard to Reed-Solomon codes, there are numerous questions, many with detailed answers, about Reed-Solomon codes on math.SE. Do a search, and you will likely get a lot more helpful information. Reed-Solomon codes are important because they are decodable using straightforward though somewhat time-consuming computation, a notion that has not entered your consciousness as yet since you blithely say about decoding a general linear code

..... if the remainder is zero, than there was no error. But if it is not, than we just look at our syndrom table of remainders which completely depends on the error polynomial. So when we know the remainder we know exactly where the error happened.

while completely ignoring the enormous storage requirements that real-life syndrome tables require. It is one thing to use a toy example as is often done in coding theory courses and textbooks to illustrate a syndrome decoding table, and quite another to use one in a practical system. For example, the "NASA standard" $[255,223]$ Reed-Solomon code over $\mathbb F_{2^8}$ has a syndrome of $32$ $\mathbb F_{2^8}$ symbols (that is, $32\times 8 = 256$ bits, so the syndrome table would have $2^{256} >0.64\times 10^{77}$ entries of $255$ (or $223$) bytes each (say $2000$ bits each) for a total exceeding $10^{88}$ bits of storage. In comparison, consider that the number of atoms in this planet has been estimated at around $10^{50}$ and the number of atoms in the known universe to be about $10^{80}$ (see here on physics.SE). Thus, the syndrome table idea is not feasible in real life; don't go about touting it as the solution and denigrating Reed-Solomon codes as being very hard to decode in comparison to the simplicity of syndrome table lookup. Reed-Solomon decoders are very practical and appear in the innards of many devices including some that might be on your worktable or stereo cabinet or even your shirtpocket.