Scaling Factor Optimization of Turbo-Polar Iterative Decoding

Zhenzhen Liu＊, Kai Niu Jiaru Lin Jingyuan Sun, Hao Guan

1 Beijing University of Posts and Telecommunications, Beijing 100876, China

2 Nokia Shanghai Bell Co., Ltd., Beijing 100876, China

I. INTRODUCTION

TURBO-POLAR code [1-2] is a type of parallel concatenated scheme of the systematic polar code (SPC) [3]. The performance of bit error rate (BER) of this scheme is better than that of the classic SPC. As the component code of turbo-polar structure, SPC is a capacity-achieving code with low encoding and decoding complexity. There are many decoding algorithms proposed, such as successive cancellation (SC) decoding [4] and successive cancellation list (SCL) decoding [5-6], successive cancellation stack (SCS) [7]. But because of the hard decision output property of those algorithms, they cannot be applicable to the iterative decoding structure of the turbo-polar code.

On the contrary, two soft-in-soft-out (SISO)algorithms of SPC, belief propagation (BP)[8-9] and soft cancellation (SCAN) [10-11], can be applied to the iterative decoding structure of the turbo-polar code. Recently,the turbo-polar decoding based on BP algorithm was proposed in [1] and the weighted iterative structure was introduced. But there is no in-depth study of the weight coefficients optimization. Until now, several publications have discussed the issue of scaling factors(SFs) optimization of other codes [12-13].In [12], the SFs are optimized based on the mutual information between extrinsics for the low-density parity-check codes (LDPC). And as to turbo code, the optimization approach of SFs is relied on mathematical statistics [13].The effects of SFs are reflected on reducing the overestimated reliability values and the correlation between the intrinsic and extrinsic information.

Focusing on the above question and in the light of [13], we propose a novel algorithm of SFs optimization of turbo-polar structure with SCAN or BP algorithm. Firstly, in order to measure the gap between the practical decoder and the ideal one, a weighted mean square error (WMSE) criterion is put forward.Secondly, the genie-aided SCAN/BP decoding is proposed as the ideal decoder. The reason is that the decoding performance assisted by the genie information is attractive. Thereafter, the SFs optimization algorithm for the turbo-polar decoding structure is presented with the help of the optimization rule and genie-aided SCAN/BP decoding. The optimization idea is that the performance of turbo-polar code with the SFs aided SCAN/BP decoder is managed as close as possible to that with the genie-aided decoding. Finally, the optimal SFs are obtained by the proposed algorithm. Simulation results demonstrate the performance improvement of the turbo-polar code with the optimal SFs.

In this paper, a SFs optimization criterion is proposed for the weighted iterative decoding of turbo-polar code.

The paper is organized as follows. Section II reviews the encoding and decoding of turbo-polar code and some symbol descriptions of SCAN and BP algorithms. The optimization criterion and the corresponding algorithm of SFs for the turbo-polar code are proposed in Section III. In Section IV, numerical results are presented. Section V concludes this paper.

II. PRELIMINARIES

2.1 Encoding and decoding of turbo-polar code

Turbo-polar code with two component SPCs was proposed in [1]. SupposeNcdenotes the code length of component code,K-elements subset A ?{1,…,Nc}, Ac={1,… ,Nc} A ,and K={1,…,K}. A vector l=(l1,…,lK) is constituted by the elements in A sequentially. Assume u=(u1,…,uK) is an information sequence and v1=(…,v1,Nc) consists of v1,Aand v1,Ac, where the information set A is selected by the Gaussian Approximation method [14], then the codeword of the first SPC encoder is generated by

where GAdenotes the sub-matrix of GNcwith rows in A. In addition,represents them-th Kronecker product ofandNc=2m. v1,Acisfixed and known to the encoder and decoder. Due to the structure of systematic code, thus we have x1,A= u and x1,Acdenotes the check sequence.

Meanwhile the random interleaved information sequence is sent to the second SPC encoder and generates the second check sequence x2,Ac. After integrating the information sequence, the first and the second check sequences, the codeword of turbo-polar code is obtained and denoted by c=(c1,…,cN),where code lengthN=2Nc?Kand code rateR=. Assuming that it is modulated by the binary phase shift keying and is transmitted under the additive white Gaussian noise (AWGN) channel, the received signal y=(y1,…,yN) can be presented as

where n=(n1,…,nN) is the i.i.d. Gaussian random noise sequence and each noise sample obeysni～ N(0,σ2).

The decoding structure of turbo-polar code is shown in figure 1. The decoding processes are presented in the following.

(i) The received signal y is split into three parts y1,p, y2,pand ysby the de-multiplexer,where y1,pand y2,pdenote the received check sequence from thefirst and the second encoders respectively and ysrepresents the received information sequence.

(ii) For the SISO1 decoder at thet-th outer iteration, the received signal sequences y1,p,ysand the a priori information sequenceare fed into the decoder and the bit log-likelihood ratio (LLR) sequenceis generated after performing SCAN or BP decoding algorithm.

Then the extrinsic information sequenceof the SISO1 decoder is obtained by subtracting ysandthat is

whereis provided by the SISO2 decoder.

Since the extrinsic information sequenceof the SISO1 decoder may be overestimated, it is necessary to scale it by multiplying the SF α1,tin the iterative decoding to improve the overall system performance. Thus the modified prior information for the SISO2 decoder is written as

where π(k) denotes the interleaver mapping function. So all the SFs α1,tcompose a sequence α1.

(iii) The SISO2 decoder outputs the bit LLRswith the help of y2,p, ysand.Similar to the Eq. (3), the extrinsic information sequenceis obtained. After de-interleaving, denoted by π?1, the a prior information for the SISO1 decoder is scaled by the SF α2,tand presented as

where α2,tdenotes thet-th element of the SFs sequence α2.

(iv) The steps (ii) and (iii) continue until the given maximum outer iteration numberMis reached.

(v) According to the de-interleaved output bit LLRs, the decision is made.

2.2 Symbol description

In order to describe the SCAN decoding processes in our paper favorably, theBandLinformation [10] which denote the LLR information are introduced. Further, due to the requirement of algorithm description, the symbol (γ, φ,w) which denotes thewnode in the group φ at a depth γ of the factor graph is also borrowed. In addition,Lγ(φ,w) andBγ(φ,w) represent theLinformation andBinformation of the node (γ,φ,w), respectively. Moreover, Lγ(φ,w) and Bγ(φ,w) denote theLinformation andBinformation of the node (γ, φ,w) of the genie-aided SCAN decoding, respectively.

Fig. 1. Iterative decoding for the turbo-polar code.

At the ε-th iteration of BP decoding, two LLR expressions of the nodewof thehlayer of factor graph are borrowed from [9]. They are the left-to-right LLRand the rightto-left LLR. Those two LLRs in the genie-aided BP decoding are represented byandrespectively.

III. SCALING FACTORS OPTIMIZATION

This section contains three aspects. First, the SFs optimization rule for turbo-polar iterative decoding structure is presented. Second, the SFs optimization based on SCAN decoding is introduced. Finally, the SFs optimization of BP decoding is briefly described.

3.1 Scaling factors optimization rule

Recall that, by scaling the extrinsic LLR information, the performance of iterative decoding can be improved and approach to that of the ideal decoding.

As to the turbo-polar structure with the standard decoder and SFs, the LLR of thek-th information bit at thet-th iteration can be presented as,

whereukandys,kare thek-th element of u and ysrespectively. Anddenotes thek-th extrinsic information from thej-th SCAN/BP decoder (j=1,2) at thet-th outer iteration.

If an ideal decoder is utilized, the LLR of thek-th information bit at thet-th iteration can be written as,

We assume that both the SCAN/BP decoder and the ideal decoder can generate LLRs of the information bits in the iterative decoding process. To improve the performance of turbo-polar code with iterative decoder, we expect that the LLR distribution of the iterative decoder with SFs will be close to that of the ideal decoder as far as possible. In other words, the closer the LLR distribution between(u) and(u) is, the better thekkSF is.

According to the unbiased estimation of statistical theory, it can be known that the estimated value is always distributed near the true value randomly. Unfortunately, by observing the statistical results, it is found that there is a big difference between the mean square value of LLR of the practical decoder and the ideal decoder. Therefore, in order to realize unbiased estimation, the weighted fac-are introduced into MSE criterion to mitigate the difference of the LLR distribution between the practical decoder and the ideal one. This is given a new name, i.e., WMSE. And it is regarded as the performance criterion in this paper. Given the SF αj,tfor thej-th decoder and thet-th iteration, the WMSE of the corresponding LLR sequences is written as

where E[?] is the expectation in terms ofk.

For optimizing the SFs under the SCAN/BP decoding, it is needed to minimize the WMSE as much as possible. From the viewpoint of mathematics, in order to min-

Eq. (9) gives a formula to compute the SFs.Based on it, the optimization of SFs under specific decoding algorithms is presented in the following.

3.2 SFs optimization for SCAN decoding

In general, the genie-aided decoder can be used as the ideal decoder. Due to the assistance of genie, SCAN decoder can generate highly reliable LLR information to improve the system performance. Therefore, the genie aided decoding can be regarded as the optimization reference of the practical SCAN decoder.

The optimization procedure of SFs under SCAN decoding is presented in Algorithm 1.This algorithm mainly includes three parts: the computation of extrinsic information of the standard SCAN decoder, the computation of extrinsic information of the genie-aided SCAN decoder and the calculation of SFs.

As to the initialization ofBinformation of the standard SCAN decoder in the information set, there is no genie information to assist it.The source bits are set to 0 or 1 equiprobably.ThusBm(i, 0)=0,i∈A.

On the other hand, for the initialization of Bm(i, 0)=0,i∈ A , some preprocessing steps are shown in line 2 of Algorithm 1. Some detailed explanations will be shown below.

Firstly, the genie informationis obtained by the aid of SPC encoding [3] as,

where xj,A=(xj,i,i∈A) denotes the information bits and GAAis the submatrix of the matrix GNcwith elementsGi,b,i∈ A,b∈A. That isgj,k=vj,lk,k∈K, wherelkdenotes thek-th element of the information set A. Assume sign(x)=1 whenx≥0 holds, and otherwise sign(x)=?1. Then the genie information is utilized to adjust the sign of B information of source bits by sign( 2gj,k? 1).

Secondly, if the amplitude of B information is very large, there is no decoding error. But it is impractical to approach by the practical SCAN decoder. In order to make the reference decoder feasible, the absolute value of soft information of source bits of the standard SCAN decoding after one iteration is used as the basic amplitude ρj=(ρj,k,k∈K) of the reference decoder.It can be written by the specific expression as

Thirdly, a factorfis applied to further adjust the B information of source bits so that an ideal decoder is obtained which has good performance and can be approached by the practical decoder. Therefore, the obtained genie-aided SCAN decoder can be used as the practical optimization objective. Here, the factorfshould be carefully selected by a brute force search.

For both decoders, theLinformation of the coded bits is initialized by the channel observations.

After initializing theLinformation of the coded bits andBinformation of the source bits, the bit LLR informationis calculated by the SCAN decoding based iterative decoding as shown in figure 1. Moreover, the extrinsic informationis taken from it.

It is important to note that the obtained SF is participated in the following SF computation. Eq. (11) gives a good explanation about that. In order to compute SF α1,t, the obtainedSFs α1,i,i＜tand α2,i,i＜tare introduced into the calculation of extrinsic information.As to the computation of SF α2,t, not only the SFs α1,i,i＜tand α2,i,i＜tof the former iter-ation, but also the SF α1,tare considered into the calculation of.

Algorithm 1. SFs optimization for SCAN decoding.

In addition, after initialization, update and output, the extrinsic informationof the genie-aided SCAN decoder is obtained by Eq. (13). Due to the iterative structure of the genie-aided SCAN decoder, the initialization effect of Bm(lk,0),k∈ K will extend to the entire decoding process.

When the number of simulation frames reaches the predefined Γ, the cross correlative functionand the autocorrelation functionare replaced by the statisti-cal average value of the samples. The optimal SFs are obtained by plugging those statistical values into SFs optimization Eq. (9).

Table I. Scaling factors for turbo-polar code with SCAN/BP decoding.

The computation complexity of Algorithm 1 is also given in this subsection. It can be calculated by the following analysis. 1) The complexity for the preparation of prior information isO(3NclogNc). 2) The computation complexity of line 9-line 17 isO(2NclogNc).Further, two for loop and one while loop is implemented on line 9-line 17. Thereafter,the complexity isO(4MΓNclogNc). 3)Integrate the above complexity in 1) and 2),the complexity of the Algorithm 1 is aboutO((4MΓ+ 3)NclogNc).

3.3 SFs optimization for BP decoding

The processes of Algorithm 1 can also be applied to the SFs optimization of BP decoding by replacing the operations related to SCAN decoding with those of BP decoding. It should be noted that BP decoding includes the inner iteration other than the outer iteration between two component decoders. As an upgraded version of BP decoding, the genie-aided BP decoding is considered as the ideal decoder.

Like the initialization process of Bm(lk,0),then,k∈ K of source bits can be initialized using the similar approach. During the decoding process of the genie-aided BP and the standard BP, the update rules in [9] are followed. Assume the maximum BP inner iteration number is Θ, then the bit LLR information of the transmitted bits of the genie-aided BP decoding is obtained by+,k∈ K.Further, the extrinsic LLR informationis extracted. As to the extrinsic information calculation of the BP decoder,=0,i∈A is allocated. After initializing and updating, the extrinsic informationof BP decoder is output. Simulation needs to be done many times in order to obtain the statistic characteristics ofand. Finally, the optimal SFs of BP decoder are calculated with Eq. (9).

IV. NUMERICAL RESULTS

In this section, the improvement of SFs to the error performance of turbo-polar code is shown. The code length and code rate of the component codes are denoted byNcandRc,respectively. Two code configurations are set to the constituent codes of turbo-polar code. That is,C1andC2denote {Nc= 128,Rc=1/2}and {Nc= 256,Rc=2/3}, respectively. And AWGN channel is the simulation channel.

For some given signal noise ratio (SNR)values, the optimal SFs under each outer iteration for the component codesC1of turbo-polar code with SCAN or BP decoding are calculated and listed in Table I. Those SFs are calculated by Eq. (9). As to afixed SNR,the SF increases with the number of outer iteration. The reason is that the exchanged extrinsic information is more accurate along with the increase of iteration number. In addition, the SF becomes large with the increase of SNR. This is due to the improved system performance. The empirical value offfor the genie-aided SCAN and BP is 4 and 12, respectively. The total simulation frame number Γ for turbo-polar code is 106.

The BER performance of turbo-polar code by SCAN decoder with different SFs are exhibited in figure 2(a), where the constituent codes areC1andC2, and they are marked with solid line and dotted line respectively.The diamond and square denote the SFs set to all 1s (standard SCAN decoding) and the optimal values (refer to Table I(a)), respectively.In addition, the outer iteration numberMis 6. For the turbo-polar code with component codesC1, it can be observed that there is about 0.3 dB gain obtained by introducing the optimal SFs at BER 10?4. Meanwhile, the performance curve of turbo-polar code with the fixed scaling factor 0.75 is also given. Compared with it, the case with the SFs obtained by the proposed method has some gains. However, the selection of fixed coefficient 0.75 is experimental. As to the determination of SFs,we provide the theoretical support.

Fig. 2. Performance comparison of turbo-polar code with different SFs.

In order to facilitate comparison, the simulation parameter is configured as [1]. That is, the component codes areC1, BP decoder is the component decoder with the maximum inner iteration number Θ=60, the outer iteration numberMis 3 and the SNR interval is set to 3.8～4.8 dB. From the simulation results offigure 2(b), it can be observed that the performance with the optimal SFs (refer to Table I(b)) has 0.7 dB gain compared to that with SFs all 1s at BER 10?4. Further, the performance of turbo-polar code with the SFs obtained by our method is better than that given in [1].

Besides, the optimum SFs for SCAN decoding and BP decoding can be calculated off line. Thus the decoding complexity with the addition of SFs is the same as that without SFs except the complexity brought by the multiplication operation of SFs. Taken the performance and complexity consideration together,it can make a conclusion that the decoding performance is improved at a little cost of complexity.

V. CONCLUSIONS

In this paper, a SFs optimization criterion is proposed for the weighted iterative decoding of turbo-polar code. And a genie-aided based SFs optimization algorithm for SCAN/BP decoding is presented. Compared with the standard iterative decoding, the case with the optimal SFs will achieve better performance.

In the future, we will further focus on the choice of target reference decoding algorithm.In addition, other scaling factor optimization approaches may be considered.

ACKNOWLEDGEMENTS

This work was supported by the National Natural Science Foundation of China (No.61671080), the National Natural Science Foundation of China (No. 61771066) and Nokia Beijing Bell Lab.

[1] D. Wu, A. Liu, Y. Zhang, et al., “Parallel concatenated systematic polar codes,”IET Elec. Letters,vol. 52, no. 1, 2016, pp. 43-45.

[2] Q. Zhang, A. Liu, Y. Zhang, et al., “Practical design and decoding of parallel concatenated structure for systematic polar codes,”IEEE Trans.Commun., vol. 64, no. 2, 2016, pp. 456-466.

[3] E. Arikan, “Systematic polar coding,”IEEE Commun. Lett., vol. 15, no. 8, 2011, pp. 860-862.

[4] E. Arikan, “Channel Polarization: A method for constructing capacity achieving codes for symmetric binary-input memoryless channels,”IEEE Trans. Inf.Theory, vol. 55, no. 7, 2009, pp. 3051-3073.

[5] I. Tal, A. Vardy, “List decoding of polar codes,”Proc. IEEE Int. Symp. Inform. Theory (ISIT), 2011,pp. 1-5.

[6] K. Chen, K. Niu, J. Lin, “Improved Successive Cancellation Decoding of Polar Codes,”IEEE Trans.Commun., vol. 61, no.8, 2013, pp. 3100-3107.

[7] K. Chen, K. Niu, “Stack Decoding of Polar Codes,”Electron. Lett., vol. 48, no. 12, 2012, pp.695-696.

[8] E. Arikan, “A performance comparison of polar codes and reed-muller codes,”IEEE Commun.Lett., vol. 12, no. 6, 2008, pp. 447-449.

[9] B. Yuan, K. Parhi, “Early stopping criteria for energy-efficient low latency belief-propagation polar code decoders,”IEEE Transactions on Signal Processing, vol. 62, no. 24, 2014, pp. 6496-6506.

[10] U. Fayyaz and J. Barry, “Low-complexity soft-output decoding of polar codes,”IEEE Sel.Com., vol. 32, no. 5, 2014, pp. 958-966.

[11] U. Fayyaz and J. Barry, “A low-complexity soft-output decoder for polar codes,”Proc. IEEE Global Communications Conference (GLOBECOM), 2013, pp. 2692-2697.

[12] F. Alberge, “Min-sum decoding of irregular LDPC codes with adaptive scaling based on mutual information,”Proc. IEEE International Symposium on Turbo Codes and Iterative Information Processing, 2016, pp. 71-75.

[13] D. Yue, H. Nguyen, “Unified scaling factor approach for turbo decoding algorithms,”IET Com., vol. 4, no. 8, 2010, pp. 905-914.

[14] P. Trifonov, “Efficient Design and Decoding of Polar Codes,”IEEE Trans. Commun., vol. 60, no.11, 2012, pp. 3221-3227.

[15] G. Roussas, “A course in mathematical statistics,”Academic Press, 1997.