Jonathan Perry, Peter Iannucci, Kermin Elliott Fleming, Hari Balakrishnan, Devavrat Shah
ACM SIGCOMM, Helsinki, Finland, August 2012
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, this
paper develops 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.
Experimental results obtained from a software implementation of a
linear-time decoder show that spinal codes achieve higher throughput
than fixed-rate LDPC codes, rateless Raptor codes, and the layered rateless coding approach of Strider, across a 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 (2268KB)]
Bibtex Entry:
@inproceedings{perry2012spinal, author = "Jonathan Perry and Peter Iannucci and Kermin Elliott Fleming and Hari Balakrishnan and Devavrat Shah", title = "{Spinal Codes}", booktitle = {ACM SIGCOMM}, year = {2012}, month = {August}, address = {Helsinki, Finland} }