1
$\begingroup$

Consider a Reed-Solomon code over a finite field of $\mathbb{F}_q$. Why is the typical block size chosen to be $q-1$ [1][2][3]? The reasoning I saw around this is that in order to maximize the rate for a fixed minimum distance. But wouldn't choosing $q$ as the code size would be even slightly better? Does it have to do something with how BCH decoders work? Wikipedia lists both $q$ and $q-1$ as a possible good choice for the block size, but doesn't cite any reference.

[1]: Manz: Fehlerkorrigierende Codes 
[2]: Pretzel: Error-correcting Codes and Finite Fields 
[3]: Hoffman: Coding Theory: The Essentials
$\endgroup$
1
  • $\begingroup$ did you see my updated answer? $\endgroup$
    – kodlu
    Commented Dec 19, 2023 at 13:26

1 Answer 1

1
$\begingroup$

Reed Solomon codes are cyclic. A cyclic code [over whatever Galois field] of length $n$ is defined with respect to reduction modulo $x^n-1$ to get the cyclic property.

Now, the generator polynomial $g$ and the parity check polynomials $h$ are defined by $g(x)h(x)=x^n-1,$ more exactly one is chosen and then the other one is determined using this equation.

The factorization of $x^n-1$ is crucial in determining the properties of the code. The nonzero elements of a finite field $GF(q)$ obey the equation $x^{q-1}-1=0,$ and form the multiplicative group $GF(q)^{\ast}.$

Thus the only choice is to make the length of the code either $q-1$ or a divisor of $q-1.$ This is because, it is known that $x^n-1$ is divisible by $x^m-1$ if and only if $n$ is divisible by $m.$ Usually we take $n=q-1,$ for efficiency since it gives the longest code for a fixed alphabet size.

Remark: For Reed-Solomon which have alphabet $GF(q)$ the factorization is trivial (no cyclotomic cosets need to be computed which are used to determine minimum distance for binary codes). So we take $g$ to have a sequence of consecutive powers of $\alpha$ the primitive element as its roots.

$\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.