1
$\begingroup$

I'm learning about Reed-Solomon codes so apologies if this is a basic question. The alphabet size $q$ in RS codes grows with the block length $n$ - in particular, we have $q \geq n$.

But intuitively, what's the reason behind this constraint? This is introduced as a part of the definition in the notes I'm reading and I see that it has implications later (e.g. Reed-Solomon codes can beat the Plotkin bound) but it's hazy to me why this must be the case.

$\endgroup$

1 Answer 1

1
$\begingroup$

You need a large enough alphabet to have enough degrees of freedom yielding codes with optimum minimum distance.

The idea of the RS codes comes from choosing generator polynomials with no conjugacy constraints (unlike the binary cyclic code case where the conjugacy constraints restrict the factorization of $x^n-1$ to products of irreducible factors in one to one correspondence with cyclotomic cosets) thus as a product of linear factors of the form $(x-c)$. Then one can simply choose a product of the form $(x-c)(x-c^2)(x-c^3)\ldots(x-c^{n-k})$ and this is the maximum degree of freedom possible in controlling consecutive roots and obtaining best possible distance.

Recall that in binary alphabet case, designing a BCH code you'll be forced to choose an irreducible factor of the form, e.g., $(x-c)(x-c^2)(x-c^4)$ which due to conjugacy will give a polynomial with coefficients over $GF(2)$ when multiplied out.

No conjugacy constraints are only possible if the generating polynomial and hence alphabet is over the full field $GF(q)$ as opposed to one of its subfields.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.