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

3 cards in “13 The fundamental theorem for a discrete channel with noise” · whole deck

13 The fundamental theorem for a discrete channel with noise

  1. What is surprising about the noisy channel coding theorem?
    One might expect that driving the error rate to zero requires redundancy growing without bound, so the rate goes to zero. Instead there is a definite capacity \(C\): information can be sent at any rate below \(C\) with arbitrarily small error.
  2. State Theorem 11, the fundamental theorem for a discrete channel with noise.
    If the source entropy per second \(H \le C\), there is a code transmitting with arbitrarily small error frequency (or equivocation). If \(H > C\), equivocation can be brought down to \(H - C + \epsilon\) but no lower: “Nature takes payment by requiring just that much uncertainty.”
    CH(x)Hy(x)attainableunattainableHy = H(x)
    Rates up to \(C\) can have negligible equivocation; beyond it, equivocation is at least \(H(x) - C\)
  3. How did Shannon prove the noisy coding theorem without constructing a code?
    By random coding: assign the \(2^{TR}\) messages to randomly chosen typical channel inputs and average the error probability over all such codes. For \(R < C\) the chance that another message lands among the \(2^{TH_y(x)}\) plausible causes of a received signal vanishes as \(T\) grows, so some code (indeed almost every code) is nearly ideal.

Source