10.3 Viterbi Algorithm

The Viterbi Algorithm is a key technique for decoding convolutional codes. It uses dynamic programming to find the most likely sequence of hidden states in a trellis diagram, efficiently determining the original message from a noisy received signal.

This algorithm employs soft-decision or hard-decision decoding, with soft-decision typically offering better performance. It uses Add-Compare-Select operations at each trellis stage and a traceback to find the most likely path, balancing accuracy and computational complexity.

Viterbi Algorithm Basics

Decoding Methods

• Maximum likelihood decoding determines the most likely transmitted sequence by comparing received sequence with all possible transmitted sequences
• Soft-decision decoding uses received signal values as input to the decoder, providing more information than hard-decision decoding
  • Utilizes analog information about the received signal
  • Generally achieves better performance compared to hard-decision decoding
• Hard-decision decoding uses binary values (0 or 1) as input to the decoder, discarding analog information about the received signal
  • Simplifies the decoding process but may result in suboptimal performance
• Decoding depth refers to the number of trellis stages considered in the decoding process
  • Longer decoding depth improves error correction capability but increases complexity
  • Typical values range from 3 to 7 times the constraint length of the convolutional code

Key Concepts

• Viterbi algorithm is a dynamic programming approach to finding the most likely sequence of hidden states in a hidden Markov model
  • Widely used in convolutional code decoding for its efficiency and optimality
• Trellis diagram represents the possible state transitions of the encoder over time
  • Each stage corresponds to a time step, and each node represents a possible encoder state
  • Branches between nodes represent state transitions based on input bits
• Path metric measures the likelihood or distance of a particular path through the trellis
  • Calculated using the received sequence and the expected output for each state transition
  • Lower path metric indicates a more likely path (for distance metrics)

Viterbi Algorithm Operations

Core Steps

• Add-Compare-Select (ACS) operation is performed at each trellis stage to update path metrics and survivor paths
  • Add: Calculate branch metrics for each possible state transition
  • Compare: Compare path metrics of arriving branches at each node
  • Select: Choose the branch with the best path metric as the survivor path
• Traceback operation determines the most likely state sequence by tracing the survivor paths backward through the trellis
  • Starts from the node with the best path metric at the final stage
  • Follows the survivor path backward to the initial stage
• Path memory stores the survivor paths at each trellis stage
  • Typically implemented as a register exchange or trace back memory
  • Size depends on the decoding depth and the number of states in the trellis

Algorithm Variations

• Viterbi algorithm can be applied to both terminated and unterminated convolutional codes
  • Terminated codes have a known initial and final state (usually all zeros)
  • Unterminated codes require a sufficiently long decoding depth to achieve good performance
• Sliding window Viterbi algorithm reduces memory requirements by processing the trellis in fixed-size windows
  • Only the most recent window of survivor paths is stored
  • Trade-off between memory usage and decoding latency

Distance Metrics in Viterbi Algorithm

Commonly Used Metrics

• Hamming distance metric counts the number of bit differences between the received sequence and the expected output sequence
  • Suitable for hard-decision decoding, where the inputs are binary values
  • Computationally simple but may not achieve optimal performance
• Euclidean distance metric calculates the squared difference between the received signal values and the expected output values
  • Suitable for soft-decision decoding, where the inputs are analog signal values
  • Provides better performance by incorporating more information about the received signal
  • Requires more computational complexity compared to Hamming distance

Metric Calculation

• Branch metric represents the distance or likelihood of a particular state transition
  • Calculated for each possible state transition at each trellis stage
  • Depends on the chosen distance metric (Hamming or Euclidean)
• Path metric accumulates the branch metrics along a particular path through the trellis
  • Updated at each trellis stage using the ACS operation
  • Represents the total distance or likelihood of a path up to the current stage
• Normalization techniques can be applied to prevent path metric overflow
  • Ensures numerical stability for long decoding depths
  • Examples include rescaling or subtracting a common value from all path metrics