learn.ifs.name

A Mathematical Theory of Communication

Shannon, 1948, A Mathematical Theory of Communication (Bell System Technical Journal)

Subscriber deck — free during early access

5 cards in “12 Equivocation and channel capacity” · whole deck

12 Equivocation and channel capacity

  1. Binary symbols at 1000 per second with 1% errors: why isn’t the information rate 990 bits per second?
    Subtracting errors ignores that the receiver doesn’t know where they are. In the extreme of a channel whose output is independent of its input, half the symbols would still be “right” by chance, yet nothing is transmitted.
  2. What is equivocation, and how does it define the rate of transmission?
    The equivocation \(H_y(x)\) is the conditional entropy of the message given the received signal: the average ambiguity left. The rate is \(R = H(x) - H_y(x)\). For 1% errors at 1000 symbols/s it is about 81 bits/s, so \(R \approx 919\) bits/s.
  3. Give the three equivalent expressions for the rate of transmission \(R\), with their interpretations.
    \(R = H(x) - H_y(x)\) (information sent minus uncertainty about what was sent) \(= H(y) - H_x(y)\) (information received minus the part due to noise) \(= H(x) + H(y) - H(x, y)\) (the bits common to both). Today this is the mutual information.
  4. What does Theorem 10 (the correction channel) show about equivocation?
    An observer seeing both sent and received messages can send correction data so all but an arbitrarily small fraction of errors are fixed if and only if the correction channel has capacity at least \(H_y(x)\): equivocation is exactly the extra information needed to correct the message.
  5. How is the capacity of a noisy channel defined?
    \(C = \max \big(H(x) - H_y(x)\big)\), maximized over all possible input sources. For a noiseless channel \(H_y(x) = 0\) and this agrees with the earlier definition.

Source