Spinal codes

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.

References

1. J. Anderson and S. Mohan. Sequential coding algorithms: A survey and cost analysis. IEEE Trans. on Comm., 32(2):169--176, 1984.
2. L. Bahl, J. Cocke, F. Jelinek, and J. Raviv. Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate (Corresp.). IEEE Trans. Info. Theory, 20(2):284--287, 1974.
3. H. Balakrishnan, P. Iannucci, J. Perry, and D. Shah. De-randomizing Shannon: The Design and Analysis of a Capacity-Achieving Rateless Code. arXiv:1206.0418, June 2012.
4. R. Barron, C. Lo, and J. Shapiro. Global design methods for raptor codes using binary and higher-order modulations. In MILCOM, 2009.
5. D. Bernstein. The Salsa20 Family of Stream Ciphers. Lecture Notes in Computer Science, 4986:84--97, 2008.
6. C. Berrou, A. Glavieux, and P. Thitimajshima. Near Shannon limit error-correcting coding and decoding: Turbo-codes (1). In ICC, 1993.
7. J. Bicket. Bit-Rate Selection in Wireless Networks. Master's thesis, Massachusetts Institute of Technology, Feb. 2005.
8. Erez, U. and Trott, M. and Wornell, G. Rateless Coding for Gaussian Channels. IEEE Trans. Info. Theory, 58(2):530--547, 2012.
9. O. Etesami, M. Molkaraie, and A. Shokrollahi. Raptor codes on symmetric channels. In ISIT, 2005.
10. J. Frigon and B. Daneshrad. Field measurements of an indoor high-speed QAM wireless system using decision feedback equalization and smart antenna array. IEEE Trans. Wireless Comm., 1(1):134--144, 2002.
11. R. Gallager. Low-density parity-check codes. IRE Trans. Information Theory, 8(1):21--28, 1962.
12. A. Gudipati and S. Katti. Strider: Automatic rate adaptation and collision handling. In SIGCOMM, 2011.
13. J. Ha, J. Kim, and S. McLaughlin. Rate-compatible puncturing of low-density parity-check codes. IEEE Trans. Info. Theory, 2004.
14. D. Halperin, W. Hu, A. Sheth, and D. Wetherall. Predictable 802.11 packet delivery from wireless channel measurements. In SIGCOMM, 2010.
15. G. Holland, N. Vaidya, and P. Bahl. A Rate-Adaptive MAC Protocol for Multihop Wireless Networks. In MobiCom, 2001.
16. P. Iannucci, J. Perry, H. Balakrishnan, and D. Shah. No Symbol Left Behind: A Link-Layer Protocol for Rateless Codes. In MobiCom, 2012.
17. F. Jelinek. Fast sequential decoding algorithm using a stack. IBM Journal of Research and Development, 13(6):675--685, 1969.
18. G. Judd, X. Wang, and P. Steenkiste. Efficient Channel-aware Rate Adaptation in Dynamic Environments. In MobiSys, June 2008.
19. IEEE Std 802.11n-2009: Enhancements for Higher Throughput.
20. J. Li and K. Narayanan. Rate-compatible low density parity check codes for capacity-approaching ARQ scheme in packet data communications. In Int. Conf. on Comm., Internet, and Info. Tech., 2002.
21. M. Luby. LT codes. In FOCS, 2003.
22. M. Luby, A. Shokrollahi, M. Watson, and T. Stockhammer. Raptor Forward Error Correction Scheme for Object Delivery. RFC 5053 (Proposed Standard), Oct. 2007.
23. R. Mantha and F. Kschischang. A capacity-approaching hybrid ARQ scheme using turbo codes. In GLOBECOM, 1999.
24. M. Mitzenmacher and E. Upfal. Probability and computing: Randomized algorithms and probabilistic analysis, chapter 13, pages 321--326. Cambridge University Press, 2005.
25. M. C. Ng, K. E. Fleming, M. Vutukuru, S. Gross, Arvind, and H. Balakrishnan. Airblue: A System for Cross-Layer Wireless Protocol Development. In ANCS, Oct. 2010.
26. R. Palanki and J. Yedidia. Rateless codes on noisy channels. In ISIT, 2005.
27. J. Perry, H. Balakrishnan, and D. Shah. Rateless Spinal Codes. In HotNets-X, Oct. 2011.
28. G. Pottie and D. Taylor. A comparison of reduced complexity decoding algorithms for trellis codes. JSAC, 7(9):1369--1380, 1989.
29. C. Schurgers and M. B. Srivastava. A Systematic Approach to Peak-to-Average Power Ratio in OFDM. In SPIE's 47th Meeting, 2001.
30. S. Sen, N. Santhapuri, R. Choudhury, and S. Nelakuditi. AccuRate: Constellation-based rate estimation in wireless networks. NSDI, 2010.
31. S. Sesia, G. Caire, and G. Vivier. Incremental redundancy hybrid ARQ schemes based on low-density parity-check codes. IEEE Trans. on Comm., 52(8):1311--1321, 2004.
32. C. Shannon. Communication in the presence of noise. Proc. of the IRE, 37(1):10--21, 1949.
33. A. Shokrollahi. Raptor codes. IEEE Trans. Info. Theory, 52(6), 2006.
34. N. Shulman. Universal channel coding. PhD thesis, Tel-Aviv University, 2004.
35. E. Soljanin, N. Varnica, and P. Whiting. Incremental redundancy hybrid ARQ with LDPC and Raptor codes. IEEE Trans. Info. Theory, 2005.
36. E. Telatar. Capacity of Multi-Antenna Gaussian Channels. European Trans. on Telecom., 10(6):585--595, 1999.
37. G. Ungerboeck. Channel coding with multilevel/phase signals. IEEE Trans. Info. Theory, IT-28(1):55--67, Jan. 1982.
38. G. Ungerboeck and I. Csajka. On improving data-link performance by increasing the channel alphabet and introducing sequence coding. In ISIT, 1976.
39. A. Vila Casado, M. Griot, and R. Wesel. Informed dynamic scheduling for Belief-Propagation decoding of LDPC codes. In IEEE ICC, 2007.
40. A. Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans. Info. Theory, 13(2):260--269, 1967.
41. M. Vutukuru, H. Balakrishnan, and K. Jamieson. Cross-Layer Wireless Bit Rate Adaptation. In SIGCOMM, 2009.
42. S. Wicker and V. Bhargava. Reed-Solomon codes and their applications. Wiley-IEEE Press, 1999.
43. S. Wong, H. Yang, S. Lu, and V. Bharghavan. Robust Rate Adaptation for 802.11 Wireless Networks. In MobiCom, 2006.

Index Terms

• Networks

  • Network types

    • Mobile networks

    • Wireless access networks