What Is Maximum Likelihood Decoding?

Maximum likelihood decoding is a method in digital communications and coding theory that selects the codeword most likely to have been transmitted given the sequence received at the channel output. The decoder searches the set of all valid codewords for the one that maximizes the conditional probability of the received sequence, a criterion that minimizes the word error probability when all codewords are equally likely to be sent. Maximum likelihood decoding belongs to the field of channel coding and draws on probability theory, combinatorics, and algorithm design. It serves as the theoretical performance benchmark against which all practical decoders are compared, even when exact ML decoding is computationally infeasible.

The computational cost of exhaustive maximum likelihood decoding grows exponentially with the length and dimension of the code, making it impractical for long block codes. However, when the encoder is a finite-state machine, such as a convolutional encoder or a trellis-coded modulation scheme, the Viterbi algorithm reduces ML decoding to a dynamic programming search over a trellis graph, achieving optimal performance with complexity that grows only linearly in code length. For linear block codes, sphere decoding and semidefinite relaxation offer efficient ML solutions for moderate block lengths.

Trellis-Based Decoding with the Viterbi Algorithm

The Viterbi algorithm, published by Andrew Viterbi in 1967, is the canonical implementation of ML decoding for convolutional codes. The algorithm maintains, at each stage of the trellis, the accumulated path metric for the single surviving path entering every state, discarding all other paths at each step by keeping only the one with the lowest cumulative Hamming distance or Euclidean distance from the received sequence. This survivor path selection reduces the decoding search from exponential to linear complexity in the number of received symbols. The Viterbi algorithm has been deployed in IEEE 802.11a/g wireless LAN standards, the GSM cellular standard, and digital video broadcast receivers. IEEE Xplore documents its applications in maximum likelihood convolutional decoding with the Viterbi algorithm, including implementations on dedicated hardware for low-latency decoding.

Soft-Decision and Hard-Decision Variants

Maximum likelihood decoding operates in two modes depending on the channel output representation. In hard-decision decoding, the receiver first quantizes each received sample to the nearest constellation point and then finds the codeword closest in Hamming distance to this binary sequence. In soft-decision decoding, the receiver passes unquantized channel observations directly to the decoder, which computes Euclidean distances or log-likelihood ratios to the candidate codewords. Soft-decision ML decoding achieves roughly 2 to 3 dB of additional coding gain over hard-decision decoding for additive white Gaussian noise channels, because it exploits the reliability information discarded by the quantization step. An overview of soft-decision trellis algorithms and their complexity-performance tradeoffs is available through ScienceDirect topics on Viterbi decoding.

Sphere Decoding for Block Codes

For linear block codes, exhaustive ML search is prohibitive, but sphere decoding limits the search to codewords lying within a Euclidean sphere of a chosen radius centered on the received vector. If the sphere contains at most one codeword, the algorithm returns the ML solution with certainty; if it contains more than one, it selects the nearest. The sphere radius is adjusted dynamically to keep average search complexity manageable, and for high signal-to-noise ratios the algorithm approaches ML performance with polynomial average complexity. Sphere decoding is applied to MIMO spatial multiplexing receivers, where the received vector is a superposition of transmitted streams and the ML problem is equivalent to finding the lattice point closest to the received signal. Practical implementations for Texas Instruments DSP platforms are described in TI's Viterbi decoding application note for the TMS320C55x, which covers both soft-output and hard-decision architectures.

Applications

Maximum likelihood decoding has applications in a wide range of communications and storage systems, including:

• Cellular and wireless LAN receivers, where convolutional and turbo codes with Viterbi decoding improve link reliability
• Deep-space communications, where coding gain is critical at very low received signal-to-noise ratios
• Magnetic and solid-state data storage, where channel codes protect against read errors
• Digital video broadcasting and satellite television receivers using trellis-coded modulation
• MIMO wireless systems, where sphere decoding achieves near-optimal performance in multi-antenna spatial multiplexing