research-article

A hardware spinal decoder

Authors:

Peter A. Iannucci,

Kermin Elliott Fleming,

Jonathan Perry,

Hari Balakrishnan,

Devavrat ShahAuthors Info & Claims

ANCS '12: Proceedings of the eighth ACM/IEEE symposium on Architectures for networking and communications systems

Pages 151 - 162

https://doi.org/10.1145/2396556.2396593

Published: 29 October 2012 Publication History

Abstract

Spinal codes are a recently proposed capacity-achieving rateless code. While hardware encoding of spinal codes is straightforward, the design of an efficient, high-speed hardware decoder poses significant challenges. We present the first such decoder. By relaxing data dependencies inherent in the classic M-algorithm decoder, we obtain area and throughput competitive with 3GPP turbo codes as well as greatly reduced latency and complexity. The enabling architectural feature is a novel alpha-beta incremental approximate selection algorithm. We also present a method for obtaining hints which anticipate successful or failed decoding, permitting early termination and/or feedback-driven adaptation of the decoding parameters.

We have validated our implementation in FPGA with on-air testing. Provisional hardware synthesis suggests that a near-capacity implementation of spinal codes can achieve a throughput of 12.5 Mbps in a 65 nm technology while using substantially less area than competitive 3GPP turbo code implementations.

References

[1]

3rd Generation Partnership Project. Technical Specification Group Radio Access Networks, TS 25.101 V3.6.0, 2001--2003.

[2]

J. Anderson and S. Mohan. Sequential coding algorithms: A survey and cost analysis. IEEE Trans. on Comm., 32(2):169--176, 1984.

[3]

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.

Digital Library

[4]

C. Berrou, A. Glavieux, and P. Thitimajshima. Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1. In ICC, 2002.

[5]

P. Black and T.-Y. Meng. Hybrid Survivor Path Architectures for Viterbi Decoders. Acoustics, Speech, and Signal Processing, IEEE International Conference on, 1:433--436, 1993.

Digital Library

[6]

C.-C. Cheng, Y.-M. Tsai, L.-G. Chen, and A. P. Chandrakasan. A 0.077 to 0.168 nJ/bit/iteration scalable 3GPP LTE turbo decoder with an adaptive sub-block parallel scheme and an embedded DVFS engine. In CICC, pages 1--4, 2010.

[7]

R. Cypher and C. Shung. Generalized Trace Back Techniques for Survivor Memory Management in the Viterbi Algorithm. In Proc. IEEE GLOBECOM, Sec 1990.

[8]

Ettus Research USRP2. http://www.ettus.com/products.

[9]

G. J. Forney. The Viterbi Algorithm. In Proceedings of the IEEE, volume 61, pages 268--278. IEEE, Mar. 1973.

[10]

L. Gonzalez Perez, E. Boutillon, A. Garcia Garcia, J. Gonzalez Villarruel, and R. Acua. VLSI Architecture for the M Algorithm Suited for Detection and Source Coding Applications. In International Conference on Electronics, Communications and Computers, pages 119 -- 124, feb. 2005.

Digital Library

[11]

J. Hagenauer and P. Hoeher. A Viterbi Algorithm with Soft-Decision Outputs and its Applications. In Proc. IEEE GLOBECOM, pages 1680--1686, Dallas, TX, Nov. 1989.

[12]

K. Jamieson. The SoftPHY Abstraction: from Packets to Symbols in Wireless Network Design. PhD thesis, MIT, Cambridge, MA, 2008.

Digital Library

[13]

B. Jenkins. Hash functions. Dr. Dobb's Journal, 1997.

[14]

C.-C. Lin, C.-C. Wu, and C.-Y. Lee. A Low Power and High-speed Viterbi Decoder Chip for WLAN Applications. In ESSCIRC '03, pages 723 --726, 2003.

[15]

E. C. Lin, K. Yu, R. A. Rutenbar, and T. Chen. A 1000-word vocabulary, speaker-independent, continuous live-mode speech recognizer implemented in a single FPGA. In FPGA, pages 60--68, 2007.

Digital Library

[16]

Nallatech. Intel Xeon FSB FPGA Socket Fillers. http://www.nallatech.com/intel-xeon-fsb-fpga-socket-fillers.html.

[17]

M. C. Ng, K. Fleming, M. Vutukuru, S. Gross, Arvind, and H. Balakrishnan. Airblue: A System for Cross-Layer Wireless Protocol Development. In ANCS'10, San Diego, CA, 2010.

Digital Library

[18]

M. C. Ng, M. Vijayaraghavan, G. Raghavan, N. Dave, J. Hicks, and Arvind. From WiFI to WiMAX: Techniques for IP Reuse Across Different OFDM Protocols. In MEMOCODE'07.

Digital Library

[19]

E. Paaske, S. Pedersen, and J. Sparsø. An Area-efficient Path Memory Structure for VLSI Implementation of High Speed Viterbi Decoders. Integr. VLSI J., pages 79--91, Nov. 1991.

Digital Library

[20]

J. Perry, H. Balakrishnan, and D. Shah. Rateless spinal codes. In HotNets-X, Oct. 2011.

Digital Library

[21]

J. Perry, P. Iannucci, K. Fleming, H. Balakrishnan, and D. Shah. Spinal Codes. In SIGCOMM, Aug. 2012.

Digital Library

[22]

M. Power, S. Tosi, and T. Conway. Reduced Complexity Path Selection Networks for M-Algorithm Read Channel Detectors. IEEE Transactions on Circuits and Systems, 55(9):2924--2933, Oct. 2008.

[23]

Xilinx. Xilinx University Program XUPV5-LX110T Development System. http://www.xilinx.com/univ/xupv5-lx110t.htm.

Cited By

Du WLiando JLi M(2021)SoftLight: Adaptive visible light communication over screen-camera linksIEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications10.1109/INFOCOM.2016.7524510(1-9)Online publication date: 10-Mar-2021
https://dl.acm.org/doi/10.1109/INFOCOM.2016.7524510
Li YWu JTan BWang MZhang W(2019)Compressive Spinal CodesIEEE Transactions on Vehicular Technology10.1109/TVT.2019.294702868:12(11944-11954)Online publication date: Dec-2019
https://doi.org/10.1109/TVT.2019.2947028
Shi PWang ZHe CZhang XCai W(2019)A novel spinal codes based on chaotic Kent mapping2019 IEEE/CIC International Conference on Communications Workshops in China (ICCC Workshops)10.1109/ICCChinaW.2019.8849929(82-86)Online publication date: Aug-2019
https://doi.org/10.1109/ICCChinaW.2019.8849929
Show More Cited By

Index Terms

A hardware spinal decoder
1. Hardware
  1. Communication hardware, interfaces and storage
    1. Wireless devices
2. Networks
  1. Network types
    1. Mobile networks
    2. Wireless access networks

Recommendations

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 ...
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 ...
Rateless spinal codes
HotNets-X: Proceedings of the 10th ACM Workshop on Hot Topics in Networks

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ANCS '12: Proceedings of the eighth ACM/IEEE symposium on Architectures for networking and communications systems

October 2012

270 pages

ISBN:9781450316859

DOI:10.1145/2396556

General Chair:
Tilman Wolf
University of Massachusetts Amherst, USA
,
Program Chairs:
Andrew W. Moore
University of Cambridge, UK
,
Viktor Prasanna
University of Southern California, USA

Copyright © 2012 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: 29 October 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ANCS '12

Sponsor:

ANCS '12: Symposium on Architecture for Networking and Communications Systems

October 29 - 30, 2012

Texas, Austin, USA

Acceptance Rates

Overall Acceptance Rate 88 of 314 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
177
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Du WLiando JLi M(2021)SoftLight: Adaptive visible light communication over screen-camera linksIEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications10.1109/INFOCOM.2016.7524510(1-9)Online publication date: 10-Mar-2021
https://dl.acm.org/doi/10.1109/INFOCOM.2016.7524510
Li YWu JTan BWang MZhang W(2019)Compressive Spinal CodesIEEE Transactions on Vehicular Technology10.1109/TVT.2019.294702868:12(11944-11954)Online publication date: Dec-2019
https://doi.org/10.1109/TVT.2019.2947028
Shi PWang ZHe CZhang XCai W(2019)A novel spinal codes based on chaotic Kent mapping2019 IEEE/CIC International Conference on Communications Workshops in China (ICCC Workshops)10.1109/ICCChinaW.2019.8849929(82-86)Online publication date: Aug-2019
https://doi.org/10.1109/ICCChinaW.2019.8849929
Lu HGao WMottola LGao JZhang P(2018)Continuous wireless link rates for internet of thingsProceedings of the 17th ACM/IEEE International Conference on Information Processing in Sensor Networks10.1109/IPSN.2018.00012(48-59)Online publication date: 11-Apr-2018
https://dl.acm.org/doi/10.1109/IPSN.2018.00012
Du WLiando JLi M(2017)Soft Hint Enabled Adaptive Visible Light Communication over Screen-Camera LinksIEEE Transactions on Mobile Computing10.1109/TMC.2016.255175016:2(527-537)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1109/TMC.2016.2551750

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