Reed-solomon coding: question on proof of minimum distance

51 Views Asked by At

In the "coefficient view" of Reed-Solomon encoding, the message is interpreted to be coefficients of a polynomial m(x). The code word is $c(x) = m(x)*g(x)$ where $g(x)$ is a generator polynomial of the form $(x-a^1)(x-a^2)..(x-a^k)$ for some primitive element $a$. The received message is then $r(x) = m(x)*g(x) + e(x)$ where $e(x)$ is the error polynomial, having non-zero coefficients where the error is located. The system can quickly detect errors by seeing if the received data is divisible by $g(x)$. If there are no errors, it will be of course. A key feature of the system is that it can detect if there are $<=k$ errors. So this raises the question: From what does it follow that an $e(x)$ with $<=k$ errors (non-zero coefficients) can't lead to an $r(x)$ that is also divisible by $g(x)$? Clearly, if $e(x)$ is to have a chance of being an undetected error, then it must itself by divisible by $g(x)$ in order for the resulting $r(x)$ to be divisible by $g(x)$. Since $g(x)$ is of degree $k$, this means that $e(x)$ must either zero or of at least degree $k$ as well to be divisible by $g(x)$. But this doesn't in itself say how many coefficients in $e(x)$ are non-zero; errors can occur in the whole message and $m(x)$ could have high degree; so couldn't $e(x)$ have just a few errors in its high coefficients, be divisible by $g(x)$ yet have $<=k$ non-zero coefficients in total? For Reed-Solomon to work (which it does) this scenario can't occur. But how to prove this fact?