Telecommunication Systems (2023) 82:499–508

https://doi.org/10.1007/s11235-023-00996-5

Puncturing scheme for polar codes based on channel reliability

estimation
Tianwei Han1 · Meiyu Fu1 · Meiling Zhang1 · Guijun Hu1

Accepted: 19 February 2023 / Published online: 13 March 2023

© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2023

Abstract
The compiled code algorithms for polar codes, which were proposed by Arikan, are of low complexity, with excellent
performance for a given code length when using optimized decoding algorithms. They have attracted widespread attention
and gained popularity since its inception. The construction of punctured polar codes allows for more flexibility in coding,
making them suitable for a greater variety of scenarios. This paper proposes an improved puncturing scheme for polar codes.
With the constraints imposed by conventional punctured polar codes, the error probability of each polarized sub-channel is
then calculated on the basis of the channel reliability estimation methodology, so as to puncture the less reliable polarized
sub-channels. Furthermore, to achieve better decoding performance, this scheme sets the initial log-likelihood rate (LLR) of
the punctured bits to infinity (or negative infinity). The simulation outcomes indicate that the improved punctured polar codes
as proposed in this paper perform better than the conventional punctured polar codes.

Keywords Polar codes · Polar code construction · Puncturing · Channel reliability estimation

Abbreviations
1 Introduction
AWGN Additive white Gaussian noise
In 2009, Arikan first introduced the concept of “Polar Codes”
B-DMC Binary-input discrete memoryless channel
[1] and proved theoretically and rigorously that polar codes
BSC Binary-input symmetric channel
can “reach” the Shannon capacity in the binary-input discrete
BEC Binary erasure channel
memoryless channel (B-DMC), which is of great signifi-
BER Bit error ratio
cance for the implementation of channel coding and decoding
BP Belief propagation
techniques for high-capacity communication transmissions.
DE Density evolution
Nevertheless, due to the changing state of the transmission
FER Frame error rate
channel in practice, it is necessary to adjust the code length,
ISAP Information set approximation puncturing
coding rate, and other parameters of the polar code flexi-
LLR Log-likelihood rate
bly to accommodate such changes. For this reason, it is also
NUC Non-uniform channels
essential to puncture the length of the polar code.
NUPGA Non-uniform polarization base on Gaussaian
The code length puncturing schemes for polar codes can
approximation
be divided into three major categories: the first category is
PDF Probability density function
to modify the constructed matrix[2]of the code word, yet
QUP Quasi-uniform Puncturing
the code length of the polar code remains limited toN =
SC Successive cancellation
L n (n = 1, 2, ...), where L refers to the dimension of the
SNR Signal-to-noise rate
constructed matrix; the second category is to cascade polar
codes with LDPC or other linear grouping codes to construct
a class of cascade codes [3–4], which can result in a relatively
B Guijun Hu high complexity of compilation for cascade codes since the
hugj@jlu.edu.cn compilation of polar codes differs from that of other group-
ing codes; the third category is to remove the corresponding
1 College of Communication Engineering, Jilin University, rows or columns from the generated matrix of polar codes to
5372 Nanhu Road, Changchun 130012, China

123
500 T. Han et al.

constitute a new puncturing methodology for linear group- on the corresponding punctured bits at the decoding side,
ing codes. As this type of grouping code would not change and the initial log-likelihood rate at the decoding side can
the compilation structure of the polar code, it retains the low affect the information bits; and the higher the coding rate,
complexity of the compilation for polar codes, making it a the greater the effect of the QUP algorithm on the informa-
straightforward and pragmatic solution for puncturing the tion bits, hence the algorithm is applicable to low coding
code length of polar codes. rate conditions. Reference [9] suggested a low-complexity
The reference [5] first investigated the puncturing scheme polar code puncturing algorithm which is based on the QUP
for polar codes and presented a random puncturing scheme algorithm, yet the complexity is decreased at the expense of
and a stopping-tree puncturing scheme. The random punc- the performance of the polar code. The distribution of the
turing of polar codes, that is, randomly selecting the coded puncturing positions in this scheme in turn restricts the loca-
bits of the code word for puncturing, provides a high degree tion set of information bits on the information sequence side,
of randomness and unstable performance, which may lead and the structure of the decoder will most probably need to
to either excellent decoding performance or total failure in change accordingly when the number of punctures varies. To
decoding. The principle of the stopping-tree puncturing for preserve the polar effect of the punctured polar code as much
polar codes draws on the structure of the Tanner diagram for as possible while simultaneously reducing the complexity of
LDPC codes, resulting in the scheme being limited to decod- the search, Rongke Liu et al. presented a novel algorithm
ing with the belief propagation (BP) decoder corresponding [10] that constructs a new punctured polar code employing
to the Tanner diagram. Using the rest of the decoders does an algorithm based on a column with a weight of 1. The punc-
not work well, extending the limitations of such a scheme tured bits of the polar code are known by the decoder, and by
in practice. Both of these schemes are feasible under cer- setting the value of the punctured bits to a fixed value of 0 or 1
tain constraints, yet they do not take advantage of the unique at coding time, and filling its LLR at the decoding end to pos-
recursive properties of polar codes and are hence not optimal itive or negative infinity, the initial LLR at the decoding side
for puncturing. Reference [6] proposed a puncturing scheme of this methodology has less effect on the information bits
based on a simplified polar matrix employing an exhaustive than the QUP algorithm which is commonly used under high
search method, which requires no modification to the decoder coding rate conditions, and can preserve the polar effect of
structure, and ensures that the polar effect of the polar code the polar code to the maximum extent. Hence, this new punc-
is maximized after puncturing, with better performance than turing scheme [10] has been generally accepted and is widely
the random puncturing of the polar code proposed in refer- applied in the rate matching of polar codes.The polarization
ence [5]. However, due to the use of an exhaustive search theory is extended to non-uniform channels (NUC) by the ref-
algorithm, the complexity of the search method of reference erence [11], and the PC construction of arbitrary code length
[6] is higher than that of reference [5]; moreover, to get the can be implemented by NUPGA, where the transmission is
corresponding simplified polar matrix also requires the use of under an additive white Gaussian noise (AWGN) channel
an additional algorithm to calculate the corresponding frozen and successive cancellation (SC) decoding. However, better
sequence at the input side before calculating the actual coding performances can only be achieved by this method when the
structure to be used, and when the construction parameters code rate is under 1/2. The impact of punctured positions on
of the polar code are changed, the amount of calculation the fixed information set was investigated in the reference
required is even greater, making it disadvantageous to imple- [12], and an information set approximate puncturing (ISAP)
ment. Reference [7] demonstrated that to find the optimal algorithm was proposed accordingly. This algorithm sets a
puncturing pattern at the code word side, it is equivalent to certain amount of guard bits before the known information
first find the optimal puncturing pattern at the information bits to calculate the required puncturing pattern based on the
sequence side, and then derive the actual puncturing pattern actual transmission block length. Similarly, this approach is
at the code word side from the established mapping relation- suitable for code rates below 1/2 to achieve better perfor-
ship, presenting a heuristic algorithm. Specifically, it first mance. For each information bit at higher code rates, a metric
selects the puncturing pattern at the information sequence referred to as reliability score is defined in the reference
side, and then obtains the actual puncturing bit position at the [13] to determine punctured bit locations by maximizing the
code word side through the mapping relationship, however, it minimum reliability score. However, certain limitations are
ignores the impact of the puncturing on the remaining chan- imposed on the application of this approach, and the employ-
nel, which leads to the loss of polar effect of the polar code. ment of different weighting factors in the algorithm can lead
Reference [8] presented a quasi-uniform puncturing (QUP) to various performances.
algorithm, which demonstrated that the performance of the Once the channel is polarized, the worse sub-channel can
polar code after puncturing is better than that of the turbo have a significant impact on the bit error ratio (BER) perfor-
code in WCDMA or LTE wireless communication systems. mance of the polar code. For this reason, the critical issue
Nevertheless, the QUP algorithm has no prior information to enhance the performance of the punctured polar codes is

123
Puncturing scheme for polar codes... 501

how to develop a strategy for picking the worst sub-channel [15], Gaussian approximation methods [16] and Tal-Vardy’s
into the punctured bits. Rather than addressing this issue, the algorithm [17]. Originally, the polar code adopted the Bhat-
puncturing scheme [10] is constructed by directly eliminating tacharyya Parameter Z (W ) as a reliability measurement for
the last P rows and corresponding columns of the generated each sub-channel, with a higher Z (W ) indicating a less reli-
matrix G N , and setting the last P bits of the polar code with able channel. Each Z (W Ni ) can be calculated recursively with
code length N to frozen bits so as to get a punctured polar a complexity of O (N log N ) when channel W is a binary
code of code length M. When performing the corresponding erasure channel (BEC). There is, nevertheless, no precise
column deletion on the generated matrix G N , it is unable to method for calculating Z (W Ni ) for other channels, such as
effectively select the relatively worse sub-channel for dele- the binary-input symmetric channel (BSC) or the binary-
tion when encountering columns with the same weight. This input additive white Gaussian channel (BAWGNC). Hence,
paper draws on the puncturing method in the reference [10], Mori et al. proposed a method that employs a DE approach
however, the difference is that this paper introduces a channel to track the probability density function (PDF) of each sub-
reliability estimation method in the puncturing strategy [14], channel and thus estimate its error probability. This method is
which evaluates the reliability of each polar sub-channel by applicable to all types of B-DMCs. The transmission channel
calculating the error probability of each of them when cod- model for channel coding in most of the research scenarios
ing, so that the less reliable sub-channel corresponding to the is the BAWGN channel. The probability density function
column selected into the puncturing vector can be added into of the LLR in density evolution can be approximated by a
the frozen set. The simulation outcomes demonstrate that the cluster of Gaussian distributions with a variance double the
method can enhance the performance of the obtained punc- mean under the BAWGN channel, thus simplifying the cal-
tured polar codes to a certain extent. culation to a one-dimensional mean and significantly cutting
This paper is structured as follows: First, some preliminary the amount of calculation. This simplified calculation of the
studies of polar codes are summarized in Sect. 2; Subse- DE is referred to as the Gaussian approximation. For any
quently, an improved approach to reliability estimation and a binary-input symmetric channel model, the well-known Tal-
proposed improved puncturing pattern are presented in Sect. Vardy’s algorithm makes the original channel a degrading
3. In Sect. 4, the polar code performance of the punctur- channel and an upgrading channel by a degrading operation
ing pattern is evaluated and compared with existing patterns. and an upgrading operation, respectively. Both are signifi-
Finally, a conclusion for this work is presented in Sect. 5. cantly close to each other at various parameter levels and can
be used to approximate the original channel to solve the diffi-
culty of direct construction due to the exponential growth of
the code length of the polarized channel output code. Once
2 Preliminaries the reliability of each sub-channel has been determined, this
research then proceeds to bit mixing, which means that the
Owing to the polarization effect, the polar code performs K sub-channels with the highest reliability are selected to
channel union and splitting by using N independent copies transmit the information bit, while the other sub-channels
of
 the channel W to obtain  a new N post-split channel transmit the frozen bit. For this step, the output is the coded
(1) (2) (N )
W N , W N , ..., W N . As the code length N increases, the original bit u 1N . The generated matrix G N of the polar code is
post-split channels would develop to two extremes: a part of a square matrix, which can be described as G N = B N G ⊗n 2 ,
 
the sub-channels would converge to perfect channels, that is, 10
whereis the Kronecker product, G 2 = ,and B N is the
develop into noise-free channels with channel capacity con- 11
verging to 1; while the other part of the sub-channels would bit-inversion alignment matrix [1]. This yields the coded code
converge to completely noisy channels, that is, channels with word sequence:
the capacity converging to 0. Given u = (u 1 , u 2 , ..., u N )
denote the information sequence. For the coding sequence x1N = u 1N G N (1)
with R as the coding rate, this study selects the (N · R) bits
of the sequence u as the information bits and transmits the When Arikan proposed polar codes, a coding algorithm
information in the “good” sub-channel, while the remaining and SC decoding algorithm were presented, while subsequent
(N − N · R) bits would be selected as the frozen bits and researchers have improved the SC algorithm by proposing
transmitted in the “bad” sub-channel. SCL and CA-SCL decoding algorithms, enabling the decod-
When coding polar codes, it is necessary to first distin- ing performance to be enhanced. Nevertheless, all these
guish the reliability of the N sub-channels, in other words, compiled code algorithms have a restriction on the code
whether they are reliable channels or not. The reliability of length, meaning that the code length must satisfy a power
each polarized channel is measured by three common meth- of 2: N = 2n . Although the information bit length K can
ods: the Bhattacharyya parameter [1], density evolution (DE) be taken arbitrarily when the code length N is fixed and

123
502 T. Han et al.

the coding rate R = K /N can be varied freely, it is no its mean and variance, it is only required to track the change
longer possible to adjust the coding rate by changing the in the mean of the information to find out the change in proba-
code length when the information bit length is fixed. From bility density under the Gaussian approximation assumption.
a practical standpoint, this research prefers to design a pair The equivalent signal-to-noise rate (SNR) of a Gaussian vari-
of coders that enable both code length and coding rate to able is also defined as m 2 /σ 2 , hence the SNR is m/2 and
be self-adjusting without changing the basic compiled code tracking the mean is also equivalent to tracking the SNR.
structure. Puncturing is a commonly adopted method when For a BAWGNC channel W with variance σ 2 , the infor-
designing codes with variable rates. The number of infor- mation source bit sequence is modulated with BPSK and its
mation bits in a coding sequence is denoted by K , with N probability density function is
representing the length of the coding sequence, and M being
2
pattern is denoted by P, whose index indicates the bits being 1 − (y−(1−2x))
p(y | x) = √ e 2σ2 (3)
punctured, with | P |= (N − M) indicating the number of 2π σ 2
bits being punctured. The coding rate of the punctured polar
code is R = K /M. The LLR for receiving signs is defined as
A major factor affecting the performance of polar codes
p(y | 0) 2y
is the worst sub-channel after the channel is polarized. Con- L(y) = ln = 2 (4)
sequently, it is a critical issue to improve the performance of p(y | 1) σ
rate-adapted polar codes by selecting the worst sub-channel
Since the channel satisfies the symmetry condition at this
into the punctured bits. The traditional puncturing scheme
point, then the decoding error probability is independent of
[10] makes no improvement to this issue. Its construction pro-
the transmitted code word, and therefore without loss of gen-
cess is to directly delete the last | P | rows and corresponding
erality, for which it can be assumed that the code word is sent
columns of the generated matrix G N , and set the last | P |
as all-zero, the LLR is a Gaussian distribution obeying a mean
bits of the polar code with code length N as frozen bits, so
of 2/σ 2 and variance of 4/σ 2 .
as to obtain a punctured polar code with code length M. By
When the LLR of each sub-channel obeys a Gaussian dis-
utilizing the principle of the traditional puncturing scheme
tribution
 with a variance double the mean, that is, L (i)
N ∼
[10], this paper introduces the channel reliability estimation (i) (i) (1)
method [14] to select rows and columns for deletion individu- N m N , 2m N , where m 1 = σ22 . The only issue to be con-
ally in the generated matrix G N until the number of deletions sidered based on such a Gaussian approximation assumption
reaches | P |, enabling it to improve the performance of the is how to calculate the mean value. Following the setting in
(i)
polar code to a certain extent.  let α N denote the probability density function of
the DE,
L (i) N i−1 . Then α (i) is a Gaussian distribution obey-
N y1 , 01 N
 
(i) (i)
3 Improved puncturing algorithm ing N m N , 2m N . Subsequently, the calculation of density
evolution is transformed into a recursive calculation of the
3.1 Improved methods for channel reliability mean value in accordance with the construction theory of the
estimation Gaussian approximation as follows:
  
(2i−1) (i) 2
−1
The Gaussian approximation [18] is a simplified processing m 2N =ϕ 1 − 1 − ϕ mN (5)
approach for DE and has long been extensively used in LDPC
codes. It is used in the coding of polar codes for channel relia-
where the function:
bility estimation [16], that is, to estimate the error probability
of individual polarized sub-channels. The fundamental pre-  
· exp − (u−x)
L
requisite for the application of the Gaussian approximation 1− √1 ∫∞
−∞ tanh
u
du , x > 0
ϕ(x) = 4π x 2 4x
method is the satisfaction of the symmetry condition, since 1 ,x = 0
it is the condition that must be satisfied by the DE method. (6)
If the probability density function for receiving the signed 
LLR satisfies: is continuous and monotonically decreasing on 0, ∞ ,
ϕ(0) = 1,ϕ(+∞) = 0, and its inverse function is denoted
f (x) = f (−x)e−x (2) by ϕ −1 (x).
The Gaussian approximation is a simplification of the DE,
then the mean m and variance σ 2 of the Gaussian distribution and as it is a simplification, it would come at the cost of
possess the following relationship: σ 2 = 2m. As the Gaus- losing a part of the performance. Fortunately, the cost is
sian distribution itself can be fully determined on the basis of small enough to be acceptable. However, equation ϕ(x)is

123
Puncturing scheme for polar codes... 503

extremely complicated to calculate, so Sae-Young Chung

proposed an approximation version of the Gaussian approx-
imation (AGA), also known as ϕ  (x).

π
x (1 − 7x ) exp(− 4 ), x ≥ 10
10 x

ϕ (x) = (7)
exp(−0.4527x 0.86 + 0.0218), 0 < x < 10

For polar codes, however, when the code length N gets

longer, there is a significant performance loss due to the
calculation error of ϕ  (x). Therefore, Jinchen Dai et al.
proposed an improved AGA. the reference [14] employed
cumulative-logarithmic error (CLE) to quantitatively evalu-
ate the complementary error of AGA over the logarithmic
domain, and proposed A new estimated function for the C-
segment:
Fig. 1 Channel polarization by means of ϕ  (x)

e0.0116x −0.4212x , 0
2
<x ≤a
ϕ AG A−2 (x) = (8)
e−0.2944x−0.3169 , a < x

where the critical point a = 7.0633.

According to the improved approximation assumptions,
the probability of error for each polarized sub-channel is:
⎛ ⎞ ⎛ ⎞
(i) (i)
(i) mN mN
Pe (W N ) = Q ⎝  ⎠= Q⎝ ⎠ (9)
(i) 2
2m N

where the complementary error function is:

 +∞
1 t2
Q(x) = √ e− 2 dt (10)
2π x

To better compare the difference and effectiveness of

both ϕ  (x)and ϕ AG A−2 (x) functions in picking channels, this Fig. 2 Channel polarization by means of ϕ AG A−2 (x)
research conducted simulations of channel polarization under
the BAWGN channel with selected code length N = 1024
and under the noise variance σ 2 = 0.5. Of these, Figs. 1 3.2 Improved puncturing criteria
and 2 employ the function ϕ  (x) and function ϕ AG A−2 (x)
respectively to calculate the error probability of each polar- In this subsection, this research proposed improved punctur-
ized sub-channel. ing criteria for ensuring the selection of punctured bits by
The Gaussian approximation construction algorithm shows using the channel reliability estimation method.
that the larger the expectation value of the channel LLR, the Let F denote the set of frozen bits information in the
more reliable the sub-channel is. Therefore, the channel cor- polar code, which contains the information corresponding to
responding to the higher value of expectation is selected as the frozen, and let gi denote the i-th column of the generated
the reliable channel. The comparison between Figs. 1 and 2 matrix G N , where i = 1, 2, ..., N . Let Q (gi ) denote the
reveals that when the ϕ  (x) function is applied to calculate position of “1” in the gi -th column of the generated matrix.
the error probability of each polarized sub-channel, the points Taking a polar code of code length 4 as an example, the
representing the subchannel are more clustered and difficult generated matrix is:
to distinguish; however, when ϕ AG A−2 (x) is employed for
⎛ ⎞
the calculation, channels are with better distribution and can 1 0 0 0
be picked out more precisely. Therefore, in the subsequent ⎜1 0 1 0⎟
G4 = ⎜
⎝1
⎟ (11)
algorithms, the ϕ AG A−2 (x) function will be employed for the 1 0 0⎠
reliability estimation of sub-channels. 1 1 1 1

123
504 T. Han et al.

As an example, the third column of the generated matrix is | Q (P) |-minimum. In this case, some well-polarized sub-
g3 = (0, 1, 0, 1)T and the position information correspond- channels may be selected into the supplementary frozen set
ing to “1” in its column is Q (g3 ) = {2, 4}. To ensure that Q (P), thus affecting the performance of the polar code.
the information of the chosen punctured bits ci = ugi is The proposed algorithm in this paper firstly satisfies the
recognized by the decoder, the frozen set F should contain | Q (P) | minimum principle and selects the punctured
the position information of all the “1” in column gi , which vector P and the supplementary frozen set Q (P) in the gen-
means that the following condition is satisfied: erated matrix of the polar code by comparing the reliability of
each polarized sub-channel, thus allowing the “poor” polar-
 
Q gi ⊆ F (12) ized sub-channel to be selected in the frozen set as far as
possible. The simulations reveal that better performance can
This condition can be deduced intuitively. By letting be achieved based on this improved approach.
u Q(gi ) denote the position of the information bits in Q (gi ), The improved algorithm steps are as follows:
and the code word information ci being affected solely by
the information in u Q(gi ) , when all the information in u Q(gi ) Improved Puncturing Algorithm
belongs to the frozen bits, the information can be transmitted
to the decoder when decoding, indicating that the information Input: Actual transmission code length M, channel
parameterσ 2  M
of the bits belongs to both the punctured and frozen bits.
1: Calculate the mother code length N = 2 log2 of the polar
For practical applications, to construct polar codes with code based on the actual transmission code length M and
code length M in this research, it is necessary to select | P |= construct the generated matrix G N .
(N − M) punctured bits and let Q (P) be the complementary 2: Calculate the Gaussian approximation auxiliary parameter
frozen set, which, from the above principle, can be introduced Pe1N based on the channel parameter σ 2 with the use of
equations (1) to (6)
by Eq. (9) when i ∈ P: 3: Perform the following steps when i = 1 : N − M
4: Calculate the column weight of each column in the generated

Q (P)  Q (gi ) ⊆ F (13) matrix G N . Record the column number gi and the number n
for which the column weight is 1.
i∈ 5: Add the column with column number gi to the punctured
vector P and add Q (gi ) to the supplementary frozen set
Naturally, since P is limited by the range of values, there Q(P ) when n = 1.
is a lower bound on the number of locations containing “1” 6: Delete the column with column number gi in G N and the
row corresponding to the position information of 1 in Q (gi ) (
in the supplementary frozen set Q (P), viz.
which corresponds to n = 1).
7: Judge the size of Pe (Q (gi )) for n columns when n > 1, add
| Q (P) |≥| P |= N − M (14) the column number gi of the largest column of Pe (Q (gi )) to
the punctured vector P and add Q (gi ) to the supplementary
frozen set Q(P ).
This can be proved by the structural relationship of the 8: Delete the column with column number gi in G N and the
generated matrix of the polar code, since the generated matrix row corresponding to the position information of 1 in Q (gi )(
G N = B N G ⊗n ⊗n which corresponds to n > 1).
2 , where G 2 is a lower triangular matrix and Output: Get the punctured vector P and the supplementary
meets all elements of “1” on the diagonal, and B N is only a frozen set Q(P ) .
reverse sorted permutation matrix, which only affects the
ordering of the columns in the generated matrix, not the
construction of the matrix columns. When choosing the last The difference between the construction algorithm pro-
(N − M) column of the matrix G ⊗n 2 as the punctured vector, posed in this paper based on Gaussian approximation as
the number of | Q (P) | is minimized and i ∈ Q (P) when assistance to screen the punctured bits and that of reference
i ∈ P. Reference [10] makes use of the principle of mini- [10] can be seen in steps 5 to 8 in this algorithm. When the
mization of | Q (P) | for the selection of punctured bits, and number of columns to be selected in the generated matrix is
the paper is also an improvement on this basis. greater than 1, the algorithm in this paper makes the selection
by using Pe (Q (gi )) of the columns that are to be picked,
3.3 Puncturing scheme on the basis of reliability and selecting the largest of them into the punctured vector
estimation and adding its corresponding Q (gi ) into the supplementary
frozen set Q(P). This measure can reduce the possibility
For the conventional puncturing algorithm [10] mentioned of some well-polarized sub-channels being eliminated, thus
above, its selection of the supplementary frozen set Q (P) enhancing performance.
of the punctured vector P is not done by the reliability In the present research, for example, if a polar code of
of the channel, but only by making use of the principle of code length M = 5 needs to be constructed in practice, it is

123
Puncturing scheme for polar codes... 505

necessary to have a generated matrix G 8 of polar codes of the

mother code with code length N = 8, and it is also required
to calculate the error probability Pe18 of the polarized sub-
channel, where the generated matrix G 8 is:
⎛ ⎞
10 0 0 0 0 0 0
⎜1 0 0 0 1 0 0 0⎟
⎜ ⎟
⎜1 0 1 0 0 0 0 0⎟
⎜ ⎟
⎜1 0 1 0 1 0 1 0⎟
G8 = ⎜
⎜1 1
⎟ (15)
⎜ 0 0 0 0 0 0⎟⎟
⎜1 1 0 0 1 1 0 0⎟
⎜ ⎟
⎝1 1 1 1 0 0 0 0⎠
11 1 1 1 1 1 1

In this case, it is necessary to pick | P |= N − M = 3

punctured bits to add to the punctured vector P by applying
Fig. 3 BER performance of polar codes with code length M = 896
the method proposed in this paper, that is: in the first step, and coding rate R = 3/4 at BAWGNC
traversing the column weights of the generated matrix G 8 ,
with only the 8th column having a column weight of 1, adding
g8 to the punctured vector P, adding Q(g8 ) to the supple- mation proposed in this paper by using the successive
mentary frozen set Q(P), and deleting the 8th column and its cancellation (SC) decoding algorithm in BAWGNC. The
corresponding row in the generated matrix G 8 . In the second total number of frames simulated is Ftotal = 106 . The stop
step, traversing the column weights of the remaining gener- condition of the simulation experiment is that the total num-
ated matrix G 8 and find that three columns have a column ber of frames in error is larger than 100 or the number of
weight of 1 (i.e. columns 4,6,7), followed by determining the frames sent reaches Ftotal .
size of its corresponding column Pe (Q (gi )) and finding that Taking the mother code of the polar code with code length
Pe (Q (g7 )) is the largest. As a result, adding g7 to the punc- N = 1024, the punctured code with code length M = 896,
tured vector P, adding Q (g7 ) to the supplementary frozen set the coding rate R = 3/4, the information bits K = 672,
Q(P), and deleting the 7th column and its corresponding row and the punctured vector size | P |= N − M = 28, under
in the remaining generated matrix G 8 . In the third step, after the same conditions, the performance of the polar code can
traversing the column weights of the remaining generated be compared with that of the method propoed in references
matrix G 8 , two columns are found to have a column weight [6,8,10,12] and [13] as shown in Figs. 3 and 4. As can be
of 1 (i.e. 4,6 columns), its corresponding column Pe (Q (gi )) observed from the figures, the method proposed in this paper
is determined, and it is found that Pe (Q (g6 )) is the largest, can achieve a gain of about 0.15dB compared with the method
adding g6 to the punctured vector P, adding Q (g6 ) to the proposed in reference [10] when the BER is 10−5 . And the
supplementary frozen set Q(P), and deleting the sixth col- proposed method obtains a gain of about 0.2 dB compared
umn and its corresponding row in the generated matrix G 8 . with the method proposed in reference [13] when the BER is
Up to this point, the punctured vector P = [6, 7, 8] and the 10−5 .The method proposed in this paper can obtain a gain of
supplementary frozen set Q(P) = [4, 6, 8] can be obtained. about 0.1dB compared with the method proposed in reference
After obtaining the punctured vector P and the supplemen- [10] when the frame error rate (FER) is 10−4 .
tary frozen set Q(P) with the algorithm in this paper, the Figures 5 and 6 demonstrate the performance of polar
remaining frozen bits and information bits are selected and codes with code length M = 640. The coding rates R are
punctured with the punctured vector P after coding, and 1/2 and 4/5. At R = 1/2, the scheme proposed in this
finally, the LLR reception value of the corresponding punc- paper performs similarly to the scheme in reference [13].
tured bits is set to infinity (or negative infinity) according to The outcomes indicate that the proposed method in this paper
the transmission value of “0” (or “1”) set for the frozen bits provides better performance than other coding methods. For
during decoding. R of 4/5, the proposed method is able to achieve a gain of
about 0.2dB compared to the method proposed in reference
[10] when the BER is 10−5 ;and the proposed method obtains
4 Performance simulation a gain of about 0.1 dB compared with the method proposed
in reference [13] when the BER is 10−6 .
This section would demonstrate the decoding performance For the quasi-uniform puncturing scheme proposed in
of the puncturing scheme based on channel reliability esti- reference [8], and the generated matrix-based puncturing

123
506 T. Han et al.

Fig. 4 FER performance of polar codes with code length M = 896 and Fig. 6 BER performance of polar codes with code length M = 640
coding rate R = 3/4 at BAWGNC and coding rate R = 4/5at BAWGNC

can be achieved in just one step, and the complexity of the

scheme is O(1). The scheme proposed in this paper, on the
other hand, requires selecting the punctured bits individually,
by using the generated matrix of the polar code, which starts
from the last column, and selects the columns with the same
weight each time, and then compares the error probability of
the polarized sub-channel for selection, and it needs to select
| P | bits as the punctured bits. Therefore, it takes | P | times
to complete the selection, making the complexity O(| P |).

5 Conclusions

This paper proposes an improved method to construct punc-

tured polar codes. When selecting the punctured vector and
Fig. 5 BER performance of polar codes with code length M = 640 supplementary frozen set for a given arbitrary code length
and coding rate R = 1/2 at BAWGNC M, reference [10] may select some good polarized channels
into the punctured vector, thus affecting the decoding per-
formance. The algorithm presented in this paper is based on
scheme proposed in reference [10], the former introduces
reference [10], which selects the punctured vectors and sup-
a bit-reversal rearrangement algorithm based on the punc-
plementary frozen sets in the generated matrix of the polar
turing algorithm, through which the punctured bits are able
code, and applies the channel reliability estimation method
to present a quasi-uniform arrangement, and provides a sim-
in reference [14] to the selection of punctured bits. This
ple construction scheme, that is, by simply taking the first
allows the poorly polarized sub-channels to be selected into
| P | bits of the punctured vector as the punctured bits, and
the punctured vector as much as possible. The simulation
then calculating its corresponding inverse order punctured
outcomes indicate that the improved punctured polar codes
vector. This can be achieved in just one step and the com-
proposed in this paper provide better performance than the
plexity of the scheme is O(1). While the latter ingeniously
conventional punctured polar codes.
makes use of the principle of code word construction by tak-
ing advantage of the morphology of the lower triangular form Acknowledgements This work was supported by the National Key
presented by the non-bit-flipped generated matrix and gives Research and Development Program of China (2020YFB1805801).
a simple construction scheme, that is, by simply taking the
Author Contributions All authors contributed to the study conception
{M + 1, M + 2, ..., N }, and then selecting the last | P | bits and design. Material preparation, data collection and analysis were per-
of the code word sequence into the punctured vector, which formed by MZ, MF and GH. The first draft of the manuscript was

123
Puncturing scheme for polar codes... 507

written by TH and all authors commented on previous versions of the 13. Han, S., Kim, B., & Ha, J. (2022). Rate-compatible punctured polar
manuscript. All authors read and approved the final manuscript. codes. IEEE Communications Letters, 26(4), 753–757.
14. Dai, J., Niu, K., & Si, Z. (2016). Evaluation and optimization of
Funding This work was supported by 2020YFB1805800. Author Meil- gaussian approximation for polar codes. Proceedings of the Amer-
ing Zhang has received research support from the Ministry of Science ican Society for Information Science & Technology, 51(1), 1–2.
and Technology of the People’s Republic of China. 15. Mori, R., & Tanaka, T. (2009). Performance of polar codes with
the construction using density evolution. IEEE Communications
Data availability Enquiries about data availability should be directed to Letters, 13(7), 519–521.
the authors. 16. Trifonov, P. (2012). Efficient design and decoding of polar codes.
IEEE Transactions on Communications, 60(11), 3221–3227.
Declarations 17. Tal, I., & A. Vardy,. (2013). How to construct polar codes. IEEE
Transactions on Information Theory, 59(10), 6562–6582.
18. Chung, S. Y., Richardson, T. J., & Urbanke, R. L. (2001). Analysis
Conflict of interest The authors have no relevant financial or non- of sum-product decoding of low-density parity-check codes using
financial interests to disclose. a Gaussian approximation. IEEE Transactions on Information The-
ory, 47(2), 657–670.
Code availability The codes generated during the current study are
available from the corresponding author on reasonable request.
Publisher’s Note Springer Nature remains neutral with regard to juris-
dictional claims in published maps and institutional affiliations.
References
Springer Nature or its licensor (e.g. a society or other partner) holds
1. Arikan, E. (2009). Channel Polarization: A method for constructing exclusive rights to this article under a publishing agreement with the
capacity-Achieving codes for symmetric binary-Input memoryless author(s) or other rightsholder(s); author self-archiving of the accepted
channels. IEEE Transactions on Information Theory, 55(7), 3051– manuscript version of this article is solely governed by the terms of such
3073. publishing agreement and applicable law.
2. Korada, S. B., Sasoglu, E., & Urbanke, R. (2010). Polar codes:
Characterization of exponent, bounds, and constructions. IEEE
Transactions on Information Theory, 56(12), 6253–6264.
3. Zhang, Y., Liu, A., & Gong, C. (2014). Polar-LDPC concatenated Mr. Tianwei Han was born in
coding for the AWGN wiretap channel. IEEE Communications Jilin Province,China in 1996.He
Letters, 18(10), 1683–1686. received the B.E (Electronics and
4. Wang, Y., Zhang, W., & Liu, Y. (2017). An improved concatenation Communication Engineering) from
scheme of Polar codes with Reed-Solomon codes. IEEE Commu- Changchun Industrial College,Jilin
nications Letters, 21(3), 468–471. Province,China,in 2020 and ME
5. Eslami, A., & Pishro-Nik, H. (2011). A practical approach to polar (Communication System) from Jilin
codes. In: IEEE Proceedings international symposium on informa- University,Jilin Province,China,in
tion theory (ISIT), vol 20, pp. 16–20. 2022.His major research interest
6. Shin, D. M., Lim, S. C., & Yang, K. (2013). Design of length- is Channel Forward Error Correc-
compatible polar codes based on the reduction of polarizing tion Coding.
matrices. IEEE Transactions on Communications, 61(7), 2593–
2599.
7. Zhang, L., Zhang, Z., & Wang, X. (2014). On the puncturing
patterns for punctured polar codes. In: In: IEEE international sym-
posium on information theory, June 29-July 4, 40(6), 121–125.
8. Niu, K., Chen, K., & Lin, J.-R. (2013). Beyond turbo codes: Ms. Meiyu Fu was born in Shan-
Rate-compatible punctured Polar codes. In: Proceedings (pp. dong Province,China in 1998.She
3423–3427). Budapest, Hungary, Jun: IEEE ICC. received the B.E (Electronics and
9. Bioglio, V., Gabry, F., & Land, I. (2017). Low-complexity punc- Communication Engineering) from
turing and shortening of Polar codes. Wireless Communications & Northeast Electric Power Univer-
Networking Conference Workshops, 18(4), 1–7. sity,Shandong Province,China,in
10. Wang, R., & Liu, R. (2014). A novel puncturing scheme for Polar 2019 and ME (Communication Sys-
codes. IEEE Communications Letters, 18(12), 2081–2084. tem) from Jilin University,Jilin
11. Oliveira, R. M., Lamare, D., & Rodrigo, C. (2021). Design of rate- Province,China,in 2022.Her major
compatible polar codes based on non-uniform channel polarization. research interest is Channel For-
IEEE Access, 41(9), 41902–41912. ward Error Correction Coding
12. Zhao, J., Zhang, W., & Liu, Y. (2021). A novel puncturing scheme
of low rate polar codes based on fixed information set. IEEE Com-
munications Letters, 25(7), 2104–2108.

123
508 T. Han et al.

Dr. Meiling Zhang received the Pro. Guijun Hu received the B.S
B.S degree in electronic science degree in electronic science and
and technology and the M.S and technology and the M.S and Ph.D
Ph.D degrees in microelectronics degrees in microelectronics and
and solid electronics from Jilin solid electronics from Jilin Uni-
University, in 2012, 2015, and 2018, versity, in 1993, 1996, and 2001,
respectively. She is currently a respectively. He is a professor with
Lecturer with the Department of the Department of Communica-
Communication Engineering, Jilin tion Engineering, Jilin University.
University. Her current research Her current research interests include
interests include polymer planar Wireless communication and Opti-
optical waveguide devices and opti- cal fiber communication technol-
cal beamforming. ogy.

123