FEC on WiFi... sure... but on disks?

[Security Now has commented on the original article (which I found through Hacker News). It's coming at it as a debunker. I guess that's okay - because FEC *doesn't* increase bandwidth - it just reduces retransmissions, helping to prevent waste. It's also not a huge breakthrough when the basic technology was used in CDs back in the 70s and 80s... and it was pioneered in 1960. [...though you could say the same for the PC or iPad.]]

I was reading about forward error correction on TCP wireless links, and it sounded so impressive I read the Wikipedia article on forward error correction. It states that FEC is used on disks. That's kind of scary. Our hard disks are now so error-prone that it's not enough to have some spare sectors - you need the data written redundantly so that errors can be corrected as the data is read. I guess it's a good thing, but still, a surprising thing.

According to the article, simple FEC is simply redundancy and voting. A bit is sent N times, and when it's read back, the value is whatever value appeared most often. Majority rules.

On disks, they use Reed-Solomon error correction. The article is math-y so kind of opaque to me - but the gist of the second, BCH codes section is that for a string of data, you can calculate a checksum value that's based on a very long polynomial. If any of the data is damaged, you may be able to reconstruct the missing data by solving the simultaneous equation.

Now who said high school algebra isn't worth studying? RS goes well beyond it, but not so far that it's totally incomprehensible.

At my level of comprehension, my first thought was: the polynomial better be simple, because solving a complex one looks hard. Well, lo and behold - that's the problem of the "decoder", which is discussed later. When the RS code was created, there was no decoder, because it was too complex. One wasn't implemented until 1969, nine years later.

From that point on, as is evident from the rest of the Wikipedia article, there were new insights that simplified the solution to the polynomial, making Reed-Solomon a practical error correction code for CDs and other systems that need rapid correction done in hardware. Very cool.