Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 37 ยท Error-correcting Codes

Reed-Solomon and Convolutional Codes

Build a Reed-Solomon style code over a prime field that survives lost symbols and errors, and a rate-1/2 convolutional code with a Viterbi decoder, all in Python.

Two code families dominate real systems. Reed-Solomon (RS) codes work on whole symbols (bytes) and are ideal for bursts and erasures: CDs, DVDs, QR codes, hard drives, RAID-6 and deep-space missions use them. Convolutional codes work on a continuous stream of bits and are decoded with the elegant Viterbi algorithm; they ran in Wi-Fi, GSM and satellite links, often combined with RS.

Both rely on the linear-code ideas you have seen, but their structure is different, so we build each from scratch.

Reed-Solomon: a polynomial through points

The core idea fits in one sentence: a polynomial of degree less than k is determined by any k of its values. Treat your k message symbols as the coefficients of a polynomial m(x). Send its values at n distinct points. Any k received values are enough to rebuild the polynomial and thus the message. Real RS codes work in a finite field like GF(256) so that symbols are bytes; here we use arithmetic modulo the prime 257, which keeps the code short and shows the same algebra.

With n evaluations of a degree-(k-1) polynomial, the code has minimum distance n - k + 1. That meets the Singleton bound, so RS codes are maximum distance separable (MDS): they can recover from n - k erasures, or correct (n - k) / 2 errors.

Python Erasure recovery: lose half, keep the message

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.

Four of eight symbols were erased and the message is recovered exactly. This is how RAID-6 and storage erasure coding survive drive failures.

Correcting errors, not just erasures

An error is worse than an erasure because you do not know which symbol is wrong. With n = 7 and k = 3, the minimum distance is 5, so up to 2 errors can be corrected. A slow but transparent decoder: try every subset of k symbols, interpolate, and keep the polynomial that agrees with at least n - t of the received values. (Practical decoders use the Berlekamp-Massey or Welch-Berlekamp algorithms, which are far faster.)

Python Brute-force error correction

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.

Convolutional codes

A convolutional encoder keeps a small memory of the last few input bits. For every input bit it emits several output bits, each an XOR of selected bits of the memory. The classic example has constraint length K = 3, rate 1/2 and generators 7 and 5 (octal), i.e. 111 and 101: for input u and the two previous bits u1, u2, it outputs u^u1^u2 and u^u2.

The encoder is a finite-state machine with 4 states (the contents of the 2-bit memory). The Viterbi algorithm finds the input sequence whose encoded output is closest to the received bits. It does this by dynamic programming over a trellis: for every state keep only the best path that reaches it, because a worse path to the same state can never become the best overall. The work is proportional to the length times the number of states, not exponential in the length.

flowchart LR
  S00["state 00"] -->|"in 0 / out 00"| S00
  S00 -->|"in 1 / out 11"| S10["state 10"]
  S10 -->|"in 0 / out 10"| S01["state 01"]
  S10 -->|"in 1 / out 01"| S11["state 11"]
  S01 -->|"in 0 / out 11"| S00
  S01 -->|"in 1 / out 00"| S10
  S11 -->|"in 0 / out 01"| S01
  S11 -->|"in 1 / out 10"| S11

One trellis section of the (7,5) code: state = the two previous input bits.

Python Encoder and Viterbi decoder

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.

Four channel flips spread across the stream are all repaired. Because every input bit influences the following K output pairs, the decoder can use later bits to resolve an earlier ambiguity, a form of redundancy a block code spends differently.

A quick comparison on the BSC

Python Does the convolutional code beat no coding?

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 small p the coded system is far better even though it spends two channel bits per data bit.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why can a Reed-Solomon code recover from n - k erasures?

    The message is a polynomial of degree less than k, and any k of its n values are enough to interpolate it.
  2. 2. What is the minimum distance of an (n, k) Reed-Solomon code?

    RS codes meet the Singleton bound d = n - k + 1, so they are maximum distance separable.
  3. 3. What does the Viterbi algorithm keep at each trellis state?

    A worse path into the same state can never beat the best one in the future, so it is discarded.
  4. 4. What is the rate of the (7,5) convolutional code in the lesson?

    Two output bits are produced for each input bit.

Summary

  • A Reed-Solomon code evaluates a message polynomial at n points; any k points recover it.
  • It meets the Singleton bound: d = n - k + 1, so it fixes n - k erasures or (n - k)/2 errors.
  • Real RS codes use GF(256) and fast decoders; the algebra is the same as in our prime-field demo.
  • A convolutional code is a small state machine with rate such as 1/2.
  • The Viterbi algorithm decodes it efficiently by keeping the best path into each state.

Next: Dictionary Compression: LZ77 and LZ78