Bidirectional stack decoding of polar codes
Abstract
Introduction/purpose: The paper introduces a reduced latency stack decoding algorithm of polar codes, inspired by the bidirectional stack decoding of convolutional codes and based on the folding technique.
Methods: The stack decoding algorithm (also known as stack search) that is useful for decoding tree codes, the list decoding technique introduced by Peter Elias and the folding technique for polar codes which is used to reduce the latency of the decoding algorithm. The simulation was done using the Monte Carlo procedure.
Results: A new polar code decoding algorithm, suitable for parallel implementation, is developed and the simulation results are presented.
Conclusions: Polar codes are a class of capacity achieving codes that have been adopted as the main coding scheme for control channels in 5G New Radio. The main decoding algorithm for polar codes is the successive cancellation decoder. This algorithm performs well at large blocklengths with a low complexity, but has very low reliability at short and medium blocklengths. Several decoding algorithms have been proposed in order to improve the error correcting performance of polar codes. The successive cancellation list decoder, in conjunction with a cyclic redundancy check, provides very good error-correction performance, but at the cost of a high implementation complexity. The successive cancellation stack decoder provides similar error-correction performance at a lower complexity. Future machine-type and ultra reliable low latency communication applications require high-speed low latency decoding algorithms with good error correcting performance. In this paper, we propose a novel decoding algorithm, inspired by the bidirectional stack decoding of classical convolutional codes, with reduced latency that achieves similar performance as the classical successive cancellation list and successive cancellation stack decoding algorithms. The results are presented analytically and verified by simulation.
References
-3rd Generation Partnership Project. 2016. Final report of 3GPP TSG RAN WG1 #87 v1.0.0. [online]. Available at: https://www.3gpp.org/DynaReport/TDocExMtg--R1-87--31665.htm [Accessed: 1 February 2021].
Alamdar-Yazdi, A. & Kschischang, F.R. 2011. A Simplified Successive-Cancellation Decoder for Polar Codes. IEEE Communications Letters, 15(12), pp. 1378–1380. Available at: https://doi.org/10.1109/LCOMM.2011.101811.111480.
Arikan, E. 2008. A performance comparison of polar codes and Reed-Muller codes. IEEE Communications Letters, 12(6), pp. 447–449. Available at: https://doi.org/10.1109/LCOMM.2008.080017.
Arikan, E. 2009. Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels. IEEE Transactions on Information Theory, 55(7), pp. 3051–3073. Available at: https://doi.org/10.1109/TIT.2009.2021379.
Arikan, E. 2010. Polar codes: A pipelined implementation. In: Proc. 4th Int. Symp. on Broad. Commun. ISBC 2010. pp. 11–14.
Aurora, H., Condo, C. & Gross, W.J. 2018. Low-Complexity Software Stack Decoding of Polar Codes. In: 2018 IEEE International Symposium on Circuits and Systems (ISCAS). pp. 1–5. Available at: https://doi.org/10.1109/ISCAS.2018.8351832.
Aurora, H. & Gross, W.J. 2018. Towards Practical Software Stack Decoding of Polar Codes. [online]. Available at: https://arxiv.org/abs/1809.03606 [Accessed: 1 February 2021].
Balatsoukas-Stimming, A., Parizi, M.B. & Burg, A. 2015. LLR-Based Successive Cancellation List Decoding of Polar Codes. IEEE Transactions on Signal Processing, 63(19), pp. 5165–5179. Available at: https://doi.org/10.1109/TSP.2015.2439211.
Forney, G.D. 2001. Codes on graphs: normal realizations. IEEE Transactions on Information Theory, 47(2), pp. 520–548. Available at: https://doi.org/10.1109/18.910573.
Hanif, M. & Ardakani, M. 2017. Fast Successive-Cancellation Decoding of Polar Codes: Identification and Decoding of New Nodes. IEEE Communications Letters, 21(11), pp. 2360–2363. Available at: https://doi.org/10.1109/LCOMM.2017.2740305.
Hashemi, S.A., Condo, C. & Gross, W.J. 2016. Simplified Successive-Cancellation List decoding of polar codes. In: 2016 IEEE International Symposium on Information Theory (ISIT). pp. 815–819. Available at: https://doi.org/10.1109/ISIT.2016.7541412.
Hashemi, S.A., Mondelli, M., Fazeli, A., Vardy, A., Cioffi, J. & Goldsmith, A. 2020. Parallelism versus Latency in Simplified Successive-Cancellation Decoding of Polar Codes. [online]. Available at: https://arxiv.org/abs/2012.13378 [Accessed: 1 February 2021].
Huang, Y., Zhang, Z., You, X. & Zhang, C. 2018. Efficient Folded SC Polar Line Decoder. In: 2018 IEEE 23rd International Conference on Digital Signal Processing (DSP). pp. 1–5. Available at: https://doi.org/10.1109/ICDSP.2018.8631807.
Kahraman, S., Viterbo, E. & Çelebi, M.E. 2013. Folded tree maximum-likelihood decoder for Kronecker product-based codes. In: 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 629–636. Available at: https://doi.org/10.1109/Allerton.2013.6736584.
Kahraman, S., Viterbo, E. & Çelebi, M.E. 2014a. Folded successive cancelation decoding of polar codes. In: 2014 Australian Communications Theory Workshop (AusCTW). pp. 57–61. Available at: https://doi.org/10.1109/AusCTW.2014.6766428.
Kahraman, S., Viterbo, E. & Çelebi, M.E. 2014b. Multiple Folding for Successive Cancelation Decoding of Polar Codes. IEEE Wireless Communications Letters, 3(5), pp. 545–548. Available at: https://doi.org/10.1109/LWC.2014.2343970.
Li, B., Shen, H. & Tse, D. 2012. An Adaptive Successive Cancellation List Decoder for Polar Codes with Cyclic Redundancy Check. IEEE Communications Letters, 16(12), pp. 2044–2047. Available at: https://doi.org/10.1109/LCOMM.2012.111612.121898.
Li, B., Shen, H. & Tse, D. 2013. Parallel Decoders of Polar Codes [online]. Available at: https://arxiv.org/abs/1309.1026v1 [Accessed: 1 February 2021].
Li, B., Shen, H., Tse, D. & Tong, W. 2014. Low-latency polar codes via hybrid decoding. In: 2014 8th International Symposium on Turbo Codes and Iterative Information Processing (ISTC). pp. 223–227. Available at: https://doi.org/10.1109/ISTC.2014.6955118.
Niu, K. & Chen, K. 2012b. CRC-Aided Decoding of Polar Codes. IEEE Communications Letters, 16(10), pp. 1668–1671. Available at: https://doi.org/10.1109/LCOMM.2012.090312.121501.
Niu, K. & Chen, K. 2012a. Stack decoding of polar codes. Electronics Letters, 48, pp. 695–697(2). Available at: https://doi.org/10.1049/el.2012.1459.
Sarkis, G., Giard, P., Vardy, A., Thibeault, C. & Gross, W.J. 2014. Fast Polar Decoders: Algorithm and Implementation. IEEE Journal on Selected Areas in Communications, 32(5), pp. 946–957. Available at: https://doi.org/10.1109/JSAC.2014.140514.
Tal, I. & Vardy, A. 2015. List Decoding of Polar Codes. IEEE Transactions on Information Theory, 61(5), pp. 2213–2226. Available at: https://doi.org/10.1109/TIT.2015.2410251.
Vangala, H., Viterbo, E. & Hong, Y. 2014a. Improved multiple folded successive cancellation decoder for polar codes. In: 2014 XXXIth URSI General Assembly and Scientific Symposium (URSI GASS). pp. 1–4. Available at: https://doi.org/10.1109/URSIGASS.2014.6929238.
Vangala, H., Viterbo, E. & Hong, Y. 2014b. A new multiple folded successive cancellation decoder for polar codes. In: 2014 IEEE Information Theory Workshop (ITW 2014). pp. 381–385. Available at: https://doi.org/10.1109/ITW.2014.6970858.
Vangala, H., Viterbo, E. & Hong, Y. 2015. A Comparative Study of Polar Code Constructions for the AWGN Channel. [online]. Available at: https://arxiv.org/abs/1501.02473 [Accessed: 1 February 2021].
Won, J.W. & Ahn, J.M. 2020. 3GPP URLLC patent analysis. ICT Express. Available at: https://doi.org/10.1016/j.icte.2020.09.001.
Xiang, L., Kaykac Egilmez, Z.B., Maunder, R.G. & Hanzo, L. 2019. CRC-Aided Logarithmic Stack Decoding of Polar Codes for Ultra Reliable Low Latency Communication in 3GPP New Radio. IEEE Access, 7, pp. 28559–28573. Available at: https://doi.org/10.1109/ACCESS.2019.2901596.
Xiang, L., Zhong, S., Maunder, R.G. & Hanzo, L. 2020. Reduced-Complexity Low-Latency Logarithmic Successive Cancellation Stack Polar Decoding for 5G New Radio and Its Software Implementation. IEEE Transactions on Vehicular Technology, 69(11), pp. 12449–12458. Available at: https://doi.org/10.1109/TVT.2020.3026915.
Proposed Creative Commons Copyright Notices
Proposed Policy for Military Technical Courier (Journals That Offer Open Access)
Authors who publish with this journal agree to the following terms:
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).