What Is Decoding?

Decoding is the process of recovering an original message or data sequence from a received signal that has been encoded for transmission or storage, typically in the presence of noise, interference, or other channel impairments. It is the inverse operation to encoding, and its effectiveness determines how reliably information survives a noisy channel. The theoretical foundation for decoding rests on Claude Shannon's 1948 channel capacity theorem, which established that reliable communication is possible up to the channel capacity provided appropriate coding and decoding methods are used. Modern decoding algorithms sit at the intersection of information theory, probability theory, and computational complexity.

Channel decoding is the dominant context in which the term appears. When a transmitter adds structured redundancy to data before sending it, the receiver exploits that redundancy to detect and correct errors. The decoder's task is to identify, from all possible codewords, the one most consistent with the received signal.

Maximum Likelihood Decoding

Maximum likelihood (ML) decoding selects the codeword that maximizes the probability of the received signal given that codeword was sent. For many channel models, particularly the additive white Gaussian noise channel, ML decoding is equivalent to finding the codeword closest to the received vector in Euclidean distance. ML decoding is optimal in the sense of minimizing word error rate, but its complexity grows exponentially with block length, making it computationally intractable for long codes without structural shortcuts. For short block lengths and high-reliability applications, ML methods remain practical and are specified in several wireless communication standards.

Viterbi Algorithm

The Viterbi algorithm solves the ML decoding problem for convolutional codes efficiently by exploiting the trellis structure of the code. Introduced by Andrew Viterbi in 1967, the algorithm performs dynamic programming over the trellis, retaining only the most likely path to each state at each time step and discarding all others. Its computational complexity grows linearly in block length and exponentially only in the constraint length of the code, making it feasible for codes used in practice. The Viterbi algorithm is used in GSM mobile telephony, digital video broadcasting, and satellite communication systems.

Belief Propagation

Belief propagation, also called the sum-product algorithm, is a message-passing algorithm for computing marginal probabilities on graphical models. Applied to decoding, it operates on the factor graph of a code, passing probability estimates (beliefs) between variable nodes representing code bits and check nodes representing parity constraints. For codes whose factor graphs are cycle-free, belief propagation is exact. For codes with cycles, such as low-density parity-check (LDPC) codes, it is an approximation, but one that performs close to the Shannon limit in practice. LDPC codes decoded by belief propagation are now specified in IEEE 802.11n, DVB-S2, and 5G NR standards.

Turbo Decoding

Turbo codes, introduced in 1993 by Berrou, Glavieux, and Thitimajshima, combine two recursive systematic convolutional codes with an interleaver and use iterative decoding between two soft-input soft-output decoders. Each decoder passes extrinsic information to the other, and after several iterations the combined decoder achieves near-Shannon-limit performance. The iterative exchange of soft information is the key insight that made turbo codes practical. Turbo decoding is used in 3G UMTS and LTE cellular networks, and the turbo principle directly influenced the later development of LDPC and polar code decoders.

Applications

Decoding has applications in a wide range of disciplines, including:

• Wireless communications, where error-correcting decoders recover data transmitted over fading radio channels
• Data storage systems, including hard drives and flash memory, where decoders correct read errors caused by media imperfections
• Deep-space and satellite communications, where link budgets demand near-optimal coding gain
• Digital video broadcasting and streaming, where decoding enables reliable delivery of compressed media over lossy channels
• DNA data storage research, where biological sequencing introduces substitution and deletion errors requiring specialized decoders