Convolutional Codes

Convolutional Codes: Memory-Based Error Protection

While block codes like Hamming codes process data in independent chunks, convolutional codes take a fundamentally different approach — they encode data as a continuous stream where each output bit depends not only on the current input but also on several previous inputs. This "memory" in the encoding process creates powerful error-correcting capabilities that have made convolutional codes the backbone of mobile communication, satellite links, and deep-space exploration for decades.

The Core Idea: Encoding with Memory

Think of it this way: imagine you are creating a secret message where each coded word depends on the current word you want to say PLUS the last two words you said. Even if some words get garbled in transmission, the receiver can figure out what you meant by exploiting the dependencies between consecutive words. This is the essence of convolutional coding — creating dependencies that a smart decoder can exploit.

A convolutional encoder is characterized by three parameters:

• k = number of input bits per time step (usually 1)
• n = number of output bits per time step (usually 2 or 3)
• K = constraint length (number of input bits that influence current output)

The code rate is r = k/n (e.g., rate 1/2 means 1 input bit produces 2 output bits — 50% overhead).

How the Encoder Works

A rate 1/2, constraint length K=3 encoder (used in GSM):

The encoder consists of:

• A shift register with K-1 = 2 memory stages (storing previous input bits)
• Two modulo-2 adders (XOR gates) with different connection patterns
• Connection polynomials: g1 = (1,1,1), g2 = (1,0,1)

Operation for input sequence 1 0 1 1:

Output sequence: 11, 10, 00, 01

Notice how each output pair depends on the current input AND the two previous inputs stored in the shift register.

The Trellis Diagram

The trellis diagram is the key representation for understanding convolutional codes. It shows all possible encoder states and transitions over time:

• States: 2^(K-1) possible register contents (4 states for K=3)
• Branches: Each state has 2 outgoing branches (for input 0 or 1)
• Labels: Each branch is labeled with the output bits
• Paths: The encoded sequence corresponds to a path through the trellis

The trellis makes decoding possible: the receiver finds the path through the trellis that most closely matches the received sequence.

Viterbi Decoding: Optimal Path Finding

The Viterbi algorithm (1967) finds the maximum-likelihood path through the trellis efficiently:

Algorithm steps:

1. Start at the known initial state (all zeros)
2. At each time step, for each state:

• Calculate the "branch metric" for each incoming branch (Hamming distance between received bits and expected bits)
• Add branch metric to the previous "path metric" of the source state
• Keep only the survivor path (minimum cumulative metric) to each state
• Discard all other paths to that state

1. After processing all received bits, trace back from the final state with lowest metric

Key insight: The number of survivor paths equals the number of states (2^(K-1)), regardless of the sequence length. This makes the algorithm computationally feasible.

Complexity: Proportional to 2^(K-1) × L, where L is the sequence length. This grows exponentially with constraint length but is linear in data length.

Free Distance: The Key Performance Metric

The free distance (dfree) is the minimum Hamming distance between any two valid encoded sequences:

For the rate 1/2, K=3 code: dfree = 5

This means any pattern of up to ⌊(dfree-1)/2⌋ = 2 bit errors in a constraint-length window can be corrected.

BER approximation for hard-decision Viterbi decoding in AWGN:

BER ≈ (1/k) × Σ cd × erfc(√(d × r × Eb/N₀))

Where cd is the number of paths at distance d from the correct path.

Coding gain: The rate 1/2, K=7 code (NASA standard) provides approximately 5 dB coding gain — meaning it achieves the same BER as uncoded BPSK with 5 dB less transmit power. This is an enormous advantage in power-limited systems.

Hard vs. Soft Decision Decoding

Hard decision: The demodulator outputs definite 0/1 decisions. The Viterbi decoder uses Hamming distance as the metric.

Soft decision: The demodulator outputs reliability information (e.g., received analog voltage level). The Viterbi decoder uses Euclidean distance.

Soft-decision decoding provides approximately 2 dB improvement over hard-decision — essentially "free" performance gain at the cost of slightly wider data paths in the decoder.

Punctured Codes: Flexible Rate Adjustment

Higher code rates (2/3, 3/4, 5/6, 7/8) can be achieved by "puncturing" — periodically deleting some output bits:

• Start with rate 1/2 mother code
• Delete selected bits according to a puncture pattern
• Rate 3/4: transmit 3 out of every 4 coded bits

The decoder inserts "erasures" at punctured positions and proceeds with standard Viterbi decoding. This allows a single encoder/decoder design to support multiple code rates.

Turbo Codes: The Convolutional Revolution

Turbo codes (1993) combine two convolutional encoders with an interleaver between them, decoded iteratively:

• Two rate 1/2 recursive systematic convolutional (RSC) encoders
• Random interleaver between them
• Iterative decoding exchanging soft information between two component decoders
• Achieve within 0.5 dB of Shannon capacity!

This breakthrough revolutionized the field and was adopted in 3G/4G cellular standards.

Applications

Key Takeaways

1. Convolutional codes encode data continuously with memory, where each output depends on current and previous input bits.
2. The Viterbi algorithm finds the optimal decoding path through the trellis with complexity proportional to 2^(K-1) per bit.
3. Free distance dfree determines error correction capability — larger constraint length generally means larger dfree and better performance.
4. Soft-decision Viterbi decoding gains approximately 2 dB over hard-decision at minimal extra complexity.
5. Puncturing allows flexible rate adjustment from a single mother code, simplifying hardware design.
6. Turbo codes (parallel concatenated convolutional codes) approach Shannon capacity and revolutionized modern digital communication.