How we can prove that the t-error-correcting Reed-Solomon code with symbols from $GF(2^m)$ generated by
$$g(X)=(X+\alpha)(X+\alpha^2)...(X+\alpha^{2t})$$
has minimum distance exactly $2t+1$ where $\alpha$ is a primitive element in $GF(2^m)$.
I remember one theorem that says no $2t$ columns of its parity-check matrix must not add to zero, but have no idea to use this.
1 Answer
A $t$-error-correcting code must have minimum distance at least $2t+1$, not $2t-1$ as you claim. Now, the Singleton bound tells us that a $[n,k]$ code has minimum distance at most $n-k+1$, but since $n-k$ equals the degree of the generator polynomial (the degree is $2t$), we have that $$d \leq 2t+1.$$ On the other hand, the BCH bound tells us that if $2t$ consecutive powers of $\alpha$ are roots of the generator polynomial, then the minimum distance of the code is at least $2t+1$, that is, $d \geq 2t+1$. Comparing these two bounds, we arrive at the conclusion that $$d = 2t+1$$ exactly without needing to look at paritycheck matrices and the like.
-
$\begingroup$ I couldn’t have done it without you @DilipSarwate, thanks. I corrected the question, it was due to a problem with the printing of my textbook! $\endgroup$ Jan 6 at 19:45