+
Skip to main content
Springer Nature Link
Log in

On Reducing Decoding Complexity of Successive-Cancellation List Flip Decoding of Polar Codes

  • Published:
Journal of Signal Processing Systems Aims and scope Submit manuscript

Abstract

The recently proposed SCLF decoding algorithm for polar codes improves the error-correcting performance of state-of-the-art SCL decoding. However, it comes at the cost of a higher complexity. In this paper, partitioned polar codes tailored for the proposed PSCLF decoding algorithm are used to reduce the complexity of SCLF. Indeed, compared to SCLF, PSCLF allows early termination and is able to restart by skipping part of the decoding tree traversed sequentially. In order to maximize the coding gain, design of partitions tailored to PSCLF is proposed. In this extended paper, dynamic flip metric is used, as well as the possibility to flip multiple times during SCL. An analysis on the impact of this strategy on the early-termination or the CRC collisions encountered in PSCLF is carried out. Error-correction performance of multiple code rates and multiple partition strategies are shown. With the baseline algorithm SCL with \(\varvec{L}\,\mathbf {=2}\), degradation of \(\mathbf {0.05}\) dB is shown with respect to SCL-64, using \(\varvec{\omega }\,\mathbf {=3}\) flip per trial with \(\varvec{T}_{\text {max}}\,\mathbf {=300}\) trials. Numerical results show that the proposed PSCLF algorithm has an error-correction performance gain of up to 0.1 dB with respect to SCLF with same decoding parameters. This work is also compared with existing techniques to reduce the complexity of the SCLF decoding algorithm. The proposed algorithm reduces the complexity up to 77 % at the frame-error rate of 0.01 with respect to SCLF and is able to reduce more the decoding complexity of SCLF embedding as well a restart mechanism. The average execution time of PSCLF matches the latency of SCL at \(\text {FER}=\mathbf {4\cdot 10^{-3}}\) and lower.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  1. Arıkan, E. (2009). Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Transactions on Information Theory, 55(7), 3051–3073. https://doi.org/10.1109/TIT.2009.2021379

    Article  MathSciNet  MATH  Google Scholar 

  2. Tal, I., & Vardy, A. (2015). List decoding of polar codes. IEEE Transactions on Information Theory, 61(5), 2213–2226. https://doi.org/10.1109/TIT.2015.2410251

    Article  MathSciNet  MATH  Google Scholar 

  3. Afisiadis, O., Balatsoukas-Stimming, A., Burg, A. (2014). A low-complexity improved successive cancellation decoder for polar codes. In: Asilomar Conf. on Signals, Syst., and Comput. (ACSSC). https://doi.org/10.1109/ACSSC.2014.7094848

  4. Generation Partnership Project (3GPP) (2018). Multiplexing and channel coding. 3GPP 38.212 V.15.3.0

  5. Chandesris, L., et al. (2018). Dynamic-SCFlip decoding of polar codes. IEEE Transactions on Communications, 66(6), 2333–2345. https://doi.org/10.1109/TCOMM.2018.2793887

    Article  Google Scholar 

  6. Yongrun, Y., Zhiwen, P., Nan, L., Xiaohu, Y. (2018). Successive cancellation list bit-flip decoder for polar codes. In: Int. Conf. on Wireless Commun. and Signal Process. (WCSP). https://doi.org/10.1109/WCSP.2018.8555688

  7. Cheng, F., et al. (2019). Bit-flip algorithm for successive cancellation list decoder of polar codes. IEEE Access, 7, 58346–58352. https://doi.org/10.1109/ACCESS.2019.2914691

    Article  Google Scholar 

  8. Rowshan, M., Viterbo, E. (2019). Improved list decoding of polar codes by shifted-pruning. In: IEEE Inf. Theory Workshop (ITW) (pp. 1–5). https://doi.org/10.1109/ITW44776.2019.8989330

  9. Pan, Y., Wang, C., Ueng, Y. (2020). Generalized SCL-Flip decoding of polar codes. In: IEEE Global Telecommun. Conf. (GLOBECOM). https://doi.org/10.1109/GLOBECOM42002.2020.9321982

  10. Ivanov, F., Morishnik, V., & Krouk, E. (2021). Improved generalized successive cancellation list flip decoder of polar codes with fast decoding of special nodes. The Journal of Communications and Networks, 23(6), 417–432. https://doi.org/10.23919/JCN.2021.000038

    Article  Google Scholar 

  11. Shen, Y., et al. (2022). Dynamic SCL decoder with path-flipping for 5G polar codes. IEEE Wireless Communications Letters, 11(2), 391–395. https://doi.org/10.1109/LWC.2021.3129470

    Article  Google Scholar 

  12. Hashemi, S., Balatsoukas-Stimming, A., Giard, P., Thibeault, C., Gross, W. (2016). Partitioned successive-cancellation list decoding of polar codes. In: IEEE Int. Conf. on Acoustics, Speech, and Signal Process. (ICASSP) (pp. 957–960). https://doi.org/10.1109/ICASSP.2016.7471817

  13. Zhou, H., Zhang, C., Song, W., Xu, S., & You, X. (2016) Segmented CRC-aided SC list polar decoding. In: IEEE Veh. Technol. Conf. (VTC) (pp. 1–5). https://doi.org/10.1109/VTCSpring.2016.7504469

  14. Ercan, F., et al (2018). Partitioned successive-cancellation flip decoding of polar codes. In: IEEE Int. Conf. Commun. (ICC) (pp. 1–6). https://doi.org/10.1109/ICC.2018.8422464

  15. Pillet, C., Sagitov, I., Domer, G., & Giard, P. (2024). Partitioned successive-cancellation list flip decoding of polar codes. In: IEEE Int. Workshop on Signal Process. Syst. (SiPS) (pp. 19–24). https://doi.org/10.1109/SiPS62058.2024.00012

  16. Balatsoukas-Stimming, A., Parizi, M., & Burg, A. (2015). LLR-based successive cancellation list decoding of polar codes. IEEE Transactions on Signal Processing, 63(19), 5165–5179. https://doi.org/10.1109/TSP.2015.2439211

    Article  MathSciNet  Google Scholar 

  17. 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), 2044–2047. https://doi.org/10.1109/LCOMM.2012.111612.121898

    Article  Google Scholar 

  18. Sagitov, I., Pillet, C., Balatsoukas-Stimming, A., & Giard, P. (2025). Restart mechanisms for the successive-cancellation list-flip decoding of polar codes. Entropy,27(3). https://doi.org/10.3390/e27030309

  19. Pillet, C., et al (2020). On list decoding of 5G-NR polar codes. In: IEEE Wireless Commun. and Netw. Conf. (WCNC). South Korea. https://doi.org/10.1109/WCNC45663.2020.9120686

  20. Sagitov, I., Pillet, C., Balatsoukas-Stimming, A., Giard, P.: Generalized restart mechanism for successive-cancellation flip decoding of polar codes. J. Signal Process. Syst., accepted, to appear (2025) https://doi.org/10.1007/s11265-025-01949-8

  21. Leroux, C., Raymond, A., Sarkis, G., & Gross, W. J. (2013). A semi-parallel successive-cancellation decoder for polar codes. IEEE Transactions on Signal Processing, 61(2), 289–299. https://doi.org/10.1109/TSP.2012.2223693

    Article  MathSciNet  MATH  Google Scholar 

  22. Giard, P., Balatsoukas-Stimming, A., Müller, T., Bonetti, A., Thibeault, C., Gross, W., Flatresse, P., & Burg, A. (2017). PolarBear: A 28-nm FD-SOI ASIC for decoding of polar codes. IEEE Journal on Emerging and Selected Topics in Circuits and Systems., 7(4), 616–629. https://doi.org/10.1109/JETCAS.2017.2745704

    Article  Google Scholar 

  23. Zhou, H., et al. (2018). Segmented successive cancellation list polar decoding with tailored CRC. Journal of Signal Processing Systems, 91, 923–935.

    Article  Google Scholar 

Download references

Acknowledgements

The original contributions presented in the study are included in the article, further inquiries can be directed to the corresponding author/s.

Funding

We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), RGPIN-2018-04284.

Author information

Authors and Affiliations

  1. LaCIME, Department of Electrical Engineering, École de technologie supérieure (ÉTS), 1100 Notre-Dame St West, Montréal, Québec, H3C 1K3, Canada

    Charles Pillet, Ilshat Sagitov & Pascal Giard

Authors
  1. Charles Pillet
    View author publications

    Search author on:PubMed Google Scholar

  2. Ilshat Sagitov
    View author publications

    Search author on:PubMed Google Scholar

  3. Pascal Giard
    View author publications

    Search author on:PubMed Google Scholar

Corresponding authors

Correspondence to Charles Pillet or Ilshat Sagitov.

Ethics declarations

Conflicts of interest

The authors declare no conflicts of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Pillet, C., Sagitov, I. & Giard, P. On Reducing Decoding Complexity of Successive-Cancellation List Flip Decoding of Polar Codes. J Sign Process Syst 97, 293–306 (2025). https://doi.org/10.1007/s11265-025-01969-4

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Version of record:

  • Issue date:

  • DOI: https://doi.org/10.1007/s11265-025-01969-4

Keywords

Profiles

  1. Charles Pillet View author profile
点击 这是indexloc提供的php浏览器服务，不要输入任何密码和下载