Viterbi Convolutional Decoding

Trace minimum-distance decoding through a finite-state convolutional-code trellis.

Viterbi Convolutional Decoding

Worked Example

Let's trace the Viterbi algorithm for decoding a rate 1/2, memory 2 convolutional code with generator polynomials (111, 101) in binary. Assume the input message is "101" and we use "Zero tail" termination (appending two zeros). The initial state is always 00.

Stage 1 (Input bit 1):
State 00 transitions to 10.
Output bits: c1 = 1^0^0 = 1, c2 = 1^0 = 1. Output is 11.
Cost accumulates based on Hamming distance to received bits.
Stage 2 (Input bit 0):
State 10 transitions to 01.
Output bits: c1 = 0^1^0 = 1, c2 = 0^0 = 0. Output is 10.
Path cost: accumulated cost + Hamming distance.
Stage 3 (Input bit 1):
State 01 transitions to 10.
Output bits: c1 = 1^0^1 = 0, c2 = 1^1 = 0. Output is 00.
Path cost is updated.
Stages 4 and 5 (Zero tail inputs 0, 0):
Input 0: State 10 transitions to 01 (output 10).
Input 0: State 01 transitions to 00 (output 11).
Final state is 00. The total encoded bits are 1110001011.
Traceback:
We start from the final state 00 and trace the surviving branches backwards. The lowest-cost survivor per state is kept. In this example, if the received bits are 1111001011 (one flip at position 3), the best Hamming metric is 1, and the decoded message is 101.

Experiment

You can interact with the Viterbi Convolutional Decoding module to observe how the trellis updates.

Select Message to "101".
Set Termination to "Zero tail".
Change Flip position to "3" and observe the "Best Hamming metric" becomes 1 because the 3rd bit of the encoded string was flipped.
Set Termination to "Unterminated" and notice how the trellis stages decrease because no zero tail bits are appended. The final state is no longer forced to be 00.

Limitations

The implemented model assumes a rate 1/2, memory 2 convolutional encoder with specific generator polynomials (111, 101). It only supports short discrete messages up to 4 bits (plus 2 tail bits). Real-world applications often use longer memory (e.g., constraint length 7) and continuously stream data, utilizing sliding window traceback rather than storing the entire trellis in memory. Furthermore, this demonstration uses hard-decision decoding (Hamming distance) instead of soft-decision decoding (Euclidean distance), which would provide better error correction performance in a continuous channel like AWGN. An empty message results in 0 trellis stages and undefined decoding behaviour.

References

The Viterbi algorithm for convolutional codes and the specific trellis structure used in this module are based on standard digital communications theory. A detailed explanation can be found in the MIT 6.02 course materials: MIT 6.02 Review on Convolutional Codes and Viterbi Decoding. This resource explains state transitions, branch metrics, and traceback.

Viterbi Convolutional Decoding