1

On the Analysis of Puncturing for
Finite-Length Polar Codes:

arXiv:1801.05095v1 [cs.IT] 16 Jan 2018

Boolean Function Approach
Song-Nam Hong∗ and Dennis Hui†
∗

Ajou University, Suwon, Korea,
Email: snhong@ajou.ac.kr

†

Ericsson Research, San Jose, CA,
Email: dennis.hui@ericsson.com

Abstract

This paper investigates the impact of puncturing on finite-length polar codes in which a puncturing
pattern pN = (p0 , ..., pN ) is applied to a length-N polar code.. We first introduce two virtual channels
to stochastically model the punctured (untransmitted) bits, which are respectively called useless channel
model (UCM) and deterministic channel model (DCM). Under each model, we derive boolean functions
in variables p0 , ..., pN −1 that can indicate which polarized channels should carry frozen bits. Based on
this, we present an efficient method to jointly optimize a puncturing pattern and an information set.
Focusing on a fixed information set, we show that there exist the so-called catastrophic puncturing
patterns that will surely lead to a block error and derive their weight distributions recursively. We then
propose the two construction methods of a rate-compatible (RC) polar code which ensures that each
puncturing pattern in the family is non-catastrophic. Simulation results demonstrate that the proposed
RC polar code outperform the RC Turbo code adopted in LTE.

January 17, 2018

DRAFT

2

Index Terms
Polar codes, puncturing, shortening, rate-compatible code, HARQ.

I. I NTRODUCTION
Polar codes, proposed by Arikan [1], achieve the symmetric capacity of binary-input discrete
memoryless channels (BI-DMCs) under a low-complexity successive cancellation (SC) decoder.
The finite-length performance of polar codes can be enhanced by using list decoder that enables
polar codes to approach the performance of optimal maximum-likelihood (ML) decoder [2]. It
was further shown in [2] that a polar code concatenated with a simple CRC outperforms welloptimized LDPC and Turbo codes even for short lengths. Due to their good performance and
low-complexity, polar codes are currently considered for possible deployment in future wireless
communication systems (i.e., 5G).
Puncturing is widely used to support various lengths and to construct rate-compatible (RC)
codes. In [5]–[7], a puncturing pattern is produced by a heuristic algorithm and then the information set of the mother polar code is optimized by taking into account the puncturing pattern. Also,
an efficient algorithm to jointly optimize a puncturing pattern and the corresponding information
set was recently proposed [10], where an exhaustive search over all possible puncturing patterns
is performed, significantly reducing the search-space by using certain symmetry of the polar
encoder. It can achieve an optimized frame-error-rate (FER) performance but still require a
higher optimization complexity. A low-complexity method for joint optimization was further
developed in [13]. It is remarkable that the above methods cannot be directly used to construct
a RC polar code since in this case, all punctured polar codes in the family and the mother
polar code should use the identical information set, i.e., the information set cannot be optimized
according to puncturing patterns. In [8], [9], puncturing patterns are optimized for the given
information set of the mother polar code. In general, this approach considerably reduces the
optimization complexity, at the cost of an increased FER.
DRAFT

January 17, 2018

3

In this paper, we investigate the impact of puncturing on polarized channels of finite-length
polar coded and, based on this, we present an efficient method to construct good (rate-compatible)
puncturing patterns. First of all, we introduce two virtual channels that stochastically model
punctured bits, which are referred to as useless channel model (UCM) and deterministic channel
model (DCM), respectively. On the one hand, in UCM, it is assumed that the output of the virtual
channel is independent of its input and hence, the polar decoder is performed by assigning zero
log-likelihood ratios (LLRs) for the punctured bits. On the other hand, in DCM, it is assumed
that the channel output is equal to its input as a pre-agreed bit (e.g., zero) with probability 1
and hence, the polar decoder is performed by assigning infinite LLRs for the punctured bits.
Suppose that a puncturing pattern pN = (p0 , ..., pN −1 ) is applied to a length-N polar code.
Our main contributions are summarized as follows.
•

We derive boolean functions in variables p0 , ..., pN −1 indicating which polarized channels
should be assigned by frozen bits. The index sets of such polarized channels in UCM and
DCM are denoted by DpN and EpN , respectively.

•

We define a reciprocal puncturing pattern which ensures that BpN = DpN (or BpN = EpN ),
where BpN denote the index set of the locations of punctured bits. Then, we derive a
necessary and sufficient condition such that a puncturing pattern is reciprocal. This condition
is used to efficiently construct a good puncturing pattern and the corresponding information
set.

•

Next, focus on a fixed information set, we show that there exist the so-called catastrophic
puncturing patterns which will surely lead to a block error. Also, we develop an efficient
recursive algorithm to characterize those puncturing patterns and their weight distributions.

•

Based on the above analysis, we present two simple methods to construct a RC polar code
which ensures that each puncturing pattern in the family is non-catastrophic. Via simulation
results, we demonstrate that the proposed RC polar code can outperform the RC Turbo code
adopted in LTE.

January 17, 2018

DRAFT

4

This paper is organized as follows. In Section II, we provide some useful notations and
definition to be used throughout the paper. In Section III, using boolean functions, we analyze
the impact of puncturing on the polarized channels of a polar code, and provide an efficient
method to jointly optimize a puncturing pattern and an information set. In Section IV, we define
the catastrophic puncturing patterns (which should be avoided) for a given information set and
derive their weight distributions. In Section , we propose two simple methods to construct a
RC polar code having a family of non-catastrophic puncturing patterns. Simulation results are
provided in Section VI. Section VII concludes the paper.
II. P RELIMINARIES
In this section we provide some useful notations and definitions that will be used in the sequel.
A. Notation
∆

Let [a : b] = {a, a + 1, . . . , b} for any integers a and b ≥ a. A polar code of length N = 2n is
considered, in which the polarized channels are indexed by 0, 1, . . . , N −1. We let A ⊆ [0 : N −1]
denote the information set that contains all the indices of unfrozen-bit channels. Accordingly,
⊗ log(N )

Ac contains all the indices of frozen bit channels. For any N = 2n , let GN = G2

be the

rate-one generator matrix of all polar codes with blocklength N , where G2 is the 2-by-2 Arikan
Kernel [1]. Also, for any M ⊆ [1 : N ] and N ⊆ [1 : N ], let GN (M, N ) denote the submatrix
of GN obtained by selecting rows and columns whose indices belong to M and N , respectively.
We define a function g(`) : [0 : N − 1] → {0, 1}n which maps ` onto a binary expansion as
g(`) = (bn , . . . , b1 ),
such that ` =

(1)

Pn

n−i
.
i=1 bi 2

B. Punctured Polar Codes
In this section, we formally define the polarized channels of a punctured polar code. Let
s denote a number of punctured bits. Then, a polar code of blocklength N is punctured by
DRAFT

January 17, 2018

5

removing a set of s columns from its generator matrix, which has the effect of reducing the
codeword length from N to Np = N − s. Formally, a punctured polar code of post-puncturing
blocklength Np is characterized by its “mother” (unpunctured) polar code of blocklength N and
a puncturing pattern pN = (p0 , . . . , pN −1 ) ∈ {0, 1}N with pi = 0 indicating that the i-th coded
bit is punctured and thus not transmitted. Let BpN = {i ∈ [0 : N − 1] : pi = 0} be the index set
which contains the zero locations in pN . Also, we let Bpc N = [0 : N − 1] \ BpN . Then, we have
Np = wh (pN ) = |Bpc N |.
For a given puncturing pattern pN , let πpN : Y N → Y Np be a projection operator that copies
Np = wh (pN ) coordinates of its input as its output based on the puncturing pattern specified
by pN , where wh (pN ) denotes the number of ones in pN , i.e. yNP = πpN (yN ) containing the
coordinates of yN corresponding to the locations of ones in pN . The notion of polarized channels
in conventional polar codes can be extended to punctured polar codes in a straightforward manner
as follows. For a given (unpunctured) polar code of blocklength N and puncturing pattern pN ,
we define the transition probability of the i-th polarized channel of the corresponding punctured
polar code as

W (i) (yNp , ui−1 , pN |ui ) =

1
2N −1

X

X

uN
i+1

Np
})
yN ∈π −1
N ({y

W N (yN |uN GN ),

(2)

p

where πp−1N (S) , {yN ∈ Y N : πpN (yN ) ∈ S} represents the inverse image of πpN (·) and the
channel transition probabilities are

W N (yN |xN ) =

Y

W (yj |xj ),

(3)

j∈[1:N ]

where W (·|·) denotes the channel transition probability of the underlying BI-DMC. For the
(i)

simplicity of notation, we let WpN denote the ith polarized channel with the transition probability
(i)

in (2), and let I(WpN ) denote the corresponding symmetric capacity.
January 17, 2018

DRAFT

6

III. I MPACT OF P UNCTURING ON P OLARIZED C HANNELS
As explained in Section II-B, punctured coded bits are not transmitted through an underlying
channel. Conventionally, a length-N polar decoder is used regardless of the number of punctured
bits and thus, the proper LLR values for those bits should be assigned. In this section, we
introduce the two virtual channels that model those punctured bits stochastically, which are
respectively called useless and deterministic channels. Under the transmitter-receiver agreement,
one of the modelings is applied to each punctured bit and according to a chosen model, the
proper LLR values are assigned. Then, we analyze their impacts on the polarized channels using
boolean functions.

A. Stochastic Modelings of Punctured Bits
We define the two virtual channels to stochastically model punctured bits, which are referred
to as useless channel model (UCM) and deterministic channel model (DCM), respectively. To
be specific, they are defined as follows.
•

In UCM, it is assumed that the punctured coded bits are transmitted over a useless BIDMC. In this case, a channel output is independent of its input and thus, the corresponding
channel can be defined as
W (yj |xj ) = PY (yj ),

(4)

for some probability distribution PY (·). Under this model, the LLRs for the punctured coded
bits are assigned by zeros since they are assumed to be equally likely of being one or zero.
•

In DCM, it is assumed that the punctured coded bits are transmitted over a deterministic (or
noiseless) BI-DMC. In this case, a channel output is identical to its input with probability 1.
In fact, this can be established by assigning the punctured coded bits with some fixed values
that have been pre-agreed with the transmitter, so that the encoder restricts the transmitted
codewords to be in the offset subspace specified by the fixed values. In this paper, without

DRAFT

January 17, 2018

7

loss of generality, the pre-agreed values are assumed to be zeros, i.e., xi = 0 for all i ∈ BpN .
Accordingly, for an index set EpN , uEpN = (ui : i ∈ EpN ) should be chosen such that
uGN ([1 : N ], BpN ) = 0,

(5)

uEpN = uE c N GN (Epc N , BpN )GN (EpN , BpN )−1 .

(6)

which is equivalent to

p

This condition shows that uEpN = (ui : i ∈ EpN ) should not carry information and be used
as frozen bits. Also, the condition (6) is satisfied as long as GN (EpN , BpN ) is a full-rank.
Under this model, the LLRs for the punctured coded bits are assigned by +∞.
In the following Sections III-B and III-C, we investigate the impact of puncturing on polarized
channels under each virtual channel model. In UCM, we show that some polarized channel,
determined by a puncturing pattern, should have zero capacity and then identify the index set,
denoted by DpN , of such polarized channels. Namely, we obtain that
(i)

I(WN ) = 0 for i ∈ DpN .

(7)

Next, in DCM, we identify the index set EpN defined above. Definitely, those index sets have
an impact on the design of an information set A as in Remark 1
Remark 1: The reliabilities of polarized channels of a polar code can be computed by several
techniques such as density evolution under a Gaussian approximation (DE/GA), tracking the
mean value, Batthacharyya parameter or mutual information of the Gaussian L-densities [12].
Let I = {i1 , i2 , ..., iN } denote the orderd index set such that the reliability of polarized channel
ij is not lower than that of polarized channel ik for i ≥ k. From this, we can construct the
information set A of the size K, by taking the first K indices from the I. Whereas, for a
punctured polar code, we need to more carefully construct an information set as follows:
•

In UCM, the information set A is constructed by taking the first K indices from the ordered
set I \ DpN where |I \ DpN | = Np .

January 17, 2018

DRAFT

8
𝑊)
𝑥"

𝑢"

𝑥#

𝑢#

𝑊"

𝑦"

𝑊#

𝑦#

(a) The polar encoder of 𝑁 = 2

𝑊)
Puncturing patterns

Polarized channel capacities
𝑍

"

𝒑)

𝑝"

AND

𝑍

"

(𝒑) )

0

0

0

1

𝑝"

0

0

1

1

𝑍

#

(𝒑) )

0

1

1

1

𝑝#

0

1

0

1

𝑍

#

𝒑)

𝑝#

OR

(b) The corresponding AND-OR representation

Fig. 1.

The capacity of polarized channel with a puncturing pattern p2 = (p0 , p1 ) for N = 2.

Stage 2

Stage 3

Fig. 2.

•

𝑍 " 𝒑+ = 0

AND

𝑍 % 𝒑+ = 0

OR

𝑍 & 𝒑+ = 1

AND

𝑍 ( 𝒑+ = 1

OR

𝑍 , 𝒑+ = 0

AND

𝑍 - 𝒑+ = 0

OR

𝑍 . 𝒑+ = 1

AND

𝑍 / 𝒑+ = 1

OR

0

0

AND

AND

0

0

1

OR

1

1

OR

1

0

0

1
1

AND

AND

OR

OR

Binary
representation

Stage 1

0

0

1
1

AND

𝑝" = 0

(0,0,0)

AND

𝑝% = 0

(0,0,1)

AND

𝑝& = 1

(0,1,0)

AND

𝑝( = 1

(0,1,1)

OR

𝑝, = 0

(1,0,0)

OR

𝑝- = 0

(1,0,1)

OR

𝑝. = 1

(1,1,0)

OR

𝑝/ = 1

(1,1,1)

The capacity of polarized channel with a puncturing pattern p8 = (p0 , p1 , ..., p7 ) for N = 8.

Likewise, in DCM, the information set A is constructed by by taking the first K indices
from the ordered set I \ EpN where |I \ EpN | = Np .

DRAFT

January 17, 2018

9

B. Useless Channel Model (UCM)
Focusing on the perfect underlying channel (i.e., I(W ) = 1), we first identify the DpN and then
show its university with respect to the underlying B-DMC channel. By incorporating puncturing
into the channel, the resulting channel in this case can be either a perfect channel or a completely
noisy (i.e. zero-capacity) channel because a punctured bit is not transmitted. Without loss of
generality, it is assumed that N copies of the channel, denoted by Wi , i ∈ [1 : N ], are used in
(i)

which I(Wi ) = 0 for i ∈ BpN and I(Wi ) = 1 for i ∈
/ BpN . We let W̄pN denote the i-th polarized
channel particularly when the underlying B-DMC is a perfect channel.
We start with the simplest case of N = 2. From [1, Proposition 4], it is easily verified that
(0)

(8)

(1)

(9)

I(W̄p2 ) ≤ min{I(W0 ), I(W1 )}
I(W̄p2 ) ≥ max{I(W0 ), I(W1 )}.
When p2 = (1, 0) is used, the capacities of resulting polarized channels are given by
(0)

(1)

I(W̄p2 ) = 0 and I(W̄p2 ) = 1,

(10)

because of I(W0 ) = 1 and I(W1 ) = 0. From (8) and (9), we can easily obtain that


 0, p2 ∈ {(0, 0), (0, 1), (1, 0)}
(0)
I(W̄p2 ) =

 1, p2 = (1, 1)


 0, p2 = (0, 0)
(1)
I(W̄p2 ) =

 1, p2 ∈ {(0, 1), (1, 0), (1, 1)}.

(11)

(12)

(i)

Also, we can simply express I(W̄p2 ) as a boolean function in variables p0 and p1 such as
(0)

I(W̄p2 ) = p0 ∧ p1

and

(1)

I(W̄p2 ) = p0 ∨ p1 ,

(13)

where “∧” and “∨” denote the AND and OR operations, respectively, and to simplify notation,
we will omit the “∨” in the following. To simplify the expression and emphasize the boolean
January 17, 2018

DRAFT

10

function, we let Z (i) (pN ) denote the capacity of the ith polarized channel, i.e., Z (i) (pN ) =
(i)

I(W̄pN ).
Note that the boolean functions in (13) can be immediately obtained from Fig. 1 (b). The
next level of recursion for N = 4 is shown in Fig. 2. We first define a binary-output function
h : [0, 1] × [0, 1] → [0, 1] as

hb (p0 , p1 ) =



 p0 ∧ p1 ,

if b = 0


 p0 p1 ,

if b = 1.

(14)

Letting g(i) = (b0 , b1 ), we can obtain
Z (i) (p4 ) = hb1 (hb0 (p0 , p2 ), hb0 (p1 , p3 )).

(15)

From this, we can obtain the boolean functions for N = 4 as follows:
Z (0) (p4 ) = p0 ∧ p1 ∧ p2 ∧ p3

(16)

Z (1) (p4 ) = p0 p1 ∧ p0 p3 ∧ p1 p2 ∧ p2 p3

(17)

Z (2) (p4 ) = p0 p2 ∧ p1 p3

(18)

Z (3) (p4 ) = p0 p1 p2 p3 .

(19)

Repeatedly applying the above recursions as in (15), we can derive the Z (i) (pN ), i = 0, . . . , N −1
as a function of a puncturing pattern pN . When the perfect underlying channel (i.e., I(W ) = 1)
is assumed, we obtain the index set of zero-capacity polarized channels as
DpN = {i ∈ [0 : N − 1] : Z (i) (pN ) = 0}.

(20)

Also, the above set is universal with respect to the underlying B-DMC channel W because
(i)

(i)

(i)

from [11, Lemma 4.7], I(WpN ) ≤ I(W̄pN ) for any W , and thus I(WpN ) = 0 for any W if
Z (i) (pN ) = 0.
DRAFT

January 17, 2018

11

C. Deterministic Channel Model (DCM)
Focusing on the simplest case of N = 2, we can see that the condition (6) is satisfied by
choosing u0 and u1 according to a puncturing pattern



u0 = 0, u1 = 0 p2



u0 = u1 ,
p2




 u =0
p2
1

as
= (0, 0)
= (0, 1)

(21)

= (1, 0).

From the above, we can see that in the third case, u1 should be frozen bits, and in the second
case, either u0 or u1 should be frozen bits. Since the second polarized channel has a higher
capacity than the first polarized channel, we choose u0 as frozen bit in the second case. Let p̄N
denote the 1’s complement of pN . Likewise the case of UCM, we can express the (21) using
boolean function as
Z (0) (p̄2 ) = p̄0 ∧ p̄1 and Z (1) (p̄2 ) = p̄0 p̄1 ,

(22)

and the condition (6) is satisfied if ui is chosen as frozen bit when Z (i) (p̄2 ) = 1. From this, we
obtain the equivalent result with the (21) as follows:
Z (0) (p2 ) = 1 if p2 ∈ {(0, 0)}

(23)

Z (1) (p2 ) = 1 if p2 ∈ {(0, 1), (1, 0), (1, 1)}.

(24)

In this simplest case, thus, we can identify the
Ep2 = {i ∈ [0 : 1] : Z (i) (p̄2 ) = 1}.

(25)

Following the same recursion procedures in UCM, we can obtain the
EpN = {i ∈ [0 : N − 1] : Z (i) (p̄N ) = 1}.

(26)

Remark 2: In UCM, the frozen bits ui for i ∈ DpN can be set by zero, without loss of
performance. In DCM, however, the frozen bits ui for i ∈ DpN should be determined as a binary
addition of other bits, and thus, we require another computations (i.e., encoding) to determine
January 17, 2018

DRAFT

12

the frozen bits. In the next section, it will be shown that for some class of puncturing patterns,
those frozen bits can be simply chosen as zeros.
Example 1: Consider the case of N = 4. From (16)-(19), we obtain the corresponding boolean
functions as
Z (0) (p̄4 ) = p̄0 ∧ p̄1 ∧ p̄2 ∧ p̄3

(27)

Z (1) (p̄4 ) = p̄0 p̄1 ∧ p̄0 p̄3 ∧ p̄1 p̄2 ∧ p̄2 p̄3

(28)

Z (2) (p̄4 ) = p̄0 p̄2 ∧ p̄1 p̄3

(29)

Z (3) (p̄4 ) = p̄0 p̄1 p̄2 p̄3 .

(30)

For p4 = (1, 0, 1, 0), we have Ep4 =(1,0,1,0) = {1, 3} from (26), which implies that the condition
(6) is satisfied by assigning u2 and u3 as frozen bits. This is verified as


 1 0 
G4 ({1, 3}, {1, 3}) = 

1 1

(31)

is a full-rank.

D. Reciprocal Puncturing Patterns
In Sections III-B and III-C above, we showed that for each pN , there exists the corresponding
index sets DpN ⊆ Ac and EpN ⊆ Ac for UCM and DCM, respectively. In order to construct a
good information set, they should be identified. In this section, we show that for some puncturing
patterns, we can ensure that BpN = DpN (or BpN = EpN ). Formally, we define:
Definition 1: A puncturing pattern pN is referred to as reciprocal if BpN = DpN under UCM
(or BpN = EpN under DCM).
Using this, we provide the main theorems of this section below:
Theorem 1: In UCM, a puncturing pattern pN is reciprocal if and only if the following
DRAFT

January 17, 2018

13

properties are satisfied:
zero-inclusion property: 0 ∈ BpN ,
one-covering property:

if i ∈ BpN and i 1 j, then j ∈ BpN ,

(32)
(33)

where i 1 j means that for every digit of ’1’ in the binary representation of index j, the
corresponding digit in the index i must also be ’1’ and i 1 0 for every i > 0.
Proof: We first prove sufficiency and then prove necessity.
a) Proof of sufficiency: It suffices to show that the input and output sequences remain the same
after each polarization stage in the modified encoder with AND-OR operators in Fig. 1 (b). Let
the binary representation of an index i be denoted by g(i) = (bi1 , bi2 , ..., bin ) where n = log2 N .
At each polarization stage k for k ∈ {1, ..., n}, there are 2n−1 pairs of basic AND-OR operators
in the form of that in Fig. 1 (b), each of which has the input pairs whose indices correspond to
`0 = (bi1 , ..., bik−1 , 0, bik+1 , .., bin ) and `1 = (bi1 , ..., bik−1 , 1, bik+1 , .., bin ). The input and the output of
each pair are identical if (p`0 , p`1 ) ∈ {(0, 0), (0, 1), (1, 1)} as in Fig. 1 (b). If the zero-inclusion
and one-covering properties are satisfied, then the input and output of each pair of these ANDOR operators are identical. Since this argument holds for every polarization stage, it follows that
those properties imply reciprocity.
b) Proof of necessity: Note that if the input and the output of the modified polar encoder are
the same (i.e., BpN = DpN ), then the input and output after each polarization stage must be
also the same because the largest bit index with value ’0’ is monotonically non-increasing after
each polarization stage as the output of the AND operator should be smaller than that of the
OR operator for the same input. Now suppose there exist i and j such that i ∈ BpN and i 1 j
but j ∈
/ BpN . There must exist `1 , `2 ∈ [1 : N ] such that i 1 `1 1 `2 1 j, `1 ∈ BpN , `2 ∈
/ BpN ,
and that `1 and `2 differ only in one bit (say, k-th bit), where k ∈ {1, 2, ..., n}. It follows that
b`k1 , b`k2 = 0, and b`m1 = b`m2 for all m 6= k. Since `1 ∈ BpN and `2 ∈
/ BpN , the input to the pair of
AND-OR operators at stage k corresponding to `1 and `2 should be different from its output as
January 17, 2018

DRAFT

14

in the 3rd column of the table in Fig. 1 (b). It follows that the input and output after (at least)
the k-th polarization stage must be different and thus the input and the output of the whole
modified polar encoder must be different. Thus, BpN 6= DpN .
Theorem 2: In DCM, a puncturing pattern pN is reciprocal if and only if the following
properties are satisfied:
N -inclusion property: N ∈ BpN ,

(34)

zero-covering property: if i ∈ BpN and i 0 j, then j ∈ BpN ,

(35)

where i 0 j means that for every digit of ’0’ in the binary representation of index j, the
corresponding digit in the index i must also be ’0’.
Proof: The proof follows the same procedures in the proof of Theorem 1.
Corollary 1: Suppose DCM is assumed. If a puncturing pattern pN is reciprocal, then we
have
ui = 0 for i ∈ EpN .

(36)

Proof: Using zero-covering property in Theorem 2, we define
ΦN (i) = {j ∈ [0 : N − 1] : i 0 j} ∪ {N − 1},

(37)
⊗ log(N )

for any i ∈ [0 : N − 1]. Due to the particular construction of GN = G2

, we can see that

xi , i-th coded bit, is determined as an addition of ui ’s with i ∈ ΦN (i). Since the pN is reciprocal
by Hypothesis assumption, we know that ΦN (i) ⊆ EpN for any i ∈ EpN . Thus, if we choose
ui = 0 for all i ∈ EpN , xi = 0 for all i ∈ BpN . This completes the proof.
From now on, we will prove a class of reciprocal puncturing patterns.
Definition 2: Let Πn denote the set of all possible permutation of (1, 2, ..., n). For any π ∈ Π,
π(i) denote the i-th element of π. For any length-n binary vector b = (b1 , ..., bn ), we define a
bit-permutation Ψπ with seed vector π ∈ Πn as
Ψπ (b) = (bπ(1) , bπ(2) , ..., bπ(n) ).
DRAFT

(38)
January 17, 2018

15

Proposition 1: Under UCM, suppose that pN is reciprocal. Then, for any π ∈ Πn , the
is also reciprocal, where
puncturing pattern pN
π with zero-location set BpN
π

BpNπ = g −1 (Ψπ (g(i))) : i ∈ BpN .

(39)

The above statement is also hold under DCM.
Proof: The proof follows the fact that one-covering property (or zero-covering property)
definitely holds for any bit-permutation π.
Example 2: In this example, we provide some reciprocal puncturing patterns. First of all, we
have:
•

In UCM, the puncturing pattern pN with BpN = {0, 1, ..., s − 1} is obviously reciprocal.

•

In DCM, the puncturing pattern pN with BpN = {N − s + 1, N − s + 2, ..., N } is obviously
reciprocal.

Using the above puncturing patterns and from Proposition 1, we are able to generate several
reciprocal puncturing patterns. In particular, when π = (n, n − 1, ..., 1) (called bit-reverse
permutation), the corresponding puncturing patterns in UCM and DCM are called quasi-uniform
puncturing (QUP) and reverse QUP (RQUP), respectively. Fig. 5 shows the frame-error-rate
(FER) performances of punctured polar codes where QUP and RQUP are used for UCM and
DCM, respectively. In this example, we observe that UCM approach is slightly better than DCM
approach at lower rate and vice versa at higher rate.

IV. C ATASTROPHIC P UNCTURING PATTERNS
From the analysis in Section III, we learned that an information set A should be carefully
designed for a punctured polar code, by taking into account a puncturing pattern and a chosen
stochastic modelling. However, this approach cannot be used on constructing a rate-compatible
code since an information set should not be changed according to the puncturing patterns in
the family, i.e., a common information set, usually optimized for a mother code, should be
January 17, 2018

DRAFT

16

100

10-1

R=3/4

FER

R=1/3
10-2

10-3

10-4
-2

UCM, (32,96) polar code
DCM, (32,96) polar code
UCM, (72,96) polar code
DCM, (72,96) polar code
-1

0

1

2

3

4

5

6

SNR [dB]

Fig. 3.

Performance comparisons of UCM and DCM approaches for various code rates. Here, the punctured polar codes of

Np = 96 are obtained by puncturing 32 bits from mother polar code of N = 128.

kept. Motivated by this, we in this section analyze the impact of puncturing patterns for a fixed
(pre-designed) information set A.
Definition 3: A puncturing pattern pN is said to be catastrophic for a polarized channel i
(obtained from any underlying channel W ) if
Z (i) (pN ) = 0.

(40)

More generally, a puncturing pattern pN is called catastrophic for a set of polarized channels
i ∈ A ⊆ [0 : N − 1] if
Z (i) (pN ) = 0 for any i ∈ A.

(41)

Obviously, a catastrophic puncturing pattern is universal with respect to the underlying BI-DMC
DRAFT

January 17, 2018

17

channel W . If a catastrophic puncturing pattern is used, then the block-error-rate (BLER) of
the corresponding punctured code is always 1 and thus, it should be avoid. From the boolean
functions in Section III, we obtain the two interesting facts:
•

Any puncturing pattern pN with wh (pN ) > N − 2wt(i) is non-catastrophic for the polarized
channel i.

•

The boolean functions Z (i) (pN ) can be always be expressed in the corresponding maximal
forms, in which each term represents a catastrophic puncturing pattern.

In the example of N = 4, the first fact is verified from (16)-(19). Also, the maximal form of
Z (2) (p4 ) is obtained using the fact pi ∧ p̄i = 0 as

Z (2) (p4 ) =p0 p2 ∧ p1 p3
=p0 p2 (p1 ∧ p̄1 )(p̄3 ∧ p3 ) ∧ p1 p3 (p0 ∧ p̄0 )(p̄2 ∧ p2 )
=p0 p1 p2 p3 ∧ p0 p1 p2 p̄3 ∧ p0 p̄1 p2 p3 ∧ p0 p̄1 p2 p̄3 ∧ p0 p1 p̄2 p3 ∧ p̄0 p1 p2 p3 ∧ p̄0 p1 p̄2 p3 ,

and the corresponding catastrophic puncturing patterns are

{(0, 0, 0, 0), (0, 0, 0, 1), (0, 1, 0, 0), (0, 1, 0, 1), (0, 0, 1, 0), (1, 0, 0, 0), (1, 0, 1, 0)}.

(42)

Using the boolean function Z (i) (pN ), we can check if pN is a catastrophic or not for a given
polarized channel i. Also, we can efficiently check it using the following lemma.
Lemma 1: A puncturing pattern pN is non-catastrophic for a polarized channel i if the
following rank-increment condition is satisfied:

Rank GN [i : N ], Bpc N
January 17, 2018



− Rank GN [i + 1 : N ], Bpc N



= 1.
DRAFT

18

Proof: When pN is applied, the capacity of the polarized channel i is given by
Z (i) (pN ) = I(ui ; {yj : j ∈ Bpc N }|u1i−1 )

= H(ui ) − H(ui |uN G [1 : N ], Bpc N , u1i−1 )
= H(ui ) − H(ui |{yj : j ∈ Bpc N }, ui−1
1 )



c
N
c
= 1 − H ui |ui G i, BpN + ui+1 G [i + 1 : N ], BpN ,
where the interference term caused by the known values u1i−1 , i.e., u1i−1 G([1 : i − 1], Bpc N ), is
eliminated. Then, we have that

H ui |{yj : j ∈ Bpc N }, ui−1
= 0,
1
if G(i, Bpc N ) is linearly independent from the rows of G([i + 1 : N ], Bpc N ). This completes the
proof.

In Section IV-A, we analyze the catastrophic puncturing patterns and then in Section ??, we
present an efficient algorithm to construct a non-catastrophic puncturing pattern.

A. Analysis of Catastrophic Puncturing Patterns
For a given polarized channel i with g(i) = (bn , . . . , b1 ), we characterize all catastrophic
puncturing patterns and their weight distributions.
1) Characterization of catastrophic puncturing patterns: Define CaN (bn , . . . , b1 ) by the set of
catastrophic puncturing patterns of the polarized channel i, i.e.,
∆

CaN (bn , . . . , b1 ) = {pN ∈ {0, 1}N : Z (i) (pN ) = 0}.

(43)

Now we develop an efficient recursive method to characterize CaN (bn , . . . , b1 ). We first construct
a binary tree consisting of N = 2n leaf nodes and n levels. When n = 4, there are four types
of binary trees, two of which are illustrated in Fig. 4. Note that the binary tree has two types
DRAFT

January 17, 2018

19
{0000,0001,0100,0101,0010,1000,1010}

{0000,0001,0100,0010,0011,0110,1000,1001,1100}

Stage 2

Stage 2

AND

OR

{00}

{00}

{00,01,10}

{00,01,10}

Stage 1

Stage 1

OR

𝑝"

Fig. 4.

OR

𝑝#

𝑝)

AND

𝑝*

𝑝"

AND

𝑝#

𝑝)

𝑝*

The binary trees to characterize the catastrophic puncturing patterns for n = 2.

of function nodes as “AND” node and “OR” node, and leaf nodes. Also, each level m contains
the same types of function nodes in which the type is completely determined by the bm as


 AND node, bm = 0

 OR node

(44)

bm = 1.

For a given node v, we define the subtree that contains all child nodes of v. As before, we can
derive the boolean function associated with the subtree. Then, the output of the node v (i.e., the
message value of its outgoing edge) represents the set of all binary sequences associated with
the leaf nodes in the subtree such that each binary sequence in the set is the root of the boolean
function. Due to the symmetry of the binary tree, all edges in the same level have the same
message value (see Fig. 4).
We let I and O represent the incoming and outgoing message values at a node, respectively.
From Fig. 4, the message value of the outgoing edge from v is computed using the following
update rules:
• Update rule at OR node:
O = {(p1 , p2 ) : p1 , p2 ∈ I}.
January 17, 2018

(45)
DRAFT

20

• Update rule at AND node:
O = {(p1 5 p2 ) : p1 , p2 ∈ I},

(46)

where, for the ease of expression, we used the notation of
∆

{(p1 5 p2 ) : p1 , p2 ∈ I} = {(p1 , p2 ) : p1 ∈ I, p2 ∈ {0, 1}lI }
∪ {(p1 , p2 ) : p1 ∈ {0, 1}lI , p2 ∈ I},
where lI denote the length of binary sequences in I. Using the binary tree and the above update
rules, we can find all catastrophic puncturing patterns recursively. Starting with n = 1, we have:
Ca2 (0) = {00, 01, 10} and Ca2 (1) = {00}.

(47)

Using them, we obtain Ca4 (b2 , b1 ) as


 {(p1 , p2 ) : p1 5 p2 ∈ C 2 (b2 )}, b1 = 0
a
4
Ca (b2 , b1 ) =

 {(p1 , p2 ) : p1 , p2 ∈ Ca2 (b2 )},
b1 = 1.
Repeatedly applying the above procedures, we have:
Proposition 2: For a polarized channel i with g(i) = (bn , . . . , b1 ), the set of catastrophic
puncturing patterns are obtained recursively as
n−m

Ca2 (bn , . . . , bm+1 ) =


 {(p1 5 p2 ) : p1 , p2 ∈ C 2n−m−1 (bn , . . . , bm+2 ), bm+1 = 0
a

 {(p1 , p2 ) : p1 , p2 ∈ Ca2n−m−1 (bn , . . . , bm+2 ),

bm+1 = 1

for m = n − 2, . . . , 1, 0, where the recursion starts with
Ca2 (0) = {00, 01, 10} and Ca2 (1) = {00}.

DRAFT

January 17, 2018

21

2) Weight distributions: We derive the weight distributions of catastrophic puncturing patterns
recursively, in which the recursion starts with simple polynomial of z at each coded bit location.
P
Pn
s
s
First of all, for any two input polynomial Dα (z) = m
s=0 dα (s)z and Dβ (z) =
s=0 dβ (s)z ,
where dα (s) and dβ (s) denote the corresponding numbers of catastrophic puncturing patterns
with zero weight s (i.e. s zeros), we obtain the output polynomials after OR and AND operations
as:
• OR operation:
∆

f1 (Dα (z), Dβ (z)) = Dα (z)Dβ (z).

(48)

• AND operation:
∆

f0 (α(z), β(z)) = Dα (z)(1 + z)m + Dβ (z)(1 + z)n − Dα (z)Dβ (z),

(49)

where m and n denote the highest degrees of Dα (z) and Dβ (z), respectively. Note that (48)
and (49) are derived from (45) and (46), respectively. As performed in Section IV-A1, using the
binary tree and the above update rules, we get:
Proposition 3: The weight distribution of the set of catastrophic puncturing patterns for a
polarized channel i of a length-N polar code can be computed recursively by
(N )

Di

N
X

∆

(z) =

(N )

di (s)z s

s=2wh (i)



(N/2)
(N/2)
= f[i] mod 2 Dbi/2c (z), Dbi/2c (z) ,
(1)

(50)

∆

for i ∈ {0, 1, 2..., N − 1}, where D0 (z) = z.
For example, from Theorem 3, we can derive the
(4)

D2 (z) = 2z 2 + 4z 3 + z 4 ,

(51)

which is well-matched to (42).
January 17, 2018

DRAFT

22

V. C ONSTRUCTION OF R ATE -C OMPATIBLE P OLAR C ODE
In this section, we will construct a RC polar code to send k information bits with M various
code rates R1 > R2 > · · · > RM , where a puncturing pattern pN
i is applied to a mother polar
code of length N = k/RM to achieve a target rate Ri . For all code rates, a fixed information
set A is used. Also, for the simplicity, it is assumed that N has the form of power of 2. Then,
we present the two efficient methods, named greedy and reciprocal constructions, to construct
RC polar codes where each puncturing pattern pN
i in the family is non-catastrophic.
Algorithm 1 Greedy algorithm to find pN
0
1: Initialization:
2:

Ao = {i1 , . . . , ik } denotes an ordered information set of A with respect to Hamming weight.

3:

= φ, and t = 1.
pN
0 = (0, . . . , 0), BpN
0

4:

while t ≤ k do
for j = 1, . . . , N : j ∈
/ BpN0 do

5:

if Z (it ) (pN
0 + ej ) = 1 then

6:

N
pN
0 = p0 + ej

7:

. ej denotes an unit vector with 1 in the jth location.
t = t + 1 and go to 4.

8:

else if j=N then

9:

N
pN
0 = p0 + er

10:

. r is randomly and uniformly chosen from the zero locations in pN
0
t=t+1

11:

end if

12:

end for

13:
14:

end while

DRAFT

January 17, 2018

23

A. Greedy Construction
The main idea of the greedy construction is as follows:
1) Find a possibly minimum weight non-catastrophic pN
0 such that
Z (i) (pN
0 ) = 1 for all i ∈ A.

(52)

N
Note that if wH (pN
0 ) > wH (p1 ), then it is impossible to construct the desired RC polar
N
code. In this section, it is assumed that wH (pN
0 ) ≤ wH (p1 ).
N
N
2) To obtain a non-catastrophic puncturing pattern pN
1 , we add wH (p1 ) − wH (p0 ) ones to

some zero locations in pN
0 .
N
N
3) Next, to obtain a non-catastrophic puncturing pattern pN
2 , we add wH (p2 ) − wH (p1 ) ones

to some zero locations in pN
1 .
N
N
4) In general, to obtain a non-catastrophic puncturing pattern pN
i , we add wH (pi )−wH (pi−1 )

ones to some zero locations in pN
1 .
5) Repeat the above procedures until obtaining all the puncturing patterns in the family.
Note that in the above, the locations to add ones are chosen arbitrary (i.e., randomly and
uniformly, or via a clever algorithm). Then, the proposed algorithm is established by developing a greedy algorithm to find the pN
0 (see Algorithm 1). In this algorithm, we used an
ordered information set Ao = {i1 , . . . , ik } (with respect to a Hamming weight) from A, where
wH (g(ij )) ≥ wH (g(ik )) for any j, k ∈ Ao with j ≥ k. This is motivated by the fact that a
polarized channel i tends to have more non-catastrophic puncturing patterns as wH (g(i)) becomes
larger. Thus, the use of the Ao makes it easier to satisfy the condition in line 6 in Algorithm
N
1, by adding fewer ones’ in pN
0 . Eventually, we are able to obtain a lower weight p0 to satisfy

(52). Note that Algorithm 1 is a randomized algorithm since, when the condition in line 6 in
Algorithm is not satisfied, i.e., we need to add more ones to pN
0 to satisfy the condition, one is
added to an arbitrary zero location of pN
0 . Note that although the use of Ao is helpful to find a
N
lower weight pN
0 , it does not ensure that Algorithm 1 finds the minimum weight p0 .
January 17, 2018

DRAFT

24

B. Reciprocal Construction
N
In this section, we construct a family of rate-compatible puncturing patterns pN
1 , ..., pM −1

where they are reciprocal. We first focus on the design of pN
M −1 = (pM −1,0 , ..., pM −1,N −1 ). In the
proposed approach, the |BpNM −1 | number of zero locations will be chosen so that the one-covering
N
N
property in Theorem 1 is satisfied. Then, we design the pN
M −2 by adding the |pM −2 | − |pM −1 |

number of additional zero locations to the pN
M −1 . This process will be continued until constructing
all the puncturing patterns in the family. The specific construction methods will be explained as
follows. Define the useful set operation below:
Definition 4: For any i, j ∈ [0 : N − 1], we say that i ⊥ j if wH (g(i) ⊕ g(j)) = wH (g(i)) +
wH (g(j)), where ⊕ denotes a binary addition. Then, for any two index sets M and N , define
a set operation as

M  N = g −1 (g(i) ⊕ g(j)) : i ⊥ j, i ∈ N , j ∈ M .
(i)

Using the above definitions and a given information set A, we derive the ordered sets LA , i =
0, ..., n, in a recursive manner as
∆

(0)

(0)

LA = {0} = {i1 }
∆

(1)

(1)

LA = {i ∈ [0 : N − 1] : wH (g(i)) = 1} \ A = {i1 , ..., i
(j)
LA

=



(j−1)
LA



(1)
LA



∆

(j)

\ A = {i1 , ..., i

(j)
(j)

|LA |

(1)
(1)

|LA |

}

},

P
(j)
for j = 2, ..., n. Then, we define a sequence of length nj=1 |LA as


(0) (1)
(1)
(n)
(n)
Iseed (A) = i1 , i1 , ..., i (1) , ..., i1 , ..., i (n) ,
|LA |

|LA |

(53)

where this sequence depends on the choice of an information set. Leveraging this sequence, we
construct the rate-compatible puncturing patterns (equivalently, BpNi ) as follows:
1) The BpNM −1 is constructed by taking the first |BpNM −1 | elements of Iseed (A). By construction
(i)

of LA ’s, the corresponding puncturing pattern pN
M −1 is reciprocal and non-catastrophic
with respect to A.
DRAFT

January 17, 2018

25

2) Next, the BpNM −2 is constructed by taking the first |BpNM −2 | elements of Iseed (A). Clearly,
BpNM −1 ⊂ BpNM −2 , namely, rate-compatibility is satisfied.
3) In general, the BpNi is constructed by taking the first |BpNi | elements of Iseed (A).
Note that if |Iseed (A)| < |BpN1 |, then it is impossible to construct the desired RC polar code. In
this case, we need to change the highest code rate. In the following example, we show that the
supportable highest rate is determined as a function of an information set.
Example 3: Suppose that N = 8 (e.g., n = 3) and A = {4, 6}. Then we have:
(0)

(1)

LA = {0} and LA = {1, 2}
(2)

(1)

(1)

(3)

(2)

(1)

LA = (LA  LA ) \ A = {g −1 ((0, 0, 1) ⊕ (0, 1, 0))} = {3}
LA = (LA  LA ) \ A = φ.
Then, we have Iseed ({4, 6}) = (0, 1, 2, 3). Also, in other example of A = {5, 7}, we have:
(0)

(1)

LA = {0} and LA = {1, 2, 4}
(2)

(1)

(1)

(3)

(2)

(1)

LA = (LA  LA ) \ A = {3, 6}
LA = (LA  LA ) \ A = φ.
Then, we have Iseed ({5, 7}) = (0, 1, 2, 4, 3, 6). This example shows that the number of possible
punctured bits varies according to the choice of information set A.
VI. N UMERICAL R ESULTS
In this section, we evaluate the performances of the proposed puncturing methods. For the
simulation, AWGN channel and BPSK modulation are assumed.
Length-flexibility: In this case, a puncturing is performed to construct a polar code whose
code length is not the power of 2. We employed a polar code with N = 128. To construct the
punctured polar code of Np = 96, we use the QUP and RQUP in Section III-D for UCM and
DCM, respectively. Also, CRC-aided list decoder is used with 8-bit CRC and list-size 8. Fig. 3
January 17, 2018

DRAFT

26

BLACK: LTE Turbo Code
RED: RC Polar Code (Greedy)
BLUE: RC Polar Code (Reciprocal)

FER

10-1

R=3/4

R=1/2

R=1/3
-2

10

10-3

-2

-1

0

1

2

3

4

5

6

7

8

9

SNR [dB]

Fig. 5.

Performance comparisons of RC polar codes and RC Turbo codes. Black lines denotes the performances of the RC

Turbo code. Also, red and blue lines denote the performances of the RC polar codes constructed by greedy and reciprocal
constructions, respectively.

shows that UCM performs better than DCM at rate 1/3, while vice versa, at rate 3/4. Hence, we
can learn that either UCM or DCM should be carefully chosen according to the code rate of a
target punctured polar code.
Rate-compatible polar code: Fig. 5 shows the performance comparisons of the proposed RC
polar codes and RC Turbo code. For the simulation, we constructed the two RC polar codes where
where one is developed by greedy construction in Section V-A and the other is by reciprocal
construction in Section V-B. As mother codes, both polar and Turbo codes have the length of
256 (e.g., N = 256). Also, for polar code, CRC-aided list decoder is used with 5-bit CRC and
list-size 32. Hence, the number of information bits for polar code is 93 while that of Turbo
DRAFT

January 17, 2018

27

code is 88. From this simulation, we observe that the proposed RC polar codes outperform the
RC Turbo code adopted in LTE. Also, we can see that a low-complexity reciprocal construction
performs very well.
VII. C ONCLUSION
We derived the boolean expressions of the capacities of polarized channels of finite-length
polar codes. Based on this, we provided a guideline to jointly optimize a puncturing and the
corresponding information set, Also, it was shown that for each fixed information set, there exist
the catastrophic puncturing patterns that should be avoided to yield a good performance. Furthermore, we presented two efficient methods to construct non-catastrophic puncturing patterns
for any fixed information set. Leveraging them, we designed the RC polar codes using noncatastrophic puncturing patterns. Via simulation results, it was demonstrated that the proposed
RC polar codes can outperform the RC Turbo code adopted in LTE. Therefore, polar codes can
be a good candidate for 5G channel coding.
R EFERENCES
[1] E. Arikan, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input
memoryless channels,” IEEE Trans. Inf. Theory, vol. 55, pp. 3051-3073, Jul. 2009.
[2] I. Tal and A. Vardy, “List decoding of polar codes,” IEEE Trans. Inf. Theory, vol. 61, pp. 2213-2226, May 2015.
[3] A. Eslami and H. Pishro-Nik, “Practical approach to polar codes,” in Int. Symp. Inf. Th., pp. 16-20, 2011.
[4] K. Chen, K. Niu, and J. Lin, “A hybrid ARQ scheme based on polar codes,” IEEE Commun. Letters, vol. 17, pp. 1996-1999,
2013.
[5] R. Wang and R. Liu, “A novel puncturing scheme for polar codes,” IEEE Commun. Lett., vol. 18, no. 12, pp. 2081-2084,
Dec. 2014.
[6] D.-M. Shin, S.-C. Lim, and K. Yang, “Design of length-compatible polar codes based on the reduction of polarizing
matrices,” IEEE Trans. Commun., vol. 61, no. 7, pp. 2593-2599, Jul. 2013.
[7] K. Niu, K. Chen and J.-R. Lin, “Beyond turbo codes: rate-compatible punctured polar codes,” in Proc. IEEE Int. Conf.
Commun. (ICC), Budapest, Hungary, Jun. 2013.
[8] L. Zhang, Z. Zhang, X. Wang, Q. Yu, and Y. Chen, “On the Puncturing Patterns for Punctured Polar Codes,” in Proc. IEEE
Int. Symp. Inf. Theory (ISIT) Huawaii, USA, Jul. 2014.
January 17, 2018

DRAFT

28

[9] H. Saber and I. Marsland, “An incremental redundancy hybrid ARQ scheme via puncturing and extending of polar codes,”
IEEE Trans. Commun., vol. 63, no. 11, pp. 3964-3973, Nov. 2015.
[10] V. Miloslavskaya, “Shortened Polar Codes,” IEEE Trans. Inf. Theory, vol. 61, pp. 4852-4865, Sep. 2015.
[11] S. Korada, “Polar codes for channel and source coding,” Ph.D. thesis, E’cole Polytechnique Fe’de’rale de Lausanne (EPFL),
2009.
[12] G. Sarkis, I. Tal, P. Giard, A. Vardy, C. Thibeault, and W. J. Gross, “Flexible and low-complexity encoding and decoding
of systematic polar codes,” IEEE trans. on commun., vol. 64, no. 7, pp. 2732-2745, Jul. 2016.
[13] V. Bioglio, F. Gabry and I. Land, “Low-Complexity Puncturing and Shortening of Polar Codes,” in Proc. IEEE Wire.
Comm. Net. Conf. (WCNC) Works., San Francisco, CA, Mar. 2017.

DRAFT

January 17, 2018

