A simplified decoding algorithm for multi-CRC polar codes

YANG Haifen,YAN Suxin,ZHANG Hao,REN Yan,HU Xiangdong, and LIN Shuisheng

School of Information and Communication Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China

Abstract: Polar codes represent one of the major breakthroughs in 5G standard, and have been proven to be able to achieve the symmetric capacity of binary-input discrete memoryless channels using the successive cancellation list (SCL) decoding algorithm.However,the SCL algorithm suffers from a large amount of memory overhead.This paper proposes an adaptive simplified decoding algorithm for multiple cyclic redundancy check(CRC)polar codes.Simulation results show that the proposed method can reduce the decoding complexity and memory space. It can also acquire the performance gain in the low signal to noise ratio region.

Keywords: polar code, successive cancellation list (SCL), cyclic redundancy check(CRC),adaptive decoding.

1.Introduction

Polar codes have attracted widespread attention since it was first introduced by Arikan[1,2].Its encoding and decoding complexity areO(NlogN)andNis the length of polar codes.In 2016,polar codes have been selected as the channel coding scheme of control channel in 5G[3].How to further improve the decoding performance and reduce complexity to satisfy the low delay and high reliable communication scenario has become the focus issue.

On the code design, construction methods of the polar codes for the additional white Gaussian noise(AWGN)and Rayleigh fading channel based on the Gaussian approximation algorithm were investigated in [4] and [5]. Zhao et al. [6] proposed a puncturing method based on the decoding reliability.To improve the error floor performance of parallel concatenated systematic polar codes, a threedimensional code scheme was given[7].In[8],a low complexity coding scheme was proposed called asymmetric polar coding that allows for any arbitrary block length.Details on the generator matrix and frozen set design,etc.,for flexible polar code lengths were shown in [9]. The corresponding distance properties and convergence analysis were given in[10,11].

The successive cancellation (SC) algorithm is widely used in polar decoding[12,13].Permutation decoding was proposed in [14] with the latency of SC decoders. However, the SC algorithm is not ideal for moderate code length.In[15],it incorporated the Fano sequential decoding into the standard SC decoding to address the inherent drawback of SC decoding, e.g., one wrong-decision will surely lead to a wrong codeword. After that, some kinds of decoding algorithms were provided, such as the belief propagation(BP)polar decoder[16–19].However,the existing stochastic BP decoders suffer from a relatively long decoding latency,resulting in low hardware efficiency. Meanwhile, sphere-decoding tree searches [20–22] and other fast decoding algorithms[23,24]were proposed, respectively. Deep learning was applied to decoding a polar code with respect to numerous configurations:the number of hidden layers,the number of nodes for each layer,and activation functions[25].A successive cancellation list (SCL) decoder was presented in [26,27], whereLis the size of the list. Empirically, the use of several decoding paths yields an error probability comparable to that under the optimal maximum a posteriori (MAP) decoding with practical values of the list size.In addition,by adding only a few extra bits of cyclic redundancy check(CRC) precoding, the resulting performance is comparable with state of the art low-density parity-check(LDPC)codes[28].

SCL decoding can significantly improve the error correction performance of polar codes. However, it needs to keepLbest candidate paths at the same time, and this comes at the cost of a lower throughput and higher area occupation when implemented in the hardware,which greatly increases the amount of computation.In particular,the high area requirement of SCL decoding is mostly dominated by its memory usage. Several techniques were proposed to speed up the SCL decoder in[29–32].However,the performance gains and the complexity cannot be simultaneously guaranteed.

CRC-aided decoding schemes were proposed to improve the performance of polar codes[33–37].The unified description of SC decoding and its improved version with list or stack were provided and the CRC-aided SCL/stack decoding schemes were proposed.Simulation results in the binary-input AWGN channel show that the SC decoding algorithm can provide significant gain of 0.5 dB over the turbo codes.Moreover,the time complexity of its decoder is much lower than that of the turbo decoder and can be close to that of the SC decoder in the high signal to noise ratio(SNR)region.

This paper proposes a multi-CRC aided adaptive simplified SCL(multi-CRC AD-SSCL)polar decoding scheme.Different from the existing multi-CRC aided SCL algorithms, a new partitioning principle is proposed based on the simplified SCL algorithm in this paper. The redundant computation in the proposed algorithm is removed by defining simplified nodes, which reduces the complexity.Compared with the conventional CRC polar scheme,the proposed algorithm divides the information sequence into multiple sub-sequences and then each sub-sequence is checked by a CRC. Furthermore, in order to ensure the decoding performance, the proposed algorithm adaptively adjusts the size of the listLuntil at least one path from sub-sequence can pass CRC.Different from the conventional algorithm which adjusts the list value and redecoding after the overall decoding is completed,the average list value required for the proposed algorithm will be effectively reduced especially at a low SNR. Theoretical analysis and simulation show that the proposed decoding algorithm can significantly reduce the computational complexity and memory overhead.In addition,it can acquire a certain performance gain in the low SNR region.

The rest of this paper is organized as follows.The coding and decoding of polar codes is given in Section 2.Section 3 introduces a construction of polar codes and gives the corresponding decoding algorithm.Simulation results are given and analyzed in Section 4.Finally,Section 5 concludes the entire paper.

2.Preliminaries

Polar codes can achieve the symmetric capacity of the binary-input discrete memoryless channel (B-DMC)through channel polarization, which consists of channel combining and channel splitting. We can construct a polar code(the lengthN=2n)as the following:

whereGNis the generation matrix of the orderN,BNis a bit-reversal permutation matrix,andF⊗nis thenth K ronecker product ofF= [1 0 ; 1 1].andare the encoded and information vectors,respectively.According to the channel polarization theory,can be divided into two subsetsuAanduAc.uA ∈XKis information bits,anduAc ∈XN-Kis frozen bits.

Supposing there is the received vector, the SC decoding algorithm generates its decisionby computing(2).

whereauirepresents the logarithmic likelihood ratio(LLR)ofui:

SC decoding can be represented as a binary treeTntraversing, which starts from the root node and advances recursively from left to right as shown in Fig.1(a).During the traversal process,SC involves two kinds of messages.Taking the nodevat the stagesas an example,one is soft information(LLR)that isav=[a1,...,a2s]and the other is hard decision estimatesβv= [β1,...,β2s]. The message passing process of the nodevis shown in Fig. 1(b),whereavlandavrcan be approximated as in (4) and (5)for 1 ≤i≤2s-1.

whereβvcan be calculated by

Fig.1 Binary tree Tn and message passing in binary tree

For a leaf nodeu,βvis the hard decision.The computational complexity of the SC algorithm isO(NlogN).Fig. 2 gives the bit error rate (BER) and frame error rate (FER) performance comparison with different code lengths at the code rate 0.5.It can be seen that the code with a longer length can bring more performance gains with the SNR increasing, while in the low SNR region the difference is ignorable.

Fig.2 BER and FER performance comparison with different code length N

3.Multi-CRC simplified decoding scheme

Fig. 3 shows the encoding structure of the multi-CRC.It divides the information sequenceSinto multiple subsequencesSiand each sub-sequence is checked by a short CRCri. Thus, compared with the conventional CRC polar encoding,multi-CRC requires a precoding module.In addition, segmenting in Fig. 3 should be carried out according to the segmentation principle as follows.

Fig.3 Encoding structure of multi-CRC

Segmentation principleWe define three special nodes in the binary treeTnto reduce complexity: rate-0 nodes(with no information bits), rate-1 nodes (with no frozen bits), rep nodes (with one information bit in rightmost leaf).The structure of a special node cannot be destroyed in the segmenting process. If the nodevat the stagesis a special node, then the length of the sub-information vectorUicorresponding to the nodevshould satisfy min length(Ui) = 2s. This segmentation principle can reduce the calculation of LLR at least 2stimes for the subinformation vectorUiduring the decoding process.

ProofThe length of the sub-information sequence length(Ui)<2sindicates that the special node is destroyed. The special node will degenerate to the ordinary node as shown in Fig.4.The circle represents the common node and the triangle represents the special node. From Fig. 4, the nodevthat degenerates into an ordinary node needs to respectively pass LLR messagesavlandavrto their sub-nodesvlandvr.Sinceavlandavrare 1×2s-1vectors,compared with the nodevbased on the segmentation principle,the degenerated nodevneeds to compute 2smore LLR values.Similarly,if the sub-nodevlorvrof the special nodevis destroyed,the sub-nodevlorvrneeds to calculate 2s-1more LLR values. □

Fig. 4 Schematic diagram of special nodes destroyed during segmentation

The decoding process is shown in Algorithm 1. Generally,the path metric(PM)[31]can be computed as

Aimed at the special nodev,we can calculate the PM as follows.

Rate-0 nodes:

Rate-1 nodes:

Rep nodes:

whereis the path index andis the estimate of bitjat path.

Algorithm 1Multi-CRC AD-SSCL decoding algorithm.

1 Initiation decoder:L=1

2Fori=1,2,...,M

//aimed at every input sub-information sequenceUi

3forj=1,2,...,Ni

//aimed at every bitjof sub-information sequenceUi

4 SSCL decoding via traverse the corresponding part of

5if0//s=stage(v)

6ifvis special node:

7 calculate the PM by(8),(9)and(10),j=j+2s,return to 3

8else

9 traverse the next corresponding nodev,return to 4

10end if

11else//s=0 that isv=uj

12 calculate the PM referring to (7), letj=j+1,return to 3

13end if14ifj=Ki

15 perform CRC detection to the current sub information biti,select and save one path by:

16Case 1Save the path which fulfills CRC and has the lowest PM,letL=L

17Case 2If no paths pass CRC:

18if2L≤Lmax//recalculateUi

19 letL=2L,i=i,return to 2

20else ifL==Lmax//calculateUi+1

21 save the path that has the lowest PM, letL=Lmax,i=i+1,return to 2

22else//recalculateUi

23 letL=Lmax,i=i,return to 2

24end if

25end if

26end for

27end for

4.Simulation and results

In this section, we compare the performance of the proposed algorithm and the conventional CRC aided adaptive SCL.The simulation is based on binary phase shift keying(BPSK)modulation and the AWGN channel.The information indexAadopts the 3rd generation partnership project(3GPP)standard in[3]andLmaxis set to 16 in simulation.

Firstly,the FER performance comparison of the conventional CRC and the three multi-CRC schemes are shown in Fig.5.The generator polynomials of CRC are

Fig.5 FER of multi-CRC vs.conventional CRC

It is shown in Fig. 5 that compared with the traditional algorithm, the three schemes can achieve certain performance gains at a low SNR. This is because the proposed algorithm uses the idea of segment decoding.The decoder can remove the paths which cannot timely pass the CRC from the path list to make the branches of the paths which can pass the CRC preserved as more as possible.Besides,the proposed algorithm adaptively adjusts the value of the listLfor SNR to improve the performance.

Fig. 6 gives the complexity of the multi-CRC simplified SCL and the conventional algorithm.The complexity of the SCL class mainly depends on the calculation units of LLR which is also called processing elements(PE).The PE computation of the proposed algorithm and the conventional algorithm can be calculated by (11)–(13). It is shown in Fig. 6 that the multi-CRC simplified SCL algorithm can efficiently reduce the complexity compared with the conventional algorithm. For example, the three methods of the proposed algorithm are only 32.8%,32.9%and 39.2%of the conventional algorithm at 2 dB,respectively.

where PEirepresents the PE size of theith subinformation vector in (11).denotes the sum of all the lists that have been used in decoding the sub-information vector. In addition, PEsave(i)denotes to save PE size of theith sub-information vector by simplified SCL decoding.

whereL′= 1+2···+Lmeans the sum of all the lists that have been used.

Fig. 6 Complexity of multi-CRC simplified SCL vs. conventional CRC

Furthermore,we calculate the memory overhead of two algorithms according to(14)and(15)respectively.

whereLirepresents the final list size of theith decoding sub-information vector in(14).Kimeans the length of the sub-sequenceCi.

whereLrepresents the final list size of the conventional algorithm.

From Fig. 7 we see that the conventional algorithm needsMconventionmemory cells to save the survival paths,while the proposed algorithms use memory multiplexing to reduce memory cells.For example,the three methods of the proposed algorithm are only 77.3%,75.7%and 74.1%of the conventional algorithm at 1 dB,respectively.

Fig.7 Memory space of multi-CRC simplified SCL vs.conventional CRC

In order to analyze the complexity of the proposed algorithm under different code lengths and code rates,Table 1 gives detailed numerical results. It can be seen that under all the situations, the proposed algorithm can reduce the decoding complexity.

Table 1 PE comparison for different code parameters

5.Conclusions

In this paper,we propose a multi-CRC simplified SCL polar decoding scheme which can reduce the computational complexity and memory cells in the decoding. The construction of polar codes based multi-CRC is given. The simulation results show that compared with conventional methods,the proposed methods can not only significantly reduce the computational complexity but also acquire a certain performance in the low SNR.