Enhancing Iterative Decoding of Polar-like Code Constructions
Final Report Abstract
Over the past 60 years, the field of channel coding has evolved from simple error detection through parity bit checking to powerful error correction using dedicated algebraic codes or concatenated coding schemes in conjunction with their respective (iterative) decoders. As it turns out, those schemes can approach the theoretical capacity limits very closely, i.e., they can operate at arbitrarily small error rates (as the codeword length goes toward infinity) at channel conditions close to signal-to-noise ratios or erasure probabilities (or other channel quality measures, respectively) as predicted by the corresponding capacity equation. Thus, “reliable communications” is possible today with practical coding schemes; yet, such coding schemes still differ significantly with respect to their specific properties such as, among others, • flexibility with respect to codeword length and code rate, • performance of short-length variants, • universality (“one code fits all”, e.g., excellent performance over AWGN, Rayleigh, erasure channels and others), • possibility of soft output decoding, • simplicity of combination with channel interfaces like spectrally efficient modulation, i.e., when performing iterative detection and decoding at the receiver, • complexity (number of operations) and ease of implementation (regular rather than random-like structures for small routing overhead), and • provability of performance. While most efforts over the past decade have focused on low-density parity-check (LDPC) codes, or, more recently, their spatially coupled offsprings, this proposal is about studying and enhancing another attractive development in the field, referred to as “polar codes”; those codes have several favorable properties and offer plenty of opportunities to be used as basic building blocks for new, tailored classes of coding schemes that may address some of the aspects listed above in a much more efficient manner, as will be further elaborated in the following. Polar codes were introduced by Erdal Arıkan; he proved that polar codes can achieve capacity of any symmetric Binary Input-Discrete Memoryless Channel (BI-DMC) under Successive Cancellation (SC) decoding for infinite codeword length. As opposed to other “random-like” channel codes with close-to-capacity performance, polar codes exhibit a very regular (algebraic) structure, opening up the potential for efficient (i.e., low-complexity) hardware implementations; this becomes particularly evident when accounting for the routing overhead in silicon chip technology, which may easily become prohibitive for iterative decoders of state-of-the-art LDPC codes. Polar codes are based on several concepts: the channel polarization effect, which is a tailored code construction of choosing “frozen” and “non-frozen” bit channels, and a structured encoding and decoding procedure, which shall be reviewed briefly in the following. It is instructive to realize that polar codes are closely related to Reed–Muller (RM) Codes. However the sequential SC decoding algorithm (and, thus, the selection of the “frozen” bit channels) follow a quite different approach, leading to many open research questions in polar code design. In this project, we focus on belief propagation (BP) decoding of polar codes and aim at enhancing the error-rate performance of the BP decoder for finite-length polar (and polar-like) codes. Despite its weaker error-rate performance when compared to the state-of-the-art Successive Cancellation List (SCL) decoder, the non-sequential decoding strategy of the BP decoder makes it more attractive for high-speed applications since its operations can be easily parallelized and, thus, implementations with high throughput and low latency are possible. Moreover, the BP decoder is of potential importance for applications requiring soft output decoding. In brief, the focus of this project is to overcome the error-rate performance gap between iterative polar decoding schemes and state-of-the-art SC list decoders while maintaining the iterative soft-in/softout character of the decoder.
Publications
- “Combining belief propagation and successive cancellation list decoding of polar codes on a GPU platform.” In: 42nd Int. Conf. on Acoustics, Speech, and Signal Processing (ICASSP). 2017
S. Cammerer, B. Leible, M. Stahl, J. Hoydis, and S. ten Brink
(See online at https://doi.org/10.1109/icassp.2017.7952840) - “Flexible Length Polar Codes through Graph Based Augmentation.” In: 11th International ITG Conference on Systems, Communications and Coding (SCC). Feb. 2017
A. Elkelesh, M. Ebada, S. Cammerer, and S. ten Brink
- “Mitigating Clipping Effects on Error Floors under Belief Propagation Decoding of Polar Codes.” In: Inter. Symp. Wireless Commun. Syst. Aug. 2017
Ahmed Elkelesh, Sebastian Cammerer, Moustafa Ebada, and Stephan ten Brink
(See online at https://doi.org/10.1109/iswcs.2017.8108145) - “Belief Propagation Decoding of Polar Codes on Permuted Factor Graphs.” In: IEEE Wireless Commun. and Networking Conf. (WCNC). Apr. 2018
A. Elkelesh, M. Ebada, S. Cammerer, and S. ten Brink
(See online at https://doi.org/10.1109/wcnc.2018.8377158) - “Belief Propagation List Decoding of Polar Codes.” In: IEEE Commun. Lett. 22.8 (Aug. 2018), pp. 1536–1539
A. Elkelesh, M. Ebada, S. Cammerer, and S. ten Brink
(See online at https://doi.org/10.1109/lcomm.2018.2850772) - “Scattered EXIT Charts for Finite Length LDPC Code Design.” In: IEEE Int. Conf. Commun. (ICC). May 2018, pp. 1–7
M. Ebada, A. Elkelesh, S. Cammerer, and S. ten Brink
(See online at https://doi.org/10.1109/icc.2018.8422961) - “Sparse Graphs for Belief Propagation Decoding of Polar Codes.” In: IEEE Inter. Symp. Inf. Theory (ISIT). June 2018, pp. 1465–1469
S. Cammerer, M. Ebada, A. Elkelesh, and S. ten Brink
(See online at https://doi.org/10.1109/isit.2018.8437581) - “Decoder-in-the-Loop: Genetic Optimization-based LDPC Code Design.” In: IEEE Access (2019)
Ahmed Elkelesh, Moustafa Ebada, Sebastian Cammerer, Laurent Schmalen, and Stephan ten Brink
(See online at https://doi.org/10.1109/access.2019.2942999) - “Decoder-Tailored Polar Code Design Using the Genetic Algorithm.” In: IEEE Trans. Commun. 67.7 (July 2019), pp. 4521–4534
A. Elkelesh, M. Ebada, S. Cammerer, and S. ten Brink
(See online at https://doi.org/10.1109/tcomm.2019.2908870) - “Deep Learning-based Polar Code Design.” In: 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton). Sept. 2019
Moustafa Ebada, Sebastian Cammerer, Ahmed Elkelesh, and Stephan ten Brink
(See online at https://doi.org/10.1109/allerton.2019.8919804) - “Genetic Algorithm-based Polar Code Construction for the AWGN Channel.” In: IEEE Inter. ITG Conf. on Syst., Commun. and Coding (SCC). Feb. 2019
A. Elkelesh, M. Ebada, S. Cammerer, and S. ten Brink
(See online at https://doi.org/10.30420/454862007) - “Near-Capacity Detection and Decoding: Code Design for Dynamic User Loads in Gaussian Multiple Access Channels.” In: IEEE Transactions on Communications 67.11 (2019), pp. 7417–7430
X. Wang, S. Cammerer, and S. ten Brink
(See online at https://doi.org/10.1109/tcomm.2019.2935726) - “Optimizing Polar Codes Compatible with Off-the-Shelf LDPC Decoders.” In: IEEE Information Theory Workshop (ITW). 2019
M. Ebada, A. Elkelesh, and S. ten Brink
(See online at https://doi.org/10.1109/itw44776.2019.8989269) - “Spatially Coupled LDPC Codes and the Multiple Access Channel.” In: 53rd Annual Conference on Information Sciences and Systems (CISS). 2019, pp. 1–6
S. Cammerer, X. Wang, Y. Ma, and S. ten Brink
(See online at https://doi.org/10.1109/ciss.2019.8692899) - “CRC-Aided Belief Propagation List Decoding of Polar Codes.” In: IEEE Inter. Symp. Inf. Theory (ISIT). June 2020
Marvin Geiselhart, Ahmed Elkelesh, Moustafa Ebada, Sebastian Cammerer, and Stephan ten Brink
(See online at https://doi.org/10.1109/isit44484.2020.9174249)
