# Adding a Rate-1 Third Dimension to Parallel Concatenated Systematic Polar Code: 3D Polar Code

Authors: Zhenzhen Liu; Kai Niu; Chao Dong; Jiaru Lin
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

In this paper, a three-dimensional polar code (3D-PC) scheme is proposed to improve the error floor performance of parallel concatenated systematic polar code (PCSPC). The proposed 3D-PC is constructed by serially concatenating the PCSPC with a rate-1 third dimension, where only a fractionλ of parity bits of PCSPC are extracted to participate in the subsequent encoding. It takes full advantage of the characteristics of parallel concatenation and serial concatenation. In addition, the convergence behavior of 3D-PC is analyzed by the extrinsic information transfer (EXIT) chart. The convergence loss between PCSPC λ=0 and different λ provides the reference for choosing the value of λ for 3D-PC. Finally, the simulation results confirm that the proposed 3D-PC scheme lowers the error floor.


---

## Body

## 1. Introduction

The novel concept of parallel concatenated systematic polar code (PCSPC) was first put forward in [1]. PCSPC scheme consists of two systematic polar codes (SPCs) [2]. It has performance advantage with respect to original SPC. In [3], the extrinsic information transfer (EXIT) charts of different length SPC have been given. As a promotion of the above EXIT chart results, the convergence behavior of PCSPC can be analyzed. It can be observed that SPC with larger code length leads to narrower opening. Therefore, it is difficult for PCSPC with large code length SPCs to converge at low error rate. The motivation of our work is to solve this problem.As we know, there is error floor for turbo code (TC) at block error rate (BLER) around10-5 [4]. In order to improve the performance of TC in the error floor region, three-dimensional turbo code (3D-TC) has been studied in [5–7]. 3D-TC scheme was proposed by serially concatenating a rate-1 cyclic recursive systematic convolutional (CRSC) code to conventional TC. It is important to note that only a fraction λ of parity bits from TC are extracted to participate in the encoding again. Compared with conventional TC, 3D-TC scheme has larger minimum distance. Therefore, 3D-TC improves the error floor performance greatly. In addition, the influence of λ of 3D-TC on convergence threshold and minimum distance has been researched in [6, 7].It is known from the literature that serial concatenated code has larger minimum distance with respect to parallel concatenated code; however, its convergence threshold is worse than that of parallel concatenation [8]. Meanwhile, inspired by the idea in [7], 3D polar code (3D-PC) scheme is proposed to improve the error floor performance of PCSPC in this paper. It makes full use of the features of parallel concatenation and serial concatenation. 3D-PC is constituted by adding a rate-1 CRSC code to PCSPC. And only a fraction λ of parity bits of PCSPC are sent to the third encoder. Moreover, the convergence behavior of 3D-PC is analyzed by EXIT chart method [9]. It can be utilized to guide the choice of λ which is an important parameter that affects the performance of 3D-PC. Simulation results corroborate the effectiveness of 3D-PC scheme to improve the low error rate performance.The paper is organized as follows. Section2 reviews systematic polar code and EXIT chart. 3D-PC scheme is proposed in Section 3. In Section 4, convergence analysis of 3D-PC is presented. The simulation results are shown in Section 5. Section 6 concludes this paper.


## 2. Preliminaries

### 2.1. Systematic Polar Code

Polar code is a capacity-achieving channel code which was proposed by Arıkan in [10]. Given code length N and code rate R=K/N, the reliabilities of N subchannels can be obtained by Gaussian approximation method [11] or other construction algorithms. Then the K subchannels with high reliability are used to transmit information bits, and other N-K subchannels are utilized to deliver frozen bits. Let set A⊂1,…,N denote the indexes of those K high reliability subchannels. Supposing that the input sequence v=v1,…,vN is given, the codeword x of polar code can be obtained by(1)x=vGN=vBNF2⊗n,where GN is the generator matrix, BN denotes the bit-reversal permutation matrix, ⊗n denotes the n-th Kronecker product, and F2=1011.Since the input source sequencev can be decomposed into two parts vA and vAc, the codeword x in (1) can be written as(2)x=vGN=vAGA+vAcGAc,where vA⊂v is the information bits, Ac=1,…,N\A denotes the complement of A, and GA consists of the rows of GN with indices in A.Systematic polar code is constructed based on polar code [2]. Assume that K-elements set B denotes the indexes of system bits; then xB denotes system bits and xBc is the check bits. Equation (2) can be rewritten as(3)xB=vAGAB+vAcGAcB,(4)xBc=vAGABc+vAcGAcBc,where GAB denotes the submatrix of GN with row indexes in A and column indexes belonging to B.As to SPC, the systematic bitsxB are known and vAc are also known and set to zero; thus vA can be calculated according to (3):(5)vA=xB-vAcGAcBGAB-1=xBGAB-1.Further, the check bitsxBc can be computed by (4):(6)xBc=xBGAB-1GABc.Here, the codewordx of SPC is achieved.


### 2.2. EXIT Chart

EXIT chart [9] is an efficient convergence analysis tool for the iterative decoding structure. It tracks the average mutual information of constituent decoders.We useX and A to denote the transmitted bits and the corresponding a priori information, respectively. And A is modeled as an independent Gaussian random variable with the following expression:(7)A=μAx+nAwith(8)uA=σA22,where nA is a Gaussian random variable with mean zero and variance σA2. Under the above assumption, the mutual information between transmitted bits X and a priori information A can be written as(9)IA=IX;A=1-∫-∞+∞12πσAe-ξ-σA222/2σA2log21+e-ξdξ.Assume that extrinsic information is denoted byE. The mutual information between X and E is calculated as(10)IE=IX;E=12·∑x=-1,1∫-∞+∞pEξ∣X=x×log22·pEξ∣X=xpEξ∣X=-1+pEξ∣X=+1dξ,where pEξ∣X=x is the probability distribution function given condition X=x. It can be obtained by Monte Carlo simulation.


## 2.1. Systematic Polar Code

Polar code is a capacity-achieving channel code which was proposed by Arıkan in [10]. Given code length N and code rate R=K/N, the reliabilities of N subchannels can be obtained by Gaussian approximation method [11] or other construction algorithms. Then the K subchannels with high reliability are used to transmit information bits, and other N-K subchannels are utilized to deliver frozen bits. Let set A⊂1,…,N denote the indexes of those K high reliability subchannels. Supposing that the input sequence v=v1,…,vN is given, the codeword x of polar code can be obtained by(1)x=vGN=vBNF2⊗n,where GN is the generator matrix, BN denotes the bit-reversal permutation matrix, ⊗n denotes the n-th Kronecker product, and F2=1011.Since the input source sequencev can be decomposed into two parts vA and vAc, the codeword x in (1) can be written as(2)x=vGN=vAGA+vAcGAc,where vA⊂v is the information bits, Ac=1,…,N\A denotes the complement of A, and GA consists of the rows of GN with indices in A.Systematic polar code is constructed based on polar code [2]. Assume that K-elements set B denotes the indexes of system bits; then xB denotes system bits and xBc is the check bits. Equation (2) can be rewritten as(3)xB=vAGAB+vAcGAcB,(4)xBc=vAGABc+vAcGAcBc,where GAB denotes the submatrix of GN with row indexes in A and column indexes belonging to B.As to SPC, the systematic bitsxB are known and vAc are also known and set to zero; thus vA can be calculated according to (3):(5)vA=xB-vAcGAcBGAB-1=xBGAB-1.Further, the check bitsxBc can be computed by (4):(6)xBc=xBGAB-1GABc.Here, the codewordx of SPC is achieved.


## 2.2. EXIT Chart

EXIT chart [9] is an efficient convergence analysis tool for the iterative decoding structure. It tracks the average mutual information of constituent decoders.We useX and A to denote the transmitted bits and the corresponding a priori information, respectively. And A is modeled as an independent Gaussian random variable with the following expression:(7)A=μAx+nAwith(8)uA=σA22,where nA is a Gaussian random variable with mean zero and variance σA2. Under the above assumption, the mutual information between transmitted bits X and a priori information A can be written as(9)IA=IX;A=1-∫-∞+∞12πσAe-ξ-σA222/2σA2log21+e-ξdξ.Assume that extrinsic information is denoted byE. The mutual information between X and E is calculated as(10)IE=IX;E=12·∑x=-1,1∫-∞+∞pEξ∣X=x×log22·pEξ∣X=xpEξ∣X=-1+pEξ∣X=+1dξ,where pEξ∣X=x is the probability distribution function given condition X=x. It can be obtained by Monte Carlo simulation.


## 3. Proposed 3D Polar Code Scheme

### 3.1. Encoding Structure

In short, 3D-PC scheme can be regarded as a concatenation of the inner code and outer code, PCSPC. The encoding structure of 3D-PC is illustrated in Figure1. First of all, the input information sequence u with length K is encoded by parallel concatenated systematic polar encoder. The component encoders of PCSPC are written as Ca and Cb, respectively. Both of them are systematic polar encoders. We use xa and xb to denote the parity bits sequence of Ca and Cb, respectively. Further, the codeword xPC can be obtained by taking the bits from xa and xb alternatively. The fraction λ of xPC is interleaved by the interleaver Πc and sent to the postencoder Cc for encoding, where λ is named as permeability rate. And codeword xc is output by the postencoder Cc. The parity bits chosen for encoding follow a certain puncturing pattern p with length 2/λ. The fraction 1-λ of xPC is passed to the channel straightly, denoted by xch. The patterns p¯ and p are complementary. Furthermore, the last codeword x of 3D-PC with code length NT is obtained by combining the input sequence u, the parity sequence xch, and the parity sequence xc. Here the code rate of 3D-PC is calculated by R=K/NT=1/3. In order to achieve higher code rate, it is need to puncture some parity bits from xch or xc. Since xc contains more information, xch is first taken into consideration.Figure 1
3D polar encoder.For complexity and performance reasons, the selectedCc encoder should meet some requirements: its decoder is as simple as possible, its decoder inputs soft information and outputs soft information, and its decoder should not introduce too much error [5]. As a result, a rate-1 cyclic recursive systematic convolutional encoder with generator polynomial g(D)=1/1+D2 is selected as the encoder Cc [6].In literature [5, 6], the interleavers Π and Πc have been well designed to increase the minimum distance. Because the design of interleaver has a great influence on the performance of TC. While the effect of interleaver on polar code is not so obvious, random interleaver is considered in this 3D polar encoding structure for convenience.In this paper, regular puncturing pattern is applied top. If p is adopted to xPC with length Nc, there are altogether Ncλ ones in the period Nc. The bits of xPC corresponding to the positions of Ncλ ones are not punctured. For example, assume that λ=1/4 and p=11000000; then every fourth bit of xa and xb is extracted and sent to Cc for encoding again. According to the relationship between p and p¯, it is easy to obtain p¯=00111111. If we apply p¯ to xPC, then the bits which are reserved are sent to the channel.


### 3.2. Decoding Structure

In general, a concatenated code can be decoded by the iterative decoding structure. The decoding diagram of 3D-PC is shown in Figure2. The sequence y is received from channel W and is demultiplexed into three parts, yu, ych, and yc. The corresponding channel logarithm likelihood ratios (LLRs) are denoted by Ψu, Ψch, and Ψc. Later they participate in the subsequent decoding. The decoders Ca-1, Cb-1, and Cc-1 are corresponding to encoders Ca, Cb, and Cc, respectively.Figure 2
The iterative decoding structure of 3D-PC.First,Ψc from channel and Γc from Ca-1 and Cb-1 are fed to Cc-1 for decoding. Then the extrinsic information Λc is deinterleaved, combined with Ψch and demultiplexed into two parts, Ψa and Ψb. The obtained Ψa and Ψb are regarded as channel LLRs of parity bits and assist Ca-1 and Cb-1 in decoding, respectively. For outer decoder, the extrinsic information related to u is exchanged between Ca-1 and Cb-1 because both the input information of Ca and that of Cb are from u. Additionally, the extrinsic information, Ξa and Ξb, of parity bits which is output by Ca-1 and Cb-1 goes through the following operations: multiplex, puncture, and interleave. Then extrinsic LLR information Γc is obtained and delivered to Cc-1 as a priori information at next iteration. The extrinsic LLR information of part parity bits xp is exchanged between inner decoder Cc-1 and outer decoder as framed in Figure 2. The exchange procedure is terminated when the given out-loop iteration number is reached and the decision is made by the LLR information of Cb-1.Since it is needed to exchange extrinsic information betweenCa-1 and Cb-1, the decoder adopted should meet the soft-in-soft-out (SISO) requirement. As to the decoding of SPC, there are two SISO decoding algorithms, belief propagation (BP) decoding [12] and soft cancellation (SCAN) decoding [13]. Therefore, BP decoder and SCAN decoder can be considered for the decoders Ca-1 and Cb-1.As to the decoding of tail-biting convolutional code, the optimal algorithm is maximum a posteriori probability (MAP) decoding algorithm, but its complexity is very high. Two suboptimal MAP decoding algorithms have been proposed for tail-biting convolutional code, tail-biting BCJR (TB-BCJR), and A3 [14]. Afterwards, a less complexity MAP algorithm has been presented to decode tail-biting convolutional code [15]. Therefore, the TB-BCJR, A3 algorithms and the low complexity MAP algorithm can be chosen as the candidate schemes for Cc-1 decoder.


## 3.1. Encoding Structure

In short, 3D-PC scheme can be regarded as a concatenation of the inner code and outer code, PCSPC. The encoding structure of 3D-PC is illustrated in Figure1. First of all, the input information sequence u with length K is encoded by parallel concatenated systematic polar encoder. The component encoders of PCSPC are written as Ca and Cb, respectively. Both of them are systematic polar encoders. We use xa and xb to denote the parity bits sequence of Ca and Cb, respectively. Further, the codeword xPC can be obtained by taking the bits from xa and xb alternatively. The fraction λ of xPC is interleaved by the interleaver Πc and sent to the postencoder Cc for encoding, where λ is named as permeability rate. And codeword xc is output by the postencoder Cc. The parity bits chosen for encoding follow a certain puncturing pattern p with length 2/λ. The fraction 1-λ of xPC is passed to the channel straightly, denoted by xch. The patterns p¯ and p are complementary. Furthermore, the last codeword x of 3D-PC with code length NT is obtained by combining the input sequence u, the parity sequence xch, and the parity sequence xc. Here the code rate of 3D-PC is calculated by R=K/NT=1/3. In order to achieve higher code rate, it is need to puncture some parity bits from xch or xc. Since xc contains more information, xch is first taken into consideration.Figure 1
3D polar encoder.For complexity and performance reasons, the selectedCc encoder should meet some requirements: its decoder is as simple as possible, its decoder inputs soft information and outputs soft information, and its decoder should not introduce too much error [5]. As a result, a rate-1 cyclic recursive systematic convolutional encoder with generator polynomial g(D)=1/1+D2 is selected as the encoder Cc [6].In literature [5, 6], the interleavers Π and Πc have been well designed to increase the minimum distance. Because the design of interleaver has a great influence on the performance of TC. While the effect of interleaver on polar code is not so obvious, random interleaver is considered in this 3D polar encoding structure for convenience.In this paper, regular puncturing pattern is applied top. If p is adopted to xPC with length Nc, there are altogether Ncλ ones in the period Nc. The bits of xPC corresponding to the positions of Ncλ ones are not punctured. For example, assume that λ=1/4 and p=11000000; then every fourth bit of xa and xb is extracted and sent to Cc for encoding again. According to the relationship between p and p¯, it is easy to obtain p¯=00111111. If we apply p¯ to xPC, then the bits which are reserved are sent to the channel.


## 3.2. Decoding Structure

In general, a concatenated code can be decoded by the iterative decoding structure. The decoding diagram of 3D-PC is shown in Figure2. The sequence y is received from channel W and is demultiplexed into three parts, yu, ych, and yc. The corresponding channel logarithm likelihood ratios (LLRs) are denoted by Ψu, Ψch, and Ψc. Later they participate in the subsequent decoding. The decoders Ca-1, Cb-1, and Cc-1 are corresponding to encoders Ca, Cb, and Cc, respectively.Figure 2
The iterative decoding structure of 3D-PC.First,Ψc from channel and Γc from Ca-1 and Cb-1 are fed to Cc-1 for decoding. Then the extrinsic information Λc is deinterleaved, combined with Ψch and demultiplexed into two parts, Ψa and Ψb. The obtained Ψa and Ψb are regarded as channel LLRs of parity bits and assist Ca-1 and Cb-1 in decoding, respectively. For outer decoder, the extrinsic information related to u is exchanged between Ca-1 and Cb-1 because both the input information of Ca and that of Cb are from u. Additionally, the extrinsic information, Ξa and Ξb, of parity bits which is output by Ca-1 and Cb-1 goes through the following operations: multiplex, puncture, and interleave. Then extrinsic LLR information Γc is obtained and delivered to Cc-1 as a priori information at next iteration. The extrinsic LLR information of part parity bits xp is exchanged between inner decoder Cc-1 and outer decoder as framed in Figure 2. The exchange procedure is terminated when the given out-loop iteration number is reached and the decision is made by the LLR information of Cb-1.Since it is needed to exchange extrinsic information betweenCa-1 and Cb-1, the decoder adopted should meet the soft-in-soft-out (SISO) requirement. As to the decoding of SPC, there are two SISO decoding algorithms, belief propagation (BP) decoding [12] and soft cancellation (SCAN) decoding [13]. Therefore, BP decoder and SCAN decoder can be considered for the decoders Ca-1 and Cb-1.As to the decoding of tail-biting convolutional code, the optimal algorithm is maximum a posteriori probability (MAP) decoding algorithm, but its complexity is very high. Two suboptimal MAP decoding algorithms have been proposed for tail-biting convolutional code, tail-biting BCJR (TB-BCJR), and A3 [14]. Afterwards, a less complexity MAP algorithm has been presented to decode tail-biting convolutional code [15]. Therefore, the TB-BCJR, A3 algorithms and the low complexity MAP algorithm can be chosen as the candidate schemes for Cc-1 decoder.


## 4. Convergence Behavior Analysis

In this part, EXIT chart is utilized to analyze the convergence threshold of 3D-PC. In Figure3, the simplified decoding structure for the calculation of EXIT chart is given. In Figure 3, IA,inner denotes the average mutual information between A(uc) and uc, IE,inner denotes the average mutual information between E(uc) and uc, IA,outer denotes the average mutual information between A(xp) and xp, and IE,outer denotes the average mutual information between E(xp) and xp. The detailed calculation processes of EXIT chart curve are presented as follows:(1)
Given signal to noise ratio (SNR),uc and 0≤IA,inner≤1; then the a priori information A(uc) can be obtained by the assumed model [9] and is sent for the inner decoder Cc-1.(2)
Monte Carlo simulation based onCc-1 is performed to get the distributions of pE of (10).(3)
ThenIE,inner is calculated by substituting pE into (10).(4)
TraverseIA,inner at a certain step size in a certain internal 0,1 and calculate the corresponding IE,inner. Then the curve which depicts the relation between IE,inner and IA,inner is obtained.Figure 3
Simplified decoding structure for EXIT chart analysis.Likewise,IE,outer can be got by the above processes. The differences are that the decoder for Monte Carlo simulation is outer decoder other than Cc-1, IA,outer is given, and the transmitted bits are xp instead of uc.Figure4 gives the EXIT chart of 3D-PC with two configurations, λ=1/4,R=1/3,SNR=3.41 and λ=1/2,R=1/3,SNR=4.8. The EXIT chart curves of the outer code and inner code are denoted by solid curves and dash curves, respectively. From Figure 4, it can be seen that there is an opening between the EXIT chart curves of inner code and outer code for both configurations. Since there is no disjoint for each pair of EXIT chart curves, the decoding of 3D-PC can reach convergence. In general, the EXIT chart curves can be depicted with the variety of SNR. The convergence threshold is the SNR at which the tunnel between EXIT chart curves pairs is very narrow. As to 3D-PC with λ=1/4 and R=1/3, the convergence threshold is 3.4 dB. Table 1 lists the convergence thresholds of 3D-PC under different λ. The simulation frames for Monte Carlo simulation are 1.0×104.Table 1
Convergence thresholds of 3D-PC.
λ λ = 1 λ = 1 / 2 λ = 1 / 4 λ = 1 / 8 λ = 0 Thresholds 6.60 dB 4.60 dB 3.40 dB 3.16 dB 2.60 dBFigure 4
EXIT chart ofλ=1/4, R=1/3, 3D-PC, SNR = 3.41 and of λ=1/2, R=1/3, 3D-PC, SNR = 4.8.From Table1, it can be observed that the convergence threshold increases with the increase of λ. Compared with the best convergence threshold when λ is 0, the convergence loss under λ=1/8 and λ=1/4 is relatively small. Therefore, those two λ configurations are set to 3D-PC.


## 5. Simulation Results

In Figure5, the BLER performance of 3D-PC is given. The underlying channel is additive white Gaussian noise (AWGN) channel. The input block size is set to K=4096. The code rate of the component SPC is 1/2. However, it is noteworthy that the output of the component SPC is K parity bits. And the total code rate of 3D-PC is R=1/3. The interleavers Π and Πc used for simulation are random interleavers. The internal iteration number of outer decoder is 1 and the iteration number between the inner decoder and the outer decoder is equal to 6. In addition, SCAN decoding algorithm is utilized for the decoding of SPC and the CRSC code is decoded by low complexity MAP decoding [15]. Different permeability rates λ are set to 3D-PC scheme, such as 1/4 and 1/8.Figure 5
Performance comparison between PCSPC and 3D-PC. For both PCSPC and 3D-PC, the input information length and code rate of them areK=4096 and R=1/3, respectively.As a comparison scheme, the performance of PCSPC is also given in Figure5. The constituent codes are SPCs with code rate 1/2 and code length 8192. Under this configuration, the total code rate of PCSPC is 1/3 which is the same as that of 3D-PC. The SCAN decoding algorithm is applied to decode the component codes. For fair comparison, total iteration numbers between the PCSPC component decoders are required to set the same for both the conventional PCSPC and the proposed 3D-PC scheme. Thereafter the outer loop number between the two constituent decoders is equal to 6.By observing Figure5, it can be found that the performance in water region is lost for 3D-PC with respect to PCSPC. This phenomenon is accordant with the analysis in Section 4. That is, the convergence threshold becomes larger with the increase of λ. In addition, 3D-PC has better BLER performance than PCSPC in low error rate. For PCSPC, error floor phenomenon begins at about BLER 2×10-4. However, the error floor does not appear around BLER 2×10-4 for 3D-PC. In other words, the error floor is lowered by the proposed 3D-PC scheme. The reason may be that 3D-PC has lager minimum distance compared with PCSPC.In addition to performance, complexity is also important. As to the conventional PCSPC [1], the computation complexity is written as(11)ΘP=O2tNlog⁡N,where t is iteration number between the component decoders and N is the code length of component systematic polar code. For the proposed 3D scheme, it includes not only the complexity of PCSPC decoder, but also the complexity of tail-biting convolutional code decoder [15]. Comprehensively, the complexity is about(12)Θ3D=OT2Nlog⁡N+4×2m×λN,where T is the out-loop iteration number, m is the memory element of tail-biting convolutional code, N is the code length of component polar code, and λ is the permeability rate. In (12), 2Nlog⁡N and 4×2m×λN denote the complexity of outer decoder and inner decoder in one outer iteration, respectively. Since the inner iteration number between the PCSPC component decoders is 1, the complexity of outer decoder is 2Nlog⁡N according to (11). As to Log-MAP algorithm, the complexity can be regarded as the metric updates in the trellis nodes. Corresponding to (12), 4 denotes the metric updates per trellis node, 2m is the state numbers, and λN denotes the input information length of tail-biting convolutional code which can be known from 3D polar encoder (refer to Section 3).In this paper,t and T are set the same to ensure that the total iteration number between the PCSPC component decoders is the same. Moreover, the increased complexity is 4×2m×TλN which is brought by inner decoder. Since the memory of the tail-biting convolutional code we use is small and 0≤λ≤1, the additional complexity of the proposed scheme is less compared with the complexity of the conventional PCSPC decoder. Here, we adopt the parameter configurations in this paper to give a specific example. Assume that N=8192,t=T=6,m=2, and λ=1/4; then ΘP=1277952 and Θ3D=1474560 are obtained by (11) and (12). Hence, compared to the complexity of the original PCSPC, the additional complexity of 3D polar code is about 15%.


## 6. Conclusion

In this paper, 3D-PC is presented to lower the error floor of PCSPC. It makes the best use of the characteristics of parallel concatenation and serial concatenation. The simulation results verify the effectiveness of 3D-PC. In addition, EXIT chart is utilized to analyze the convergence threshold of 3D-PC under different permeability rate configurations. The obtained convergence thresholds can guide the choice of permeability rate of 3D-PC.



---

*Source: 8928761-2018-05-03.xml*