- 169 views
- 261 downloads
Fast and Simplified Successive-Cancellation Based Decoders for Polar Codes
-
- Author / Creator
- Haghighi Ardakani, Maryam
-
Polar codes are the first class of error correction codes with explicit construction that provably achieve the channel capacity. In addition, polar codes enjoy low-complexity encoding and low hardware and computational complexities under successive-cancellation (SC) decoding. Therefore, they have been selected to be used for the control channel in the fifth generation of mobile communication standards (5G). Although polar codes are asymptotically capacity-achieving under SC decoding, the SC decoding fails to provide reasonable error correction performance for short to moderate code length. This limitation is due to the performance gap between the SC decoder and the maximum-likelihood (ML) decoder. Successive-cancellation list (SCL) and successive-cancellation flip (SCF) decoding are proposed to improve the performance of polar codes. However, their serial decoding nature results in significant decoding latency. To reduce this latency some operations can be done in parallel. Specifically, special nodes are identified in the decoding tree of polar codes that can be decoded without serially traversing the decoding tree.
In this thesis, we present fast implementations of the SCL and SCF decoders. In particular, we propose fast parallel list decoders for five newly-identified nodes in the decoding tree of a polar code, which significantly reduces the decoding latency. We also present novel fast SCF decoders that decode some special nodes in the decoding tree of a polar code without serially computing bit log-likelihood ratios. Our proposed fast decoders significantly reduce the decoding latency without sacrificing the error-rate performance.
Another limitation of polar codes is lack of length flexibility. Polar codes are constructed by the recursive Kronecker product of a size-2 polarizing matrix, which limits their code length to integer powers of two. Incorporating larger size polarizing matrices in conjunction with the size-2 kernel enables the construction of multi-kernel polar codes. Multi-kernel codes are also decoded with a SC decoder and thus suffer its long decoding latency. This made devising fast decoding solutions for larger size kernels necessary. The size-3 kernels have drawn much attention due to their sufficiently high polarization exponents and the lowest decoding complexity among non-binary kernels. Hence, we identify a new node in the decoding tree of polar codes constructed by two commonly used size-3 kernels and propose a low-complexity decoder for it. Moreover, we adapt the generalized-repetition (G-REP) node introduced for the binary kernel to be used in the fast SC decoding of the size-3 kernel polar codes. The proposed fast decoders reduce the decoding latency at the cost of a slight degradation in error correction performance. Furthermore, the two specific size-3 kernels that can achieve the optimal polarization have a zero in their last rows. This results in the error-rate performance degradation of the repetition (REP) and G-REP nodes in addition to increased memory requirements for their fast decoders. Thus, we propose modifications to the REP and G-REP nodes that simultaneously result in improved error-rate performance and reduced memory requirements for their fast decoders.
-
- Graduation date
- Fall 2020
-
- Type of Item
- Thesis
-
- Degree
- Doctor of Philosophy
-
- License
- Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.