Skip to content
Tutorials Center
My learning

Topics

Lesson 4 of 37 ยท Getting Started

The Communication System

Walk through Shannon's model of communication: source, encoder, noisy channel, decoder. Simulate a binary symmetric channel and see why a repetition code trades rate for reliability.

Shannon pictured every communication system, from a telegraph to a video call, as the same chain of five boxes. Thinking in this model lets you ask precise questions: how many bits does the source really produce, how much can the channel carry, and how should the encoder and decoder be designed?

In this lesson you will meet the chain, simulate the most important noisy channel in the theory, and measure the cost of the simplest way to fight noise.

The five boxes

flowchart LR
    S["Source<br/>produces a message"] --> E["Encoder<br/>message to channel symbols"]
    E --> C["Noisy channel"]
    C --> D["Decoder<br/>guess the message"]
    D --> R["Receiver"]
    N["noise"] --> C

Shannon's diagram of a communication system.

  • Source: emits symbols with some statistics (English letters, sensor readings, pixels).
  • Encoder: turns messages into sequences of channel inputs. It has two jobs that Shannon showed can be separated: source coding (remove redundancy, compress) and channel coding (add structured redundancy to survive noise).
  • Channel: the physical medium. It corrupts what goes in, randomly.
  • Decoder: looks at the channel output and guesses what was sent.
  • Receiver: the destination of the message.

The separation theorem says that, in the long run, you lose nothing by designing the compressor and the error-correcting code independently. That is why the course has separate chapters for source coding and channel coding.

A noisy channel as a probability table

A discrete memoryless channel is described by the conditional probabilities p(y | x): given input x, what output y appears? "Memoryless" means each use is independent of the earlier ones.

The binary symmetric channel (BSC) flips each bit independently with probability f. It is the hydrogen atom of coding theory: simple, but it contains the essential difficulty.

Python Simulate 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.

At f = 0.5 the output is statistically independent of the input: the channel carries nothing. At f = 0.1 roughly one bit in ten is wrong, which is useless for a bank transfer without extra protection.

The simplest defense: repetition

Send each bit three times and let the decoder take a majority vote. A single flip in a block of three is corrected. The price: you now use three channel bits for each message bit, so the rate is 1/3.

Python Repetition code with majority vote

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.

The error rate falls quickly as you repeat more, from about 0.1 to well below 0.001. But the rate falls too: to get arbitrarily small errors with this scheme you must send more and more bits per message bit, and the rate goes to zero.

Shannon's surprise

The natural conclusion is "reliability costs rate". Shannon's 1948 result overturned it. For a BSC with f = 0.1, there exist codes of rate about 0.53 (the capacity, computed in Channel Capacity) whose error probability can be made as small as you wish, with the rate staying fixed. Repetition is a very poor code; much smarter ones exist. The rest of this course builds toward them.

Shannon's proof was an existence proof using random codes. It told engineers where the limit lay, and it took until the 1990s (turbo and LDPC codes) to get practical codes close to it.

Two numbers for the whole system

Question Answer Chapter
How few bits describe the source? Entropy H(X) Entropy
How many reliable bits per channel use? Capacity C Channel Capacity

If the source needs H bits per symbol and the channel supports C bits per use, reliable communication is possible when H < C and impossible when H > C.

Python Rate bookkeeping for a toy system

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.

The source needs about 0.469 bits per toss and the channel delivers about 0.531 bits per use, so you can in principle send one toss per channel use reliably. These two formulas are derived in the next chapters.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which component adds structured redundancy to fight noise?

    The channel coder adds redundancy so the decoder can detect and correct errors; the source coder removes redundancy.
  2. 2. A repetition code sends each bit 5 times. What is its rate?

    Rate = message bits per channel bit = 1/5.
  3. 3. In a binary symmetric channel with flip probability 0.5, how much information passes?

    At f = 0.5 the output is independent of the input, so nothing can be learned through the channel.
  4. 4. What did Shannon prove about reliability and rate?

    The noisy-channel coding theorem says rates below capacity are achievable with vanishing error probability.

Summary

  • A communication system is source, encoder, noisy channel, decoder, receiver.
  • Source coding removes redundancy; channel coding adds useful redundancy; the separation theorem lets you design them independently.
  • The binary symmetric channel flips each bit with probability f.
  • Repetition lowers errors but lowers the rate too; Shannon showed far better trade-offs exist.

Next: Entropy