Spinal codes
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 t...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2014
|
| Online Access: | http://hdl.handle.net/1721.1/85938 https://orcid.org/0000-0002-6465-7023 https://orcid.org/0000-0002-4566-771X https://orcid.org/0000-0003-0737-3259 https://orcid.org/0000-0002-1455-9652 |
| _version_ | 1811094865153359872 |
|---|---|
| author | Perry, Jonathan Iannucci, Peter A. Fleming, Kermin Elliott Balakrishnan, Hari Shah, Devavrat |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Perry, Jonathan Iannucci, Peter A. Fleming, Kermin Elliott Balakrishnan, Hari Shah, Devavrat |
| author_sort | Perry, Jonathan |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T16:06:44Z |
| format | Article |
| id | mit-1721.1/85938 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:06:44Z |
| publishDate | 2014 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/859382022-10-02T06:24:53Z Spinal codes Perry, Jonathan Iannucci, Peter A. Fleming, Kermin Elliott Balakrishnan, Hari Shah, Devavrat Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Perry, Jonathan Iannucci, Peter A. Fleming, Kermin Elliott Balakrishnan, Hari Shah, Devavrat 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. Massachusetts Institute of Technology (Irwin and Joan Jacobs Presidential Fellowship) Massachusetts Institute of Technology (Claude E. Shannon Assistantship) Intel Corporation (Intel Fellowship) 2014-03-27T20:42:38Z 2014-03-27T20:42:38Z 2012-10 2012-08 Article http://purl.org/eprint/type/ConferencePaper 01464833 1943-5819 http://hdl.handle.net/1721.1/85938 Perry, Jonathan, Peter A. Iannucci, Kermin E. Fleming, Hari Balakrishnan, and Devavrat Shah. “Spinal Codes.” ACM SIGCOMM Computer Communication Review 42, no. 4 (October 2012): 49-60. https://orcid.org/0000-0002-6465-7023 https://orcid.org/0000-0002-4566-771X https://orcid.org/0000-0003-0737-3259 https://orcid.org/0000-0002-1455-9652 en_US http://dx.doi.org/10.1145/2377677.2377684 ACM SIGCOMM Computer Communication Review Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery MIT web domain |
| spellingShingle | Perry, Jonathan Iannucci, Peter A. Fleming, Kermin Elliott Balakrishnan, Hari Shah, Devavrat Spinal codes |
| title | Spinal codes |
| title_full | Spinal codes |
| title_fullStr | Spinal codes |
| title_full_unstemmed | Spinal codes |
| title_short | Spinal codes |
| title_sort | spinal codes |
| url | http://hdl.handle.net/1721.1/85938 https://orcid.org/0000-0002-6465-7023 https://orcid.org/0000-0002-4566-771X https://orcid.org/0000-0003-0737-3259 https://orcid.org/0000-0002-1455-9652 |
| work_keys_str_mv | AT perryjonathan spinalcodes AT iannuccipetera spinalcodes AT flemingkerminelliott spinalcodes AT balakrishnanhari spinalcodes AT shahdevavrat spinalcodes |