Convolutional Codes

Block codes divide a data stream into fixed blocks and add parity independently to each block. Convolutional codes take a fundamentally different approach: the encoder has memory, and each output bit depends not only on the current input bit but also on a fixed number of previous input bits. This memory-based encoding produces a continuous stream of coded bits and is particularly effective for channels with continuous noise, making convolutional codes essential in wireless communication, satellite links, and GSM systems.

Core Concept of Convolutional Codes

The encoder of a convolutional code is a finite state machine built from shift registers. When 1 input bit enters, the register shifts and generates n output bits using n XOR (modulo-2 adder) circuits. Each XOR circuit computes a linear combination of the current input bit and the K-1 bits stored in the register, where K is the constraint length. The output at any moment thus depends on K consecutive input bits, giving the code its memory.

The code rate R = k/n (where k = input bits per clock, n = output bits per clock) measures bandwidth efficiency. The most common configuration is rate 1/2 with K = 3 or K = 7. Increasing K improves error correction capability exponentially but also increases decoding complexity, since the number of encoder states is 2^(K-1). For K = 7, there are 64 states, which is the standard used in NASA's deep space communication and in 3G/4G wireless standards.

The generator polynomials g1 and g2 define which register taps feed each XOR. They are usually written in binary (bit pattern of register connections) or octal shorthand. For the standard rate 1/2 K=3 code: g1 = 111 (connects input, D1, D2 to output 1) and g2 = 101 (connects input and D2 to output 2). In octal, these are g1=7 and g2=5.

Mathematical Expression

The output sequences v1 and v2 are computed by the convolution of the input sequence u with the generator sequences g1 and g2 over GF(2). This is where the name convolutional code comes from. The output at time n is:

• v1(n) = u(n) XOR u(n-1) XOR u(n-2) [generator g1 = 111]
• v2(n) = u(n) XOR u(n-2) [generator g2 = 101]

The free distance d_free is the minimum Hamming weight among all non-zero codewords, and it determines error correction capability. For the rate 1/2 K=3 code, d_free = 5, allowing correction of t = floor((d_free - 1)/2) = 2 bit errors. Higher constraint lengths increase d_free and hence correction power.

Practical Understanding

Convolutional codes are particularly suited to channels where errors occur continuously and randomly (AWGN channels) rather than in bursts. They provide coding gain, meaning that a coded system with convolutional encoding can achieve the same bit error rate as an uncoded system but at a lower required signal-to-noise ratio. For example, a rate 1/2 K=7 code provides approximately 5 dB of coding gain over uncoded BPSK on an AWGN channel.

In practice, convolutional codes are almost never used alone for decoding. They are paired with the Viterbi algorithm, which performs maximum likelihood sequence estimation efficiently by exploiting the trellis structure of the code. The trellis is a time-expanded state diagram of the encoder, and Viterbi decoding finds the most likely path through this trellis given the received sequence.

Given:
Input sequence: u = 1, 0, 1, 1 (followed by 2 zero flush bits: 1,0,1,1,0,0)
Encoder: Rate 1/2, K=3, g1=111, g2=101
Initial state: D1=0, D2=0

Why this formula applies:
v1(n) = u(n) XOR D1 XOR D2,  v2(n) = u(n) XOR D2

Formula:
v1 = u XOR D1 XOR D2,   v2 = u XOR D2

Substitution and Calculation (state = D1,D2):
Time 1: u=1, state=00 → v1=1X0X0=1, v2=1X0=1  Output: 11  Next state: 10
Time 2: u=0, state=10 → v1=0X1X0=1, v2=0X0=0  Output: 10  Next state: 01
Time 3: u=1, state=01 → v1=1X0X1=0, v2=1X1=0  Output: 00  Next state: 10
Time 4: u=1, state=10 → v1=1X1X0=0, v2=1X0=1  Output: 01  Next state: 11
Time 5: u=0, state=11 → v1=0X1X1=0, v2=0X1=1  Output: 01  Next state: 01
Time 6: u=0, state=01 → v1=0X0X1=1, v2=0X1=1  Output: 11  Next state: 00

Final Answer:
Encoded output: 11 10 00 01 01 11  (12 bits for 4 data + 2 flush bits)
Code rate = 1/2 confirmed: 6 input bits produced 12 output bits

Exam Tip: Number of encoder states = 2^(K-1). For K=3, there are 4 states. Flush bits (K-1 zeros appended at end) are required to return encoder to zero state. Free distance d_free determines correction power, not constraint length alone.

Mechanism Summary

• Each new input bit shifts into the register, and the oldest bit is discarded. This shift operation creates a sliding window of K bits that influences all current outputs.
• At each clock cycle, n output bits are generated. For rate 1/2, two bits come out for every one bit in.
• The trellis diagram represents encoder operation over time. Each node is a state, each branch is one clock transition with input and output labeled.
• K-1 tail bits (zeros) are appended at end of message to flush the encoder back to all-zero state, enabling proper trellis termination.
• Puncturing is used to increase code rate without redesigning the encoder: some output bits are periodically deleted before transmission.

Quick Revision

• Convolutional encoder: shift register with XOR feedback. Code rate R = k/n. Constraint length K = register length + 1.
• Number of states in encoder = 2^(K-1). For K=7 (standard), 64 states.
• Generator polynomials define which register taps feed each output. Written in binary or octal.
• Output at time n is modulo-2 convolution of input with generator polynomial, hence the name.
• Free distance d_free determines error correction: t = floor((d_free - 1)/2) errors correctable.
• Exam trap: Constraint length K is NOT the number of delay elements. K = number of delay elements + 1 = memory M + 1.
• Flush bits = K-1 zeros must be appended after message to terminate trellis properly.