[klodolph]

Some additions, as "exercise for the reader":

1. The finite field you choose has a minimum size. What is the minimum size field 2^bits for an RS(N,K) coding system? What happens when you try to construct a Reed-Solomon code with a finite field that is too small?

2. Consider a Reed-Solomon coding system which uses a lookup table for the finite field multiplication operation that fits in L1 cache. Given that the table already fits in L1 cache, how could you make the encoder/decoder faster, if you had a smaller finite field?

[nayuki]

> What is the minimum size field 2^bits for an RS(N,K) coding system?

Your field size must be at least N+1, noting that you shouldn't use the value 0 in the encoding matrix.

> What happens when you try to construct a Reed-Solomon code with a finite field that is too small?

Your system of linear equations doesn't have enough linearly independent equations.

> how could you make the encoder/decoder faster

Maybe put the lookup table in a 64-bit general-purpose register and use bit shifting, or in a 128/256/512-bit SIMD register and use extraction instructions (shuffle bytes, etc.).

[shachaf]

Hmm, do you mean N+K+1 (to have enough points for both the data and parity shards)? Why isn't N+K sufficient, fitting a polynomial to N points and emitting K more?

[corsix]

Using the notation from the article, N+K is sufficient for RS(N,K). One point of confusion is that different authors use different notation; some use RS(num data shards, num parity shards), some use RS(total num shards, num data shards), and some use RS(total num shards, num parity shards). Per the article, I'll use RS(num data shards, num parity shards).

As for where the +1 comes from, the clue is in the "noting that you shouldn't use the value 0 in the encoding matrix" remark. The TLDR is that the +1 isn't required, and arises from an (incorrect) attempt to fix an incorrect construction. The non-TLDR is rather long. First, we need to move from polynomials (per the article) to matrices (per the quoted remark). For this movement, let F denote the polynomial from the article, then it so happens that F(k+1) can be expressed as a linear combination of F(1), F(2), ..., F(k). Similarly, F(k+2) can be expressed as a linear combination of F(1), F(2), ..., F(k). This continues to be true up to F(k+t) (and beyond). These various linear combinations can be written as a k-by-t matrix, which is what the quoted remark means by "encoding matrix". Second, once thinking with matrices rather than with polynomials, people want to construct the encoding matrix directly, rather than deriving it from a polynomial. In this direct construction, the requirement is that every square submatrix (of any size) of the k-by-t matrix is invertible. Accordingly, no element of the k-by-t matrix can be zero, as the 1-by-1 submatrix containing just that zero element isn't invertible. Third, one common (but incorrect) direct construction is to create a k-by-t Vandermonde matrix. Such a matrix is usually constructed from some number of distinct elements, but if zero is used as such an element, then the resultant matrix will contain zeroes, which is problematic. Excluding zero causes the Vandermonde construction to _sometimes_ work, but it still doesn't _always_ work. Per https://www.corsix.org/content/reed-solomon-for-software-rai..., there's a slightly different Vandermonde construction that _does_ always work, and also a Cauchy construction that always works, both of which work for zero. Both of these correct constructions have a strong parallel to the polynomial construction: they involve choosing N+K distinct field elements, which is akin to choosing the N+K distinct x co-ordinates for the polynomial.