3 ms·

Maybe it's because of the way you put it, but I can't help but see an algorithm that exponentially increases the reliability of the message by linearily adding

Maybe it's because of the way you put it, but I can't help but see an algorithm that exponentially increases the reliability of the message by linearily adding bits. 1 bit for an error rate of 1/4, 2 bits for 1/16, 3 bits for 1/64. Am I wrong or was this really lost on everyone, back in the day?

mturmon 14y ago
But then, to decrease error probability arbitrarily close to zero, you need arbitrarily many parity bits. That is undesirable. Shannon showed you can decrease it arbitrarily close to zero using a finite number of parity bits. Surprised? Not content with that, Shannon showed how to compute the ratio of overhead you needed. He also showed that, if you used slightly less overhead than his formula, no matter how clever your code was, your error probability would be rather large. Then, the reader felt humble and rather amazed. About fifty years later, people started to figure out how to make codes (in general situations) that got very close to the best-possible ratio Shannon found.
- Dylan16807 14y ago
  It took me a minute to digest this, but I see where the problem was. It's not exactly a finite number of parity bits, but a finite percentage of parity bits. The first step is to calculate the parity:data ratio needed to just barely overwhelm the effect of noise. Then to increase reliability you combine messages, costing no additional bits. Combining messages dilutes spikes in noise so that the parity is not overwhelmed, to an arbitrary certainty. This also goes to show that the direction you approach a problem from makes a big difference. It's easy to get the impression that you can't make efficient very-low-error codes by looking at the effect/cost of parity bits. But it's also easy to realize that fusing messages can provide statistical certainty that noise levels don't spike above redundancy levels. - - Also, in a completely different point: Adding standard parity technically consumes arbitrarily many bits, but log(n) is a very small number. This has to be considered along with the fact that Shannon pulled a bit of a hat trick. To make an efficient code safer you have to increase the block size and therefore the latency. You can't get these improvements for free.
- ordinary 14y ago
  Thank you, that does explain it.

mturmon 14y ago

But then, to decrease error probability arbitrarily close to zero, you need arbitrarily many parity bits. That is undesirable. Shannon showed you can decrease it arbitrarily close to zero using a finite number of parity bits. Surprised? Not content with that, Shannon showed how to compute the ratio of overhead you needed. He also showed that, if you used slightly less overhead than his formula, no matter how clever your code was, your error probability would be rather large. Then, the reader felt humble and rather amazed. About fifty years later, people started to figure out how to make codes (in general situations) that got very close to the best-possible ratio Shannon found.

Dylan16807 14y ago
It took me a minute to digest this, but I see where the problem was. It's not exactly a finite number of parity bits, but a finite percentage of parity bits. The first step is to calculate the parity:data ratio needed to just barely overwhelm the effect of noise. Then to increase reliability you combine messages, costing no additional bits. Combining messages dilutes spikes in noise so that the parity is not overwhelmed, to an arbitrary certainty. This also goes to show that the direction you approach a problem from makes a big difference. It's easy to get the impression that you can't make efficient very-low-error codes by looking at the effect/cost of parity bits. But it's also easy to realize that fusing messages can provide statistical certainty that noise levels don't spike above redundancy levels. - - Also, in a completely different point: Adding standard parity technically consumes arbitrarily many bits, but log(n) is a very small number. This has to be considered along with the fact that Shannon pulled a bit of a hat trick. To make an efficient code safer you have to increase the block size and therefore the latency. You can't get these improvements for free.
ordinary 14y ago
Thank you, that does explain it.