Reed–Solomon error correction
Reed & Solomon's original view: The codeword as a sequence of values

There are different encoding procedures for the Reed–Solomon code, and thus, there are different ways to describe the set of all codewords.In the original view of Reed & Solomon (1960), every codeword of the Reed–Solomon code is a sequence of function values of a polynomial of degree less than k {\displaystyle k}. In order to obtain a codeword of the Reed–Solomon code, the message symbols (each within the q-sized alphabet) are treated as the coefficients of a polynomial p {\displaystyle p} of degree less than k, over the finite field F {\displaystyle F} with q {\displaystyle q} elements.In turn, the polynomial p is evaluated at n ≤ q distinct points a 1, …, a n {\displaystyle a_{1},\dots,a_{n}} of the field F, and the sequence of values is the corresponding codeword. Common choices for a set of evaluation points include {0, 1, 2,..., n − 1}, {0, 1, α, α,..., α }, or for n < q, {1, α, α,..., α },..., where α is a primitive element of F.

Formally, the set C {\displaystyle \mathbf {C} } of codewords of the Reed–Solomon code is defined as follows: C = { (p (a 1), p (a 2), …, p (a n)) | p is a polynomial over F of degree < k }. {\displaystyle \mathbf {C} ={\Bigl \{}\;{\bigl (}p(a_{1}),p(a_{2}),\dots,p(a_{n}){\bigr)}\;{\Big |}\;p{\text{ is a polynomial over }}F{\text{ of degree }}<k\;{\Bigr \}}\,.} Since any two distinct polynomials of degree less than k {\displaystyle k} agree in at most k − 1 {\displaystyle k-1} points, this means that any two codewords of the Reed–Solomon code disagree in at least n − (k − 1) = n − k + 1 {\displaystyle n-(k-1)=n-k+1} positions. Furthermore, there are two polynomials that do agree in k − 1 {\displaystyle k-1} points but are not equal, and thus, the distance of the Reed–Solomon code is exactly d = n − k + 1 {\displaystyle d=n-k+1}. Then the relative distance is δ = d / n = 1 − k / n + 1 / n = 1 − R + 1 / n ∼ 1 − R {\displaystyle \delta =d/n=1-k/n+1/n=1-R+1/n\sim 1-R}, where R = k / n {\displaystyle R=k/n} is the rate. This trade-off between the relative distance and the rate is asymptotically optimal since, by the Singleton bound, every code satisfies δ + R ≤ 1 + 1 / n {\displaystyle \delta +R\leq 1+1/n}.Being a code that achieves this optimal trade-off, the Reed–Solomon code belongs to the class of maximum distance separable codes.

While the number of different polynomials of degree less than k and the number of different messages are both equal to q k {\displaystyle q^{k}}, and thus every message can be uniquely mapped to such a polynomial, there are different ways of doing this encoding. The original construction of Reed & Solomon (1960) interprets the message x as the coefficients of the polynomial p, whereas subsequent constructions interpret the message as the values of the polynomial at the first k points a 1, …, a k {\displaystyle a_{1},\dots,a_{k}} and obtain the polynomial p by interpolating these values with a polynomial of degree less than k. The latter encoding procedure, while being slightly less efficient, has the advantage that it gives rise to a systematic code, that is, the original message is always contained as a subsequence of the codeword.
detectable_format:multiple_sections[3], combination:two_responses