Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 46 ยท Information and Channel Coding

Information and Channel Coding: The Big Picture

Chapter 7 overview: source coding versus channel coding, redundancy, code rate, coding gain, FEC versus ARQ, and a first experiment with a repetition code.

Chapter 6 ended with a hard fact: for a given modulation, the bit error rate is set by Eb/N0, and the only way to improve it is to spend more energy. In 1948 Claude Shannon showed there is a way around that. By adding carefully designed redundancy to the data, a system can make errors as rare as you like at a fixed power, provided the data rate stays below a limit called the channel capacity. That is the promise of channel coding, and it is why your phone, your hard drive, your QR code and a probe at the edge of the solar system all work.

This chapter explains the two halves of the story: source coding removes redundancy you do not need, and channel coding adds redundancy you do.

Two rows of blocks. Top row: source, source encoder, channel encoder, modulator. A noisy channel links to the bottom row: demodulator, channel decoder, source decoder, sink.
Source coding squeezes, channel coding protects. Shannon showed the two can be designed separately.

What you will learn

  • Distinguish source coding from channel coding.
  • Define code rate, redundancy and coding gain.
  • Compare forward error correction (FEC) with automatic repeat request (ARQ).
  • See what a repetition code buys and what it costs.

Key terms

  • Source coding: compression, removing statistical redundancy to use fewer bits.
  • Channel coding: adding structured redundancy so errors can be detected or corrected.
  • Code rate R = k / n: k information bits per n coded bits.
  • Coding gain: the reduction in required Eb/N0 for a target BER.
  • FEC / ARQ: correct errors at the receiver, or detect them and ask for a retransmission.

Two kinds of redundancy

Text, images and speech are full of predictable structure: the letter after q is nearly always u, neighboring pixels look alike. Source coding exploits that structure. ZIP, JPEG, MP3 and video codecs all do it. The output has fewer bits and less structure, so every remaining bit matters.

That makes it fragile, so a second step puts back a different kind of redundancy. Channel coding takes k information bits and produces n > k coded bits using a rule that the receiver knows. A random bit error then breaks the rule, and the receiver can notice it and often repair it. The ratio R = k/n is the code rate, and 1 โˆ’ R is the fraction of the transmission spent on protection.

Shannon's separation theorem says that, in the limit of long blocks, you lose nothing by designing the two steps separately: compress as much as possible first, then protect.

FEC and ARQ

There are two ways to use the redundancy:

  • FEC (forward error correction): the receiver corrects errors itself. It needs no return path, which is essential for broadcasting, deep-space links, optical discs and flash memory.
  • ARQ (automatic repeat request): the code only detects errors (for example with a CRC), and the receiver asks for a retransmission. Cheap and powerful when a return channel exists and delay is acceptable. Wi-Fi and TCP-style protocols use it.
  • Hybrid ARQ combines both: correct what you can, and retransmit when you cannot. LTE and 5G use it.

What coding buys

A code improves the BER at the same Eb/N0 or, equivalently, reaches the same BER at lower Eb/N0. The horizontal shift between the curves is the coding gain, in dB. Modern codes (turbo, LDPC, polar) work within a fraction of a dB of the Shannon limit. Older and simpler codes, such as the ones in this chapter, give gains of a few decibels, which in a satellite link can be the difference between a dish the size of a house and one the size of a dinner plate.

Coding is not free. The redundancy costs bandwidth (a rate-1/2 code needs twice the symbol rate) or throughput, plus decoder complexity and delay. A repetition code, the simplest possible, shows the trade clearly: repeat each bit three times and decide by majority vote. One error in three can be corrected, but you send three times as much. Better codes get more correction per extra bit.

Two jobs

Source coding Remove waste
Channel coding Add protection
1 / 4

The road ahead

  1. Entropy and channel capacity: how many bits a source needs and how many a channel can carry.
  2. Hamming and block codes: parity, distance and the (7,4) code.
  3. Convolutional codes and Viterbi decoding: shift-register encoders and trellis decoding.
  4. Chapter review.

Try it

Flip any of the three copies of a bit and see whether majority voting recovers it. This is a demonstration of a repetition code, not a channel model.

Repetition code by hand

Now count: if each transmitted bit is flipped with probability p (a binary symmetric channel), the 3x repetition code fails when two or three copies flip, with probability 3pยฒ(1โˆ’p) + pยณ = 3pยฒ โˆ’ 2pยณ.

Python Repetition code on a binary symmetric channel

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 ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the code rate of a code that turns 4 information bits into 7 coded bits?

    R = k/n = 4/7.
  2. 2. Which describes source coding?

    Source coding is compression.
  3. 3. A deep-space probe cannot ask for retransmissions in time. Which technique fits best?

    FEC corrects errors at the receiver without any return path.
  4. 4. A 3x repetition code is used over a channel with flip probability p = 0.1. What is the error probability after majority decoding?

    3pยฒ โˆ’ 2pยณ = 0.03 โˆ’ 0.002 = 0.028.

Summary

  • Source coding removes redundancy; channel coding adds structured redundancy so errors can be found and fixed.
  • Code rate R = k/n; coding gain is the dB reduction in Eb/N0 for the same BER.
  • FEC corrects at the receiver, ARQ asks for retransmission, hybrid ARQ does both.
  • Even a repetition code shows the trade: lower error rate for lower rate.

Next: Entropy and channel capacity