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

4 cards in “9 The fundamental theorem for a noiseless channel” · whole deck

9 The fundamental theorem for a noiseless channel

  1. State the fundamental theorem for a noiseless channel (Theorem 9).
    For a source with entropy \(H\) bits per symbol and a channel of capacity \(C\) bits per second, one can encode to transmit at an average rate of \(\frac{C}{H} - \epsilon\) symbols per second for arbitrarily small \(\epsilon\), but never faster than \(\frac{C}{H}\).
  2. Describe Shannon’s cumulative-probability construction of a code.
    Sort the length-\(N\) messages by decreasing probability \(p_s\); encode message \(s\) by the binary expansion of the cumulative probability \(P_s\) of all more probable messages, to \(m_s\) places with \(\log_2 \frac{1}{p_s} \le m_s < 1 + \log_2 \frac{1}{p_s}\). Probable messages get short codes, and all codes differ.
  3. How close does the cumulative-probability code get to the entropy?
    The average length per symbol \(H'\) satisfies \(G_N \le H' < G_N + \frac1N\), so it approaches \(H\) as the block length \(N\) grows: longer delay buys better efficiency.
  4. What did Fano’s independent coding method do?
    Sort messages by probability and split them repeatedly into two groups of nearly equal probability, assigning 0 or 1 at each split; apart from minor differences it equals Shannon’s method (Shannon–Fano coding).

Source