Sometimes it feels like it’s kind of trying to bait you into thinking: Hmm, that doesn’t seem that hard to prove, maybe I should spend some spare time on it.
edit: in case it’s not obvious I’m not trying to be presumptive The fart of trying some of these doesn’t last long .
I may fantasize for a minute after reading one, then remember there have been many “simple”problems that went unproven for hundreds of year or longer.
something like trisecting an angle with a protractor I would guess drove a few people to near insanity.
The linked wiki article said that given 12 bits, the BG code can encode them as 24 bits with the ability to correct up to 3 bit errors and detect up to 7. If I'm understanding RS codes correctly, an RS code with 12 data and 12 parity bits would be able to correct up to 6 bit errors and detect up to 12. So what is the advantage of a BG code in that case?
> By adding t check symbols to the data, a Reed–Solomon code can detect (but not correct) any combination of up to and including t erroneous symbols, OR locate and correct up to and including ⌊t/2⌋ erroneous symbols at unknown locations
So it looks like you would have to choose between, either:
A) correcting 6 bits OR
B) detecting 12 bit errors.
[1] https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_cor...
if the number of corrupted bits is no more than six, you can reconstruct the original message
if the number of corrupted bits is between 6 and 12, you will detect the corruption
if the number of corrupted bits is larger than 12, you may or may not detect the corruption.
Glad to hear there were breakthroughs in the field, thanks for the heap of links for me to delve into. :)
John Conway [1] (who recently passed away due to COVID) wrote a famous book about it: Sphere Packings, Lattices and Groups -- which summarizes the subject concisely.
A recent (2017) break through, was the proof that the Leech Lattice [2] yields the optimal sphere packing in dimension 24 [3]. The error correcting code constructed from this lattice is the Binary Golay Error Correcting Code [4]. It is able to correct 3 bits for every 24 bits, and maximally efficient in doing so. It was used to communicate with the Voyager probes.
[1] https://en.wikipedia.org/wiki/John_Horton_Conway [2] https://en.wikipedia.org/wiki/Leech_lattice [3] https://arxiv.org/pdf/1603.06518.pdf [4] https://en.wikipedia.org/wiki/Binary_Golay_code