Journal Home > Volume 2 , Issue 4
Intelligent and Converged Networks 2021, 2(4): 334-346 https://doi.org/10.23919/ICN.2021.0024
Open Access | Issue | Published: 30 December 2021

Polar codes: Encoding/decoding and rate-compatible jointly design for HARQ system

Show Author's Information Qiaoli Zeng1,  Quan Zhou1,  Xiangkun He2,  Youming Sun1,  Xiangcheng Li1,  Haiqiang Chen1( )
School of Computer, Electronics and Information and Guangxi Colleges and Universities Key Laboratory of Multimedia Communications and Information Processing, Guangxi University, Nanning 530004, China
Department of Mechanical and Aerospace Engineering, Nanyang Technological University, Singapore 999002, Singapore
Keywords:
polar code, rate compatible, hybrid automatic re-transmission request, polar coding/decoding
Cite this article:
Zeng Q, Zhou Q, He X, et al. Polar codes: Encoding/decoding and rate-compatible jointly design for HARQ system. Intelligent and Converged Networks, 2021, 2(4): 334-346. https://doi.org/10.23919/ICN.2021.0024
Download citation
EndNote(RIS)
BibTeX

1135

Views

951

Downloads

Citations

4

Crossref

N/A

WoS

2

Scopus

N/A

CSCD

Abstract Full text About this article

Polar coding are the first class of provable capacity-achieving coding techniques for a wide range of channels. With an ideal recursive structure and many elegant mathematical properties, polar codes are inherently implemented with low complexity encoding and decoding algorithms. Since the block length of the original polar construction is limited to powers of two, rate-compatible polar codes (RCPC) are presented to meet the flexible length/rate transmission requirements in practice. The RCPC codes are well-conditioned to combine with the hybrid automatic repeat request (HARQ) system, providing high throughput efficiency and such RCPC-HAPQ scheme is commonly used in delay-insensitive communication system. This paper first gives a survey of both the classical and state-of-the-art encoding/decoding algorithms for polar codes. Then the RCPC construction methods are discussed, including the puncturing, shortening, multi-kernel construction, etc. Finally, we investigate several RCPC-HARQ jointly design systems and discuss their encoding gain and re-transmission diversity gain.


menu
Abstract
Full text
Outline
About this article

Polar codes: Encoding/decoding and rate-compatible jointly design for HARQ system

Show Author's information Qiaoli Zeng1, Quan Zhou1, Xiangkun He2, Youming Sun1, Xiangcheng Li1, Haiqiang Chen1( )
School of Computer, Electronics and Information and Guangxi Colleges and Universities Key Laboratory of Multimedia Communications and Information Processing, Guangxi University, Nanning 530004, China
Department of Mechanical and Aerospace Engineering, Nanyang Technological University, Singapore 999002, Singapore

Abstract

Polar coding are the first class of provable capacity-achieving coding techniques for a wide range of channels. With an ideal recursive structure and many elegant mathematical properties, polar codes are inherently implemented with low complexity encoding and decoding algorithms. Since the block length of the original polar construction is limited to powers of two, rate-compatible polar codes (RCPC) are presented to meet the flexible length/rate transmission requirements in practice. The RCPC codes are well-conditioned to combine with the hybrid automatic repeat request (HARQ) system, providing high throughput efficiency and such RCPC-HAPQ scheme is commonly used in delay-insensitive communication system. This paper first gives a survey of both the classical and state-of-the-art encoding/decoding algorithms for polar codes. Then the RCPC construction methods are discussed, including the puncturing, shortening, multi-kernel construction, etc. Finally, we investigate several RCPC-HARQ jointly design systems and discuss their encoding gain and re-transmission diversity gain.

Keywords: polar code, rate compatible, hybrid automatic re-transmission request, polar coding/decoding

References(67)

1

R. G. Gallager, Low-density parity-check codes, IRE Transactions on Information Theory, vol. 8, no. 1, pp. 21–28, 1962.
DOI Google Scholar
2

P. Wang, L. Yin, and J. Lu, Efficient helicopter−satellite communication scheme based on check-hybrid LDPC coding, Tsinghua Science and Technology, vol. 23, no. 3, pp. 323–332, 2018.
DOI Google Scholar
3

B. Lin, Y. Pei, L. Yin, and J. Lu, Design and efficient hardware implementation shemes for non-quasi-cyclic LDPC codes, Tsinghua Science and Technology, vol. 22, no. 1, pp. 92–103, 2017.
DOI Google Scholar
4
C. Berrou, A. Glavieux, and P. Thitimajshima, Near Shannon limit error-correcting coding and decoding: Turbo-codes, in Proc. ICC’93-IEEE International Conference on Communications, Geneva, Switzerland, 1993, pp. 1064–1070.
5

E. Arikan, Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels, IEEE Transactions on Information Theory, vol. 55, no. 7, pp. 3051–3073, 2009.
DOI Google Scholar
6

E. Arikan, On the origin of polar coding, IEEE Journal on Selected Areas Communications, vol. 34, no. 2, pp. 209–223, 2016.
DOI Google Scholar
7

M. S. Pinsker, On the complexity of decoding, Probl. Peredachi Inf., vol. 1, no. 1, pp. 113–116, 1965.
Google Scholar
8

J. L. Massey, Capacity, cutoff rate, and coding for a direct-detection optical channel, IEEE Transaction Communications, vol. 29, no. 11, pp. 1615–1621, 1981.
DOI Google Scholar
9
I. Tal and A. Vardy, List decoding of polar codes, in Proc. 2011 IEEE International Symposium on Information Theory, St. Petersburg, Russia, 2011, pp. 1–5.https://doi.org/10.1109/ISIT.2011.6033904
DOI
10

B. Yuan and K. K. Parhi, Low-latency successive-cancellation list decoders for polar codes with multibit decision, IEEE Transactions on Very Largescale Integration(VLSI)Systems, vol. 23, no. 10, pp. 2268–2280, 2015.
DOI Google Scholar
11
J. Han, R. Liu, and R. Wang, Simplified multi-bit SC list decoding for polar codes, in Proc. 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Shanghai, China, 2016, pp. 996–1000.https://doi.org/10.1109/ICASSP.2016.7471825
DOI
12

K. Niu and K. Chen, Stack decoding of polar codes, Electronic Letters, vol. 48, no. 12, pp. 695–697, 2012.
DOI Google Scholar
13

K. Chen, K. Niu, and J. Lin, Improved successive cancellation decoding of polar codes, IEEE Transactions on Communications, vol. 61, no. 8, pp. 3100–3107, 2013.
DOI Google Scholar
14

J. Lin, C. Xiong, and Z. Yan, A high throughput list decoder architecture for polar codes, IEEE Transactions on Very Large Scale Integration(VLSI)Systems, vol. 24, no. 6, pp. 2378–2391, 2016.
DOI Google Scholar
15

C. Xiong, J. Lin, and Z. Yan, Symbol-decision successive cancellation list decoder for polar codes, IEEE Transactions on Signal Processing, vol. 64, no. 3, pp. 675–687, 2016.
DOI Google Scholar
16

A. Elkelesh, M. Ebada, S. Cammerer, and S. T. Brink, Belief propagation list decoding of polar codes, IEEE Communications Letters, vol. 22, no. 8, pp. 1536–1539, 2018.
DOI Google Scholar
17
A. Elkelesh, M. Ebada, S. Cammerer, and S. T. Brink, Belief propagation decoding of polar codes on permuted factor graphs, in Proc. 2018 IEEE Wireless Communications and Networking Conference (WCNC), Barcelona, Spain, 2018, pp. 1–6.https://doi.org/10.1109/WCNC.2018.8377158
DOI
18
S. Cammerer, B. Leible, M. Stahl, J. Hoydis, and S. T. Brink, Combining belief propagation and successive cancellation list decoding of polar codes on a GPU platform, in Proc. 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), New Orleans, LA, USA, 2017, pp. 3664–3668.https://doi.org/10.1109/ICASSP.2017.7952840
DOI
19
K. Chen, K. Niu, Z. He, and J. Lin, Polar coded HARQ scheme with chase combining, in Proc. 2014 IEEE Wireless Communications and Networking Conference (WCNC), Istanbul, Turkey, 2014, pp. 474–479.https://doi.org/10.1109/WCNC.2014.6952074
DOI
20

S. B. Korada, E. Şaşoğlu, and R. Urbanke, Polar codes: Characterization of exponent, bounds, and constructions, IEEE Transactions on Information Theory, vol. 56, no. 12, pp. 6253–6264, 2010.
DOI Google Scholar
21

N. Presman, O. Shapira, and S. Litsyn, Mixed-kernels constructions of polar codes, IEEE Journal on Selected Areas in Communications, vol. 34, no. 2, pp. 239–253, 2016.
DOI Google Scholar
22
K. Niu, K. Chen, and J. Lin, Beyond turbo codes: Rate-compatible punctured polar codes, in Proc. 2013 IEEE International Conference on Communications (ICC), Budapest, Hungary, 2013, pp. 3423–3427.https://doi.org/10.1109/ICC.2013.6655078
DOI
23
K. Niu, J. Dai, K. Chen, J. Lin, Q. T. Zhang, and A. V. Vasilakos, Rate-compatible punctured polar codes: Optimal construction based on polar spectra, https://arxiv.org/pdf/1612.01352, 2017.
24

B. Yuan and K. K. Parhi, Low-latency successive-cancellation polar decoder architectures using 2-bit decoding, IEEE Transactions on Circuits and Systems I:Regular Papers, vol. 61, no. 4, pp. 1241–1254, 2014.
DOI Google Scholar
25

C. Sun, Z. Fei, D. Jia, C. Cao, and X. Wang, Secure transmission scheme for parallel relay channels based on polar coding, Tsinghua Science and Technology, vol. 23, no. 3, pp. 357–365, 2018.
DOI Google Scholar
26
R. Mori and T. Tanaka, Non-binary polar codes using reed-solomon codes and algebraic geometry codes, presented at 2010 IEEE Information Theory Workshop, Dublin, Ireland, 2010.https://doi.org/10.1109/CIG.2010.5592755
DOI
27

N. Presman, O. Shapira, S. Litsyn, T. Etzion, and A. Vardy, Binary polarization kernels from code decompositions, IEEE Transactions on Information Theory, vol. 61, no. 5, pp. 2227–2239, 2015.
DOI Google Scholar
28

H. Lin, S. Lin, and K. A. S. Abdel-Ghaffar, Linear and nonlinear binary kernels of polar codes of small dimensions with maximum exponents, IEEE Transactions on Information Theory, vol. 61, no. 10, pp. 5253–5270, 2015.
DOI Google Scholar
29
H. Mahdavifar, M. El-Khamy, J. Lee, and I. Kang, On the construction and decoding of concatenated polar codes, in Proc. IEEE International Symposium on Information Theory, Istanbul, Turkey, 2013, pp. 952–956.https://doi.org/10.1109/ISIT.2013.6620367
DOI
30
A. Eslami and H. Pishro-Nik, A practical approach to polar codes, in Proc. 2011 IEEE International Symposium on Information Theory, St. Petersburg, Russia, 2011, pp. 16–20.https://doi.org/10.1109/ISIT.2011.6033837
DOI
31
S. M. Abbas, Y. Fan, J. Chen, and C. Y. Tsui, Concatenated LDPC-polar codes decoding through belief propagation, in Proc. 2017 IEEE International Symposium on Circuits and Systems (ISCAS), Baltimore, MD, USA, 2017, pp. 1–4.https://doi.org/10.1109/ISCAS.2017.8050835
DOI
32

J. Ha, J. Kim, and S. W. McLaughlin, Rate-compatible puncturing of low-density parity-check codes, IEEE Transactions on Information Theory, vol. 50, no. 11, pp. 2824–2836, 2004.
DOI Google Scholar
33

J. Ha, J. Kim, D. Klinc, and S. W. McLaughlin, Rate-compatible punctured low-density parity-check codes with short block lengths, IEEE Transactions on Information Theory, vol. 52, no. 2, pp. 728–738, 2006.
DOI Google Scholar
34

K. Niu and K. Chen, CRC-aided decoding of polar codes, IEEE Communications Letters, vol. 16, no. 10, pp. 1668–1671, 2012.
DOI Google Scholar
35
L. Zhang, Z. Zhang, X. Wang, Q. Yu, and Y. Chen, On the puncturing patterns for punctured polar codes, in Proc. 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA, 2014, pp. 121–125.https://doi.org/10.1109/ISIT.2014.6874807
DOI
36
J. Kim, J. -H. Kim, and S. Kim, An efficient search on puncturing patterns for short polar codes, in Proc. 2015 International Conference on Information and Communication Technology Convergence (ICTC), Jeju, Republic of Korea, 2015, pp. 182–184.https://doi.org/10.1109/ICTC.2015.7354523
DOI
37
M. Hanif and S. Vafi, An efficient puncturing method for the short and long length polar codes, in Proc. 2017 11th International Conference on Signal Processing and Communication Systems (ICSPCS), Surfers Paradise, Australia, 2017, pp. 1–5.https://doi.org/10.1109/ICSPCS.2017.8270452
DOI
38

L. Li, W. Song, and K. Niu, Optimal puncturing of polar codes with a fixed information set, IEEE Access, vol. 7, pp. 65965–65972, 2019.
DOI Google Scholar
39

J. Zhao, W. Zhang, and Y. Liu, A novel puncturing scheme of low rate polar codes based on fixed information set, IEEE Communications Letters, vol. 25, no. 7, pp. 2104–2108, 2021.
DOI Google Scholar
40
V. Bioglio, F. Gabry, and I. Land, Low-complexity puncturing and shortening of polar codes, presented at 2017 IEEE Wireless Communications and Networking Conference Workshops (WCNCW), San Francisco, CA, USA, 2017.https://doi.org/10.1109/WCNCW.2017.7919040
DOI
41

R. Wang and R. Liu, A novel puncturing scheme for polar codes, IEEE Communications Letters, vol. 18, no. 12, pp. 2081–2084, 2014.
DOI Google Scholar
42
W. Liu, Y. Wang, A. Li, P. Yu, and F. Zhou, An improved puncturing scheme for polar codes, in Proc. 2020 International Wireless Communications and Mobile Computing (IWCMC), Limassol, Cyprus, 2020, pp. 154–158.https://doi.org/10.1109/IWCMC48107.2020.9148522
DOI
43

V. Miloslavskaya, Shortened polar codes, IEEE Transactions on Information Theory, vol. 61, no. 9, pp. 4852–4865, 2015.
DOI Google Scholar
44

A. Alamdar-Yazdi and F. R. Kschischang, A simplified successive-cancellation decoder for polar codes, IEEE Communications Letters, vol. 15, no. 12, pp. 1378–1380, 2011.
DOI Google Scholar
45

M. Jeong and S. Hong, SC-Fano decoding of polar codes, IEEE Access, vol. 7, pp. 81682–81690, 2019.
DOI Google Scholar
46

I. Tal and A. Vardy, List decoding of polar codes, IEEE Transactions on Information Theory, vol. 61, no. 5, pp. 2213–2226, 2015.
DOI Google Scholar
47

K. Chen, K. Niu, and J. R. Lin, List successive cancellation decoding of polar codes, Electronics Letters, vol. 48, no. 9, pp. 500–501, 2012.
DOI Google Scholar
48
H. Zhou, C. Zhang, W. Song, S. Xu, and X. You, Segmented CRC-aided SC list polar decoding, presented at 2016 IEEE 83rd Vehicular Technology Conference (VTC Spring), Nanjing, China, 2016.https://doi.org/10.1109/VTCSpring.2016.7504469
DOI
49

C. Wang, Y. Pan, Y. Lin, and Y. Ueng, Post-processing for CRC-aided successive cancellation list decoding of polar codes, IEEE Communications Letters, vol. 24, no. 7, pp. 1395–1399, 2020.
DOI Google Scholar
50
O. Afisiadis, A. Balatsoukas-Stimming, and A. Burg, A low-complexity improved successive cancellation decoder for polar codes, in Proc. 2014 48th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, USA, 2014, pp. 2116–2120.https://doi.org/10.1109/ACSSC.2014.7094848
DOI
51
Z. Zhang, K. Qin, L. Zhang, H. Zhang, and G. Chen, Progressive bit-flipping decoding of polar codes over layered critical sets, presented at GLOBECOM 2017 - 2017 IEEE Global Communications Conference, Singapore, 2017.https://doi.org/10.1109/GLOCOM.2017.8254149
DOI
52
F. Ercan, C. Condo, S. A. Hashemi, and W. J. Gross, Partitioned successive-cancellation flip decoding of polar codes, presented at 2018 IEEE International Conference on Communications (ICC), Kansas City, MO, USA, 2018.https://doi.org/10.1109/ICC.2018.8422464
DOI
53

B. Dai, C. Gao, Z. Yan, and R. Liu, Parity check aided SC-flip decoding algorithms for polar codes, IEEE Transactions on Vehicular Technology, vol. 70, no. 10, pp. 10359–10368, 2021.
DOI Google Scholar
54
E. Arikan, Polar code: A pipelined implementation, presented at 4th International Symposium on Broadband Communication (ISBC 2010), Melaka, Malaysia, 2010.
55
N. Doan, S. A. Hashemi, M. Mondelli, and W. J. Gross, On the decoding of polar codes on permuted factor graphs, in Proc. 2018 IEEE Global Communications Conference (GLOBECOM), Abu Dhabi, United Arab Emirates, 2018, pp. 1–6.https://doi.org/10.1109/GLOCOM.2018.8647308
DOI
56

Y. Shen, W. Song, Y. Ren, H. Ji, X. You, and C. Zhang, Enhanced belief propagation decoder for 5G polar codes with bit-flipping, IEEE Transactions on Circuits and Systems II:Express Briefs, vol. 67, no. 5, pp. 901–905, 2020.
DOI Google Scholar
57

M. Zhang, Z. Li, and L. Xing, An enhanced belief propagation decoder for polar codes, IEEE Communications Letters, vol. 25, no. 10, pp. 3161–3165, 2021.
DOI Google Scholar
58

J. Hagenauer, Rate-compatible punctured convolutional codes (RCPC codes) and their applications, IEEE Transactions on Communications, vol. 36, no. 4, pp. 389–400, 1988.
DOI Google Scholar
59

K. Chen, K. Niu, and J. Lin, A hybrid ARQ scheme based on polar codes, IEEE Communications Letters, vol. 17, no. 10, pp. 1996–1999, 2013.
DOI Google Scholar
60

J. Gao, P. Fan, and L. Li, Optimized polarizing matrix extension based HARQ scheme for short packet transmission, IEEE Communications Letters, vol. 24, no. 5, pp. 951–955, 2020.
DOI Google Scholar
61
K. Mueadkhunthod, W. Phakphisut, L. M. M. Myint, and P. Supnithi, An early termination technique of polar codes for IR-HARQ scheme, in Proc. 2020 International Conference on Advanced Technologies for Communications (ATC), Nha Trang, Vietnam, 2020, pp. 193–198.https://doi.org/10.1109/ATC50776.2020.9255464
DOI
62

H. Saber and I. Marsland, An incremental redundancy hybrid ARQ scheme via puncturing and extending of polar codes, IEEE Transaction on Communications, vol. 63, no. 11, pp. 3964–3976, 2015.
DOI Google Scholar
63
L. Ma, J. Xiong, and Y. Wei, An incremental redundancy HARQ scheme for polar code, arXiv preprint arXiv: 1708.09679, 2017.
64
M. El-Khamy, H. Lin, J. Lee, H. Mahdavifar, and I. Kang, HARQ rate-compatible polar codes for wireless channels, in Proc. 2015 IEEE Global Communications Conference (GLOBECOM), San Diego, CA, USA, 2015, pp. 1–6.https://doi.org/10.1109/GLOCOM.2015.7417429
DOI
65
B. Li, D. Tse, K. Chen, and H. Shen, Capacity-achieving rateless polar codes, in Proc. 2016 IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain, 2016, pp. 46–50.https://doi.org/10.1109/ISIT.2016.7541258
DOI
66

M. Zhao, G. Zhang, C. Xu, H. Zhang, R. Li, and J. Wang, An adaptive IR-HARQ scheme for polar codes by polarizing matrix extension, IEEE Communications Letters, vol. 22, no. 7, pp. 1306–1309, 2018.
DOI Google Scholar
67

S. Hong and M. Jeong, An efficient construction of rate-compatible punctured polar (RCPP) codes using hierarchical puncturing, IEEE Transactions on Communications, vol. 66, no. 11, pp. 5041–5052, 2018.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 15 December 2021
Accepted: 18 January 2022
Published: 30 December 2021
Issue date: December 2021

Copyright

© All articles included in the journal are copyrighted to the ITU and TUP.

Acknowledgements

Acknowledgment

The authors are very grateful to the editor and reviewers for their comments and constructive suggestions, which help to enrich the content and improve the presentation of this paper. This work was supported by the National Nature Science Foundation of China (Nos. 61761006, 61961004, and 61762011) and the National Nature Science Foundation of Guangxi (Nos. 2017GXNSFAA198263 and 2018GXNSFAA294059).

Rights and permissions

This work is available under the CC BY-NC-ND 3.0 IGO license: https://creativecommons.org/licenses/by-nc-nd/3.0/igo/

Return