research-article

Rateless spinal codes

Authors:

Jonathan Perry,

Hari Balakrishnan,

Devavrat ShahAuthors Info & Claims

HotNets-X: Proceedings of the 10th ACM Workshop on Hot Topics in Networks

Article No.: 6, Pages 1 - 6

https://doi.org/10.1145/2070562.2070568

Published: 14 November 2011 Publication History

Abstract

A fundamental problem in wireless networks is to develop communication protocols that achieve high throughput in the face of noise, interference, and fading, all of which vary with time. An ideal solution is a rateless wireless system, in which the sender encodes data without any explicit estimation or adaptation, implicitly adapting to the level of noise or interference. In this paper, we present a novel rateless code, the spinal code, which uses a hash function over the message bits to produce pseudo-random bits that in turn can be mapped directly to a dense constellation for transmission. Results from theoretical analysis and simulations show that spinal codes essentially achieve Shannon capacity, and out-perform best-known fixed rate block codes.

References

[1]

R. Barron, C. Lo, and J. Shapiro. Global design methods for raptor codes using binary and higher-order modulations. In IEEE MILCOM, 2009.

Digital Library

[2]

J. Bicket. Bit-Rate Selection in Wireless Networks. Master's thesis, Massachusetts Institute of Technology, Feb. 2005.

[3]

U. Erez, M. Trott, and G. Wornell. Coding for Gaussian Channels. In ISIT 05-06, journal version on Arxiv, 2007.

[4]

A. Gudipati and S. Katti. Automatic rate adaptation. In Hotnets, 2010.

Digital Library

[5]

A. Gudipati and S. Katti. Strider: Automatic rate adaptation and collision handling. In SIGCOMM, 2011.

Digital Library

[6]

J. Ha, J. Kim, and S. McLaughlin. Rate-compatible puncturing of low-density parity-check codes. IEEE Trans. on Info. Theory, 2004.

Digital Library

[7]

G. Holland, N. Vaidya, and P. Bahl. A Rate-Adaptive MAC Protocol for Multihop Wireless Networks. In MobiCom, 2001.

Digital Library

[8]

G. Judd, X. Wang, and P. Steenkiste. Efficient Channel-aware Rate Adaptation in Dynamic Environments. In MobiSys, June 2008.

Digital Library

[9]

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.

[10]

M. Luby. LT codes. In FOCS, 2003.

[11]

R. Mantha and F. Kschischang. A capacity-approaching hybrid ARQ scheme using turbo codes. In GLOBECOM, 1999.

[12]

Y. Polyanskiy, H. Poor, and S. Verdú. Channel coding rate in the finite blocklength regime. IEEE Trans. on Info. Theory, 56(5), 2010.

Digital Library

[13]

S. Sen, N. Santhapuri, R. Choudhury, and S. Nelakuditi. AccuRate: Constellation-based rate estimation in wireless networks. NSDI, 2010.

Digital Library

[14]

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.

[15]

A. Shokrollahi. Raptor codes. IEEE Trans. Info. Theory, 52(6), 2006.

Digital Library

[16]

E. Soljanin, N. Varnica, and P. Whiting. Incremental redundancy hybrid ARQ with LDPC and Raptor codes. IEEE Trans. on Info. Theory, 2005.

[17]

G. Ungerboeck. Channel coding with multilevel/phase signals. IEEE Trans. on Info. Theory, IT-28(1):55--67. Jan. 1982.

Digital Library

[18]

G. Ungerboeck and I. Csajka. On improving data-link performance by increasing the channel alphabet and introducing sequence coding. In ISIT, 1976.

[19]

M. Vutukuru, H. Balakrishnan, and K. Jamieson. Cross-Layer Wireless Bit Rate Adaptation. In SIGCOMM, 2009.

Digital Library

[20]

S. Wong, H. Yang, S. Lu, and V. Bharghavan. Robust Rate Adaptation for 802.11 Wireless Networks. In MobiCom, 2006.

Digital Library

Cited By

Li AWu SChen XSun S(2025)Tight Upper Bounds on the BLER of Spinal Codes Over the AWGN ChannelIEEE Transactions on Communications10.1109/TCOMM.2024.343539173:1(332-347)Online publication date: Jan-2025
https://doi.org/10.1109/TCOMM.2024.3435391
Yu XLiang LJiang KChen T(2025)Low Complexity Unquantized Forward Stack Decoding Algorithm for Spinal Codes in Measurement While Drilling CommunicationIEEE Access10.1109/ACCESS.2025.353164913(22637-22646)Online publication date: 2025
https://doi.org/10.1109/ACCESS.2025.3531649
Rowshan MQiu MXie YGu XYuan J(2024)Channel Coding Toward 6G: Technical Overview and OutlookIEEE Open Journal of the Communications Society10.1109/OJCOMS.2024.33900005(2585-2685)Online publication date: 2024
https://doi.org/10.1109/OJCOMS.2024.3390000
Show More Cited By

Index Terms

Rateless spinal codes
1. Networks
  1. Network types
    1. Mobile networks
    2. Wireless access networks

Recommendations

Spinal codes
Special october issue SIGCOMM '12

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 ...
Spinal codes
SIGCOMM '12: Proceedings of the ACM SIGCOMM 2012 conference on Applications, technologies, architectures, and protocols for computer communication

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 ...
Power-aware rateless codes in mobile wireless communication
HotNets-XI: Proceedings of the 11th ACM Workshop on Hot Topics in Networks

Rateless error correction codes hold great potential for increasing the capacity of practical wireless networks by obviating the need for transmitters to estimate the highest reliable rate of an unpredictable wireless channel and send information at ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

HotNets-X: Proceedings of the 10th ACM Workshop on Hot Topics in Networks

November 2011

148 pages

ISBN:9781450310598

DOI:10.1145/2070562

General Chairs:
Hari Balakrishnan
MIT
,
Dina Katabi
MIT
,
Program Chairs:
Aditya Akella
University of Wisconsin-Madison
,
Ion Stoica
UC Berkeley

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 November 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

HOTNETS-X

Sponsor:

SIGCOMM

HOTNETS-X: Tenth ACM Workshop on Hot Topics in Networks

November 14 - 15, 2011

Massachusetts, Cambridge

Acceptance Rates

Overall Acceptance Rate 110 of 460 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

86
Total Citations
View Citations
585
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li AWu SChen XSun S(2025)Tight Upper Bounds on the BLER of Spinal Codes Over the AWGN ChannelIEEE Transactions on Communications10.1109/TCOMM.2024.343539173:1(332-347)Online publication date: Jan-2025
https://doi.org/10.1109/TCOMM.2024.3435391
Yu XLiang LJiang KChen T(2025)Low Complexity Unquantized Forward Stack Decoding Algorithm for Spinal Codes in Measurement While Drilling CommunicationIEEE Access10.1109/ACCESS.2025.353164913(22637-22646)Online publication date: 2025
https://doi.org/10.1109/ACCESS.2025.3531649
Rowshan MQiu MXie YGu XYuan J(2024)Channel Coding Toward 6G: Technical Overview and OutlookIEEE Open Journal of the Communications Society10.1109/OJCOMS.2024.33900005(2585-2685)Online publication date: 2024
https://doi.org/10.1109/OJCOMS.2024.3390000
Yu XLiang LJiang KChen TDu S(2024)Low Complexity Encoding Design for Fiber Optic Measurement While Drilling Communication System Based on Superposition Spinal CodesIEEE Access10.1109/ACCESS.2024.347763612(155598-155606)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3477636
Zhang ZZhao LBai J(2023)A Decoding Algorithm for Spinal Codes over Fading ChannelProceedings of the 2023 9th International Conference on Communication and Information Processing10.1145/3638884.3638948(415-419)Online publication date: 14-Dec-2023
https://dl.acm.org/doi/10.1145/3638884.3638948
Chen XLi AWu S(2023)Tight Upper Bounds on the Error Probability of Spinal Codes over Fading Channels2023 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT54713.2023.10206448(1277-1282)Online publication date: 25-Jun-2023
https://doi.org/10.1109/ISIT54713.2023.10206448
An NZhang YLi WZhou T(2023)Security analysis and state offset encryption scheme for Spinal codes2023 IEEE International Conference on Sensors, Electronics and Computer Engineering (ICSECE)10.1109/ICSECE58870.2023.10263344(703-709)Online publication date: 18-Aug-2023
https://doi.org/10.1109/ICSECE58870.2023.10263344
Ninkovic VVukobratovic DHäger CWymeersch HAmat A(2023)Rateless Autoencoder Codes: Trading off Decoding Delay and ReliabilityICC 2023 - IEEE International Conference on Communications10.1109/ICC45041.2023.10278853(6361-6366)Online publication date: 28-May-2023
https://doi.org/10.1109/ICC45041.2023.10278853
Mucchi LShahabuddin SAlbreem MAbdallah SCaputo SPanayirci EJuntti M(2023)Signal Processing Techniques for 6GJournal of Signal Processing Systems10.1007/s11265-022-01827-795:4(435-457)Online publication date: 2-Feb-2023
https://doi.org/10.1007/s11265-022-01827-7
Zou YLin DJiang Z(2023)A Coded Modulation Scheme for IoT SystemIoT as a Service10.1007/978-3-031-37139-4_12(127-134)Online publication date: 19-Jul-2023
https://doi.org/10.1007/978-3-031-37139-4_12
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten