Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 46 ยท Information and Channel Coding

Chapter 7 Review: Information and Channel Coding

Review chapter 7: entropy, Shannon capacity, Hamming and convolutional codes in one picture and table, a code-parameter checker, a CRC demo and a ten-question quiz.

Chapter 7 had a simple message: noise cannot be beaten by brute force alone, but it can be beaten by redundancy, up to a limit that Shannon computed. You met the limit (entropy and capacity), a short block code (Hamming) and a stream code with a famous decoder (convolutional with Viterbi). This page collects them.

Left: BER against Eb/N0 for uncoded BPSK and a schematic coded system 3 dB to the left, with an arrow marking the coding gain. Right: four recap cards for entropy, capacity, Hamming and convolutional codes.
Redundancy, spent wisely, buys decibels. The coded curve in the figure is schematic; the real gains are measured in the lessons.

Chapter in one table

Idea Key formula or fact Example
Entropy H = โˆ’ฮฃ pยทlog2 p fair coin 1 bit; p = 0.11 gives 0.5 bit
Source coding average length โ‰ฅ H; Huffman within 1 bit 0.4, 0.3, 0.2, 0.1 gives 1.9 vs 1.846
BSC capacity C = 1 โˆ’ H(p) 0.5 bit per use at p = 0.11
AWGN capacity C = Bยทlog2(1 + SNR) 3 kHz, 30 dB gives about 29.9 kbit/s
Shannon limit Eb/N0 โ‰ฅ (2^ฮท โˆ’ 1)/ฮท โ†’ โˆ’1.59 dB real modulations sit 7 to 10 dB above
Block code (n, k), rate k/n, detect dmin โˆ’ 1, correct โŒŠ(dmin โˆ’ 1)/2โŒ‹ Hamming (7,4), dmin = 3
Convolutional K, rate, generators; Viterbi keeps 2^(Kโˆ’1) survivors (7, 5) code, dfree = 5
Soft decisions Euclidean metric on analog samples about 2 dB better than hard
FEC vs ARQ correct at receiver vs detect and retransmit HARQ combines both

Mistakes to avoid

  • Comparing coded and uncoded systems at equal Es/N0 instead of equal Eb/N0. Coding lowers the energy per transmitted bit by the rate.
  • Treating Shannon capacity as something a specific modulation can reach. It is the ceiling for any scheme.
  • Forgetting that a code with dmin = 3 can either correct one error or detect two, not both at once.
  • Using a CRC to correct errors. It detects them; correction needs a different code.

Try it

First, a code-parameter checker. For each code it computes the rate, how many errors it detects and corrects, and whether it is perfect, meaning the decoding spheres of radius t around the codewords fill the whole space of 2โฟ words.

Python Code parameter checker

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.

Second, a CRC. The CRC-8 below uses the polynomial xโธ + xยฒ + x + 1 (0x07); the standard check value for the ASCII message 123456789 is 0xF4. The code then flips every bit of a message one at a time and counts how many corruptions the CRC catches.

Python CRC-8 error detection

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.

Check your understanding

Quick check ยท 10 questions

of 10 answered You scored / 10 ยท perfect!

  1. 1. What is the entropy of a source with two symbols of probability 0.25 and 0.75?

    H = โˆ’0.25ยทlog2(0.25) โˆ’ 0.75ยทlog2(0.75) = 0.5 + 0.311 = 0.811 bits.
  2. 2. A channel has B = 4 kHz and SNR = 255. What is its capacity?

    C = 4000 ยท log2(256) = 4000 ยท 8 = 32 kbit/s.
  3. 3. What is the lowest Eb/N0 at which reliable communication is possible at all?

    As spectral efficiency tends to zero the bound is ln 2, which is โˆ’1.59 dB.
  4. 4. A block code has dmin = 7. How many errors can it correct, and how many can it detect?

    t = โŒŠ(7 โˆ’ 1)/2โŒ‹ = 3 and detection reaches dmin โˆ’ 1 = 6 errors.
  5. 5. In Hamming (7,4), what is the code rate and what does a nonzero syndrome tell the decoder?

    R = 4/7 and the syndrome equals the column of H at the flipped bit.
  6. 6. Why does the Viterbi algorithm need to keep only one survivor per state?

    Merging paths have identical continuations, so the one with the lower metric dominates.
  7. 7. Which is the best description of soft-decision decoding?

    Soft decoding keeps the confidence information and gains about 2 dB over hard decisions.
  8. 8. A system must work with no return channel and long delays. Which approach fits?

    Without a return path, errors must be corrected at the receiver.
  9. 9. A coded system with rate 1/2 is compared with uncoded BPSK. The fair comparison is at equal:

    Coding spreads the energy over more transmitted bits; the comparison must use energy per information bit.
  10. 10. Huffman coding of probabilities 1/2, 1/4, 1/8, 1/8 gives an average length of:

    Lengths 1, 2, 3, 3 give 0.5 + 0.5 + 0.375 + 0.375 = 1.75 bits, which equals the entropy.

Summary

  • Entropy gives the compression limit and capacity the reliability limit; Shannon's theorems say both can be approached.
  • Block codes are described by (n, k, dmin); Hamming (7,4) corrects one error with rate 4/7.
  • Convolutional codes are decoded with the Viterbi algorithm; soft decisions add about 2 dB.
  • Compare coded and uncoded systems at equal Eb/N0, with Eb the energy per information bit.

Next: Wireless and Optical Systems: the Big Picture