Fountain Codes for When Half Your Packets Vanish

A balloon at 30,000 metres transmits telemetry through air so thin it’s nearly vacuum. The radio link is marginal. Packets arrive out of order, or don’t arrive at all. You can’t afford a bidirectional protocol—asking “please resend packet 47” wastes seconds you don’t have, and by then the balloon has drifted into worse signal.

Fountain codes solve this by making every transmitted packet equally useful. Encode your data once, then generate an endless stream of redundant packets. The receiver reconstructs the original from any sufficient subset—doesn’t matter which ones arrive. If you need 100 packets’ worth of information, maybe 120 packets will do it, or 150 if conditions are bad. You keep transmitting until you hear back, or don’t, and trust that enough got through.

Here’s a toy implementation—Rust on the balloon, Haskell on the ground:

fn encode_packet(data: &[u8], seed: u64) -> (Vec<bool>, u8) {
    let mut rng = seed;
    let mut pattern = Vec::with_capacity(data.len());
    let mut symbol = 0u8;

    for &byte in data {
        rng = rng.wrapping_mul(1103515245).wrapping_add(12345);
        let include = rng % 2 == 0;
        pattern.push(include);
        if include {
            symbol ^= byte;
        }
    }

    (pattern, symbol)
}

import Data.Bits (xor)
import Data.List (find, partition)
import Data.Word (Word8)

type Row = ([Bool], Word8)

decode :: [[Bool]] -> [Word8] -> Maybe [Word8]
decode patterns received
  | length patterns /= length received = Nothing
  | length pivots == width = traverse valueFor [0 .. width - 1]
  | otherwise = Nothing
  where
    width = case patterns of
      [] -> 0
      (p:_) -> length p
    pivots = eliminate width (zip patterns received)
    valueFor col = snd <$> find (\(bits, _) -> bits !! col) pivots

eliminate :: Int -> [Row] -> [Row]
eliminate width rows = go 0 rows []
  where
    go col remaining pivots
      | col >= width = pivots
      | otherwise =
          let (without, with) = partition (not . (!! col) . fst) remaining
          in case with of
            [] -> go (col + 1) remaining pivots
            (pivot:rest) ->
              let reduce row@(bits, _)
                    | bits !! col = xorRow row pivot
                    | otherwise = row
                  remaining' = map reduce (without ++ rest)
                  pivots' = map reduce pivots ++ [pivot]
              in go (col + 1) remaining' pivots'

xorRow :: Row -> Row -> Row
xorRow (a, x) (b, y) = (zipWith (/=) a b, xor x y)

The Rust side generates packets by XORing random subsets of the source data. Each packet is a linear combination. The Haskell decoder treats it as a system of equations over GF(2)—once you have enough linearly independent equations, Gaussian elimination recovers the original.

Real implementations (LT codes, Raptor codes) use degree distributions tuned so that most packets XOR just a few symbols, with occasional high-degree packets to mop up stragglers. NASA’s Deep Space Network uses Raptor codes now. Your balloon probably uses something simpler, but the principle holds: when the channel is hostile, send redundancy that doesn’t care which pieces survive.