EE Seminar: Adaptive Successive Cancellation List Decoding of Polar Codes
~~Speaker: Ayelet Aharon,
M.Sc. student under the supervision of Prof. Simon Litsyn
Wednesday, March 11, 2015 at 15:30
Room 011, Kitot Bldg., Faculty of Engineering
Adaptive Successive Cancellation List Decoding of Polar Codes
Abstract
Polar codes, invented by Arikan, are the first to achieve the Shannon capacity over discrete memoryless channels (DMC) with feasible implementation complexity of O(n*log(n)), where n is the code's length. Successive Cancelation List (SCL) decoding combined with Cyclic Redundancy Check (CRC) improves polar codes' performances to the extent of being better than those of modern coding techniques. The SCL decoder explores simultaneously L decoding paths which results in running time complexity of O(L*n*log(n)) and space complexity of O(L*n) where L is the list size.
In this work an adaptive version of the SCL decoder, namely ASCL decoder, is proposed. While decoding, the ASCL decoder decides, with the help of predefined thresholds, how many paths to allocate at each decoding step according to the input's noise level and the vulnerability of the currently decoded bit to mistakes. At each decoding step, up to L_max paths can be allocated (if a threshold has isolated more paths the algorithm uses sorting to detect the L_max most probable paths) leading to a space complexity of O(L_max*n). The running time complexity is O(L_average*n*log(n)), where L_average≤L_max is the average list size the decoder uses, which can be monitored by changing the thresholds suitably.
For a given running time complexity, the proposed algorithm's BLER performance is significantly improved in comparison to this of the SCL decoder. Furthermore, for a high enough SNR, the BLER performance of the ASCL decoder with any 2≤L_average≤L_max is similar to this of the SCL decoder with list size L=L_max. This makes the ASCL decoder a valuable replacement to the SCL decoder.
Unlike the SCL which requires to perform sorting at (almost) each decoding step, the ASCL decoder avoids most of these procedures due to its use of thresholds. By utilizing this property even further, we suggest modified versions of the ASCL decoder which completely avoid sorting at the expense of a relatively small decrease of the BLER performance.
Finally, since the ASCL decoder (as well as any other list decoding procedure), relies on the use of a CRC, we establish a set of guidelines to assist in finding the optimal CRC length for a given SNR value. A wise choice of the CRC can prevent an unnecessary and sometimes significant loss in performance, especially when the decoder's performance has the potential of improving drastically as the SNR grows.
