[go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

High-performance software implementations of SCAN decoder for polar codes

  • Published:
Annals of Telecommunications Aims and scope Submit manuscript

Abstract

This paper presents the first optimized software implementation of a SCAN decoder for Polar codes. Unlike SC and SC-List decoding algorithms, the SCAN decoding algorithm provides soft outputs (useful for, e.g., parallel concatenated decoders Zhang et al. IEEE Trans Commun 64(2):456–466 2016). Despite the strong data dependencies in the SCAN decoding, two highly parallel software implementations are devised for x86 processor target. Different parallelization strategies, algorithmic improvements, and source code optimizations were applied in order to enhance the throughput of the decoders. The impact of the parallelization approach, the code rate, and the code length on the throughput and the latency is investigated. Extensive experimentations demonstrate that the proposed software polar decoder can exceed 600 Mb/s on a single core and reaches multi-Gb/s when using four cores simultaneously. These decoders can then achieve real-time performance required in many applications such as software defined radio or cloud-RAN systems where network physical layer is implemented in software.

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+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

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

Similar content being viewed by others

References

  1. Zhang Q, Liu A, Zhang Y, Liang X (2016) Practical design and decoding of parallel concatenated structure for systematic polar codes. IEEE Trans Commun 64(2):456–466

    Article  Google Scholar 

  2. Arikan E (2009) Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Trans Inf Theory 55(7):3051–3073

    Article  MathSciNet  MATH  Google Scholar 

  3. Tal I, Vardy A (2015) List decoding of polar codes. IEEE Trans Inf Theory 61(5):2213–2226

    Article  MathSciNet  MATH  Google Scholar 

  4. Sarkis G, Giard P, Vardy A, Thibeault C, Gross WJ (2015) Unrolled polar decoders, part ii: Fast list decoders. IEEE J Sel Areas Commun - Special Issue on Recent Advances In Capacity Approaching Codes (submitted)

  5. Arikan E (2008) A performance comparison of polar codes and reed-muller codes. IEEE Commun Lett 12(6):447–449

    Article  Google Scholar 

  6. Guo J, Qin M, Fabregas G, Siegel PH (2014) Enhanced belief propagation decoding of polar codes through concatenation. In: Proceedings of the IEEE international symposium on information theory (ISIT), pp 2987–2991

  7. Fayyaz UU, Barry JR (2013) A low-complexity soft-output decoder for polar codes. In: Proceedings of the IEEE global communications conference (GLOBECOM), pp 2692–2697

  8. Fayyaz UU, Barry JR (2013) Polar codes for partial response channels. In: Proceedings of the IEEE international conference on communications (ICC), pp 4337–4341

  9. Fayyaz UU (2014) Polar code design and decoding for magnetic recording, Georgia Institute of Technology, PhD thesis

  10. Zhao S-M, Xu SP, Xing C (2015) Concatenated polar-coded multilevel modulation. In: Proceedings of the 10th international conference on communications and networking in China (ChinaCom), pp 153–157

  11. Wu D, Liu A, Zhang Q, Zhang Y (2015) Concatenated polar codes based on selective polarization. In: Proceedings of the 12th international computer conference on wavelet active media technology and information processing (ICCWAMTIP), pp 436–442

  12. Sha J, Liu J, Lin J, Wang Z (2016) A stage-combined belief propagation decoder for polar codes. J Signal Process Syst, 1–8

  13. Wang Y-CHY, Narayanan KR (2016) Interleaved concatenations of polar codes with bch and convolutional codes. IEEE J Selected Areas Commun 34:267–277

    Article  Google Scholar 

  14. Li G, Jianjun M, Jiao X, Guo J, Liu X (2017) Enhanced belief propagation decoding of polar codes by adapting the parity-check matrix. EURASIP J Wirel Commun Netw 40:9

    Google Scholar 

  15. Zhang Q, Liu A, Pan X, Zhang Y (2017) Symbol-based belief propagation decoder for multilevel polar coded modulation. IEEE Commun Lett 21:24–27

    Article  Google Scholar 

  16. Le Gal B, Jego C (2015) High-throughput multi-core LDPC decoders based on x86 processor. IEEE Trans Parallel Distrib Syst (TPDS) 27(5):1373–1386

    Article  Google Scholar 

  17. Wu M, Sun Y, Wang G, Cavallaro JR (2011) Implementation of a high throughput 3GPP turbo decoder on GPU. J Signal Process Sys Springer. 65(171)

  18. Grayver E (2013) Implementing software defined radio. Springer, New York

    Book  Google Scholar 

  19. Checko A, Christiansen HL, Yan Y, Scolari L, Kardaras G, Berger MS, Dittmann L (2015) Cloud RAN for mobile networks—a technology overview. IEEE Commun Surv Tutor 17(1):405–426

    Article  Google Scholar 

  20. Giard P, Sarkis G, Thibeault C, Gross WJ (2014) A fast software polar decoder. In: Proceedings of the IEEE international conference on acoustics, speech and signal processing (ICASSP), pp 7555–7559

  21. Le Gal B, Leroux C, Jego C (2015) Multi-Gb/s software decoding of polar codes. IEEE Trans Signal Process 63(2):349–359

    Article  MathSciNet  Google Scholar 

  22. Le Gal B, Leroux C, Jego C (2014) Software polar decoder on an embedded processor. In: Proceedings of the IEEE workshop on signal processing systems (SiPS), pp 1–6

  23. Sarkis G, Giard P, Vardy A, Thibeault C, Gross W (2014) Increasing the speed of polar list decoders. In: Proceedings of the IEEE workshop on signal processing systems (SiPS), pp 1–6

  24. Berhault G, Leroux C, Jego C, Dallet D (2015) Hardware implementation of a soft cancellation decoder for polar codes. In: Proceedings of the IEEE conference on design & architectures for signal & image processing, pp 1–8

  25. Lin J, Xiong C, Yan Z (2015) Reduced complexity belief propagation decoders for polar codes. In: Proceedings of the IEEE workshop on signal processing systems (SiPS), pp 1–6

  26. Tal I, Vardy A (2013) How to construct polar codes. IEEE Trans Inf Theory 59(10):6562–6582

    Article  MathSciNet  MATH  Google Scholar 

  27. Alamdar-Yazdi A, Kschischang FR (2011) A simplified successive-cancellation decoder for polar codes. IEEE Commun Lett 15(12):1378–1380

    Article  Google Scholar 

  28. Andrade J, Falcao G, Silva V (2014) Optimized fast Walsh-Hadamard transform on GPUs for non-binary LDPC decoding. Parallel Comput Elsevier 40(9):449–453

    Article  MathSciNet  Google Scholar 

  29. Hou Y, Liu R, Peng H, Zhao L (2015) High throughput pipeline decoder for LDPC convolutional codes on GPU. IEEE Commun Lett 19(12):2066–2069

    Article  Google Scholar 

  30. Giard P, Sarkis G, Leroux C, Thibeault C, Gross WJ (2016) Low-latency software polar decoders. Journal of Signal Processing Systems

  31. Deilmann M (2012) A guide to vectorization with intel C++ compilers. Intel Corporation

  32. Sarkis G, Giard P, Thibeault C, Gross WJ (2014) Autogenerating software polar decoders. In: Proceedings of the IEEE Global conference on signal and information processing (GlobalSIP), pp 6–10

  33. Sarkis G, Tal I, Giard P, Vardy A, Thibeault C, Gross WJ (2016) Flexible and low-complexity encoding and decoding of systematic polar codes. IEEE Trans Commun 64(7):2732–2745

    Article  Google Scholar 

  34. Leroux C, Tal I, Vardy A, Gross WJ (2011) Hardware architectures for successive cancellation decoding of polar codes. In: Proceedings of the IEEE International conference on acoustics, speech and signal processing (ICASSP), pp 1665–1668

  35. Bjerke H (2008) SIMD tutorial. CERN openlab

  36. Intel corporation (2014) Intel 64 and IA-32 architectures optimization reference manual order number: 248966-029 edition

  37. Chapman B, Jost G, Van Der Pas R (2008) Using OpenMP: portable shared memory parallel programming. The MIT Press

  38. Reddy BK, Nitin C (2012) GPU implementation of belief propagation decoder for polar codes. In: Proceedings of the forty sixth Asilomar conference on signals, systems and computers (ASILOMAR), pp 1272–1276

  39. Sarkis G, Giard P, Vardy A, Thibeault C, Gross WJ (2016) Fast list decoders for polar codes. IEEE J Selected Areas Commun 34:318—328

    Article  Google Scholar 

  40. Shen Y, Zhang C, Yang J, Zhang S, You X (2016) Low-latency software successive cancellation list polar decoder using stage-located copy. In: Proceedings of the IEEE International conference on digital signal processing (DSP), pp 84–88

Download references

Author information

Authors and Affiliations

  1. IMS Laboratory, UMR CNRS 5218, Bordeaux-INP, Talence, France

    Bertrand Le Gal, Camille Leroux & Christophe Jego

Authors
  1. Bertrand Le Gal
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Camille Leroux
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Christophe Jego
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bertrand Le Gal.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Le Gal, B., Leroux, C. & Jego, C. High-performance software implementations of SCAN decoder for polar codes. Ann. Telecommun. 73, 401–412 (2018). https://doi.org/10.1007/s12243-018-0634-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12243-018-0634-7

Keywords