Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 46 ยท Information and Channel Coding

Convolutional Codes and Viterbi Decoding

Learn convolutional encoders, constraint length, the trellis diagram and the Viterbi algorithm with hard and soft decisions, using a runnable rate-1/2 example.

Block codes chop the data into separate blocks and treat each one alone. A convolutional code works on a continuous stream: every output bit depends on the current input bit and a few previous ones, held in a short shift register. There are no block boundaries to worry about, and the encoder is a few flip-flops and exclusive-OR gates.

Convolutional codes were the workhorse of space communication for decades (Voyager, Mars rovers, GSM phones, satellite TV). They are decoded by the Viterbi algorithm, which finds the most likely transmitted sequence by walking through a graph called the trellis. The algorithm is one of the most widely used in engineering; it also appears in speech recognition and gene finding.

Left: a shift-register encoder with two delay cells and two XOR gates. Right: a four-state trellis with a highlighted path for input 1 0 1 1, whose output pairs are 11 10 00 01.
The encoder is a tiny state machine; the trellis unrolls that machine in time.

What you will learn

  • Read a convolutional encoder: constraint length K, rate, generator polynomials.
  • Write the state table and draw a trellis.
  • Run the Viterbi algorithm by hand and in code.
  • Explain the benefit of soft-decision decoding.
  • Define free distance and relate it to performance.

Key terms

  • Constraint length K: number of input bits that influence an output (current bit plus K โˆ’ 1 stored bits).
  • Generator polynomials: the tap pattern of each output; (7, 5) in octal means taps 111 and 101.
  • State: contents of the shift register (2^(Kโˆ’1) states).
  • Trellis: the state diagram unrolled over time.
  • Free distance dfree: the smallest Hamming distance between two different coded sequences.

The encoder

The classic example has K = 3: the input bit u enters a register of two delay cells holding the previous bits s1 and s2. Two outputs are computed each time:

out1 = u โŠ• s1 โŠ• s2 (taps 111, octal 7), out2 = u โŠ• s2 (taps 101, octal 5).

Two output bits for every input bit gives rate R = 1/2. The state is the pair (s1, s2), so there are four states. On each step the register shifts: new s1 = u, new s2 = old s1.

Because every transition is determined by the state and the input, you can write the whole encoder as a table:

State (s1 s2) Input 0: next, output Input 1: next, output
00 00, 00 10, 11
10 01, 10 11, 01
01 00, 11 10, 00
11 01, 01 11, 10

Feeding in 1 0 1 1 from state 00 follows the path 00 โ†’ 10 โ†’ 01 โ†’ 10 โ†’ 11 and produces 11 10 00 01, the highlighted path in the trellis. Real systems append K โˆ’ 1 zero tail bits so the encoder returns to state 00 at the end.

Distance and decoding

Two coded sequences differ in some number of positions; the smallest such number is the free distance. For this (7, 5) code dfree = 5: any error pattern with fewer than 3 errors in a short window can be corrected. Longer constraint lengths give larger dfree and better performance at the cost of more states: K = 7, the NASA standard, has 64 states and dfree = 10.

Decoding means finding the path through the trellis whose coded output is closest to what was received. There are exponentially many paths, but the Viterbi algorithm does it with only 2^(Kโˆ’1) survivors:

  1. At each time step, for each state, compute the path metric of each of the two paths that enter it (previous metric plus the branch metric, the distance between the received pair and the transition's output).
  2. Keep only the better path (the survivor) and remember where it came from.
  3. At the end, start from the best final state (state 00 if tails were used) and trace the survivors backward to read off the input bits.

The key observation is that if two paths merge in a state, they have the same future, so the worse one can never become the best. Work per bit is constant: about 2^K additions and comparisons.

Hard versus soft decisions

With hard decisions the demodulator first decides each coded bit as 0 or 1, and the branch metric is the Hamming distance. With soft decisions the decoder keeps the analog value of each received sample and the branch metric is the squared Euclidean distance to the ideal ยฑ1. Soft decoding uses the information that a received value of 0.05 is much less certain than 1.4. It typically gains about 2 dB over hard decisions, as the experiment below confirms. For this reason satellite and Wi-Fi receivers pass soft values to their decoders.

Common misconceptions

  • "A rate-1/2 code just repeats each bit." Each output is a different combination of the current and past input bits, so errors in one bit are spread over several outputs.
  • "Viterbi checks every possible path." It keeps only one survivor per state, which is what makes it fast.
  • "A larger constraint length is always better." Complexity doubles per extra memory cell, and eventually decoders become too slow or power-hungry.
  • "Hard decisions lose nothing." They throw away reliability information, costing roughly 2 dB.

Try it

First, the encoder and a hard-decision and soft-decision Viterbi decoder, simulating 125,000 bits per point. The coded system uses energy Ec = Eb/2 per coded bit, so the comparison with uncoded BPSK is fair at equal Eb/N0.

Python Viterbi decoder: hard and soft decisions

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, watch the Viterbi algorithm work on a short message: a few received bits with errors, the path metrics at each step and the decoded result. The code prints the trellis computations for you to follow by hand.

Python Viterbi by hand, step by step

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

of 5 answered You scored / 5 ยท perfect!

  1. 1. A convolutional encoder has two memory cells (constraint length 3) and two output bits per input bit. What are its rate and number of states?

    Two outputs per input gives R = 1/2; two memory cells give 2ยฒ = 4 states.
  2. 2. In the (7, 5) encoder, the current state is 10 and the input is 0. What is the output pair and the next state?

    With s1 = 1, s2 = 0, u = 0: out1 = 0โŠ•1โŠ•0 = 1, out2 = 0โŠ•0 = 0; the next state is (u, s1) = (0, 1).
  3. 3. Why can the Viterbi algorithm discard the worse of two paths that enter the same state?

    From a given state onward the possible continuations are identical, so the cheaper path always wins.
  4. 4. Roughly how much does soft-decision decoding gain over hard-decision decoding?

    Using the reliability of each received value typically gives about 2 dB.
  5. 5. Why are tail bits appended to the message?

    K โˆ’ 1 zeros flush the register, so the decoder can trace back from state 00.

Summary

  • A convolutional encoder is a shift register with XOR taps; K and the generators define the code and rate.
  • The trellis shows all state transitions over time; each coded sequence is a path through it.
  • Viterbi decoding keeps one survivor per state and traces back the best path, at constant work per bit.
  • Soft decisions gain about 2 dB over hard decisions; larger K increases dfree but also complexity.

Next: Chapter 7 review