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 ?
Best Answer
By definition a Reed-Solomon polynomial is a multiple of the generator, and the sum of two multiples is a multiple.