> This algorithm remains mysterious to me to this day.
The basic idea of Reed-Solomon is to represent a piece of data as though it's the coefficients on a polynomial and then transmitting the value of various points on the polynomial. You have the opportunity to provide an infinite number of points, and you only need the <order of the polynomial> to be correct to derive the original polynomial. If the polynomial is overspecified, then you have the opportunity to derive the original polynomial for each set of points and see whether or not you get the same result each time. Various combinations of this outcome result in no errors, errors that are corrected, or errors that are detected but not corrected.
The rest of Reed-Solomon is about which polynomial to pick, as the selection of polynomial and where to evaluate it makes the coefficients easier to derive, and how "finite field" math works. We're used to math over all real numbers from math class; finite fields define the same operations but over a finite number of numbers (i.e. "all uint8s"). This is convenient when implementing this algorithm on a computer. (The math, of course, still works when "all real numbers" is the domain of the coefficients and points; restricting to fixed-size integers just makes things easier for computers.)
I'm not a mathematician. It works like magic for me.
Simply put. Suppose you have 64 bits (8 bytes) of regular RAM. For ECC-enabled memory, a similar block of memory will occupy 72 bits (9 bytes). The first 64 bits will be identical. What would need to be stored in the remaining 8 bits so that any of the 72 bits could be detected and recovered, assuming only one bit was corrupted?
The basic idea of Reed-Solomon is to represent a piece of data as though it's the coefficients on a polynomial and then transmitting the value of various points on the polynomial. You have the opportunity to provide an infinite number of points, and you only need the <order of the polynomial> to be correct to derive the original polynomial. If the polynomial is overspecified, then you have the opportunity to derive the original polynomial for each set of points and see whether or not you get the same result each time. Various combinations of this outcome result in no errors, errors that are corrected, or errors that are detected but not corrected.
The rest of Reed-Solomon is about which polynomial to pick, as the selection of polynomial and where to evaluate it makes the coefficients easier to derive, and how "finite field" math works. We're used to math over all real numbers from math class; finite fields define the same operations but over a finite number of numbers (i.e. "all uint8s"). This is convenient when implementing this algorithm on a computer. (The math, of course, still works when "all real numbers" is the domain of the coefficients and points; restricting to fixed-size integers just makes things easier for computers.)