[dragontamer]

https://www.backblaze.com/blog/reed-solomon/

In particular, these two images:

* https://www.backblaze.com/blog/wp-content/uploads/2015/06/bl...

* https://www.backblaze.com/blog/wp-content/uploads/2015/06/RS...

Note: Backblaze here uses "vertical data" (G * data) instead of what I did earlier "horizontal data" in the form of (data*G). But otherwise, still a good blogpost.

------------

So if you have 5 data + 1 parity, you now have a 5x6 generator matrix, giving you one extra column for erasures.

If one column is erased, you replace the erased column with the parity column, creating a 5x5 matrix.

As long as all columns were linearly independent, the resulting 5x5 matrix remains invertable.

The specific matrix multiplications / inversions / operations are well documented in that blogpost.

-----------

EDIT: Erasure decoding is much easier than error decoding. Error decoding requires figuring out the "locator", and then applying the calculated errors at those locations. Since we already know the locations in an "erasure" situation, we can just manipulate the matrix in an obvious manner.

--------

EDIT2: Ah right, the "systematic form" of the Vandemonde-Reed Solomon construction is to perform Gaussian Elimination on the non-systematic matrix (with the goal of forming an identity-sub-matrix). After gaussian elimination, the "column of ones" (or the simple XOR) disappears. (Erm... row of ones in the Backblaze pictures)

So maybe the Golay code you're thinking of is a better example as a matrix with an explicit parity bit.

[shiftingleft]

I think we're talking about different things.

I would be interested in a way based on coding theory that solves the problem in the blog-post. Something of a form similar to this one would be a solution to me:

  def find_missing_number(nums: List[int]):
    # 1. Define some code C (possibly using nums)
    # 2. Encode a message using C (or interpret nums as a word or codeword)
    # 3. Do something with the word
    # 4. Find the locations of the errors in the word
    # 5. The locations of the errors tell us the missing number(s)

The answer on stackoverflow seems to use methods very related to RS decoding, however I can't quite squint enough at it to see, whether it could actually be solved using the exact same methods in RS decoding.