Proving reed solomon codes are linear

Question

I'm supposed to prove that any two reed solomon codes added together produce a reed solomon code.

We're supposed to prove this over the coefficient encoding, where the code word is the evaluation of some polynomial $P(x)$ at ${0,1,...,m−1}$. Assume we are working on GF(p) for large enough p.

I created two polynomials to represent the reed-solomon codes: $$P_{0}(x) = c_{n-1}x^{n-1} +...+ c_{1}x + c_{0}$$ message is $(c_{n-1},...c_{0})$ $$P_{1}(x) = d_{n-1}x^{n-1} +...+ d_{1}x + d_{0}$$ message is $(d_{n-1},...d_{0})$

Their sum is $$P(x) = (d_{n-1}+c_{n-1}) x^{n-1} +...+ (d_{1} + c_{1}) x + (d_{0} + c_{0})$$ message is $(d_{n-1}+c_{n-1},...,d_{0} + c_{0})$

I know I need to prove that

• $P(i) = R(i)$ where $R(i)$ is the received code for at least $n+k$ points, where k is the errors
• $P(x)$ is a unique degree-$(n-1)$ polynomial with at least $n+k$ received points

But I'm not sure how to do so. I'd appreciate some hints! I was considering induction

EDIT - still kinda stuck on this. Is it enough to prove that the polynomial is n-1 degree ?

Answer 1

The notation that the OP's instructor is using is very non-standard; most coding people use $n$ for the number of symbols in each codeword (a codeword is a vector in an $n$-dimensional space) and $k$ for the number of information symbols (the data we wish to transmit).

Be that as it may, and sticking with the OP's notation, the information symbols $c_0, c_1, \ldots, c_{n-1}$ (these are elements of GF$(p)$) that the transmitter wish to convey to the receiver are encoded using a Reed-Solomon code which operates follows. The information symbols are treated as the coefficients of a polynomial $P(x) = c_0 + c_1x + \cdots + c_{n-1}x^{n-1}$ and what is transmitted is the $m$-vector $\big(P(0), P(1), \ldots, P(m-1)\big)$. What is absolutely crucial is the requirement that $n \leq m$, that is, there are at least as many transmitted symbols as the number of information symbols that we wish to convey to the receiver (and preferably several more). If we like, we can represent $\big(P(0), P(1), \ldots, P(m-1)\big)$ as another polynomial $$Q(z) = P(0) + P(1)z + \cdots + P(m-1)z^{m-1}$$ and think of the encoding process as mapping the information polynomial $P(x)$ to the codeword polynomial $Q(z)$. With this as background,

The OP is asked to prove that the sum of any two codeword polynomials is a codeword polynomial, that is, if $Q(z)$ and $Q^\prime(z)$ are two codeword polynomials (corresponding to information polynomials $P(x)$ and $P^\prime(x)$) respectively,) then $Q(z)+Q^\prime(z)$ is also a codeword polynomial, that is, there exists some information polynomial $R(x)$ (remember it must have degree $n-1$ or less) such that $Q(z)+Q^\prime(z)$ is the image of $R(x)$:

$$ P(x) \mapsto Q(z), \quad P^\prime(x) \mapsto Q^\prime(z), \implies \exists R(x) \mapsto Q(z)+Q^\prime(z) $$ It seems to me that $R(x) = P(x)+P^\prime(x)$ fits the bill, but the OP's mmv.

Answer 2

By definition a Reed-Solomon polynomial is a multiple of the generator, and the sum of two multiples is a multiple.