[function_seven]

What if the parity bytes exceed 255? I'm assuming this is done with modular arithmetic, but does mod math work to recover missing data from the parity bits without trial and error? (i.e. is the recovery function a one-to-one mapping in reverse?)

I'm not well-versed in modular arithmetic, so excuse me if the answer is obvious to those that are.

[jtolds]

For this particular case, this is not done using modular arithmetic. The parity values are simply rational - they might be fractional, negative, larger than 255, etc.

This erasure code is not at all optimal; it only serves to teach the basics of how one could work. In practice you'll definitely want a Galois Field or something.

[ouring1986]

Pardon my ignorance, but how would a system using a Galois Field work? All this stuff is really interesting to me.

[zeeboo]

In math a field is a structure with enough properties to be able to do polyoninals, meaning addition and multiplication. If you pick a field appropriately, you end up with some properties that guarantee that this interpolation trick works. If you pick it even more appropriately you can have the elements and operations efficient on computers. Turns out that a Galois Field has all those properties.

Specifically, you start with the base field of integers mod 2 and it turns out addition is xor, and multiplication is and. From that, you can create polynomials. Just like you could create a field by considering a set of elements modulo some prime, if you pick a "prime" polynomial and take the set of polynomials modulo your "prime" polynomial, then you get another field. Prime in this case means irreducible, which means you can't factor it.

So what people do is pick an irreducible polynomial of degree 7 and that maps perfectly to a byte. So for example a byte with bit pattern 01100011 would be the polynomial x^6 + x^5 + x + 1. You can then generate some tables that make multiplication and addition of these elements modulo your irreducible polynomial fast, and then apply this interpolation technique.

Hopefully that helps explain it. I was a little loose with terms and details so some stuff might be wrong.