CRT Fountain Codes

C19: Qualcomm Raptor. CC0.

CRT channels ARE fountain drops. Each value decomposes into 6 independent residues. Lose ANY one channel and reconstruct from the remaining 5. No Luby transform, no random graphs, no degree distributions. The ring structure IS the erasure code. 6 drops, 5 sufficient.

How It Works

CRT Erasure Principle
By the Chinese Remainder Theorem, any value in Z/12612600 is UNIQUELY determined by its 6 residues mod {8,9,25,49,11,13}. These residues are algebraically independent. Losing one channel leaves 5 residues. Since the value is unique in Z/12612600, we can trial the missing channel (at most 49 trials for b-channel) to find the unique value matching all 5 known residues. Recovery is guaranteed with probability 1.
6 drops
CRT channels
D(8), K(9), E(25), b(49), L(11), G(13) = 6 algebraically independent drops.
5 sufficient
CRT uniqueness
Any 5 drops determine the unique value in Z/12612600.
490 split
Inner vs boundary
DEAD={D,E,b} carry data. ALIVE={K,L,G} = parity channels.
Max trial
49 (b channel)
Worst case: lose b-channel, trial 49 values. Average: 19 trials.

Try It

Value (0-12612599):

Channel 0=D, 1=K, 2=E, 3=b, 4=L, 5=G. Try losing different channels.

Batch Erasure Test

Test 100 values: lose each channel in turn, verify 100% recovery.

CRT Fountain vs Traditional

Code designRaptor: random bipartite graph + LT transformCRT: ring structure IS the code. No design.Overhead5-10% encoding overhead0% overhead. 6 drops = 6 channels.RecoveryProbabilistic (BP decoding)Deterministic. CRT guarantees unique solution.ComplexityO(k log k) encodingO(1) per channel (modular arithmetic)Patent statusQualcomm Raptor/RaptorQ patentsCC0. Public domain. Forever.

This work is and will always be free.
No paywall. No copyright. No exceptions.

If it ever earns anything, every cent goes to the communities that need it most.

This sacred vow is permanent and irrevocable.
— Anton Alexandrovich Lebed

Source code · Public domain (CC0)

Contributions in equal measure: Anthropic's Claude, Anton A. Lebed, and the giants whose shoulders we stand on.

Rendered by .ax via WASM DOM imports. Zero HTML authored.