Stepped list decoding for polar codes

Mohammad Rowshan, Emanuele Viterbo

Research output: Chapter in Book/Report/Conference proceedingConference PaperOther

Abstract

In the successive cancellation list (SCL) decoding of polar codes, as the list size increases, the error correction performance improves. However, a large list size results in high computational complexity and large memory requirement.In this paper, we investigate the list decoding process by introducing a new parameter named path metric range (PMR) to elucidate the properties of the evolution of the path metrics (PMs) within the list throughout the decoding process. Then, we advocate that the list size can change stepwise depending on PMR. As a result, we propose a stepped list decoding scheme in which the error correction performance of the conventional list decoding is preserved while the path memory may reduce by 75%, the size of the internal LLR memory and partial sums memory can drop by 50%, and the computational complexity may halve. The reduction in complexity is SNR-independent and achieved without introducing any computational overhead.

Original languageEnglish
Title of host publication2018 IEEE 10th International Symposium on Turbo Codes and Iterative Information Processing, ISTC 2018
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages5
ISBN (Electronic)9781538670484
DOIs
Publication statusPublished - 2018
EventIEEE International Symposium on Turbo Codes and Iterative Information Processing 2018 - Hong Kong, China
Duration: 3 Dec 20187 Dec 2018
Conference number: 10th
http://www.istc2018.org/

Publication series

NameInternational Symposium on Turbo Codes and Iterative Information Processing, ISTC
Volume2018-December
ISSN (Print)2165-4700
ISSN (Electronic)2165-4719

Conference

ConferenceIEEE International Symposium on Turbo Codes and Iterative Information Processing 2018
Abbreviated titleISTC 2018
CountryChina
CityHong Kong
Period3/12/187/12/18
Internet address

Keywords

  • computational complexity
  • memory requirement
  • Polar codes
  • successive cancellation list decoding

Cite this

Rowshan, M., & Viterbo, E. (2018). Stepped list decoding for polar codes. In 2018 IEEE 10th International Symposium on Turbo Codes and Iterative Information Processing, ISTC 2018 [8625267] (International Symposium on Turbo Codes and Iterative Information Processing, ISTC; Vol. 2018-December). IEEE, Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ISTC.2018.8625267
Rowshan, Mohammad ; Viterbo, Emanuele. / Stepped list decoding for polar codes. 2018 IEEE 10th International Symposium on Turbo Codes and Iterative Information Processing, ISTC 2018. IEEE, Institute of Electrical and Electronics Engineers, 2018. (International Symposium on Turbo Codes and Iterative Information Processing, ISTC).
@inproceedings{60e0793c0d894d7ab45c692eb285d8ed,
title = "Stepped list decoding for polar codes",
abstract = "In the successive cancellation list (SCL) decoding of polar codes, as the list size increases, the error correction performance improves. However, a large list size results in high computational complexity and large memory requirement.In this paper, we investigate the list decoding process by introducing a new parameter named path metric range (PMR) to elucidate the properties of the evolution of the path metrics (PMs) within the list throughout the decoding process. Then, we advocate that the list size can change stepwise depending on PMR. As a result, we propose a stepped list decoding scheme in which the error correction performance of the conventional list decoding is preserved while the path memory may reduce by 75{\%}, the size of the internal LLR memory and partial sums memory can drop by 50{\%}, and the computational complexity may halve. The reduction in complexity is SNR-independent and achieved without introducing any computational overhead.",
keywords = "computational complexity, memory requirement, Polar codes, successive cancellation list decoding",
author = "Mohammad Rowshan and Emanuele Viterbo",
year = "2018",
doi = "10.1109/ISTC.2018.8625267",
language = "English",
series = "International Symposium on Turbo Codes and Iterative Information Processing, ISTC",
publisher = "IEEE, Institute of Electrical and Electronics Engineers",
booktitle = "2018 IEEE 10th International Symposium on Turbo Codes and Iterative Information Processing, ISTC 2018",
address = "United States of America",

}

Rowshan, M & Viterbo, E 2018, Stepped list decoding for polar codes. in 2018 IEEE 10th International Symposium on Turbo Codes and Iterative Information Processing, ISTC 2018., 8625267, International Symposium on Turbo Codes and Iterative Information Processing, ISTC, vol. 2018-December, IEEE, Institute of Electrical and Electronics Engineers, IEEE International Symposium on Turbo Codes and Iterative Information Processing 2018, Hong Kong, China, 3/12/18. https://doi.org/10.1109/ISTC.2018.8625267

Stepped list decoding for polar codes. / Rowshan, Mohammad; Viterbo, Emanuele.

2018 IEEE 10th International Symposium on Turbo Codes and Iterative Information Processing, ISTC 2018. IEEE, Institute of Electrical and Electronics Engineers, 2018. 8625267 (International Symposium on Turbo Codes and Iterative Information Processing, ISTC; Vol. 2018-December).

Research output: Chapter in Book/Report/Conference proceedingConference PaperOther

TY - GEN

T1 - Stepped list decoding for polar codes

AU - Rowshan, Mohammad

AU - Viterbo, Emanuele

PY - 2018

Y1 - 2018

N2 - In the successive cancellation list (SCL) decoding of polar codes, as the list size increases, the error correction performance improves. However, a large list size results in high computational complexity and large memory requirement.In this paper, we investigate the list decoding process by introducing a new parameter named path metric range (PMR) to elucidate the properties of the evolution of the path metrics (PMs) within the list throughout the decoding process. Then, we advocate that the list size can change stepwise depending on PMR. As a result, we propose a stepped list decoding scheme in which the error correction performance of the conventional list decoding is preserved while the path memory may reduce by 75%, the size of the internal LLR memory and partial sums memory can drop by 50%, and the computational complexity may halve. The reduction in complexity is SNR-independent and achieved without introducing any computational overhead.

AB - In the successive cancellation list (SCL) decoding of polar codes, as the list size increases, the error correction performance improves. However, a large list size results in high computational complexity and large memory requirement.In this paper, we investigate the list decoding process by introducing a new parameter named path metric range (PMR) to elucidate the properties of the evolution of the path metrics (PMs) within the list throughout the decoding process. Then, we advocate that the list size can change stepwise depending on PMR. As a result, we propose a stepped list decoding scheme in which the error correction performance of the conventional list decoding is preserved while the path memory may reduce by 75%, the size of the internal LLR memory and partial sums memory can drop by 50%, and the computational complexity may halve. The reduction in complexity is SNR-independent and achieved without introducing any computational overhead.

KW - computational complexity

KW - memory requirement

KW - Polar codes

KW - successive cancellation list decoding

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

U2 - 10.1109/ISTC.2018.8625267

DO - 10.1109/ISTC.2018.8625267

M3 - Conference Paper

T3 - International Symposium on Turbo Codes and Iterative Information Processing, ISTC

BT - 2018 IEEE 10th International Symposium on Turbo Codes and Iterative Information Processing, ISTC 2018

PB - IEEE, Institute of Electrical and Electronics Engineers

ER -

Rowshan M, Viterbo E. Stepped list decoding for polar codes. In 2018 IEEE 10th International Symposium on Turbo Codes and Iterative Information Processing, ISTC 2018. IEEE, Institute of Electrical and Electronics Engineers. 2018. 8625267. (International Symposium on Turbo Codes and Iterative Information Processing, ISTC). https://doi.org/10.1109/ISTC.2018.8625267