# Performance Analysis of CRC Codes for Systematic and Nonsystematic Polar Codes with List Decoding

Authors: Takumi Murata; Hideki Ochiai
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Successive cancellation list (SCL) decoding of polar codes is an effective approach that can significantly outperform the original successive cancellation (SC) decoding, provided that proper cyclic redundancy-check (CRC) codes are employed at the stage of candidate selection. Previous studies on CRC-assisted polar codes mostly focus on improvement of the decoding algorithms as well as their implementation, and little attention has been paid to the CRC code structure itself. For the CRC-concatenated polar codes with CRC code as their outer code, the use of longer CRC code leads to reduction of information rate, whereas the use of shorter CRC code may reduce the error detection probability, thus degrading the frame error rate (FER) performance. Therefore, CRC codes of proper length should be employed in order to optimize the FER performance for a given signal-to-noise ratio (SNR) per information bit. In this paper, we investigate the effect of CRC codes on the FER performance of polar codes with list decoding in terms of the CRC code length as well as its generator polynomials. Both the original nonsystematic and systematic polar codes are considered, and we also demonstrate that different behaviors of CRC codes should be observed depending on whether the inner polar code is systematic or not.


---

## Body

## 1. Introduction

Polar codes, proposed by Arıkan [1], are known to achieve the symmetric capacity for any given binary-input memoryless channels (B-MCs) with low complexity at both encoder and decoder. Polar codes are characterized bychannel polarization which is caused by channel splitting and channel combining, and information bits are transmitted over good channels. To identify those channels accurately, first Arıkan proposed a technique which recursively updates mutual information of the channels. However, complete estimation of mutual information can be performed over the binary erasure channel only. Therefore, several researchers proposed channel estimation techniques such as density evolution [2], Gaussian approximation [3], and channel upgrading/degrading [4]. Their performance, however, turn out to be inferior to modern capacity approaching codes such as turbo and low-density parity-check (LDPC) codes when they are compared under the constraint of the same block length.Various types of decoding algorithms have been proposed for polar codes, such as successive cancellation list (SCL) [5, 6], belief propagation [7], and linear program [8]. In particular, it is well known that the SCL decoder can significantly improve the performance of the polar codes. Furthermore, based on the observation that the correct codeword is in the list but not necessarily the most likely one, Tal and Vardy proposed the use of error detecting codes, such as cyclic redundancy-check (CRC) codes, in order to identify the correct codeword from the list. The effectiveness of such CRC-assisted SCL decoder has been subsequently recognized by several other researchers [9, 10]. Software implementation of its fast decoder has been also developed in [11].The performance of the polar codes concatenated with CRC code as its outer code, together with the list decoding and CRC code detection (or list-CRC decoding [11]), depends on the length of the CRC code and its generator polynomial. To date, however, little attention has been paid to the structure of CRC codes themselves. Most of the preceding studies employ the CRC codes with 16 bits or longer and their length has been determined empirically. Otherwise, perfect error detection capability is assumed for simulation purpose, assuming thatideal CRC codes are employed. Nevertheless, if the block length of the code is short, the relative redundancy associated with CRC codes becomes dominant and thus reduces the overall efficiency of the concatenated code. The CRC code design for convolutional codes has been recently studied in [12], where the optimal CRC codes are identified by developing the equivalent composite convolutional codes based on combination of the original convolutional codes and CRC codes. More recently, an optimal CRC search algorithm for polar codes by using SCL decoder is developed in [13]. However, identifying the best CRC code length for the concatenated polar coding system has remained unknown. In this work, therefore, we attempt to analyze the effect of the CRC code length on the resulting frame error rate (FER) performance of the concatenated polar codes with list-CRC decoding. We first show that the miss-detection error probability of the CRC codes that depends on theirlength directly leads to degradation in terms of the FER performance. We also demonstrate that even if the length of CRC codes is identical, the performance of the list-CRC decoding may be affected by the generator polynomials of CRC codes employed.Systematic polar coding, also proposed by Arıkan [14], is an effective approach to improve the performance of the conventional polar codes in terms ofbit error rate (BER). However, the price of the systematic polar codes is their additional processing complexity that requires the SC decoding at the encoder side. Later, a simpler encoding scheme has been proposed in [15], where the conventional polar encoding is employed twice, instead of the SC decoder. Other efficient encoding schemes are proposed more recently in [16], where the three encoding implementations are described based on the trade-off between time and space complexity. In this work, we also address the CRC code property requirement for systematic polar codes. Based on the fact that the distance spectrum property of the systematic polar codes is different from that of the nonsystematic ones [17], we demonstrate that the CRC code structure suitable for systematic polar codes is different from that for the original nonsystematic codes.This paper is organized as follows. In Section2, the system model considered throughout the paper is described. Section 3 develops the relationship between the CRC code length and the resulting FER performance of the concatenated polar codes with the list-CRC decoder. In Section 4, the analytical results developed are compared with the corresponding simulations. Finally, Section 5 concludes the paper. We note that our initial results on the conventional nonsystematic polar codes are reported in the conference paper [18]. This paper is its considerable extension including the systematic polar codes and their distance spectrum properties.


## 2. System Model

We consider the binary polar codes concatenated with a binary CRC code at the transmitter, together with their SCL decoding at the receiver. Information bits of lengthk are first encoded by CRC encoder to generate K=k+r bits, where the parity bits of length r are appended by the cyclic encoder for the purpose of correct information identification at the decoder. This output sequence (i.e., CRC codeword) is encoded by the inner polar encoder to generate the binary codeword of length N. This is modulated by binary phase-shift keying (BPSK) and transmitted over an additive white Gaussian noise (AWGN) channel. At the receiver, the likelihood is calculated from the received signal and then passed to the list-CRC decoder, where L survived paths (codeword candidates) from the list decoder are tested by CRC detector starting from the most likely path. When the candidate codeword is determined to be correct by the CRC detector, the corresponding k information bits are considered as the transmitted information bits.


### 2.1. Polar Codes

Following the notation of [1], let W:X→Y denote a binary-input memoryless channel (B-MC) with input alphabet X={0,1} and output alphabet Y. We denote the corresponding channel transition probability as Wy∣x, where x∈X and y∈Y.The polar encoding is denoted byx1N=u1NGN, where x1N=(x1,x2,…,xN)∈{0,1}N is the codeword, u1N=(u1,u2,…,uN)∈0,1N is the information block, and GN is the generator matrix of the polar codes, which is the mapping function of XN→XN [1]. The generator matrix is represented by the following recursive form:(1)GN=BNF2⊗n,F2=1011,where n=log2N, F⊗n denotes the nth Kronecker power of F, and BN is the bit-reversal permutation matrix.Polar codes combine theN input binary channels at the encoder and then split them at the decoder. After the channel combining and splitting processes, the set of N binary-input coordinate channels, referred to asbit channels and commonly denoted by WN(i):X→YN×Xi-1 for 1≤i≤N, can be expressed as(2)WNiy1N,u1i-1∣ui≜∑ui+1N∈XN-i12N-1WNy1N∣u1N,WNy1N∣u1N=∏i=1NWyi∣xi,where the set of the vectors (y1N,u1i-1) corresponds to the output of the channel WN(i) and ui is its input.Due to the channel combining and splitting operation, the mutual information of the bit channel,I(WN(i)), polarizes to either 0 or 1. Polar codes select K out of N bit positions as information bits based on their channel reliabilities. We denote the set of the selected channels for information transmission as A⊂{1,2,…,N}. Its complement Ac contains thefrozen bits that are known to the receiver a priori and thus are not transmitted. The code rate of the polar codes is thus given by K/N.


### 2.2. Concatenated Encoder

As an outer code, the CRC sequence of lengthr bits is added to the information sequence. This CRC code is of rate k/(k+r) and thus the effective rate of the polar code is K/N=(k+r)/N but only k bits represent information. Therefore, increasing r for better error detection performance may lead to increased code rate and thus reduction of the error correcting capability of the inner polar code. Hence, the redundancy introduced by the CRC code should be designed carefully, especially when the block length N is relatively short.


### 2.3. List-CRC Decoding

Polar codes with SC decoding are proved to achieve channel capacity for any binary-input memoryless channels. For a given channel indexi with 1≤i≤N, the estimated bit u^i that corresponds to ui is expressed as(3)u^i=arg⁡maxui⁡WNiy1N,u^1i-1∣ui,fori∈A,0,fori∈Ac,where y1N=(y1,y2,…,yN) is the received symbol vector and u^1i-1=(u^1,u^2,…,u^i-1) is the previously estimated bit vector with respect to the ith bit.SCL decoding searches a limited number of paths that correspond to the input bits in a tree diagram; that is, it retains at mostL candidates in parallel [5, 6] for some positive integer L that represents the list size.When theL most likely paths are determined at the final stage, the path that holds the highest likelihood is chosen as the most reliable path and its information sequence is tested by CRC detector (which is referred to as aCRC test in what follows). If the CRC test indicates that the most likely candidate is incorrect, the candidate with the second highest likelihood will be tested. This process is iterated until any of the candidates that pass the CRC test is found, or all the L candidates are tested.Although the use of CRC codes should improve the performance, increasing the length of CRC bits should reduce the efficiency as mentioned in the previous subsection. On the other hand, if the CRC code length is not sufficient, it may erroneously detect the incorrect candidate as correct one. Therefore, there should be a trade-off in the length of CRC code, which will be elaborated in the next section.


### 2.4. Systematic Encoding

For a systematic code, each codeword can be explicitly formed by the information bits and parity bits. In many conventional block codes, a systematic encoding structure is adopted for its practical advantage upon retrieval of information bits from the decoded codeword. On the other hand, the original polar codes described in Section2.1 have a nonsystematic structure. However, it has been shown that systematic polar coding [14] outperforms the original polar codes in terms of BER even though the FER performance remains identical.For systematic polar encoding, there are largely two encoding approaches. The first approach is the basic technique for general linear codes where the parity bits are identified from the generator matrix, and the second one is to employ the SC decoder as a part of encoding process, which is briefly described as follows: letx1N={xA,xAc} be a codeword vector, where xA denotes a part of the codeword corresponding to information index and xAc denotes the corresponding parity bits. First, information sequence u1K is set as xA and all the bits in xAc are set as erased bits, and then decoding of the codeword is performed by the SC decoder. Consequently, we obtain a temporary information sequence u′1N={u′A,u′Ac}, and then xAc is determined by encoding the temporary sequence u′1N.


## 2.1. Polar Codes

Following the notation of [1], let W:X→Y denote a binary-input memoryless channel (B-MC) with input alphabet X={0,1} and output alphabet Y. We denote the corresponding channel transition probability as Wy∣x, where x∈X and y∈Y.The polar encoding is denoted byx1N=u1NGN, where x1N=(x1,x2,…,xN)∈{0,1}N is the codeword, u1N=(u1,u2,…,uN)∈0,1N is the information block, and GN is the generator matrix of the polar codes, which is the mapping function of XN→XN [1]. The generator matrix is represented by the following recursive form:(1)GN=BNF2⊗n,F2=1011,where n=log2N, F⊗n denotes the nth Kronecker power of F, and BN is the bit-reversal permutation matrix.Polar codes combine theN input binary channels at the encoder and then split them at the decoder. After the channel combining and splitting processes, the set of N binary-input coordinate channels, referred to asbit channels and commonly denoted by WN(i):X→YN×Xi-1 for 1≤i≤N, can be expressed as(2)WNiy1N,u1i-1∣ui≜∑ui+1N∈XN-i12N-1WNy1N∣u1N,WNy1N∣u1N=∏i=1NWyi∣xi,where the set of the vectors (y1N,u1i-1) corresponds to the output of the channel WN(i) and ui is its input.Due to the channel combining and splitting operation, the mutual information of the bit channel,I(WN(i)), polarizes to either 0 or 1. Polar codes select K out of N bit positions as information bits based on their channel reliabilities. We denote the set of the selected channels for information transmission as A⊂{1,2,…,N}. Its complement Ac contains thefrozen bits that are known to the receiver a priori and thus are not transmitted. The code rate of the polar codes is thus given by K/N.


## 2.2. Concatenated Encoder

As an outer code, the CRC sequence of lengthr bits is added to the information sequence. This CRC code is of rate k/(k+r) and thus the effective rate of the polar code is K/N=(k+r)/N but only k bits represent information. Therefore, increasing r for better error detection performance may lead to increased code rate and thus reduction of the error correcting capability of the inner polar code. Hence, the redundancy introduced by the CRC code should be designed carefully, especially when the block length N is relatively short.


## 2.3. List-CRC Decoding

Polar codes with SC decoding are proved to achieve channel capacity for any binary-input memoryless channels. For a given channel indexi with 1≤i≤N, the estimated bit u^i that corresponds to ui is expressed as(3)u^i=arg⁡maxui⁡WNiy1N,u^1i-1∣ui,fori∈A,0,fori∈Ac,where y1N=(y1,y2,…,yN) is the received symbol vector and u^1i-1=(u^1,u^2,…,u^i-1) is the previously estimated bit vector with respect to the ith bit.SCL decoding searches a limited number of paths that correspond to the input bits in a tree diagram; that is, it retains at mostL candidates in parallel [5, 6] for some positive integer L that represents the list size.When theL most likely paths are determined at the final stage, the path that holds the highest likelihood is chosen as the most reliable path and its information sequence is tested by CRC detector (which is referred to as aCRC test in what follows). If the CRC test indicates that the most likely candidate is incorrect, the candidate with the second highest likelihood will be tested. This process is iterated until any of the candidates that pass the CRC test is found, or all the L candidates are tested.Although the use of CRC codes should improve the performance, increasing the length of CRC bits should reduce the efficiency as mentioned in the previous subsection. On the other hand, if the CRC code length is not sufficient, it may erroneously detect the incorrect candidate as correct one. Therefore, there should be a trade-off in the length of CRC code, which will be elaborated in the next section.


## 2.4. Systematic Encoding

For a systematic code, each codeword can be explicitly formed by the information bits and parity bits. In many conventional block codes, a systematic encoding structure is adopted for its practical advantage upon retrieval of information bits from the decoded codeword. On the other hand, the original polar codes described in Section2.1 have a nonsystematic structure. However, it has been shown that systematic polar coding [14] outperforms the original polar codes in terms of BER even though the FER performance remains identical.For systematic polar encoding, there are largely two encoding approaches. The first approach is the basic technique for general linear codes where the parity bits are identified from the generator matrix, and the second one is to employ the SC decoder as a part of encoding process, which is briefly described as follows: letx1N={xA,xAc} be a codeword vector, where xA denotes a part of the codeword corresponding to information index and xAc denotes the corresponding parity bits. First, information sequence u1K is set as xA and all the bits in xAc are set as erased bits, and then decoding of the codeword is performed by the SC decoder. Consequently, we obtain a temporary information sequence u′1N={u′A,u′Ac}, and then xAc is determined by encoding the temporary sequence u′1N.


## 3. Performance Analysis of List-CRC Decoding

The exact performance analysis of SC decoding is challenging due to correlation between codeword bits. For a binary erasure channel (BEC), Parizi and Telatar have shown that the correlations between the erasure events decay fast and thus the union bound on the frame error probability becomes tight as the codeword length increases [19]. More recently, Shuval and Tal have derived an improved lower bound for a binary memoryless symmetric channel based on the correlation between the codeword bits [20].In this section, we analyze the performance of the list-CRC decoding for a given length of CRC bitsr, provided that the statistical distribution of the correct candidate in the list is available. We note that the distribution itself is difficult to analyze, and thus we simply assume that it is obtained by resorting to Monte-Carlo simulation based on the conventional list decoding without concatenation of error detecting codes.


### 3.1. Ideal Decoding Error Probability

LetCp⊂XN denote the (N,k+r) polar code as our inner code and let Cc⊂Xk+r denote a set of the codewords encoded by r-bit CRC encoder as our outer code.For a given information sequenceu1k∈Xk, c1k+r∈Cc represents the corresponding CRC codeword. Likewise, we denote the codeword of polar codes by x1N∈Cp.For a given received sequencey1N∈YN, the estimated codeword of list decoder c^1k+r is expressed by(4)c^1k+r=arg⁡maxcA∈Cc⁡WNy1N∣cA,cAc,where cA and cAc are the vectors corresponding to information and frozen bits, respectively, and the resulting estimated information sequence u^1k is denoted by(5)u^1k=Icc^1k+r,where Ic(·) is the decoding operation of Cc which maps Xk+r→Xk.LetL denote the number of the candidate codewords generated by the list decoder, let L={1,2,…,L} be a set of indices in the list, and let l⋆ denote the list index which corresponds to the correct codeword. Here, without loss of generality we assume that smaller indices correspond to more likely candidates. If the correct codeword is not in the list, that is, l⋆∉L, we assume that l⋆>L. Moreover, let pl⋆(γ,l) = the probability conditioned on γ, that is, Pr⁡{l⋆=l∣γ} denote the distribution of l⋆, that is, the probability that the index l⋆ agrees with l at a given SNR γ=Eb/N0 over an AWGN channel.If we assume the ideal case where the correct codeword in the list can be identified without error, the ideal decoding error probabilityPe,id(γ,L) is expressed as(6)Pe,idγ,L=1-∑l=1Lpl⋆γ,l.


### 3.2. Undetected Error Probability of CRC Codeword

The CRC test may fail with a certain probabilityPud (i.e., undetected error probability of the CRC codeword). As Pud increases, the error correcting performance of the concatenated polar codes may be degraded.In general, the undetected error probability of the codeCc over a binary symmetric channel (BSC) with crossover probability p∈[0,1/2] is given by [21](7)PudCc,p=∑i=1k+rAipi1-pk+r-i,where Ai(1≤i≤k+r) is the weight distribution of Cc. We note that the CRC code Cc may be calledgood if the relationship(8)PudCc,p≤PudCc,12=2k-12k+r≈12rholds for all p [21]. The upper bound of (8) may be also achieved if all the binary sequences of length k+r; that is, all the elements of Xk+r may appear in the list with equal probability [22] (in other words, the candidates in the list are modeled ascompletely random strings [22]).The major challenge in analyzing the probabilityPud in the case of polar codes with list-CRC decoding is that, due to the correlation among the codewords, the binary sequences in the list may be also correlated. Nevertheless, as mentioned in [22], the upper bound of Pud in (8) would be a good estimate of the probability of the undetected error, provided that the minimum distance of CRC code is much lower than that of the candidates in the list.


### 3.3. Approximate Upper Bound on Decoding Error Probability

Given the above undetected error probability model of CRC code, the probability of correct detection by the CRC test is lower bounded as(9)Pcd=1-Pud≥1-2k-12k+r.On theL-candidate list decoding, if the lth estimate codeword is correct, all the codewords up to the (l-1)th list should be incorrect. In other words, all the (l-1) codewords must be correctly detected as invalid codewords by the CRC test and each probability is bounded by (9). Hence, the correct decoding probability Pc(γ,L) is expressed as(10)Pcγ,L=pl⋆γ,1+∑l=2Lpl⋆γ,l∏l′=1l-1Pr⁡c1k+rl′∉Cc∣l⋆=l≥pl⋆γ,1+∑l=2Lpl⋆γ,l∏l′=1l-11-2k-12k+r-l′-1,where c1k+r(l) is the lth estimate vector of polar codes in the list and the term 2k+r-(l′-1) corresponds to the number of remaining binary sequences of length k+r prior to the l′th CRC test. Since 2k+r≫L, we may express(11)Pcγ,L≳∑l=1Lpl⋆γ,l1-2-rl-1.Thus, the approximate upper bound of the decoding error probability for the list CRC-concatenated system Pe(γ,L) with the candidates ofcompletely random strings is expressed as(12)Peγ,L=1-Pcγ,L≲1-∑l=1Lpl⋆γ,l1-2-rl-1≈1-∑l=1Lpl⋆γ,l1-l-12-r(13)=Pe,idγ,L+2-r∑l=1Lpl⋆γ,ll-1︸≜Pγ,r,L.We observe that the first term in (13) corresponds to the ideal error performance when CRC test is perfect and is derived in (6), whereas the second term P(γ,r,L) in (13) is the performance degradation associated with the imperfect CRC code, which can be reduced by increasing the redundant bit length r. Therefore, we should select r such that P(γ,r,L) is negligible compared to Pe,id(γ,L).


## 3.1. Ideal Decoding Error Probability

LetCp⊂XN denote the (N,k+r) polar code as our inner code and let Cc⊂Xk+r denote a set of the codewords encoded by r-bit CRC encoder as our outer code.For a given information sequenceu1k∈Xk, c1k+r∈Cc represents the corresponding CRC codeword. Likewise, we denote the codeword of polar codes by x1N∈Cp.For a given received sequencey1N∈YN, the estimated codeword of list decoder c^1k+r is expressed by(4)c^1k+r=arg⁡maxcA∈Cc⁡WNy1N∣cA,cAc,where cA and cAc are the vectors corresponding to information and frozen bits, respectively, and the resulting estimated information sequence u^1k is denoted by(5)u^1k=Icc^1k+r,where Ic(·) is the decoding operation of Cc which maps Xk+r→Xk.LetL denote the number of the candidate codewords generated by the list decoder, let L={1,2,…,L} be a set of indices in the list, and let l⋆ denote the list index which corresponds to the correct codeword. Here, without loss of generality we assume that smaller indices correspond to more likely candidates. If the correct codeword is not in the list, that is, l⋆∉L, we assume that l⋆>L. Moreover, let pl⋆(γ,l) = the probability conditioned on γ, that is, Pr⁡{l⋆=l∣γ} denote the distribution of l⋆, that is, the probability that the index l⋆ agrees with l at a given SNR γ=Eb/N0 over an AWGN channel.If we assume the ideal case where the correct codeword in the list can be identified without error, the ideal decoding error probabilityPe,id(γ,L) is expressed as(6)Pe,idγ,L=1-∑l=1Lpl⋆γ,l.


## 3.2. Undetected Error Probability of CRC Codeword

The CRC test may fail with a certain probabilityPud (i.e., undetected error probability of the CRC codeword). As Pud increases, the error correcting performance of the concatenated polar codes may be degraded.In general, the undetected error probability of the codeCc over a binary symmetric channel (BSC) with crossover probability p∈[0,1/2] is given by [21](7)PudCc,p=∑i=1k+rAipi1-pk+r-i,where Ai(1≤i≤k+r) is the weight distribution of Cc. We note that the CRC code Cc may be calledgood if the relationship(8)PudCc,p≤PudCc,12=2k-12k+r≈12rholds for all p [21]. The upper bound of (8) may be also achieved if all the binary sequences of length k+r; that is, all the elements of Xk+r may appear in the list with equal probability [22] (in other words, the candidates in the list are modeled ascompletely random strings [22]).The major challenge in analyzing the probabilityPud in the case of polar codes with list-CRC decoding is that, due to the correlation among the codewords, the binary sequences in the list may be also correlated. Nevertheless, as mentioned in [22], the upper bound of Pud in (8) would be a good estimate of the probability of the undetected error, provided that the minimum distance of CRC code is much lower than that of the candidates in the list.


## 3.3. Approximate Upper Bound on Decoding Error Probability

Given the above undetected error probability model of CRC code, the probability of correct detection by the CRC test is lower bounded as(9)Pcd=1-Pud≥1-2k-12k+r.On theL-candidate list decoding, if the lth estimate codeword is correct, all the codewords up to the (l-1)th list should be incorrect. In other words, all the (l-1) codewords must be correctly detected as invalid codewords by the CRC test and each probability is bounded by (9). Hence, the correct decoding probability Pc(γ,L) is expressed as(10)Pcγ,L=pl⋆γ,1+∑l=2Lpl⋆γ,l∏l′=1l-1Pr⁡c1k+rl′∉Cc∣l⋆=l≥pl⋆γ,1+∑l=2Lpl⋆γ,l∏l′=1l-11-2k-12k+r-l′-1,where c1k+r(l) is the lth estimate vector of polar codes in the list and the term 2k+r-(l′-1) corresponds to the number of remaining binary sequences of length k+r prior to the l′th CRC test. Since 2k+r≫L, we may express(11)Pcγ,L≳∑l=1Lpl⋆γ,l1-2-rl-1.Thus, the approximate upper bound of the decoding error probability for the list CRC-concatenated system Pe(γ,L) with the candidates ofcompletely random strings is expressed as(12)Peγ,L=1-Pcγ,L≲1-∑l=1Lpl⋆γ,l1-2-rl-1≈1-∑l=1Lpl⋆γ,l1-l-12-r(13)=Pe,idγ,L+2-r∑l=1Lpl⋆γ,ll-1︸≜Pγ,r,L.We observe that the first term in (13) corresponds to the ideal error performance when CRC test is perfect and is derived in (6), whereas the second term P(γ,r,L) in (13) is the performance degradation associated with the imperfect CRC code, which can be reduced by increasing the redundant bit length r. Therefore, we should select r such that P(γ,r,L) is negligible compared to Pe,id(γ,L).


## 4. Simulation Results

In this section, we investigate the FER performance of the CRC-concatenated nonsystematic and systematic polar codes with list-CRC decoding through various simulations with emphasis on the difference in the CRC code length as well as its generator polynomials. Throughout simulations, we employ BPSK for modulation and the channel model is AWGN. The polar codes simulated are designed according to [2] with design-SNR REb/N0=-1.5917 dB (as proposed in [23]), where R is the rate of the inner polar codes. The list size of the SCL decoding is chosen as L=32. We also consider the fixed spectral efficiency scenario where the code rate of the entire system is 1/2. This is achieved by setting the parameters of polar codes as (N,N/2+r) with N and r representing the code length of the polar code and the redundant bits imposed by the CRC code, respectively. Therefore, increasing CRC code length (for better list-CRC decoding performance) leads to an increment of the code rate of polar codes with no effective increase of information bits, which in turn reduces the error correction capability. Therefore, it should reveal the trade-off relationship.


### 4.1. Comparison of CRC Code Length

We first examine the trade-off between the CRC code length and the code rate of polar codes. In what follows, we describe the generator polynomial of CRC encoders by the hexadecimal representation; for example, the notation 0x8810 for 16-bit CRC encoder indicates1000100000010000 in binary representation, which corresponds to x16+x12+x5, and addition of the implicit “+1” term specifies the generator polynomial of g(x)=x16+x12+x5+1 [24].Figures1 and 2 compare the FER performance of the conventional nonsystematic polar codes with code lengths N=512 and 2048, respectively, where the CRC code length r is chosen from 4, 8, 10, and 16. In this example, only the results with the CRC polynomials that are found to be best among those compared for each r are shown.Figure 1
FER performance of list-CRC decoding with various lengths of CRC code with the code lengthN=512.Figure 2
FER performance of list-CRC decoding with various lengths of CRC with the code lengthN=2048.From the results withN=512 shown in Figure 1, because of the loss in terms of code rate, the case of CRC-16, which is a commonly adopted scenario in the study of CRC-concatenated polar codes, turns out to be inferior to that of CRC-10. Therefore, the negative effect of the rate loss associated with the CRC code length becomes dominant compared to the improvement achieved by the reduction of the undetected error probability Pud for the short polar codes. On the other hand, when N=2048, the performance gap between CRC-16 and CRC-10 becomes smaller as observed in Figure 2. This stems from the fact that as N increases the effect of the relative loss in the code rate becomes negligibly small.For both cases, the performance loss due to the miss-detection of CRC codes becomes noticeable whenr is small.


### 4.2. Performance Comparison of Analytical and Simulation Results

We next examine the validity of the FER upper bound expression given by (12). We first obtain the statistical distribution of the correct paths l⋆ by Monte-Carlo simulation (without concatenating CRC code). This has been done by counting the locations of the correct paths through the simulation of 107 trials. We note that the precise FER performance depends on the particular realization of the polar codes, and hence its theoretical characterization should be challenging. It is thus left as future work.


#### 4.2.1. Comparison with Generator Polynomials for Nonsystematic Polar Codes

We first consider the case ofN=2048 and r=8 for nonsystematic polar codes. We have selected two specific groups of generator polynomials of CRC codes: (1) all the eighth-order primitive polynomials and (2) all the seventh-order primitive polynomials multiplied by (x+1). The multiplication of the factor (x+1) makes the CRC detector capable of detecting all the odd Hamming weight errors and thus is found to be preferable in some applications. Also, the cases where we insert a random interleaver after CRC encoder are considered where the block diagram of this particular scenario is depicted in Figure 3.Figure 3
A block diagram of the CRC-concatenated polar codes with an interleaver.The results for the generator polynomials consisting of all the eighth-order primitive polynomials are compared in Figure4. We observe that without interleaving, some specific CRC polynomials may poorly perform compared to the analytical results. This may be caused by the fact that bit error patterns due to the SC decoder, namely, the sequences in the list, and the distance property of the CRC codes do not match well for this system. However, with interleaving, the resulting performance becomes similar and comparable with the analytical result (derived based on the assumption of the list withcompletely random strings).Figure 4
Comparison of FER performances between the analytical bound and full simulations for list-CRC decoding with the CRC codes based on the eighth-order primitive polynomials. The dashed line represents the analytical result. The dotted and solid lines correspond to the simulation results with and without interleaving, respectively.The results for the seventh-order primitive polynomials multiplied by(x+1) are compared in Figure 5. In this case, all the simulation results without insertion of interleaver are inferior to the analytical bound as opposed to the results in Figure 4. Insertion of interleavers may mitigate this gap, but we still observe that the performance achieved by the CRC codes designed in this manner will be poor compared to the cases shown in Figure 4. Therefore, the introduction of the term (x+1) of the CRC polynomial, which makes all the odd-weight errors detectable, may not be effective in the case of the investigated nonsystematic polar codes. The reason for this behavior will be elucidated through the comparison with the systematic polar codes in what follows.Figure 5
Comparison of FER performances between the analytical bounds and full simulations for list-CRC decoding with CRC codes based on the seventh-order primitive polynomials multiplied by(x+1). The dashed line represents the analytical result. The dotted and solid lines correspond to the simulation results with and without interleaving, respectively.


#### 4.2.2. Comparison with Generator Polynomials for Systematic Polar Codes

We next consider the case of systematic polar coding, where all the parameters are chosen identically to the previous results with nonsystematic encoding. The results for the eighth-order primitive polynomials are compared in Figure6. These results show that the concatenated polar coding systems, both with and without interleaver, agree with the analytical result.Figure 6
Comparison of FER performances between the analytical bound and full simulations for systematic polar codes and list-CRC decoding with the CRC codes based on the eighth-order primitive polynomials. The dotted and solid lines correspond to the simulation results with and without interleaving, respectively.The results for the seventh-order primitive polynomials multiplied by(x+1) are compared in the case of systematic polar codes in Figure 7. In contrast to the results of nonsystematic polar codes shown in Figure 5, the systematic polar codes are not affected by whether the factor (x+1) is present or not in the generator polynomial of the CRC codes. This performance difference between two encoding approaches can be explained by the input-output weight enumerator function (IOWEF) of polar codes.Figure 7
Comparison of FER performances between the analytical bounds and full simulations for systematic polar codes and list-CRC decoding with the CRC codes based on the seventh-order primitive polynomials multiplied by(x+1). The dotted and solid lines correspond to the simulation results with and without interleaving, respectively.In Table1, for the codeword of the polar codes with the first and second lowest Hamming weights (i.e., d=8 and 16 in our case), the corresponding numbers of the odd and even Hamming weight information sequences are compared. The IOWEF is calculated by the method based on SCL decoding with generation of huge list size as proposed in [17], and the associated parameters here are set as N=512, R=1/2, and L=220. The result of the conventional nonsystematic polar codes in the table indicates that the even-weight input sequence is dominant when the minimum Hamming weight codeword is generated, whereas the numbers of odd and even-weight input sequences are equal in the case of systematic polar codes. As the SNR increases, the candidate codewords are dominated by those with the minimum Hamming weight. Therefore, for the nonsystematic polar codes where the even-weight errors occur frequently, the use of the CRC polynomials with the factor (x+1), which are capable of detecting all the odd-weight errors, becomes ineffective. On the other hand, since the systematic polar codes have balanced minimum Hamming weights of even and odd, the inclusion of the factor (x+1) may not affect the undetected error probability.Table 1
The number of even and odd weight inputs with code lengthN=512, code rate R=1/2, and list size L=220.
Output weight d m i n = 8 d = 16 Input weight Odd Even Odd Even Nonsystematic 1 63 3470 114297 Systematic 32 32 55840 62114


## 4.1. Comparison of CRC Code Length

We first examine the trade-off between the CRC code length and the code rate of polar codes. In what follows, we describe the generator polynomial of CRC encoders by the hexadecimal representation; for example, the notation 0x8810 for 16-bit CRC encoder indicates1000100000010000 in binary representation, which corresponds to x16+x12+x5, and addition of the implicit “+1” term specifies the generator polynomial of g(x)=x16+x12+x5+1 [24].Figures1 and 2 compare the FER performance of the conventional nonsystematic polar codes with code lengths N=512 and 2048, respectively, where the CRC code length r is chosen from 4, 8, 10, and 16. In this example, only the results with the CRC polynomials that are found to be best among those compared for each r are shown.Figure 1
FER performance of list-CRC decoding with various lengths of CRC code with the code lengthN=512.Figure 2
FER performance of list-CRC decoding with various lengths of CRC with the code lengthN=2048.From the results withN=512 shown in Figure 1, because of the loss in terms of code rate, the case of CRC-16, which is a commonly adopted scenario in the study of CRC-concatenated polar codes, turns out to be inferior to that of CRC-10. Therefore, the negative effect of the rate loss associated with the CRC code length becomes dominant compared to the improvement achieved by the reduction of the undetected error probability Pud for the short polar codes. On the other hand, when N=2048, the performance gap between CRC-16 and CRC-10 becomes smaller as observed in Figure 2. This stems from the fact that as N increases the effect of the relative loss in the code rate becomes negligibly small.For both cases, the performance loss due to the miss-detection of CRC codes becomes noticeable whenr is small.


## 4.2. Performance Comparison of Analytical and Simulation Results

We next examine the validity of the FER upper bound expression given by (12). We first obtain the statistical distribution of the correct paths l⋆ by Monte-Carlo simulation (without concatenating CRC code). This has been done by counting the locations of the correct paths through the simulation of 107 trials. We note that the precise FER performance depends on the particular realization of the polar codes, and hence its theoretical characterization should be challenging. It is thus left as future work.


### 4.2.1. Comparison with Generator Polynomials for Nonsystematic Polar Codes

We first consider the case ofN=2048 and r=8 for nonsystematic polar codes. We have selected two specific groups of generator polynomials of CRC codes: (1) all the eighth-order primitive polynomials and (2) all the seventh-order primitive polynomials multiplied by (x+1). The multiplication of the factor (x+1) makes the CRC detector capable of detecting all the odd Hamming weight errors and thus is found to be preferable in some applications. Also, the cases where we insert a random interleaver after CRC encoder are considered where the block diagram of this particular scenario is depicted in Figure 3.Figure 3
A block diagram of the CRC-concatenated polar codes with an interleaver.The results for the generator polynomials consisting of all the eighth-order primitive polynomials are compared in Figure4. We observe that without interleaving, some specific CRC polynomials may poorly perform compared to the analytical results. This may be caused by the fact that bit error patterns due to the SC decoder, namely, the sequences in the list, and the distance property of the CRC codes do not match well for this system. However, with interleaving, the resulting performance becomes similar and comparable with the analytical result (derived based on the assumption of the list withcompletely random strings).Figure 4
Comparison of FER performances between the analytical bound and full simulations for list-CRC decoding with the CRC codes based on the eighth-order primitive polynomials. The dashed line represents the analytical result. The dotted and solid lines correspond to the simulation results with and without interleaving, respectively.The results for the seventh-order primitive polynomials multiplied by(x+1) are compared in Figure 5. In this case, all the simulation results without insertion of interleaver are inferior to the analytical bound as opposed to the results in Figure 4. Insertion of interleavers may mitigate this gap, but we still observe that the performance achieved by the CRC codes designed in this manner will be poor compared to the cases shown in Figure 4. Therefore, the introduction of the term (x+1) of the CRC polynomial, which makes all the odd-weight errors detectable, may not be effective in the case of the investigated nonsystematic polar codes. The reason for this behavior will be elucidated through the comparison with the systematic polar codes in what follows.Figure 5
Comparison of FER performances between the analytical bounds and full simulations for list-CRC decoding with CRC codes based on the seventh-order primitive polynomials multiplied by(x+1). The dashed line represents the analytical result. The dotted and solid lines correspond to the simulation results with and without interleaving, respectively.


### 4.2.2. Comparison with Generator Polynomials for Systematic Polar Codes

We next consider the case of systematic polar coding, where all the parameters are chosen identically to the previous results with nonsystematic encoding. The results for the eighth-order primitive polynomials are compared in Figure6. These results show that the concatenated polar coding systems, both with and without interleaver, agree with the analytical result.Figure 6
Comparison of FER performances between the analytical bound and full simulations for systematic polar codes and list-CRC decoding with the CRC codes based on the eighth-order primitive polynomials. The dotted and solid lines correspond to the simulation results with and without interleaving, respectively.The results for the seventh-order primitive polynomials multiplied by(x+1) are compared in the case of systematic polar codes in Figure 7. In contrast to the results of nonsystematic polar codes shown in Figure 5, the systematic polar codes are not affected by whether the factor (x+1) is present or not in the generator polynomial of the CRC codes. This performance difference between two encoding approaches can be explained by the input-output weight enumerator function (IOWEF) of polar codes.Figure 7
Comparison of FER performances between the analytical bounds and full simulations for systematic polar codes and list-CRC decoding with the CRC codes based on the seventh-order primitive polynomials multiplied by(x+1). The dotted and solid lines correspond to the simulation results with and without interleaving, respectively.In Table1, for the codeword of the polar codes with the first and second lowest Hamming weights (i.e., d=8 and 16 in our case), the corresponding numbers of the odd and even Hamming weight information sequences are compared. The IOWEF is calculated by the method based on SCL decoding with generation of huge list size as proposed in [17], and the associated parameters here are set as N=512, R=1/2, and L=220. The result of the conventional nonsystematic polar codes in the table indicates that the even-weight input sequence is dominant when the minimum Hamming weight codeword is generated, whereas the numbers of odd and even-weight input sequences are equal in the case of systematic polar codes. As the SNR increases, the candidate codewords are dominated by those with the minimum Hamming weight. Therefore, for the nonsystematic polar codes where the even-weight errors occur frequently, the use of the CRC polynomials with the factor (x+1), which are capable of detecting all the odd-weight errors, becomes ineffective. On the other hand, since the systematic polar codes have balanced minimum Hamming weights of even and odd, the inclusion of the factor (x+1) may not affect the undetected error probability.Table 1
The number of even and odd weight inputs with code lengthN=512, code rate R=1/2, and list size L=220.
Output weight d m i n = 8 d = 16 Input weight Odd Even Odd Even Nonsystematic 1 63 3470 114297 Systematic 32 32 55840 62114


## 4.2.1. Comparison with Generator Polynomials for Nonsystematic Polar Codes

We first consider the case ofN=2048 and r=8 for nonsystematic polar codes. We have selected two specific groups of generator polynomials of CRC codes: (1) all the eighth-order primitive polynomials and (2) all the seventh-order primitive polynomials multiplied by (x+1). The multiplication of the factor (x+1) makes the CRC detector capable of detecting all the odd Hamming weight errors and thus is found to be preferable in some applications. Also, the cases where we insert a random interleaver after CRC encoder are considered where the block diagram of this particular scenario is depicted in Figure 3.Figure 3
A block diagram of the CRC-concatenated polar codes with an interleaver.The results for the generator polynomials consisting of all the eighth-order primitive polynomials are compared in Figure4. We observe that without interleaving, some specific CRC polynomials may poorly perform compared to the analytical results. This may be caused by the fact that bit error patterns due to the SC decoder, namely, the sequences in the list, and the distance property of the CRC codes do not match well for this system. However, with interleaving, the resulting performance becomes similar and comparable with the analytical result (derived based on the assumption of the list withcompletely random strings).Figure 4
Comparison of FER performances between the analytical bound and full simulations for list-CRC decoding with the CRC codes based on the eighth-order primitive polynomials. The dashed line represents the analytical result. The dotted and solid lines correspond to the simulation results with and without interleaving, respectively.The results for the seventh-order primitive polynomials multiplied by(x+1) are compared in Figure 5. In this case, all the simulation results without insertion of interleaver are inferior to the analytical bound as opposed to the results in Figure 4. Insertion of interleavers may mitigate this gap, but we still observe that the performance achieved by the CRC codes designed in this manner will be poor compared to the cases shown in Figure 4. Therefore, the introduction of the term (x+1) of the CRC polynomial, which makes all the odd-weight errors detectable, may not be effective in the case of the investigated nonsystematic polar codes. The reason for this behavior will be elucidated through the comparison with the systematic polar codes in what follows.Figure 5
Comparison of FER performances between the analytical bounds and full simulations for list-CRC decoding with CRC codes based on the seventh-order primitive polynomials multiplied by(x+1). The dashed line represents the analytical result. The dotted and solid lines correspond to the simulation results with and without interleaving, respectively.


## 4.2.2. Comparison with Generator Polynomials for Systematic Polar Codes

We next consider the case of systematic polar coding, where all the parameters are chosen identically to the previous results with nonsystematic encoding. The results for the eighth-order primitive polynomials are compared in Figure6. These results show that the concatenated polar coding systems, both with and without interleaver, agree with the analytical result.Figure 6
Comparison of FER performances between the analytical bound and full simulations for systematic polar codes and list-CRC decoding with the CRC codes based on the eighth-order primitive polynomials. The dotted and solid lines correspond to the simulation results with and without interleaving, respectively.The results for the seventh-order primitive polynomials multiplied by(x+1) are compared in the case of systematic polar codes in Figure 7. In contrast to the results of nonsystematic polar codes shown in Figure 5, the systematic polar codes are not affected by whether the factor (x+1) is present or not in the generator polynomial of the CRC codes. This performance difference between two encoding approaches can be explained by the input-output weight enumerator function (IOWEF) of polar codes.Figure 7
Comparison of FER performances between the analytical bounds and full simulations for systematic polar codes and list-CRC decoding with the CRC codes based on the seventh-order primitive polynomials multiplied by(x+1). The dotted and solid lines correspond to the simulation results with and without interleaving, respectively.In Table1, for the codeword of the polar codes with the first and second lowest Hamming weights (i.e., d=8 and 16 in our case), the corresponding numbers of the odd and even Hamming weight information sequences are compared. The IOWEF is calculated by the method based on SCL decoding with generation of huge list size as proposed in [17], and the associated parameters here are set as N=512, R=1/2, and L=220. The result of the conventional nonsystematic polar codes in the table indicates that the even-weight input sequence is dominant when the minimum Hamming weight codeword is generated, whereas the numbers of odd and even-weight input sequences are equal in the case of systematic polar codes. As the SNR increases, the candidate codewords are dominated by those with the minimum Hamming weight. Therefore, for the nonsystematic polar codes where the even-weight errors occur frequently, the use of the CRC polynomials with the factor (x+1), which are capable of detecting all the odd-weight errors, becomes ineffective. On the other hand, since the systematic polar codes have balanced minimum Hamming weights of even and odd, the inclusion of the factor (x+1) may not affect the undetected error probability.Table 1
The number of even and odd weight inputs with code lengthN=512, code rate R=1/2, and list size L=220.
Output weight d m i n = 8 d = 16 Input weight Odd Even Odd Even Nonsystematic 1 63 3470 114297 Systematic 32 32 55840 62114


## 5. Conclusion

In this work, we have investigated the performance of list-CRC decoder for CRC-concatenated polar codes. In particular, we have focused on the relationship between the FER performance and CRC code length by deriving the analytical bound of the FER. Furthermore, the effect of the generator polynomials of CRC codes on the polar code structure has been analyzed. Specifically, it has been firstly shown that there is a trade-off relationship between the FER performance and CRC code length when the overall code rate of the concatenated system is identical. In general, if the CRC is longer than necessary for a given target FER, the performance degradation will be expected due to the relative increase in the code rate of the inner polar codes. Secondly, it has been shown that the performance of the nonsystematic polar codes depends on the generator polynomials of CRC codes, and it is not effective in employing the term(x+1) that makes all the odd-weight errors detectable from the viewpoint of their distance spectrum properties. This is in contrast to the systematic polar codes, where the performance is robust against the structure of the CRC codes.



---

*Source: 7286909-2018-05-08.xml*