Re:Researchers Defeat Randomness to Create Ideal Code
by ajb on Saturday November 27, 2021 @02:50AM
(#29358402)
Yes, if the message is only 40 bits long there is a 100% chance. But the point is that you still only need 20 bits even if the message is 100000 bits long
Because if 50% of bits are corrupted, each bit has a >50% chance of being corrupted, so
With 20 bits you have only a 1 in 2^20 chance of missing all the corrupted bits.
The 20 bits don't allow you do correct anything, BTW. To do that you need a locally decodable code. What we are talking about here is the ability to detect corruption of the original data.
Because if 50% of bits are corrupted, each bit has a >50% chance of being corrupted, so With 20 bits you have only a 1 in 2^20 chance of missing all the corrupted bits.
The 20 bits don't allow you do correct anything, BTW. To do that you need a locally decodable code. What we are talking about here is the ability to detect corruption of the original data.