How Viterbi Algorithm Decodes Convolutional Codes

The Viterbi algorithm is a dynamic programming method designed to find the most likely sequence of hidden states—known as the Viterbi path—that corresponds to an observed sequence of received signals. In digital communications, it serves as the maximum-likelihood decoder for convolutional codes transmitted across noisy binary channels. By tracking state transitions through a structured graph called a trellis diagram, the algorithm evaluates received binary streams, calculates error metrics, continuously discards suboptimal paths, and accurately reconstructs the original binary information with high computational efficiency.

Convolutional Encoding and Channel Noise

To understand Viterbi decoding, one must first look at the encoding process. A convolutional encoder processes an incoming stream of binary information bits through a series of shift registers. The output bits are generated by performing modulo-2 addition (XOR operations) on selected register contents based on predefined generator polynomials. Because the output depends not only on the current input bit but also on previous bits stored in memory, the encoder introduces mathematical redundancy with memory.

When these encoded binary bits are transmitted across a physical channel, noise causes bit-flip errors (in a Binary Symmetric Channel) or signal degradation (in an Additive White Gaussian Noise channel). The receiver receives a corrupted binary sequence that may no longer perfectly match any valid output sequence generated by the transmitter.

The Trellis Representation

The state of a convolutional encoder at any given time is defined by the binary values held within its shift registers. As new bits enter, the encoder moves from its current state to a new state, emitting a specific binary output pair or triplet.

When these transitions are mapped across time, they form a trellis diagram. Each node in the trellis represents an encoder state at a specific time step, and the branches connecting nodes represent the valid state transitions and their corresponding expected binary output codes.

The Viterbi Decoding Procedure

The Viterbi algorithm operates on the received sequence by stepping through the trellis diagram sequentially using three core operations:

  1. Branch Metric Calculation (BMC): For every time step, the algorithm compares the received binary bits with the expected binary code on every branch of the trellis. For hard-decision decoding on a binary channel, the algorithm calculates the Hamming distance—the count of differing bits between the received binary pair and the expected branch pair.
  2. Add-Compare-Select (ACS):
    • Add: The algorithm adds the branch metric of each transition to the accumulated metric (Path Metric) of the starting state.
    • Compare: Multiple branches often converge into a single state at the next time step. The algorithm compares the accumulated path metrics of all incoming paths.
    • Select: The path with the lowest accumulated metric (least number of bit errors) is chosen as the “survivor path” for that state, while all other competing paths entering that state are permanently discarded.
  3. Traceback: After processing the entire sequence—or reaching a sufficient traceback depth (typically 5 to 7 times the constraint length of the code)—the algorithm traces backward along the chain of survivor paths. Because all survivor paths converge to a single dominant historical path, tracing backward identifies the exact sequence of states the encoder moved through.

Data Recovery and Efficiency

Once the historical state path is determined through traceback, the decoder extracts the original input bits associated with each state transition, effectively recovering the uncorrupted binary data.

Instead of exhaustively evaluating every possible sequence—which would scale exponentially with the length of the transmission—the Viterbi algorithm scales linearly with sequence length. By discarding non-surviving paths at every step, it guarantees finding the mathematically optimal, maximum-likelihood binary sequence while maintaining the computational feasibility required for real-time digital communication systems.