What is it?

Imagine sending a flashlight signal through a thick fog. The person on the other end sees a blurry, flickering light — not the clean pattern you sent. They need to guess the most likely original message.

The Viterbi cipher simulates this. A message is convolutionally encoded — each bit produces multiple output bits that overlap with neighboring bits. The encoded signal is then passed to you with some bits possibly flipped (noise). You use the Viterbi algorithm to find the most likely path through the encoding trellis, undoing the noise.

Concrete Example

The message CAT (binary: 01000011 01000001 01010100) is encoded using a rate-1/2 convolutional encoder. Each input bit produces 2 output bits. The generators [7, 5] mean:

Generator 7 (binary 111):  output_bit0 = input_bit XOR prev_bit1 XOR prev_bit2
Generator 5 (binary 101):  output_bit1 = input_bit XOR prev_bit2

The result is a stream twice as long as the original. The Viterbi algorithm traces through all possible states to find which path produces the encoded output with the fewest errors.

How It Works

1. The answer is converted to binary bits (8 bits per ASCII character)
2. A convolutional encoder with memory (constraint length 3) creates overlapping output bits
3. Higher difficulties flip some bits to simulate transmission noise
4. Build a trellis: all possible states × time steps, with branch metrics (Hamming distance)
5. Use the Viterbi algorithm to find the minimum-cost survivor path
6. Convert the decoded bits back to ASCII characters → the answer

Step-by-Step Solving

def viterbi_decode(encoded, gen0, gen1, constraint):
    # Build trellis and find min-cost path
    n_states = 1 << (constraint - 1)
    # For each time step, compute branch metrics
    # Track survivor paths and their cumulative costs
    # Back-trace from the lowest-cost final state
    pass  # See the Viterbi algorithm for full implementation

Real-World Applications

• Deep space networks (NASA/JPL): Voyager, Mars rovers, and New Horizons all use convolutional codes decoded by the Viterbi algorithm
• Digital TV (DVB-T, ATSC): Broadcast television uses Viterbi decoding to handle interference
• GSM mobile phones: Every voice call is convolutionally encoded and Viterbi-decoded
• WiFi (802.11a/g/n): Uses convolutional codes for error correction in wireless transmissions
• Speech recognition: The Viterbi algorithm also powers Hidden Markov Models (HMMs) used in speech-to-text