3 ms·
This little article failed to say the really surprising thing about channel coding, which is that good channel codes exist at all. There's a simple argument th
by mturmon 14y ago
This little article failed to say the really surprising thing about channel coding, which is that good channel codes exist at all. There's a simple argument that seems to indicate that they should not exist. If I remember correctly, this argument was commonly accepted by engineers at the time Shannon's paper came out.
The argument is: you have a communications channel that flips bits with some probability, say 1/4. Suppose you want to transmit one bit. The first bit might have an error, so you add a parity bit -- now P(error) is 1/16. But that parity bit might have an error, so you add a second parity bit, and you're down to P(error) of 1/64. So you are driving P(error) to zero, but at the expense of ever-increasing overhead.
If you keep on adding parity bits, it's not clear that you can ever make the error probability arbitrarily small, while still transmitting some information.
That is, in the simple approach above, P(error) -> 0, but Overhead -> Infinity.
It is "intuitively obvious" that's a fundamental problem, or at least it was, until Shannon's results showed that intuition was wrong, or at least needed correction. In fact, the amount of overhead-per-bit is not infinite, but is a finite number related to channel capacity.
- gwern 14y ago> This little article failed to say the really surprising thing about channel coding, which is that good channel codes exist at all. There's a simple argument that seems to indicate that they should not exist. If I remember correctly, this argument was commonly accepted by engineers at the time Shannon's paper came out. I did not know that, thanks. (Now I understand better why Hamming, in 'You and Your Research', calls Shannon a 'man of infinite courage'.)
- ordinary 14y agoMaybe 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 agoBut 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 agoIt 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 agoThank you, that does explain it.