# A Novel Scheme of Product Polar Codes with High Efficiency and Rate Compatibility

Authors: Mohammad Abu Hanif; Sina Vafi
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

This paper presents a new structure of product codes formed by combining two polar codes. The encoding performance of these codes is verified by implementing an exhaustive search algorithm, which determines their minimum weight specifications. Conducted analysis and simulations confirm that with the equal code length and rate, the newly proposed codes outperform the conventional polar codes in high energy per bit-to-noise ratios (Eb/N0≤5 dB). This is concluded from punctured and nonpunctured product codes.


---

## Body

## 1. Introduction

Polar codes are promising forward error correction (FEC) codes for the next generation of broadband networks including the fifth generation of wireless networks (5G). These codes are recognized as capacity-achieving codes under a successive cancellation (SC) decoding technique, which were initially constructed for the symmetric binary-input discrete memoryless channel (BI-DMC) [1]. However, at a short code length, their bit error rate (BER) performance is not as reliable as other known codes, such as low-density-parity-check (LDPC) and turbo codes. This limits their reputation as a good code for a wide range of applications. In order to overcome this issue, short length codes are combined with other codes to form a scheme of high-performance concatenated codes [2].A serially concatenated code was proposed based on an inner polar code and an outer Reed-Solomon (RS-polar) code [3]. It is shown that the block error rate performance of the code is improved at the expense of increasing the length and complexity of the RS code. Eslami and Pishro-Nik showed that a high-performance concatenated code can be formed by combining polar and LDPC codes [4]. In [5], Tal and Vardy considered concatenation of a polar code with an outer cyclic redundancy check (CRC) code. The CRC code together with the usage of a list decoding algorithm concludes a high-performance code formed by the short length polar code. An alternative scheme of these codes is achieved, when the CRC code is replaced by the parity-check code [6]. In this case, parity-check codes having low multiplicity in their minimum weight are selected [7].On the other hand, construction of a parallel concatenated code formed by two polar codes was proposed in [8]. Based on the same code length and rate, the designed code outperforms the single one. More recent work demonstrates a parallel construction of multiple polar codes having different rates [9]. Constructed code has high performance at the expense of high complexity. Alternatively, a parallel concatenated code was presented by combining a polar code with a Recursive Systematic Convolutional (RSC) code [10]. Codes obtained by this method conclude a performance better than other well-known codes (turbo codes and LDPC codes), mainly at the error floor region due to utilizing a modified interleaver, which is matched with specifications of the constituent RSC code.The main similarity between the above-mentioned codes is the serial combination of a polar code with a nonpolar code. On the other hand, a turbo product code is based on multiple polar codes (polar-TPC) introduced in [11]. In this work, nonpunctured constituent polar codes are used to form a product code, where SCL-Chase decoding algorithm was proposed.This paper presents a new scheme of serially concatenated codes constituted by two systematic polar codes linked by an interleaver. Codes are constructed on the basis of the message, whose length is the product of the length of constituent codes. This code can be also introduced as a polar code, as every bit of the codeword is properly polarized. Moreover, the puncturing structure of these codes will be verified. Unlike a punctured single polar code, which applies a relatively high number of punctured bits, punctured product polar codes can be constructed by removing a low number of bits applied in one of the constituent codes. This feature will allow decoders to interactively exchange their decoded information with each other and improve the error correcting capability of the code. Conducted simulations confirm that with the same rate and code length, punctured product polar codes have better performance than single punctured polar codes. In addition, it is analysed that the proposed code decoded with BP decoding has similar performance to codes decoded with the SCL-Chase-based algorithm.The rest of the paper is organized as follows. A brief introduction of polar codes is given in Section2. In Section 3, the structure of product polar codes and their comparison with single polar codes formed by the same rate and length are explained. Puncturing technique of the proposed code is presented in Section 4. Numerical results are given in Section 5. Finally, Section 6 concludes the paper.


## 2. Basic Structure of Polar Codes

LetN=2n n∈ℤ,n>0 and K be the length and dimension of a N,K polar code, respectively. The rate of this code is R=K/N. Let GN=G2⊗logN be the generator matrix of the polar code with rate one and length N, where ⋅⊗q denotes the qth Kronecker power and G2≔1011 as in [1]. It is shown that as N approaches to infinity, under successive cancellation (SC) decoding, a fraction of rows of GN leads to good channels suitable for carrying messages with length K. Other channels are referred to as bad channels. In order to measure how good a binary-input channel W is, Arikan used the Bhattacharyya parameter of W, which is defined as [1]
(1)ZW=∑y∈YWyx=0Wyx=1,where WYX is the channel transitional probability of input alphabet X=0,1 and output alphabet Y,x∈X,y∈Y. For binary erasure channel (BEC) with ZW11=0.5, the reliability of bit channels can be recursively determined by [1]
(2)ZWN2i−1=2ZWN/2i−ZWN/2i2,ZWN2i=ZWN/2i2,where ZWNi, 1≤i≤N, is the Bhattacharyya parameter of channel WNi. The code construction rule (3) is channel-independent [12]. This means, the same rule can be used for constructing codes for any binary-input channel [12]. However, it shows that for the additive white Gaussian noise (AWGN) channel, with zero mean and variance N0/2, the code works better if equation (2) is initialized by [13–15]
(3)ZW11=∫−∞∞Wyx=−1Wyx=1=exp−EcN0,where Ec=REb and Eb is the energy spent per bits. In this case, the coded bits (x) are modulated by binary phase shift keying (BPSK) modulation. Hence, channels with low ZW values are referred to as noiseless channels (or good channels).LetAℐ be the set of good channels. Similarly, Aℐc denotes the frozen set, which specifies the set of bad channels. Let u=u1u2⋯uN be a message vector of length N. In this vector, there are K message bits (uAℐ) and N−K frozen bits (uAℐc=0). The codeword vector is generated by x=uGN, where GN is a N×N generator matrix.In systematic polar encoding, the codeword is split into two parts [16]. This can be written as x=xℬxℬc, where ℬ is an arbitrary subset of 1,2,⋯,N. These parts are recognized as message and parity parts of the codeword, respectively. In this case,
(4)xℬ=uAℐGAℐℬ+uAℐcGAℐcℬ,
(5)xℬc=uAℐGAℐℬc+uAℐcGAℐcℬ,where GPQ is a P×Q generator matrix formed by taking rows of P indices and columns of Q indices of GN. In general, frozen bits are set to the value of zero. Hence, uAℐc is a zero vector and xℬc can be calculated as
(6)xℬc=xℬGAℐℬ−1GAℐℬc.


### 2.1. Effect of the Minimum Weight on the Performance of Polar Code

The minimum weight (dmin) of a systematic polar code is determined based on the weights of its rows, whose indices are elements of Aℐ. This is given by [10, 17]
(7)dmin=minb∈Aℐ2ωb,where ωb is the number of ones in the binary expansion of b. In polar codes, the lowest expected parity weight of the codeword is one [4]. This means that dmin of the code is obtained from messages, whose weights are not greater than dmin−1. Based on this property and using equation (7), Table 1 gives minimum weight specifications of different polar codes. In this table, Ndmin gives the multiplicity of the minimum weight determined by an exhaustive search algorithm, which considers all possible messages with weight no greater than dmin−1 of the code.Table 1
Minimum weight specifications of polar codes with rates 1/2 and 1/4.
Polar code
dmin Ndmin
Polar code
dmin Ndmin
(8, 4)
4 (14)
(8, 2)
4 (2)
(16, 8)
4 (28)
(16, 4)
8 (14)
(32, 16)
4 (8)
(32, 8)
8 (12)
(64, 32)
8 (662)
(64, 16)
16 (364)
(128, 64)
8 (1724)
(128, 32)
16
(256, 128)
8 (2330)
(256, 64)
16
(512, 256)
8
(512, 128)
32
(1024, 512)
8
(1024, 256)
32
(2048, 1024)
16
(2048, 512)
64
(4096, 2048)
16
(4096, 1024)
64
(8192, 4096)
16
(8192, 2048)
64As a class of linear block codes, performance of polar codes can be analysed by its Input-output weight enumerating function (IOWEF), which is given by [18]
(8)ACW,H=∑ω,hAω,hWωHh,where Aω,h is the number of codewords with weight h obtained from messages with weight ω. Based on IOWEF, the conditional weight enumerating function (CWEF) of the code is defined by
(9)AωCH=1ω!∂ωACW,H∂WωW=0.This leads to expressing the upper bound of the probability of error for the code decoded by a maximum likelihood decoding technique as follows:(10)Pbe≤∑ω=1kωkAωCHH=e−REb/N0,where Eb/N0 is the signal-to-noise ratio per bit. The above bound can also be represented as
(11)Pbe≤∑dΠDdΠHdΠH=e−REb/N0,where
(12)Dd∏=∑j+ω=d∏ωNω,jK.Here,Nω,j gives the number of codewords generated by an input message with weight ω, whose parity-check bits have weight j. With a good approximation, the above probability is given by
(13)Pbe≈12∑d∏Dd∏erfcd∏REbN0.LetPdΠγb=DdΠerfcdΠγb, where γb=REb/N0. The relative contribution of each weight to the overall BER is given by
(14)P¯d∏γb=Pd∏γb∑d∏Pd∏γb.Example 1.
The IOWEF of (8, 4) systematic polar code is given by(15)ACSPW,H=1+4WH4+6W2H4+4W3H4+W4H8.
The CWEF of this code isA0CSPH=1,A1CSPH=4H4,A2CSPH=6H4,A3CSPH=4H4,A4CSPH=H8.
From (11) and (12), probability of error of the code is Pbe≈48erfc4REbN0+128erfc4REbN0+128erfc4REbN0+48erfc8REbN0=3.5erfc4REbN0+0.5erfc8REbN0.
Considering (12) and CWEF of the code, it is evident that the effect of codewords with weight 4 on the performance of the code is much higher than that with weight 8.Figure1 shows the relative contribution of the three lowest weights of (16, 8) and (32, 16) polar codes. It is clearly observed that by increasing Eb/N0s, the minimum weight has the highest effect on the performance of code. Figure 2 shows the relative contribution of low weights of (32, 8) and (64, 16) polar codes with R=1/4. The weight distributions of these short length codes conclude minimum weights with high multiplicities. Considering the probability of error given in equation (10), the existence of either the minimum weight with a high multiplicity or a low minimum weight relative to the length of the codeword will deteriorate performance of the polar code. As shown in the figures, this is more sensible at the medium to high Eb/N0s.Figure 1
Relative contribution of different weights to the BER performance of (16, 8) and (32, 16) polar codes.Figure 2
Relative contribution of different weights to the BER performance of (32, 8) and (64, 16) polar codes.


## 2.1. Effect of the Minimum Weight on the Performance of Polar Code

The minimum weight (dmin) of a systematic polar code is determined based on the weights of its rows, whose indices are elements of Aℐ. This is given by [10, 17]
(7)dmin=minb∈Aℐ2ωb,where ωb is the number of ones in the binary expansion of b. In polar codes, the lowest expected parity weight of the codeword is one [4]. This means that dmin of the code is obtained from messages, whose weights are not greater than dmin−1. Based on this property and using equation (7), Table 1 gives minimum weight specifications of different polar codes. In this table, Ndmin gives the multiplicity of the minimum weight determined by an exhaustive search algorithm, which considers all possible messages with weight no greater than dmin−1 of the code.Table 1
Minimum weight specifications of polar codes with rates 1/2 and 1/4.
Polar code
dmin Ndmin
Polar code
dmin Ndmin
(8, 4)
4 (14)
(8, 2)
4 (2)
(16, 8)
4 (28)
(16, 4)
8 (14)
(32, 16)
4 (8)
(32, 8)
8 (12)
(64, 32)
8 (662)
(64, 16)
16 (364)
(128, 64)
8 (1724)
(128, 32)
16
(256, 128)
8 (2330)
(256, 64)
16
(512, 256)
8
(512, 128)
32
(1024, 512)
8
(1024, 256)
32
(2048, 1024)
16
(2048, 512)
64
(4096, 2048)
16
(4096, 1024)
64
(8192, 4096)
16
(8192, 2048)
64As a class of linear block codes, performance of polar codes can be analysed by its Input-output weight enumerating function (IOWEF), which is given by [18]
(8)ACW,H=∑ω,hAω,hWωHh,where Aω,h is the number of codewords with weight h obtained from messages with weight ω. Based on IOWEF, the conditional weight enumerating function (CWEF) of the code is defined by
(9)AωCH=1ω!∂ωACW,H∂WωW=0.This leads to expressing the upper bound of the probability of error for the code decoded by a maximum likelihood decoding technique as follows:(10)Pbe≤∑ω=1kωkAωCHH=e−REb/N0,where Eb/N0 is the signal-to-noise ratio per bit. The above bound can also be represented as
(11)Pbe≤∑dΠDdΠHdΠH=e−REb/N0,where
(12)Dd∏=∑j+ω=d∏ωNω,jK.Here,Nω,j gives the number of codewords generated by an input message with weight ω, whose parity-check bits have weight j. With a good approximation, the above probability is given by
(13)Pbe≈12∑d∏Dd∏erfcd∏REbN0.LetPdΠγb=DdΠerfcdΠγb, where γb=REb/N0. The relative contribution of each weight to the overall BER is given by
(14)P¯d∏γb=Pd∏γb∑d∏Pd∏γb.Example 1.
The IOWEF of (8, 4) systematic polar code is given by(15)ACSPW,H=1+4WH4+6W2H4+4W3H4+W4H8.
The CWEF of this code isA0CSPH=1,A1CSPH=4H4,A2CSPH=6H4,A3CSPH=4H4,A4CSPH=H8.
From (11) and (12), probability of error of the code is Pbe≈48erfc4REbN0+128erfc4REbN0+128erfc4REbN0+48erfc8REbN0=3.5erfc4REbN0+0.5erfc8REbN0.
Considering (12) and CWEF of the code, it is evident that the effect of codewords with weight 4 on the performance of the code is much higher than that with weight 8.Figure1 shows the relative contribution of the three lowest weights of (16, 8) and (32, 16) polar codes. It is clearly observed that by increasing Eb/N0s, the minimum weight has the highest effect on the performance of code. Figure 2 shows the relative contribution of low weights of (32, 8) and (64, 16) polar codes with R=1/4. The weight distributions of these short length codes conclude minimum weights with high multiplicities. Considering the probability of error given in equation (10), the existence of either the minimum weight with a high multiplicity or a low minimum weight relative to the length of the codeword will deteriorate performance of the polar code. As shown in the figures, this is more sensible at the medium to high Eb/N0s.Figure 1
Relative contribution of different weights to the BER performance of (16, 8) and (32, 16) polar codes.Figure 2
Relative contribution of different weights to the BER performance of (32, 8) and (64, 16) polar codes.


## 3. Structure of Product Polar Codes (PPCS)

Product codes are represented as one of the most well-known codes, whose high error-correcting capability is guaranteed due to their high minimum weight. Figure3(a) shows the basic structure of product codes. In this code, every message with length K=K1×K2 is converted to K2 blocks with length K1. The N1,K1 outer code encodes every block and generates K2 codewords with length N1. Codewords obtained from the first encoder are transposed to construct N1 blocks of length K2, which are considered as the message for the N2,K2 (inner) code. Finally, codewords obtained from the second encoding are multiplexed to form a codeword with length N=N1×N2 for the concatenated code. The minimum weight of product codes is calculated by dmin1×dmin2 [19], where dmin1 and dmin2 are minimum weights of the N1,K1 and N2,K2 constituent codes, respectively.Figure 3
(a) Two-dimensional codeword structure of product polar codes. (b) The encoding structure of product polar codes.
(a)
(b)The product code can be viewed as a serially concatenated code, which is formed byN1∗K2,K1∗K2 outer and N1∗N2,N1∗K2 inner codes. This structure is shown in Figure 3(b). Indeed, the N1,K1 outer code encodes K2 blocks of messages with length K1⋅K2∗N1 codewords obtained from this encoding which are interleaved to form N1 messages with length K2. Finally, every K2 bit message is encoded by the N2,K2 code to conclude a codeword with a length of N1∗N2 [20].The behaviour of the product code allows us to analyse its performance by utilizing the uniform interleaver with lengthN1K2, which maps information with length ℓ into all distinct N1K2ℓ permutations of it with equal probability of 1N1K2ℓ as seen in [18]. The analysis conducted by the uniform interleaver represents the average performance of the code. Indeed, for each value of the signal-to-noise ratio, there will always be an interleaver, which provides better performance for the code compared to the uniform interleaver. In this case, the CWEF of the product code is expressed by [18]
(16)AωCPRH=∑ℓ=0N1K2Aω,ℓCoK2⋅AℓCiN1HN1K2ℓ,where Aω,ℓCoK2 and AℓCiN1H are the number of codewords with weight ℓ obtained to form messages with weight ω of the outer code and CWEF of the inner code, respectively. As ACiN1L,H=ACiL,HN1 from (9), we have
(17)AℓCiN1H=1ℓ!∂ℓACiL,H∂LℓL=0N1.LetfL,H=ACiL,H. Based on the Leibnitz theorem, the above equation is given by
(18)AℓCiN1H=1ℓ!∑i=0ℓℓ0∂ℓ−ifN1−1L,H∂Lℓ−i∂ifL,H∂LiL=0=1ℓ!∂ℓfN1−1L,H∂Lℓ⋅fL,H+fN1−1L,H∂ℓfL,H∂Lℓ+∑i=1ℓ−1ℓi∂ℓ−ifN1−1L,H∂Lℓ−i∂ifL,H∂LiL=0.The third term is expressed as(19)1ℓ!∑i=1ℓ−1ℓi∂ℓ−ifN1−1L,H∂Lℓ−i∂ifL,H∂LiL=0=∑i=1ℓ−1AℓCiN1−1HAiCiH.In product polar codes with theR=1/4 constituent by two half rate polar codes, the minimum weight obtained from messages with weight of dmin is 2dmin [4]. Hence, the lowest order of H obtained from the third term will be 2dmin. By contrast, for the first and second terms, the expected lowest order of H is dmin as they are only formed by one derivative. Therefore, for different Eb/N0s, the third term will not be as effective as the first and second terms on the performance of the code. This will be more evident, when the value of Eb/N0 increases. Continuing the Leibnitz theorem for the first and second terms, CWEF of the inner code is approximately given by
(20)AℓCiN1H≈1ℓ!fN1−1L,H∂ℓfL,H∂Lℓ⋅fL,H+N1−1fN1−1L,H∂ℓfL,H∂LℓL=0.ForL=0, fN1−1L,H=1. Hence,
(21)AℓCiN1H=1ℓ!N1∂ℓfL,H∂LℓL=0=N1AℓCiH.Similarly,Aω,ℓCoK2=K2Aω,ℓCo. Therefore, CWEF of the product code is finalised as follows:
(22)AωCPRH=∑ℓ=0N1K2N1K2Aω,ℓCo⋅AℓCiHN1K2ℓ.As shown in Section 1.1, codewords with the minimum weight have the most effect on the performance of the code at the medium to high signal-to-noise ratios. Therefore, equation (24) can be approximately given by
(23)AωCPRH≅N1K2Aω,dminCo⋅AdminCiHN1K2dmin.As the lowest order ofH obtained from AdminCiH is 2dmin, more simplified CWEF of the product code is given by
(24)AωCPRH≈N1K2Aω,dminCo⋅Admin,2dminCiH2dminN1K2dmin.On the other hand, the CWEF of a single polar code with rateR′ and minimum weight of dmin′ is approximately given by
(25)AωCSPH≈Aω,dmin′CSPHdmin′,where Aω,dmin′CSP is number of codewords with the weight of dmin′ generated from messages with weight ω.Based onR′=R and dmin′=dmin2, Table 2 shows conditions for different product codes with R=1/4, which satisfy AωCPRH<AωCSPH. Considering (10), this inequality concludes that the product polar code can produce a lower upper bound of probability of error than that obtained from the single polar code. Conditions are formed by Aω,dminCo⋅Admin,2dminCi=10Aω,dmin′CSP, which assumes that the multiplicity of the minimum weight obtained from the product code is much greater than that generated by the single code. It is observed that the expected lower probability of error for the product code is guaranteed by Eb/N0s that are applicable in communication systems.Table 2
Minimum weight specifications of polar codes with rates 1/2 and 1/4.
Product code
N1∗K2
dmin
X=dminN1K2
Exponential form of10∗1/X
AωCPRH<AωCSPH if
8,4×8,4
32
4
35960
e−8.1876
Eb/N0<3.75 dB
8,4×16,8
64
4
635376
e−11.0594
Eb/N0<5.38 dB
16,8×16,8
128
4
1.0668×107
e−13.8802
Eb/N0<6.50 dB
32,16×32,16
512
4
2.8299×109
e−19.4609
Eb/N0<8.20 dB
64,32×64,32
2048
8
7.5714×1021
e−48.0761
Eb/N0<5.28 dBIn particular cases, multiplicity of minimum weight of the product code can be similar or even smaller than the multiplicity of the minimum weight of the single code. This will provide a better condition for the product code to outperform the single code at the error floor region.Figure4 shows the probability of error for the (64, 16) code. In these graphs, only the minimum weight specifications of the code are considered in (13). Based on the exhaustive search algorithm, multiplicity of 196 for the minimum weight of the (64, 16) product code is obtained. From Table 1, it is observed that codes have the same minimum weight but the product code generates lower multiplicity for the minimum weight. This consequently provides a better error correcting compared to the single polar code. Again, the improvement should be mainly observed at the medium to high Eb/N0s, where the practical behaviour of codes is matched with the calculated Pbes [18].Figure 4
Probability of error for (64, 16) polar code.


### 3.1. Reliability of Bit Channels for Product Polar Codes

The codeword obtained from the product polar encoding can be expressed as aN1×N2 matrix. This matrix can also be represented by two K1×N1 and N2−K2×N1 submatrices, which denote the codeword of the outer code and parity bits of the inner code, respectively. The reliability of bits for the first and second submatrices is directly determined from equation (2). In every row of the first submatrix, computation is initialized by the value given in equation (3). Therefore, bits positioned at the same column will have the same reliability value. The reliability of bits at the inner code is determined on the basis of reliability of interleaved bits obtained from the first submatrix. Indeed, reliabilities calculated from K1 rows of the first submatrix are considered as the initialized values for determining the reliability of bits positioned at the second submatrix.Table3 shows the reliability of bit channels for the (16, 4) product polar code constituted by two (4, 2) polar codes, which are recursively calculated by equation (2). In this case, channels are considered as binary AWGN and followed the polar code construction method proposed in [13–15] with Eb/N0=0 dB. In the first encoding, reliability of bits positioned at the first two rows is obtained. This is accomplished when α≤i≤n2K2=2α,N2=2n2,n2=1,2,3,⋯,α=n2−1 is applied for equation (2). In this case, ZW2α−1js, 1≤j≤K2, are channel reliabilities of bits placed in one column of the first submatrix. Then, from these calculated values, those reliabilities positioned at one column of the matrix are applied as ZW2j′, 1≤j′≤2, to determine reliabilities of parity bits for codewords of the N2,K2 polar code. All of the reliabilities relevant to the inner code are expressed as ZW4j′, 1≤j′≤4 in equation (2).Table 3
Reliability of bits for (16, 4) polar codes.
Product polar code
(16, 4) single polar code
First encoding
Second encoding
0.84
0.25
0.36
0.018
0.9745
0.4410
0.5911
0.0363
0.9994
0.6875
0.8328
0.0713
0.84
0.25
0.36
0.018
0.7062
0.0637
0.1300
0.0003
0.9137
0.1233
0.2430
0.0007
0.9745
0.4410
0.5911
0.0363
0.9497
0.1945
0.3493
0.0013
0.7062
0.0637
0.1300
0.0003
0.4987
0.0041
0.0169
1.12e−07This table also gives the reliabilities of bit channels for the single (16, 4) polar code. Similar to the single code, the product code effectively polarizes the channel as either good or bad channels. Such recognition allows us to construct polar codes with arbitrary lengths andR>1/4 originated from the main product polar code when a number of codeword bits are punctured.


## 3.1. Reliability of Bit Channels for Product Polar Codes

The codeword obtained from the product polar encoding can be expressed as aN1×N2 matrix. This matrix can also be represented by two K1×N1 and N2−K2×N1 submatrices, which denote the codeword of the outer code and parity bits of the inner code, respectively. The reliability of bits for the first and second submatrices is directly determined from equation (2). In every row of the first submatrix, computation is initialized by the value given in equation (3). Therefore, bits positioned at the same column will have the same reliability value. The reliability of bits at the inner code is determined on the basis of reliability of interleaved bits obtained from the first submatrix. Indeed, reliabilities calculated from K1 rows of the first submatrix are considered as the initialized values for determining the reliability of bits positioned at the second submatrix.Table3 shows the reliability of bit channels for the (16, 4) product polar code constituted by two (4, 2) polar codes, which are recursively calculated by equation (2). In this case, channels are considered as binary AWGN and followed the polar code construction method proposed in [13–15] with Eb/N0=0 dB. In the first encoding, reliability of bits positioned at the first two rows is obtained. This is accomplished when α≤i≤n2K2=2α,N2=2n2,n2=1,2,3,⋯,α=n2−1 is applied for equation (2). In this case, ZW2α−1js, 1≤j≤K2, are channel reliabilities of bits placed in one column of the first submatrix. Then, from these calculated values, those reliabilities positioned at one column of the matrix are applied as ZW2j′, 1≤j′≤2, to determine reliabilities of parity bits for codewords of the N2,K2 polar code. All of the reliabilities relevant to the inner code are expressed as ZW4j′, 1≤j′≤4 in equation (2).Table 3
Reliability of bits for (16, 4) polar codes.
Product polar code
(16, 4) single polar code
First encoding
Second encoding
0.84
0.25
0.36
0.018
0.9745
0.4410
0.5911
0.0363
0.9994
0.6875
0.8328
0.0713
0.84
0.25
0.36
0.018
0.7062
0.0637
0.1300
0.0003
0.9137
0.1233
0.2430
0.0007
0.9745
0.4410
0.5911
0.0363
0.9497
0.1945
0.3493
0.0013
0.7062
0.0637
0.1300
0.0003
0.4987
0.0041
0.0169
1.12e−07This table also gives the reliabilities of bit channels for the single (16, 4) polar code. Similar to the single code, the product code effectively polarizes the channel as either good or bad channels. Such recognition allows us to construct polar codes with arbitrary lengths andR>1/4 originated from the main product polar code when a number of codeword bits are punctured.


## 4. A Puncturing Technique for Product Polar Codes

AN,K polar code is punctured by removing a number of rows and columns from the generator matrix. Let X be the number of punctured bits. The codeword length and rate of the newly designed code are N−X and K/N−X, respectively. In product polar codes, puncturing can be conducted on one of its constituent codes. The rate of these codes formed by two constituent N1,K1 and N2,K2 codes is determined by
(26)Rp=K1×K2N1−φN2,where φ is the number of bits removed from the N1,K1 code.In order to haveRp equal to the rate of the N−X,K single polar code (N=N1×N2, K=K1×K2), the following condition should be satisfied:
(27)φ=XN2.This means a lower number of bits punctured from one of the constituent codes are required in comparison with the number of punctured bits applied for the single code.Based on the two-dimensional structure of the codeword,φ rows or columns representing the most unreliable bits of a constituent code will be removed. The structure of punctured codewords for the (64, 16) product code is given by
(28)×C1,2C1,3C1,4×C1,6C1,7C1,8×C2,2C2,3C2,4×C2,6C2,7C2,8×C3,2C3,3C3,4×C3,6C3,7C3,8×C4,2C4,3C4,4×C4,6C4,7C4,8×C5,2C5,3C5,4×C5,6C5,7C5,8×C6,2C6,3C6,4×C6,6C6,7C6,8×C7,2C7,3C7,4×C7,6C7,7C7,8×C8,2C8,3C8,4×C8,6C8,7C8,8,where Ci,j, i,j∈Aℐ, and Aℐ=4,6,7,8 are message bits and the rest are parity bits. In this matrix,“×” denotes position of punctured bits. This code is constructed by two (8, 4) polar codes. For a punctured code formed based on a low value of φ, it is possible to do the puncturing by selecting bits that are not adjacent to each other [21]. In this code, the first and fifth bits of the (8, 4) code have the lowest reliabilities. Hence, the information positioned at the mentioned columns (first and fifth columns) of the matrix is punctured. In this case, at every decoding step of the outer code, there would be at least one valid (nonpunctured) information, which assists the decoder to recover the original codeword.On the other hand, based on transposing the received information, at the second decoder, some adjacent information is recognized as punctured information. However, as shown in Figure5, due to interactive iterative decoding of the product code, in every iteration, decoded information obtained from two decoders is exchanged with each other. This allows both decoders to effectively recover the original information transmitted over the noisy channel. Regardless the error floor effect, existence of a good error correcting performance is expected from the medium to high Eb/N0s, where the first decoder has a better chance to correctly decode the received information.Figure 5
Structure of interactive iterative decoding of product codes.By contrast, in a single polar code formed by a high number of punctured bits, it is possible to puncture adjacent bits or those having high reliability. This is mainly evident for codes withX≥K/2 [21]. Moreover, as interactive iterative decoding is not conducted for a single polar code, it is expected that with the same rate and length, punctured product polar codes outperform punctured single polar codes.


### 4.1. Puncturing Effect on the Channel Reliability for SPC and PPC

The reliability of the bit channel can effect error performance of the punctured code. Puncturing a bit ultimately deletes its bit-channel reliability. This consequently reduces the overall bit-channel reliability (Zsum) of the code and mitigates decoding performance. The overall reliability of a polar code is defined by
(29)Zsum=∑i∈NZWNi.As mentioned above, theZsum value is reduced, when bits are punctured. Therefore, it is essential to keep Zsum as high as possible to have a good performance for the punctured code. Let ζ be the overall reliability of nonpunctured bits of a punctured code, which is given by
(30)ζ=Zsum−∑j∈ApZWNj,where ZWNj is the bit-channel reliability value of the j-th bit of the codeword and Ap represents the set of indices applied for punctured codeword bits. Obviously, for Ap=0, the code is considered as a nonpunctured one. From (29) and (30), the below inequality can be observed
(31)ζ≤Zsum.Therefore, ifζ is tightly upper bounded, punctured bits have less effect on the code performance. This requires careful selection of puncturing bits so that the calculated ζ remains close to Zsum of the code.As mentioned before, in product polar codes, a lower of number of bits are punctured from their constituent codes compared to a single punctured code. Hence, less effect of punctured bits on the performance of product code compared to the single code is expected. Table4 confirms this subject for the number of punctured product polar and single codes formed by the equal code length and rate.Table 4
Comparison ofζ for different codes. The channel reliability is calculated for binary AWGN channel with SNR=0dB.
N
Product code
Single code
Zsum
ζ
Zsum
ζ
48
23.5443
10.0989
23.5443
8.0056
192
94.1771
40.3955
94.1771
30.5400
768
376.7085
161.5818
376.7085
120.8185
3072
1.5068×103
646.3274
1.5068×103
482.8405
12288
6.0273×103
2.5853×103
6.0273×103
1.9313×103


## 4.1. Puncturing Effect on the Channel Reliability for SPC and PPC

The reliability of the bit channel can effect error performance of the punctured code. Puncturing a bit ultimately deletes its bit-channel reliability. This consequently reduces the overall bit-channel reliability (Zsum) of the code and mitigates decoding performance. The overall reliability of a polar code is defined by
(29)Zsum=∑i∈NZWNi.As mentioned above, theZsum value is reduced, when bits are punctured. Therefore, it is essential to keep Zsum as high as possible to have a good performance for the punctured code. Let ζ be the overall reliability of nonpunctured bits of a punctured code, which is given by
(30)ζ=Zsum−∑j∈ApZWNj,where ZWNj is the bit-channel reliability value of the j-th bit of the codeword and Ap represents the set of indices applied for punctured codeword bits. Obviously, for Ap=0, the code is considered as a nonpunctured one. From (29) and (30), the below inequality can be observed
(31)ζ≤Zsum.Therefore, ifζ is tightly upper bounded, punctured bits have less effect on the code performance. This requires careful selection of puncturing bits so that the calculated ζ remains close to Zsum of the code.As mentioned before, in product polar codes, a lower of number of bits are punctured from their constituent codes compared to a single punctured code. Hence, less effect of punctured bits on the performance of product code compared to the single code is expected. Table4 confirms this subject for the number of punctured product polar and single codes formed by the equal code length and rate.Table 4
Comparison ofζ for different codes. The channel reliability is calculated for binary AWGN channel with SNR=0dB.
N
Product code
Single code
Zsum
ζ
Zsum
ζ
48
23.5443
10.0989
23.5443
8.0056
192
94.1771
40.3955
94.1771
30.5400
768
376.7085
161.5818
376.7085
120.8185
3072
1.5068×103
646.3274
1.5068×103
482.8405
12288
6.0273×103
2.5853×103
6.0273×103
1.9313×103


## 5. Numerical Results

The bit error rate (BER) and frame error rate (FER) performances of different product and single polar codes transmitted over the AWGN channel are verified. Codes are modulated by BPSK and decoded by the soft-in soft-out belief propagation method mentioned in [16]. For product codes, four iterations are considered for the interactive decoding between two constituent decoders. For single systematic polar codes, decoding is accomplished by 60 iterations. A successive cancellation list with cyclic redundancy check (SCL-CRC) decoding is performed with the list size of either L=4 or L=8. Moreover, m-bit CRC code is applied. This means m bits added to the message bits.Figure6 shows the performance of (64, 16) codes. It is observed that the product code has a similar BER performance to the single code with SCL-CRC (L=8 and m=4) decoding. Constituent half rate codes are decoded by 30 iterations. In addition, at Eb/N0=4.5 dB, this code shows a performance better than the single polar code. The product code provides significantly better performance than SPC with BP decoding.Figure 6
Performance of (64, 16) codes decoded by different algorithms.Figure7 shows the performance of two product codes and their performance with BCH-polar [22] and RS-polar [23] codes. Constituents of both product codes are based on non-half rate polar codes. It shows that the (256, 42) product code with rate R=1/6 has close FER performance with BCH-based polar code. In addition, the (512, 171) product code is constituted by (32, 19) and (16, 9) polar codes. At Eb/N0=4.0 dB, this code has 2.0 dB and 0.85 dB gain in BER performance compared to RS-polar and LDPC-polar codes, respectively. Similarly, the (1984, 946) product code constituted by the (62, 43) and (32, 22) polar codes has close performance to the single (2048, 1024) polar code decoded by SCL-CRC decoding with L=4 and m=4. All product codes apply 30 iterations in their BP decoding.Figure 7
Performance of product polar codes and their comparison with BCH-polar, RS-polar, and LDPC-polar codes.Figure8 shows the performance of the (800, 256) product and (768, 256) single polar codes. In this case, the product code is constructed by two (32, 16) polar codes, which are decoded by BP decoding, including 90 iterations. Due to interactive iterative decoding applied in the product code, one decoder can properly recover punctured information from a block of information and deliver them to the second decoder for the next step of decoding. It is observed that the product code provides similar performance to decoding based SPC, while outperforming the single polar code decoded by BP decoding.Figure 8
BER and FER performance of (800, 256) product polar code and its comparison with other codes.Figure9 shows the BER and FER performances of the (3196, 1024) product and (3072, 1024) single polar codes. Again, 90 iterations were considered for BP decoding of constituent codes. It is observed that the product code has a better BER performance compared to the single code. It also has similar FER performance with the single code decoded by the SCL-CRC technique with L=4 and m=4.Figure 9
BER and FER performances of (3196, 1024) product and (3072, 1024) single polar codes.Furthermore, BER performance of the (2562, 2392) product polar code and polar-TPC proposed in [11] are analysed in Figure 10. Codes are modulated by quadrature phase shift keying (QPSK). Sixty (60) iterations are applied for BP decoding of the product polar code. It is concluded that the product code decoded by ten and twenty interactive iterations has similar performance to polar-TPC decoded by the SCL-Chase algorithm with the list size of L=8 and L=32, respectively.Figure 10
BER performance of (2562, 2392) codes.


## 6. Conclusions and Future Work

The paper presented a product coding scheme of polar codes formed by two different rates of polar codes. The conducted analysis and simulation results confirmed that the constructed product codes outperform the conventional polar codes. This is mainly evident in the medium to high signal-to-noise ratios, which is applicable for both nonpunctured and punctured codes. In the future work, a modification of the structure of punctured product polar codes will be followed aimed at improving their performance.



---

*Source: 7573147-2020-04-13.xml*