[math-fun] Re And you think You have problems ...

...

I have a 1Mbit file; I'm willing to add 100K additional bits for error correction. What should I do?

Perhaps you could add six bits of error correcting code for each block of 64 bits. That provides room for a code of Hamming-distance three, so you'd get single-error correction in each block. (But double-errors would be corrected wrong.)

-- Don Reble djr@nk.ca

We can do a little better than that! If we have length 2^20 = 1048576 and 100000 check bits, we have rate .09536. So by the Gilbert-Varshamov bound there is a binary linear code with minimum distance 12792, which will correct any error patterm with up to 6396 errors. Neil Sloane