Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 37 ยท Projects and Practice

Practice Problems with Solutions: Channels, Codes and Compression

Ten worked information theory problems on channel capacity, mutual information, Hamming codes, sphere-packing, Shannon-Hartley, KL divergence, LZ77, Reed-Solomon and rate-distortion.

The best way to own an idea is to use it on a problem you have not seen. This lesson has ten problems covering the second half of the course: channel capacity, error-correcting codes, compression and applications. Try each one with pen and paper first, then run the solution code to check your answer. The code is a worked solution, not just an answer: read it, change the numbers, and see what moves.

Useful facts: H(p) = -p log2 p - (1-p) log2 (1-p); capacity of a BSC is 1 - H(p); of a BEC is 1 - e; Shannon-Hartley is C = B log2(1 + S/N); a code with minimum distance d corrects floor((d-1)/2) errors. You may want to revisit channel capacity and Hamming codes.

Problems 1 to 5

Problem 1. A binary symmetric channel flips each bit with probability 0.2. What is its capacity? How many bits can you send reliably over 1000 uses?

Problem 2. The joint distribution of X and Y is p(0,0) = 0.3, p(0,1) = 0.2, p(1,0) = 0.1, p(1,1) = 0.4. Compute H(X), H(Y), H(X|Y) and I(X;Y).

Problem 3. With the Hamming(7,4) code of the earlier lesson (data bits first, then three parity bits), the received word is 1 0 1 1 1 1 0. Decode it.

Problem 4. A designer proposes a single-error-correcting binary code with n = 8 and k = 5. Is that possible? What about n = 10, k = 6, and n = 15, k = 11? Use the sphere-packing bound 2^k (1 + n) <= 2^n.

Problem 5. A telephone line has bandwidth 3000 Hz and SNR 25 dB. What is its capacity? What SNR in dB would a 200 kHz channel need to carry 1 Mbit/s?

Python Solutions to problems 1 to 5

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For problem 4, note the difference between "allowed by the bound" and "exists": the sphere-packing bound is necessary, not sufficient. For (10, 6) a single-error-correcting code does exist, as you can build by shortening the Hamming(15,11) code; (15, 11) meets the bound exactly (a perfect code).

Problems 6 to 10

Problem 6. A fair coin (p = 0.5) is modelled as a biased one with q = 0.9 for heads. Compute KL(p || q) and KL(q || p) in bits. Why are they different?

Problem 7. Decode the LZ77 tokens (0,0,'a') (0,0,'b') (2,3,'c') (1,2,'d'), where each token is (offset, length, next symbol).

Problem 8. A Reed-Solomon code has n = 10 symbols and k = 6. How many erasures can it recover? How many errors can it correct? Can it still recover the message if two symbols are erased and one other symbol is in error?

Problem 9. A passphrase of 5 words chosen uniformly from a list of 7776 words, versus a PIN of 6 random digits: compare their entropy and the time to guess if an attacker tries 10^9 guesses per second.

Problem 10. A Gaussian source has variance 4. What is the smallest rate (bits per sample) that lets you reconstruct it with mean squared error 1? What SNR in dB does that correspond to?

Python Solutions to problems 6 to 10

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For problem 8, an error costs twice as much as an erasure: a code with minimum distance d handles e erasures and t errors whenever e + 2t <= d - 1.

How to keep practicing

  • Change the numbers in each solution and predict the result before you run the code.
  • Build your own problem from the simulator project: for a target BER of 1e-4 at p = 0.02, which code and rate would you choose?
  • Take a text file and estimate its entropy with the analyzer; then compress it with your mini compressor and compare with the estimate.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. The capacity of a BSC with p = 0.2 is about:

    H(0.2) is about 0.722, so 1 - H(0.2) is about 0.278.
  2. 2. A code with minimum distance d handles e erasures and t errors together when:

    Each error costs two units of distance (location and value), each erasure one.
  3. 3. Is a single-error-correcting binary code with n = 8 and k = 5 possible?

    The sphere-packing bound requires 2^k (1 + n) <= 2^n, which fails here.
  4. 4. Which has more entropy: 5 words from 7776 or a 6-digit PIN?

    5 * log2(7776) is about 64.6 bits, while 6 * log2(10) is about 19.9 bits.

Summary

  • Capacity, mutual information and entropy problems all reduce to a few formulas you can code in a handful of lines.
  • Sphere-packing is a quick feasibility check for error-correcting codes.
  • Errors cost twice as much distance as erasures.
  • Shannon-Hartley links bandwidth, SNR and rate; rate-distortion links rate and quality.
  • Checking answers with code is a habit worth keeping.

Next: Back to the Information Theory track