AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
PDF (1.2 MB)
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

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

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
Show Author Information

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.

References

1

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

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.

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.

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.

6

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

7

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

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.

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
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.

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
12

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

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.

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.

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.

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.

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
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
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
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.

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.

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
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.

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.

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
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.

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.

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
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
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
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.

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.

34

K. Niu and K. Chen, CRC-aided decoding of polar codes, IEEE Communications Letters, vol. 16, no. 10, pp. 1668–1671, 2012.

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
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
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
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.

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.

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
41

R. Wang and R. Liu, A novel puncturing scheme for polar codes, IEEE Communications Letters, vol. 18, no. 12, pp. 2081–2084, 2014.

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
43

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

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.

45

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

46

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

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.

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
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.

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
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
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
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.

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
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.

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.

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.

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.

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.

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
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.

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
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
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.

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.

Intelligent and Converged Networks
Pages 334-346
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

1274

Views

978

Downloads

4

Crossref

3

Scopus

Altmetrics

Received: 15 December 2021
Accepted: 18 January 2022
Published: 30 December 2021
© All articles included in the journal are copyrighted to the ITU and TUP.

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