How to modify polar codes for list decoding

Mohammad Rowshan; Emanuele Viterbo

doi:10.1109/ISIT.2019.8849539

How to modify polar codes for list decoding

Mohammad Rowshan, Emanuele Viterbo

Electrical and Computer Systems Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

11 Citations (Scopus)

Abstract

Polar codes are constructed based on the reliability of bit-channels. This construction suits the successive cancellation (SC) decoding, where one error in the successive estimation of the bits fails the decoding. However, in SC list (SCL) decoding, the correct path may remain in the list by tolerating multiple penalties. This characteristic of list decoding demands a different approach in code construction.In this work, we modify the conventional construction by a greedy search algorithm in which a bit-swapping approach is employed to re-distribute the low-reliability bits in the subblocks aiming for a reduction in the probability of correct path elimination. The numerical results for polar codes of length 1 kb under CRC-aided SCL decoding show improvements of about 0.4 dB for R=0.8 and over 0.2 dB for R=0.5 at L=32.

Original language	English
Title of host publication	2019 IEEE International Symposium on Information Theory
Subtitle of host publication	Proceedings
Editors	Giuseppe Caire, Venugopal V. Veeravalli, Aaron B. Wagner, Gilles Zemor
Place of Publication	Piscataway NJ USA
Publisher	IEEE, Institute of Electrical and Electronics Engineers
Pages	1772-1776
Number of pages	5
ISBN (Electronic)	9781538692912, 9781538692905
ISBN (Print)	9781538692929
DOIs	https://doi.org/10.1109/ISIT.2019.8849539
Publication status	Published - 2019
Event	IEEE International Symposium on Information Theory 2019 - Paris, France Duration: 7 Jul 2019 → 12 Jul 2019 https://2019.ieee-isit.org/ https://ieeexplore.ieee.org/xpl/conhome/8827389/proceeding (Proceedings)

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Publisher	IEEE, Institute of Electrical and Electronics Engineers
ISSN (Print)	2157-8095
ISSN (Electronic)	2157-8117

Conference

Conference	IEEE International Symposium on Information Theory 2019
Abbreviated title	ISIT 2019
Country/Territory	France
City	Paris
Period	7/07/19 → 12/07/19
Internet address	https://2019.ieee-isit.org/ https://ieeexplore.ieee.org/xpl/conhome/8827389/proceeding (Proceedings)

Keywords

bit-swapping
code construction
list decoding
Polar codes
successive cancellation

Access to Document

10.1109/ISIT.2019.8849539

Cite this

Rowshan, M., & Viterbo, E. (2019). How to modify polar codes for list decoding. In G. Caire, V. V. Veeravalli, A. B. Wagner, & G. Zemor (Eds.), 2019 IEEE International Symposium on Information Theory: Proceedings (pp. 1772-1776). (IEEE International Symposium on Information Theory - Proceedings). IEEE, Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ISIT.2019.8849539

Rowshan, Mohammad ; Viterbo, Emanuele. / How to modify polar codes for list decoding. 2019 IEEE International Symposium on Information Theory: Proceedings. editor / Giuseppe Caire ; Venugopal V. Veeravalli ; Aaron B. Wagner ; Gilles Zemor. Piscataway NJ USA : IEEE, Institute of Electrical and Electronics Engineers, 2019. pp. 1772-1776 (IEEE International Symposium on Information Theory - Proceedings).

@inproceedings{68bbbed1c53b411dba185bc269f84e99,

title = "How to modify polar codes for list decoding",

abstract = "Polar codes are constructed based on the reliability of bit-channels. This construction suits the successive cancellation (SC) decoding, where one error in the successive estimation of the bits fails the decoding. However, in SC list (SCL) decoding, the correct path may remain in the list by tolerating multiple penalties. This characteristic of list decoding demands a different approach in code construction.In this work, we modify the conventional construction by a greedy search algorithm in which a bit-swapping approach is employed to re-distribute the low-reliability bits in the subblocks aiming for a reduction in the probability of correct path elimination. The numerical results for polar codes of length 1 kb under CRC-aided SCL decoding show improvements of about 0.4 dB for R=0.8 and over 0.2 dB for R=0.5 at L=32.",

keywords = "bit-swapping, code construction, list decoding, Polar codes, successive cancellation",

author = "Mohammad Rowshan and Emanuele Viterbo",

year = "2019",

doi = "10.1109/ISIT.2019.8849539",

language = "English",

isbn = "9781538692929",

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

publisher = "IEEE, Institute of Electrical and Electronics Engineers",

pages = "1772--1776",

editor = "Giuseppe Caire and Veeravalli, {Venugopal V.} and Wagner, {Aaron B.} and Gilles Zemor",

booktitle = "2019 IEEE International Symposium on Information Theory",

address = "United States of America",

note = "IEEE International Symposium on Information Theory 2019, ISIT 2019 ; Conference date: 07-07-2019 Through 12-07-2019",

url = "https://2019.ieee-isit.org/, https://ieeexplore.ieee.org/xpl/conhome/8827389/proceeding",

}

Rowshan, M & Viterbo, E 2019, How to modify polar codes for list decoding. in G Caire, VV Veeravalli, AB Wagner & G Zemor (eds), 2019 IEEE International Symposium on Information Theory: Proceedings. IEEE International Symposium on Information Theory - Proceedings, IEEE, Institute of Electrical and Electronics Engineers, Piscataway NJ USA, pp. 1772-1776, IEEE International Symposium on Information Theory 2019, Paris, France, 7/07/19. https://doi.org/10.1109/ISIT.2019.8849539

How to modify polar codes for list decoding. / Rowshan, Mohammad; Viterbo, Emanuele.

2019 IEEE International Symposium on Information Theory: Proceedings. ed. / Giuseppe Caire; Venugopal V. Veeravalli; Aaron B. Wagner; Gilles Zemor. Piscataway NJ USA : IEEE, Institute of Electrical and Electronics Engineers, 2019. p. 1772-1776 (IEEE International Symposium on Information Theory - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - How to modify polar codes for list decoding

AU - Rowshan, Mohammad

AU - Viterbo, Emanuele

PY - 2019

Y1 - 2019

N2 - Polar codes are constructed based on the reliability of bit-channels. This construction suits the successive cancellation (SC) decoding, where one error in the successive estimation of the bits fails the decoding. However, in SC list (SCL) decoding, the correct path may remain in the list by tolerating multiple penalties. This characteristic of list decoding demands a different approach in code construction.In this work, we modify the conventional construction by a greedy search algorithm in which a bit-swapping approach is employed to re-distribute the low-reliability bits in the subblocks aiming for a reduction in the probability of correct path elimination. The numerical results for polar codes of length 1 kb under CRC-aided SCL decoding show improvements of about 0.4 dB for R=0.8 and over 0.2 dB for R=0.5 at L=32.

AB - Polar codes are constructed based on the reliability of bit-channels. This construction suits the successive cancellation (SC) decoding, where one error in the successive estimation of the bits fails the decoding. However, in SC list (SCL) decoding, the correct path may remain in the list by tolerating multiple penalties. This characteristic of list decoding demands a different approach in code construction.In this work, we modify the conventional construction by a greedy search algorithm in which a bit-swapping approach is employed to re-distribute the low-reliability bits in the subblocks aiming for a reduction in the probability of correct path elimination. The numerical results for polar codes of length 1 kb under CRC-aided SCL decoding show improvements of about 0.4 dB for R=0.8 and over 0.2 dB for R=0.5 at L=32.

KW - bit-swapping

KW - code construction

KW - list decoding

KW - Polar codes

KW - successive cancellation

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

U2 - 10.1109/ISIT.2019.8849539

DO - 10.1109/ISIT.2019.8849539

M3 - Conference Paper

AN - SCOPUS:85073145065

SN - 9781538692929

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1772

EP - 1776

BT - 2019 IEEE International Symposium on Information Theory

A2 - Caire, Giuseppe

A2 - Veeravalli, Venugopal V.

A2 - Wagner, Aaron B.

A2 - Zemor, Gilles

PB - IEEE, Institute of Electrical and Electronics Engineers

CY - Piscataway NJ USA

T2 - IEEE International Symposium on Information Theory 2019

Y2 - 7 July 2019 through 12 July 2019

ER -

Rowshan M, Viterbo E. How to modify polar codes for list decoding. In Caire G, Veeravalli VV, Wagner AB, Zemor G, editors, 2019 IEEE International Symposium on Information Theory: Proceedings. Piscataway NJ USA: IEEE, Institute of Electrical and Electronics Engineers. 2019. p. 1772-1776. (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2019.8849539

How to modify polar codes for list decoding

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Cite this