Jonathan Perry
Massachusetts Institute of Technology, Cambridge, MA,
Spinal codes are a new class of rateless codes that enable wireless networks to cope with
time-varying channel conditions in a natural way, without requiring any explicit bit rate
selection. The key idea in the code is the sequential application of a pseudo-random hash
function to the message bits, to produce a sequence of coded symbols for transmission. This
encoding ensures that two input messages that differ in even one bit lead to very different
coded sequences after the point at which they differ, providing good resilience to noise
and bit errors. To decode spinal codes, we develop an approximate maximum-likelihood
decoder, called the bubble decoder, which runs in time polynomial in the message size
and achieves the Shannon capacity over both additive white Gaussian noise (AWGN) and
binary symmetric channel (BSC) models. The decoder trades off throughput for computa-
tion (hardware area or decoding time), allowing the decoder to scale gracefully with avail-
able hardware resources. Experimental results obtained from a software implementation
of a linear-time decoder show that spinal codes achieve higher throughput than fixed-rate
LDPC codes [11], rateless Raptor codes [35], and the layered rateless coding approach [8]
of Strider [12], across a wide range of channel conditions and message sizes. An early
hardware prototype that can decode at 10 Mbits/s in FPGA demonstrates that spinal codes
are a practical construction.
[PDF (2175KB)]