Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 37 ยท Projects and Practice

Project: An Error-Correction Simulator

Build an end-to-end simulator with a message source, repetition, Hamming and convolutional encoders, a binary symmetric channel and decoders, then compare bit error rates with the Shannon limit.

In this project you assemble the pieces of the whole chapter into one program: a communication-system simulator. A source produces random bits, an encoder adds redundancy, a binary symmetric channel flips bits, and a decoder tries to repair the damage. You will measure the bit error rate (BER) of several codes, plot them as a table against the crossover probability, and compare them with the theoretical limit given by Shannon's theorem.

The design is a classic software pattern: every code is an object with an encode and a decode method and a rate. The simulator does not care which code it is testing.

Step 1: the framework and three codes

Python Step 1: codes as objects

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.

Notice the pattern: at tiny p everything with coding is near zero; as p grows, the codes fail at different points. The repetition code with 5 copies is strongest here but has rate 0.2, far from Hamming's 0.57.

Step 2: add a convolutional code

The convolutional encoder and Viterbi decoder from the earlier lesson plug into the same interface. We process the stream in blocks of 100 information bits (plus 2 tail bits) to limit the decoder's memory.

Python Step 2: a convolutional code in the framework

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 convolutional code at rate 1/2 reaches error rates far below Hamming at similar p, at the price of a slower decoder.

Step 3: how far from the limit?

For each code rate R, Shannon's theorem gives the largest crossover probability for which reliable communication is possible at all: the p* with 1 - H(p*) = R. We find it by bisection. A practical short code with BER of, say, 1e-3 at a much smaller p is nowhere near this limit; modern LDPC and turbo codes get close.

Python Step 3: the Shannon limit for each rate

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.

A rate-1/2 code could in principle work on a channel that flips up to 11% of the bits; our simple codes already struggle at 5%. The gap is the price of short block lengths and simple structure.

Ideas to extend the project

  • Add the extended Hamming (8,4) code from the linear codes lesson and report how often it detects (but cannot repair) two errors.
  • Replace hard-decision decoding with a binary erasure channel and measure how much better each code does when errors are located.
  • Add Interleaved(code, depth) to defend against burst errors: write bits in a matrix by rows and send by columns.
  • Plot BER against p on a log scale with Matplotlib.

Always fix the random seed in simulations. Your results become reproducible, and a change in BER after you change code can be trusted to come from the code and not the noise.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why implement every code with the same encode/decode interface?

    The simulator only calls encode, the channel and decode, so any new code can be compared with the others.
  2. 2. Which code in the first table has the highest rate while still correcting errors?

    Hamming(7,4) has rate 4/7, about 0.57, compared with 0.33 and 0.2 for the repetition codes.
  3. 3. What does the Shannon limit for a rate-1/2 code on a BSC tell us?

    It solves 1 - H(p) = R: for R = 1/2 that is about p = 0.11.
  4. 4. Why fix the random seed in a simulation?

    Reproducible results let you attribute changes to the code, not to different random noise.

Summary

  • A simulator chains source, encoder, channel and decoder; each code is an object with a common interface.
  • Repetition codes trade rate for reliability; Hamming improves rate; convolutional codes with Viterbi decoding are stronger.
  • BER versus crossover probability is the standard way to compare codes.
  • Shannon's limit 1 - H(p) = R bounds what any code of rate R can do.
  • Fixed seeds make simulations reproducible.

Next: Project: A Mini Compressor