I forgot to add: based upon Galleger's results, those who've been laughing at Roman numerals for the past 1,000 years for their "inefficiency" at representing large numbers might want to rethink their mirth. At 05:15 PM 1/25/2019, Henry Baker wrote:
The problem with standard ECC is that *all bits are treated the same*, regardless of bit position. Too bad if the corrupted will & testament reads "Mallory has just inherited $XYZ,000.00"; X matters a heck of a lot more than Y, which matters a heck of a lot more than Z.
Clearly, one would like to put more redundancy into X than Y, and more into Y than Z.
Alternatively, encode X into more bits than Y, which enables "standard" ECC to better deal with errors in X than in Y.
As a warmup, consider mapping integers n in the range [0,2^k) into k-bit bit-strings; alternatively, use *unary* coding 1^(2^k) for these same integers. Although the unary coding has the desired property, it is quite inefficient.
If I understand his papers, Gallager solved this problem back in the 1970's, by choosing a fixed large number M and unary encoding floor(n/M) and Huffman encoding mod(n,M) (almost always standard binary encoding of mod(n,M)).
Although Gallager considered *variable- length codes*, so these unary codes don't have to be full length, I suspect that the answer doesn't change by more than a constant factor (??) if a fixed maximum length is specified for the unary coding of floor(n/M).
Is there a better method of protecting the high order bits of n using a more sophisticated type of ECC than this unary encoding hack of Gallager's ?