What Are Convolutional codes?

Convolutional codes are a class of error-correcting codes used in channel coding that generate redundant output bits by passing information bits through a finite-memory shift register whose outputs are combined by modular addition. Unlike block codes, which encode fixed-length input blocks independently, convolutional codes process an incoming bit stream continuously, with each output symbol depending on a window of recent input bits determined by the constraint length of the code. This memory structure allows convolutional codes to exploit temporal correlations in the encoded stream and to achieve reliable communication over noisy channels when paired with a maximum-likelihood decoder. First described by Peter Elias in 1955, convolutional codes became a cornerstone of practical channel coding in satellite communication, cellular networks, and digital broadcasting.

The rate of a convolutional code is expressed as k/n, where k input bits produce n output bits at each step. Common rates are 1/2 and 1/3. The constraint length K governs how many input bits influence each output symbol and determines the number of states in the trellis representation of the code.

Code Structure and Trellis Representation

A convolutional encoder consists of a shift register with K stages, multiple modulo-2 adder connections to the register taps, and n output lines, one per encoded bit produced per input bit. The specific connections from register stages to adders are described by the code's generator polynomials. The internal state of the shift register at any moment encodes the encoder's memory, and the transitions between states as each new input bit arrives form a trellis diagram: a graph that unfolds the code's state machine across time. The trellis is central to decoding because the most likely transmitted sequence corresponds to the most likely path through it. The IEEE Xplore paper on maximum-likelihood decoding of convolutional codes provides analysis of decoder implementations and their error correction capability for different code parameters.

Viterbi Decoding

The Viterbi algorithm, published by Andrew Viterbi in 1967, is the standard algorithm for maximum-likelihood decoding of convolutional codes. It performs a dynamic-programming search through the trellis, computing a branch metric for each possible state transition at each time step and maintaining for each state only the path with the minimum cumulative metric. The algorithm eliminates suboptimal paths incrementally, avoiding the exponential growth in complexity that would result from exhaustive search. The original Viterbi paper on error bounds and decoding established the theoretical foundation for this approach. In hardware, the Viterbi decoder operates at rates of hundreds of megabits per second in modern integrated circuits, making it practical for real-time decoding in wireless receivers. The soft-decision variant, which accepts analog likelihood values rather than hard bit decisions from the demodulator, provides an additional coding gain of roughly 2 decibels compared to hard-decision decoding.

Turbo Codes and Successor Approaches

Convolutional codes are building blocks for turbo codes, introduced by Berrou, Glavieux, and Thitimajshima in 1993, which concatenate two recursive systematic convolutional encoders separated by an interleaver and apply iterative belief propagation decoding. Turbo codes achieve near-Shannon-limit performance and replaced standalone convolutional codes in standards including 3GPP LTE. Tail-biting convolutional codes, which set the initial register state equal to the final state to produce a periodic trellis, are used in control channels of LTE and WiMAX where block-code-like behavior is needed. The IEEE Xplore paper on tail-biting convolutional codes addresses reduced-complexity decoding algorithms for this variant.

Applications

Convolutional codes have applications across communications engineering, including:

• Satellite and deep-space communication, where they were adopted by NASA and the CCSDS standard for their ability to recover data across long-distance noisy links
• Digital multimedia broadcasting standards such as DVB and ISDB, where concatenated Reed-Solomon and convolutional coding protects audio and video streams
• Cellular radio systems, where 2G GSM and early 3G standards used convolutional coding for speech and control channels
• Wireless local area networks, including early IEEE 802.11a/g physical layers that employed convolutional codes at rates 1/2 through 3/4