Simplified Successive Cancellation Decoding of Polar Codes Has Sublinear Latency

Marco Mondelli; Seyyed Ali Hashemi; John Cioffi; Andrea Goldsmith

doi:10.1109/ISIT44484.2020.9174141

Simplified Successive Cancellation Decoding of Polar Codes Has Sublinear Latency

Marco Mondelli, Seyyed Ali Hashemi, John Cioffi, Andrea Goldsmith

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

Abstract

This work analyzes the latency of the simplified successive cancellation (SSC) decoding scheme for polar codes proposed by Alamdar-Yazdi and Kschischang. It is shown that, unlike conventional successive cancellation decoding, where latency is linear in the block length, the latency of SSC decoding is sublinear. More specifically, the latency of SSC decoding is O(N^1-1/μ), where N is the block length and μ is the scaling exponent of the channel, which captures the speed of convergence of the rate to capacity. Numerical results demonstrate the tightness of the bound and show that most of the latency reduction arises from the parallel decoding of subcodes of rate 0 and 1.

Original language	English (US)
Title of host publication	2020 IEEE International Symposium on Information Theory, ISIT 2020 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	401-406
Number of pages	6
ISBN (Electronic)	9781728164328
DOIs	https://doi.org/10.1109/ISIT44484.2020.9174141
State	Published - Jun 2020
Externally published	Yes
Event	2020 IEEE International Symposium on Information Theory, ISIT 2020 - Los Angeles, United States Duration: Jul 21 2020 → Jul 26 2020

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2020-June
ISSN (Print)	2157-8095

Conference

Conference	2020 IEEE International Symposium on Information Theory, ISIT 2020
Country/Territory	United States
City	Los Angeles
Period	7/21/20 → 7/26/20

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT44484.2020.9174141

Cite this

Mondelli, M., Hashemi, S. A., Cioffi, J., & Goldsmith, A. (2020). Simplified Successive Cancellation Decoding of Polar Codes Has Sublinear Latency. In 2020 IEEE International Symposium on Information Theory, ISIT 2020 - Proceedings (pp. 401-406). Article 9174141 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2020-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT44484.2020.9174141

@inproceedings{5d85090ca4ef49f48c789fc4fed3ca4c,

title = "Simplified Successive Cancellation Decoding of Polar Codes Has Sublinear Latency",

abstract = "This work analyzes the latency of the simplified successive cancellation (SSC) decoding scheme for polar codes proposed by Alamdar-Yazdi and Kschischang. It is shown that, unlike conventional successive cancellation decoding, where latency is linear in the block length, the latency of SSC decoding is sublinear. More specifically, the latency of SSC decoding is O(N1-1/μ), where N is the block length and μ is the scaling exponent of the channel, which captures the speed of convergence of the rate to capacity. Numerical results demonstrate the tightness of the bound and show that most of the latency reduction arises from the parallel decoding of subcodes of rate 0 and 1.",

author = "Marco Mondelli and Hashemi, {Seyyed Ali} and John Cioffi and Andrea Goldsmith",

note = "Publisher Copyright: {\textcopyright} 2020 IEEE.; 2020 IEEE International Symposium on Information Theory, ISIT 2020 ; Conference date: 21-07-2020 Through 26-07-2020",

year = "2020",

month = jun,

doi = "10.1109/ISIT44484.2020.9174141",

language = "English (US)",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "401--406",

booktitle = "2020 IEEE International Symposium on Information Theory, ISIT 2020 - Proceedings",

address = "United States",

}

Mondelli, M, Hashemi, SA, Cioffi, J & Goldsmith, A 2020, Simplified Successive Cancellation Decoding of Polar Codes Has Sublinear Latency. in 2020 IEEE International Symposium on Information Theory, ISIT 2020 - Proceedings., 9174141, IEEE International Symposium on Information Theory - Proceedings, vol. 2020-June, Institute of Electrical and Electronics Engineers Inc., pp. 401-406, 2020 IEEE International Symposium on Information Theory, ISIT 2020, Los Angeles, United States, 7/21/20. https://doi.org/10.1109/ISIT44484.2020.9174141

Simplified Successive Cancellation Decoding of Polar Codes Has Sublinear Latency. / Mondelli, Marco; Hashemi, Seyyed Ali; Cioffi, John et al.
2020 IEEE International Symposium on Information Theory, ISIT 2020 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2020. p. 401-406 9174141 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2020-June).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Simplified Successive Cancellation Decoding of Polar Codes Has Sublinear Latency

AU - Mondelli, Marco

AU - Hashemi, Seyyed Ali

AU - Cioffi, John

AU - Goldsmith, Andrea

PY - 2020/6

Y1 - 2020/6

N2 - This work analyzes the latency of the simplified successive cancellation (SSC) decoding scheme for polar codes proposed by Alamdar-Yazdi and Kschischang. It is shown that, unlike conventional successive cancellation decoding, where latency is linear in the block length, the latency of SSC decoding is sublinear. More specifically, the latency of SSC decoding is O(N1-1/μ), where N is the block length and μ is the scaling exponent of the channel, which captures the speed of convergence of the rate to capacity. Numerical results demonstrate the tightness of the bound and show that most of the latency reduction arises from the parallel decoding of subcodes of rate 0 and 1.

AB - This work analyzes the latency of the simplified successive cancellation (SSC) decoding scheme for polar codes proposed by Alamdar-Yazdi and Kschischang. It is shown that, unlike conventional successive cancellation decoding, where latency is linear in the block length, the latency of SSC decoding is sublinear. More specifically, the latency of SSC decoding is O(N1-1/μ), where N is the block length and μ is the scaling exponent of the channel, which captures the speed of convergence of the rate to capacity. Numerical results demonstrate the tightness of the bound and show that most of the latency reduction arises from the parallel decoding of subcodes of rate 0 and 1.

UR - http://www.scopus.com/inward/record.url?scp=85090422915&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85090422915&partnerID=8YFLogxK

U2 - 10.1109/ISIT44484.2020.9174141

DO - 10.1109/ISIT44484.2020.9174141

M3 - Conference contribution

AN - SCOPUS:85090422915

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 401

EP - 406

BT - 2020 IEEE International Symposium on Information Theory, ISIT 2020 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2020 IEEE International Symposium on Information Theory, ISIT 2020

Y2 - 21 July 2020 through 26 July 2020

ER -

Mondelli M, Hashemi SA, Cioffi J, Goldsmith A. Simplified Successive Cancellation Decoding of Polar Codes Has Sublinear Latency. In 2020 IEEE International Symposium on Information Theory, ISIT 2020 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2020. p. 401-406. 9174141. (IEEE International Symposium on Information Theory - Proceedings). doi: 10.1109/ISIT44484.2020.9174141

Simplified Successive Cancellation Decoding of Polar Codes Has Sublinear Latency

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this