Spinal codes
Authors:
Open Access
- 13 August 2012
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 42 (4) , 49-60
Abstract
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.Keywords
This publication has 28 references indexed in Scilit:
- The Salsa20 Family of Stream Ciphers2008
- Rate-Compatible Puncturing of Low-Density Parity-Check CodesIEEE Transactions on Information Theory, 2004
- Incremental Redundancy Hybrid ARQ Schemes Based on Low-Density Parity-Check CodesIEEE Transactions on Communications, 2004
- Field measurements of an indoor high-speed QAM wireless system using decision feedback equalization and smart antenna arrayIEEE Transactions on Wireless Communications, 2002
- Capacity of Multi‐antenna Gaussian ChannelsEuropean Transactions on Telecommunications, 1999
- A comparison of reduced complexity decoding algorithms for trellis codesIEEE Journal on Selected Areas in Communications, 1989
- Sequential Coding Algorithms: A Survey and Cost AnalysisIEEE Transactions on Communications, 1984
- Channel coding with multilevel/phase signalsIEEE Transactions on Information Theory, 1982
- Optimal decoding of linear codes for minimizing symbol error rate (Corresp.)IEEE Transactions on Information Theory, 1974
- Low-density parity-check codesIEEE Transactions on Information Theory, 1962