Comment by shiftingleft | Hacker News Reader

Comment by shiftingleft | Hacker News Reader

Parent Full thread

Thanks a lot for the detailed answer!

I'm familiar with some subset of coding and number theory, so you can assume at least some more knowledge (Galois Fields, or basics of RS codes for example).

Small nitpick: The Vandermonde matrix actually isn't square. It's a (k × n) matrix, (where typically k ≠ n). Therefore, it can't be invertible.

I see that many codes contain a parity bit (for example the extended Golay code), however I don't see how the operation of recovering "the missing number" could be implemented in terms of a code and its encoding/decoding algorithms.

I've found this on stackoverflow: https://stackoverflow.com/a/3492967/3868157

It describes a way to recover the missing number by constructing a Vandermonde matrix using the given numbers. This would correspond to constructing a generator matrix of a specific RS code [1]. However, after this I'm not so sure about the relation between encoding/decoding and recovering the missing number.

In the end they also factor a polynomial (that could be something analogous to the error locator polynomial?).

[1]: although I'm not sure if it's strictly an RS code

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.

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.

Reply on news.ycombinator.com