3 ms·
> If the encoding is that corrupted, if you choose 20 bits at random to examine, there's less than 1/1000000 chance that you chose one of the corrupted ones. I
by dataflow 5y ago
> If the encoding is that corrupted, if you choose 20 bits at random to examine, there's less than 1/1000000 chance that you chose one of the corrupted ones.
Is there a typo somewhere here? I'm confused what you're saying. So if my message is 40 bits long and you randomly pick 20 bits to examine, there's a less than one-in-a-million chance that you choose a corrupted bit?
Why? Wouldn't that be an almost 100% chance (= 1 - (20/40 * 19/39 * 18/38 * ...))? Or in terms of whether you recovered the correct value, wouldn't that be a 50% chance (20/40)? Sorry this probably sounds really dumb but I feel like I'm not understanding what you intended to write.
- ajb 5y agoYes, 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.