Imler.dyndns.org

Stupid Reed-Solomon Tricks

May 1st, 2008

I just stumbled across a pretty neat thing you can do with a Reed-Solomon encoded bitstream. If the data you’re feeding into the RS system has sidebar information about erasures, and you can model the proportion of erasures to undetectible bad symbols (as a function of raw bit error rate), you can use the observed number of erasures in your input stream to reliably guess if the data in your input buffer is gibberish.*

It turns out that not running known gibberish through your ECC significantly drops your false positive rate.

Yeah, I’m building a packet protocol on top of a lower speed channel with a bit reliability of only 80% - 85%. The guys at the bar tell me that my beer-fueled rants on the topic are, “Impressive”.

*To illustrate: A RS(10,2) system can correctly decode if 8 > 2*errors + erasures. Let’s say that you know an erasure is twice as likely as an error if the Bit Error Rate is constant over your sample area. (not a bad assumption for small sample areas) Given 4 erasures, you can expect about 2 errors, and 8 > 2*2 + 4 won’t ever correct, and running RS will probably give you garbage.

Entry Filed under: Uncategorized