Convolutional Codes & Viterbi Decoding

Memory-based encoding, trellis representations, and the algorithm that reached the edge of the solar system

Roadmap

Historical Origins

Block Codes vs. Convolutional Codes

Encoder Structure

Generator Polynomials

State Diagram

Trellis Diagram

Code Rate & Constraint Length

Free Distance

The Viterbi Algorithm

Branch & Path Metrics

Viterbi: Worked Example (1/3)

Viterbi: Worked Example (2/3)

Viterbi: Worked Example (3/3)

Hard vs. Soft Decision Decoding

Most modern Viterbi decoders use 3-bit (8-level) soft quantization. Diminishing returns beyond 4 bits.

Punctured Convolutional Codes

Applications: Deep Space

Applications: Terrestrial Communications

Sequential Decoding

Python: Convolutional Encoder

class ConvolutionalEncoder:
    """Rate 1/n convolutional encoder with K constraint length."""
    def __init__(self, generators, K):
        """
        generators: list of generator polynomials (octal)
        K: constraint length
        """
        self.generators = [int(oct_str) for oct_str in generators]
        self.K = K
        self.n = len(generators)
        self.state = 0  # shift register state

    def _octal_to_taps(self, octal_val):
        """Convert octal generator to binary tap positions."""
        binary = bin(int(str(octal_val), 8))[2:]
        return [int(b) for b in binary.zfill(self.K)]

    def encode_bit(self, input_bit):
        """Encode single input bit, return n output bits."""
        # Shift input into register
        combined = (input_bit << (self.K - 1)) | self.state
        outputs = []
        for gen in self.generators:
            taps = self._octal_to_taps(gen)
            out = 0
            for i, tap in enumerate(taps):
                if tap:
                    out ^= (combined >> (self.K - 1 - i)) & 1
            outputs.append(out)
        # Update state
        self.state = (combined >> 1) & ((1 << (self.K-1)) - 1)
        return outputs

    def encode(self, message):
        """Encode full message with tail bits."""
        self.state = 0
        output = []
        # Encode message bits
        for bit in message:
            output.extend(self.encode_bit(bit))
        # Add tail bits to flush encoder to state 0
        for _ in range(self.K - 1):
            output.extend(self.encode_bit(0))
        return output

Python: Encoder Demo & Test

# Create rate 1/2, K=3 encoder with generators (7, 5)
encoder = ConvolutionalEncoder(['7', '5'], K=3)

# Encode a message
message = [1, 1, 0, 1, 0]
encoded = encoder.encode(message)
print(f"Message:  {message}")
print(f"Encoded:  {encoded}")
# Output: [1,1, 1,0, 0,1, 0,0, 0,1, 1,1, 0,0]

# Show output as pairs
pairs = [(encoded[i], encoded[i+1]) for i in range(0, len(encoded), 2)]
print(f"As pairs: {pairs}")
# [(1,1), (1,0), (0,1), (0,0), (0,1), (1,1), (0,0)]

# Verify by tracing state machine manually
encoder2 = ConvolutionalEncoder(['7', '5'], K=3)
print("\nStep-by-step trace:")
print(f"{'Time':>4} {'Input':>5} {'State':>7} {'Output':>7}")
for i, bit in enumerate(message + [0, 0]):  # +tail
    state_before = format(encoder2.state, '02b')
    out = encoder2.encode_bit(bit)
    print(f"{i:>4} {bit:>5} {state_before:>7} {''.join(map(str,out)):>7}")

# Verify: rate = len(message) / len(encoded)
rate = len(message) / (len(message) + encoder.K - 1) / encoder.n
print(f"\nEffective rate: {len(message)}/{len(encoded)} "
      f"= {len(message)/len(encoded):.3f}")

Python: Viterbi Decoder

def viterbi_decode(received, generators, K):
    """Hard-decision Viterbi decoder for rate 1/n convolutional code."""
    n_outputs = len(generators)
    n_states = 1 << (K - 1)
    n_steps = len(received) // n_outputs

    # Precompute branch outputs for each state and input
    enc = ConvolutionalEncoder([str(g) for g in generators], K)
    branch_output = {}
    for state in range(n_states):
        for inp in [0, 1]:
            enc.state = state
            out = enc.encode_bit(inp)
            next_state = enc.state
            branch_output[(state, inp)] = (next_state, out)

    # Initialize path metrics
    INF = float('inf')
    path_metric = [INF] * n_states
    path_metric[0] = 0
    survivor = [[[] for _ in range(n_states)] for _ in range(n_steps)]

    # Forward pass: ACS
    for t in range(n_steps):
        rx = received[t * n_outputs : (t + 1) * n_outputs]
        new_metric = [INF] * n_states
        for state in range(n_states):
            if path_metric[state] == INF:
                continue
            for inp in [0, 1]:
                ns, out = branch_output[(state, inp)]
                bm = sum(r != o for r, o in zip(rx, out))
                candidate = path_metric[state] + bm
                if candidate < new_metric[ns]:
                    new_metric[ns] = candidate
                    survivor[t][ns] = survivor[max(0,t-1)][state] + [inp] \
                                       if t > 0 else [inp]
        path_metric = new_metric

    # Trace back from state 0
    return survivor[n_steps - 1][0][: -(K-1)]  # remove tail bits

Performance Characteristics

Summary