How NASA talks to spacecraft billions of kilometers away — the algorithm behind deep space communication
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.
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.
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
| Level | What Happens | Time Estimate |
|---|---|---|
| 1 | Clean encoded signal, no bit flips | <10s |
| 2-4 | 5-15% of bits flipped (noise) | 20-60s |
| 5-7 | 20-35% bit flips, longer messages | 1-5m |