Partitioned List Decoding of Polar Codes: Analysis
and Improvement of Finite Length Performance
Seyyed Ali Hashemi∗, Marco Mondelli† , S. Hamed Hassani‡, Rüdiger Urbanke§, and Warren J. Gross∗

arXiv:1705.05497v2 [] 29 Aug 2017

∗ McGill

University, Canada; emails: seyyed.hashemi@mail.mcgill.ca, warren.gross@mcgill.ca
† Stanford University, USA; email: mondelli@stanford.edu
‡ University of Pennsylvania, USA; email: hassani@seas.upenn.edu
§ EPFL, Switzerland; email: ruediger.urbanke@epfl.ch

Abstract—Polar codes represent one of the major recent
breakthroughs in coding theory and, because of their attractive
features, they have been selected for the incoming 5G standard.
As such, a lot of attention has been devoted to the development of
decoding algorithms with good error performance and efficient
hardware implementation. One of the leading candidates in
this regard is represented by successive-cancellation list (SCL)
decoding. However, its hardware implementation requires a
large amount of memory. Recently, a partitioned SCL (PSCL)
decoder has been proposed to significantly reduce the memory
consumption [1].
In this paper, we examine the paradigm of PSCL decoding
from both theoretical and practical standpoints: (i) by changing
the construction of the code, we are able to improve the performance at no additional computational, latency or memory cost,
(ii) we present an optimal scheme to allocate cyclic redundancy
checks (CRCs), and (iii) we provide an upper bound on the list
size that allows MAP performance.
Index Terms—Code Construction, CRC Selection, Partitioned
List Decoder, Polar Codes

I. I NTRODUCTION
Polar codes, introduced by Arıkan [2], achieve the capacity
of any binary memoryless symmetric (BMS) channel with
encoding and decoding complexity Θ(N log2 N ), where N
is the block length of the code. The code construction can
be performed with complexity Θ(N ) [3], [4]. Furthermore,
by taking advantage of the partial order between the synthetic
channels, it is possible to construct a polar code by computing
the reliability of a sublinear fraction of the synthetic channels
[5]. A unified characterization of the performance of polar
codes in several regimes is provided in [6]. Here, let us just
recall the following basic facts: the
√ error probability scales
with the block length roughly as 2− N [7]; the gap to capacity
scales with the block length as N −1/µ , and bounds on the
scaling exponent µ are provided in [6], [8], [9]; and polar
codes are not affected by error floors [6]. All the results
mentioned above hold under the successive-cancellation (SC)
decoder originally proposed by Arıkan in [2].
A SC list (SCL) decoder with space complexity O(LN ) and
time complexity O(LN log2 N ) is presented in [10], where
L is the size of the list. Empirically, the use of several
decoding paths yields an error probability comparable to that
under optimal MAP decoding with practical values of the list
size. In addition, by adding only a few extra bits of cyclic
redundancy check (CRC) precoding, the resulting performance

is comparable with state-of-the-art LDPC codes. Because of
their attractive properties, polar codes have been selected for
the eMBB control channel in the incoming 5G standard [11].
Although SCL significantly improves the error-correction
performance of polar codes, it comes at the cost of lower speed
and higher area occupation when implemented in hardware. In
particular, it was shown in [12] that the high area requirement
of SCL is mostly dominated by its memory usage. Several
techniques have been proposed to speed up SCL [13], [14]
without degrading its error-correction performance. However,
all these techniques require the same amount of memory as
the SCL decoder. The partitioned SCL (PSCL) algorithm in
[1] breaks the code into constituent codes (partitions) and
each constituent code is decoded with the SCL algorithm.
It was shown that the memory requirement of PSCL can be
significantly reduced as the number of partitions increases.
However, as the number of partitions increases, the errorcorrection performance of PSCL degrades in comparison with
SCL at the same list size.
In this paper, we present several improvements on the
original PSCL scheme. These improvements are both practical,
in the sense that they boost the error-correction performance of
the code, and theoretical, in the sense of the analysis and the
understanding of the algorithm. In particular, our contributions
can be summarized as follows.
1) Improved Code Construction. Inspired by [15], we
propose a novel code construction which leads to a
remarkable gain in the finite length performance. In
particular, the idea is to design the polar code for a
“better” channel, namely for a channel with a larger SNR
compared to the channel that is used for transmission.
Furthermore, the performance improvement comes at
no additional cost in terms of memory, latency, or
operational complexity, since we are simply constructing
a polar code for a better channel and do not alter any
of the encoding or decoding procedures.
2) CRC Selection Scheme. We propose a successive CRC
assignment strategy to select the number of CRC bits.
Our approach is based on the successive minimization
of the error probability for each partition. As such, this
selection strategy is optimal in the sense that it minimizes the total error probability of the PSCL decoding
algorithm.

û0

α 0→
1

û1

B. Successive-Cancellation (SC) Decoding

1

β 0→1
1

û2
û3
û4
û5

SC decoding can be represented on a binary tree as shown
in Fig. 1 for a polar code of length 8. The decoder is
−1
−1
}
= {α0n , α1n , . . . , αN
given as input the vector α0→N
n
n
of logarithmic likelihood ratio (LLR) values. At each level t
of SC decoding, the LLR values are calculated as
!!
 i 
i+2t
α
α
t+1
t+1
tanh
, (2)
αit = 2 arctanh tanh
2
2

α 0→
2

3

β 0→
2

3

α0→7
3

7
4→
α2
7
4→

β2

û6

t

Fig. 1.

t

i
i
αi+2
= αi+2
t
t+1 + (1 − 2βt )αt+1 ,

û7

(3)

and the hard-decision estimates βt are calculated as

Polar code SC decoding tree for N = 8.

t

i+2
i
βti = βt−1
⊕ βt−1
,

3) List Size Requirement for MAP Decoding. We present an
upper bound on the size of the list that ensures optimal
MAP performance. The proof holds for the special case
of the binary erasure channel (BEC), but numerical simulations suggest that the claim holds for the transmission
over general channels. The bound exploits the fact that
the information bits tend to cluster at the end of the
successive decoding process.
The remainder of the paper is organized as follows. After
revising some preliminary material about the various decoding
algorithms of polar codes in Section II, the following 3
sections contain the contributions of this work: Section III
describes the improved code construction; Section IV presents
the scheme to select the number of CRC bits; and Section V
provides the upper bound on the size of the list sufficient to
ensure MAP performance. Finally, Section VI provides some
concluding remarks.

=

(4)

i+2t
βt−1
,

(5)

where ⊕ is the bitwise XOR operation. Eventually, at a leaf
node, the i-th bit ûi is estimated as
(
0, if i ∈ F or αi0 ≥ 0,
i
ûi = β0 =
(6)
1, otherwise.
A hardware-friendly formulation of (2) can be written as
t

t

i+2
i
αit = sgn(αit+1 ) sgn(αi+2
t+1 ) min(|αt+1 |, |αt+1 |),

(7)

which introduces negligible error-correction performance loss
in comparison with (2), see [16]. In this paper, we use (7) and
(3) in the numerical simulations. Let us consider that the LLR
values are quantized with Qα bits. The memory requirement
of SC decoding can be calculated as [16]
MSC = (2N − 1) Qα + N − 1.

(8)

C. Successive-Cancellation List (SCL) Decoding

II. P RELIMINARIES
A. Polar Coding
A polar code of length N with K information bits and rate
R , K/N is denoted by P(N, K) and can be constructed
by concatenating two polar codes of length N2 . This recursive
construction can be described with a matrix multiplication as
x = uBN G⊗n ,

t
βti+2

(1)

where u = {u0 , u1 , . . . , uN −1 } is the sequence of input bits,
x = {x0 , x1 , . . . , xN −1 } is the sequence of coded bits, BN is
the bit-reversal permutation matrix, G⊗n
 is the n-th Kronecker
product of the polarizing matrix G = 11 01 , and n = log2 N .
The transformation (1) is polarizing in the sense that the
synthetic channels seen by the input bits tend to become either
completely noiseless or completely noisy. Thus, the information bits are assigned to the positions of u corresponding to
the best K synthetic channels. The remaining positions of
u are “frozen” to predefined values that are known at the
decoder. This set of frozen positions is denoted by F . The
resulting u is coded into x using (1); then, x is modulated
and transmitted through the channel. Throughout this paper,
we consider Binary Phase-Shift Keying (BPSK) modulation.

In order to improve the error-correction performance, the
SCL decoder with list size L, denoted by SCL(L), employs L
SC decoders in parallel. For i ∈ {0, . . . , N − 1}, when the i-th
bit ûi needs to be estimated, instead of (6), the SCL decoder
creates two paths corresponding to the decisions ûi = 0 and
ûi = 1. In order to keep L candidates out of the 2L generated
paths, a path metric (PM) based on LLRs was developed in
[12]. A hardware-friendly formulation of such a path metric
can be stated as
PM−1l = 0,
(
PMi−1l +|αi0l |,
PMil =
PMi−1l ,

1−sgn(αi0 )
l
,
2

if ûil 6=
otherwise,

(9)

where l is the path index.
Eventually, the SCL decoder outputs a list of L candidate
codewords. A CRC can be used to assist the SCL decoder in
order to find the correct codeword in the list of candidates. Let
us assume the path metric values are quantized with QPM bits.
The memory requirement of SCL decoding can be derived as
[12]
MSCL = (N + (N − 1) L) Qα + LQPM + (2N − 1) L. (10)

·104

α 0→ N
β 0→ N
n− 4 −
1
2

Memory Bits

n− 4 −
1
2

SCL

α

0→
n− N
1 2 −1

SCL

β 0→ N
n−
1 2 −1
1
−
N
N →
2 1
n−

SCL

α

−1
α0→N
n

PSCL(P ,8)
SC
SCL(8)

6
4
2
20

21

1
N

−

22
23
Number of Partitions

24

25

1→
N −
2 1

β n−

Fig. 3. Memory bits required by PSCL(P ,8) as a function of the number
of partitions P . The PSCL decoder provides a significant improvement in
the memory requirement compared to the SCL decoder and it approaches the
memory required by the SC decoder for practical values of P .

SCL
Fig. 2.

PSCL tree structure for P = 4.
100

D. Partitioned Successive-Cancellation List (PSCL) Decoding




X N
N
+L
− 1  Qα
=
2k
P


log2 P

MPSCL

k=0

log2 P

+ LQPM +



X N
2N
+
L
−
1
,
2k
P

(11)

k=1

where 2 ≤ P < N . It should be noted that in (11), only
one copy of the top log2 P levels of the tree has to be
stored, whereas for the bottom part, L copies are needed.
The savings in memory bits guaranteed by the PSCL decoder
are summarized in Fig. 3 for P(1024, 512) with L = 8,
Qα = 6 and QPM = 8. Note that the memory requirement
of PSCL(P ,8) quickly become close to those of the standard
SC decoder as P increases. However, this memory saving is
obtained at the cost of a higher error probability. Fig. 4 shows
the degradation in the frame error rate (FER) performance of
PSCL, as the number of partitions increases.

10−1

FER

SCL-based decoders have large memory requirements,
which results in a large area occupation in the hardware
implementation. To overcome this issue, the PSCL decoder
was proposed in [1]. As shown in Fig. 2, the PSCL decoding
tree is divided into P subtrees, called partitions: each partition
is a polar code of length N/P and it is decoded by using a
CRC-aided SCL decoder with list size L. We denote the PSCL
decoder with P partitions and list size L as PSCL(P ,L).
At the end of each partition, a CRC can be used to select the
codeword that is passed to the next partition. In case there is
more than one compatible codeword, the one with the largest
path metric is selected. As a result, it is not necessary to store
L full trees as in SCL, but only L copies of the part of the tree
contained in the partitions. Moreover, memory can be shared
among the P partitions, which results in significant savings as
P increases.
The memory requirement of PSCL with P partitions can be
calculated as [1]

10−2
SC
SCL(8)
PSCL(2,8)
PSCL(4,8)
PSCL(8,8)

10−3

1

1.5

2

2.5

3

Eb /N0 [dB]
Fig. 4. FER comparison between SC, SCL(8), and PSCL(P , 8) for P ∈
{2, 4, 8} when no CRC is used. The polar code is P(1024, 512) and it is
optimized for SNR = 2 dB.

III. I MPROVED C ODE C ONSTRUCTION
In this section, we describe an improved code construction
that allows to obtain a gain in the error-correction performance
at no additional complexity cost.
∗
Denote by W = BAWGN(SNR ) the Binary Additive
White Gaussian Noise channel with SNR equal to SNR∗ and
let Pα (N, K) be the polar code of length N and rate K/N designed for the transmission over Wα = BAWGN(SNR∗ /α).
In words, when α = 1, Pα (N, K) is the polar code designed
for W and, as α goes from 1 to 0, Pα (N, K) is a polar code
designed for better and better channels.
Consider the transmission of the family of polar codes
{Pα (N, K) : α ∈ [0, 1]} over the channel W . Note that the
transmission channel is fixed, while the codes of the family
are designed for different channels as α varies. Empirically,
one observes that the error probability under MAP decoding
decreases as α goes from 1 to 0. However, the error probability
under SC decoding increases as α goes from 1 to 0. The latter
is due to the fact that the frozen positions of a polar code

PSCL(4,8)

10−1

10−1

10−2

10−2

10−3

10−2

10−3

FER

100

FER

FER

PSCL(2,8)
100

10−4
10−3
10−5

10−4

10−4
2
1

2

3

Eb /N0 [dB]
Design SNR = 2 dB
Design SNR = 4 dB

1

2

3

Eb /N0 [dB]
Design SNR = 3 dB
Design SNR = 5 dB

Fig. 5. FER for the transmission of P(1024, 512) under PSCL decoding
with L = 8 and P ∈ {2, 4}. Different curves correspond to different design
SNR values and no CRC is used.

are chosen in order to minimize its error probability under
SC decoding. Starting from these two observations, in [15] a
trade-off between complexity and performance is developed
by considering practical decoders (e.g., SCL). The tradeoff comes from the fact that, as the decoder becomes more
complex (e.g., the list size increases), the best performance is
achieved for smaller values of α.
This principle can also be applied to PSCL decoding, as
shown in the numerical simulations of Figs. 5–7. In particular, different curves of Fig. 5 refer to different codes (i.e.,
codes designed for different SNRs). The x-axis corresponds
to SNR of the transmission channel, and y-axis labels the
correspondent FER. Note that, at Eb /N0 = 3 dB, a polar
code constructed for SNR = 5 dB significantly outperforms
the polar code optimized for SNR = 3 dB (which is the SNR
of the channel over which the transmission takes place).
Fig. 6 plots the error-correction performance of the code
as a function of the design SNR. The transmission channel is
fixed and it has Eb /N0 = 3 dB. Different curves correspond to
different decoding algorithms. For SC decoding, the best errorcorrection performance is achieved for a code constructed for
SNR = 3 dB. Again, this is to be expected, since the polar
code is constructed in order to minimize the error probability
under SC decoding. For SCL(8), the best error-correction
performance is achieved when the code is constructed for
SNR = 5 dB. For PSCL(2, 8), the optimal design SNR is
4.5 dB, and for PSCL(4, 8), it is 4 dB. Note that, as the
number of partitions increases, the optimal design SNR for
PSCL decoding moves from that for SCL decoding to that for
SC decoding. This is due to the fact that, as the number of
partitions increases, the error-correction performance of PSCL
moves from that of SCL to that of SC (see also Fig. 4).

3

4

5

Design SNR [dB]
SC - Eb /N0 = 3 dB

PSCL(2,8) - Eb /N0 = 3 dB

SCL(8) - Eb /N0 = 3 dB

PSCL(4,8) - Eb /N0 = 3 dB

Fig. 6.
FER for PSCL(2,8), PSCL(4,8), SCL(8), and SC decoding of
P(1024, 512) as a function of the design SNR. Different curves correspond to
different decoding algorithms and no CRC is used. Note that the transmission
takes place over a BAWGN with SNR = 3 dB.

Fig. 7 summarizes the gains in the error-correction performance guaranteed by the improved code construction. It also
compares the error-correction performance of polar codes with
that of an LDPC code of length 1152 and rate 1/2 which
is used in the WiMAX standard. The dashed curves refer to
polar codes in which the design SNR is equal to the SNR
of the transmission channel, i.e., polar codes constructed in
the standard way. The continuous curves refer to polar codes
in which the design SNR is chosen in order to minimize the
FER. Both PSCL(2, 8) and PSCL(4, 8) exhibit gains of 0.5
dB at a target FER of 10−3 . Note that these gains come
“for free”, since changing the design SNR does not affect
the computational complexity, the latency or the memory
requirement.
IV. CRC S ELECTION S CHEME
In this section, we discuss the use of CRC bits and we
present a strategy to choose the length of the CRC that
minimizes the FER.
The error-correction performance under SCL decoding is
lower bounded by that under MAP decoding. However, in
scenarios of interest in practical applications, even the performance of the MAP decoder is not satisfactory compared to
state-of-the-art coding schemes, such as LDPC codes. In order
to address this issue, it was shown in [10] that, by adding a
CRC, the error-correction performance under SCL decoding
significantly outperforms that under MAP decoding with no
CRC, and it is comparable to that of state-of-the-art LDPC
codes.
Denote by C the length of the CRC. In order to send K
bits of information for N channel uses, we need to use a code
of block length N and rate (K + C)/N . More specifically, let

100

Partition 1 - Eb /N0 = 2 dB

10−2

Partition 2 - Eb /N0 = 2 dB
−1

10

FER

FER

10−2
SC
SCL(8) - Standard
SCL(8) - Improved
PSCL(2,8) - Standard
PSCL(2,8) - Improved
PSCL(4,8) - Standard
PSCL(4,8) - Improved
WiMAX LDPC

10−3

10−4

10−5

1

1.5

10−3

2

2.5

0

3

Fig. 7. FER performance comparison between the standard and the improved
construction of the code P(1024, 512). Different curves correspond to
different decoding algorithms and no CRC is used. Note that gains of 0.5
dB are obtained at a target FER of 10−3 for PSCL(2, 8) and PSCL(4, 8).
The error-correction performance of the WiMAX LDPC code of length 1152
and rate 1/2 is also plotted for comparison.

us focus on the PSCL decoder with P partitions. Consider the
vectors c = {c1 , c2 , . . . , cP } and k = {k1 , k2 , . . . , kP }, where
cp is the length of the CRC concatenated to the p-th partition
and kp represents the number of information bits associated
to the p-th partition. Clearly,

p=1

cp = C,

P
X

kp = K.

10

15

CRC Length

Eb /N0 [dB]

P
X

5

(12)

p=1

Then, in the p-th partition, we select the most reliable kp + cp
bits and use the first kp to store the information bits and the
last cp to store the CRC bits.
On the one hand, if cp is too small, then some of the
incorrect paths might pass the CRC and one of these incorrect
paths might be transmitted to the next partition, thus causing
an error. On the other hand, if cp is too large, then the positions
chosen to store the CRC might not be sufficiently reliable.
Hence, there is a trade-off in the choice of the vector c.
We propose a successive CRC assignment strategy that can
be described as follows. For p ∈ {1, . . . , P }, we evaluate
numerically the FER of the p-th partition as a function of cp ,
assuming that the previous partitions were decoded correctly.
Then, we choose the value of cp that minimizes the FER. In
this way, the FER of the PSCL algorithm is minimized.
Fig. 8 and Fig. 9 consider the transmission of the polar
code P(1024, 512) over a channel with SNR = 2 dB and
represent the error-correction performance of the P partitions
of the PSCL decoder as a function of the length of the CRC
for P = 2 and P = 4, respectively. The design SNR of
the code is equal to the SNR of the transmission channel.
For PSCL(2,8), partition 1 and partition 2 achieve the best
error-correction performance with a CRC of length 4 and
7 respectively. Therefore, we conclude that PSCL(2,8) has

Fig. 8. Effect of the CRC length on the FER for PSCL(2,8) decoding of
P(1024, 512). Different curves correspond to different partitions. The SNR
of the transmission channel and the design SNR of the code are equal to 2
dB.

optimal performance when a CRC of length 4 is concatenated
to the first partition and a CRC of length 7 is concatenated to
the second. Similarly, for PSCL(4,8), partitions 1, 2, 3, and 4
achieve the best error-correction performance with CRCs of
length 2, 4, 7, and 4, respectively. Therefore, PSCL(4,8) has
optimal performance with c = {2, 4, 7, 4}.
Fig. 10 summarizes the gains in the error-correction performance guaranteed by the successive CRC assignment strategy
and also provides a comparison with the LDPC code of
length 1152 and rate 1/2 which is used in the WiMAX
standard. In particular, we consider the SCL(8), PSCL(2,8),
and PSCL(4,8) decoders and we compare the successive CRC
assignment scheme with the CRC lengths chosen in [1]. All the
algorithms exhibit gains of about 1/4 dB at the target FER of
10−3 . It is worth mentioning that, in order to further improve
the performance, one can also optimize the CRC generating
polynomial for each partition as discussed in [17] for SCL
decoders.
V. L IST S IZE R EQUIREMENT FOR MAP D ECODING
In this section, we present a simple upper bound on the
list size of the SCL decoder that guarantees the same errorcorrection performance as the MAP decoder.
Recall that MAP decoding of a code of length N with K
information bits requires finding the most reliable codeword
out of the 2K possible codewords. Note also that SCL decoding with list size 2K provides a list of 2K codewords from
which the most reliable one is selected. Therefore, SCL(2K )
is equivalent to MAP decoding. For polar codes, in order for
SCL to be equivalent to MAP, Theorem 1 asserts that the
list size can be chosen to be much smaller than 2K . As we
will argue shortly, the result of Theorem 1 can be particularly
useful when low-rate polar codes are deployed.
Theorem 1: Consider the transmission of P(N, K) over a
BEC and let M denote the number of information bits located

10−1

Partition 1 - Eb /N0 = 2 dB
Partition 2 - Eb /N0 = 2 dB

10−1

Partition 3 - Eb /N0 = 2 dB

FER

FER

Partition 4 - Eb /N0 = 2 dB

10−2

10−2
SCL(16)
SCL(1024)

10−3
0

5

10

15

1

CRC Length

1.5

2

2.5

3

Eb /N0 [dB]

Fig. 9. Effect of the CRC length on the FER for PSCL(4,8) decoding of
P(1024, 512). Different curves correspond to different partitions. The SNR
of the transmission channel and the design SNR of the code are equal to 2
dB.

Fig. 11. FER performance comparison between SCL(1024) and SCL(16)
for the transmission of P(128, 10) on a BAWGN channel. Note that, since
there are 10 information bits in the code, SCL(1024) is equivalent to MAP
decoding. It can be seen that, since 6 of the information bits are located after
the last frozen bit, SCL(16) results in the same error-correction performance
as the MAP decoder.

100
10−1

FER

10−2
10−3
SCL(8) - CRC(32) [1]
SCL(8) - CRC(7)
PSCL(2,8) - CRC(16,16) [1]
PSCL(2,8) - CRC(4,7)
PSCL(4,8) - CRC(8,8,8,8) [1]
PSCL(4,8) - CRC(2,4,7,4)
WiMAX LDPC

−4

10

10−5
10−6
1

1.5

2

2.5

3

Eb /N0 [dB]
Fig. 10. FER performance comparison for the transmission of P(1024, 512)
between the proposed successive CRC assignment scheme (solid) and the
CRC lengths chosen in [1] (dashed). Different curves correspond to different
decoding algorithms. In the successive CRC assignment scheme, the lengths
of the CRCs are optimized separately for each value of the SNR of the
transmission channel. Note that gains of about 1/4 dB are obtained at a
target FER of 10−3 for all the decoding algorithms. The error-correction
performance of the WiMAX LDPC code of length 1152 and rate 1/2 is also
plotted for comparison.

after the last frozen bit. Then, SCL decoding with L = 2K−M
is equivalent to MAP decoding.
Proof: Recall that for the case of the transmission over
a BEC, the synthetic channels seen by the input bits are also
BECs. Hence, the SCL decoder doubles the number of paths
every time that one of the information bits cannot be decoded
and all these paths are equally likely. Furthermore, when the
SCL decoder encounters a frozen position, it tries to decode
such a position and, if this is possible, it cancels all the paths

that do not agree with the value of this position.
Run the SCL decoder until the last frozen bit. As there
are at most K − M information bits until this position, there
are at most 2K−M equally likely paths. Therefore, the SCL
decoder will not exceed its list size. Assume now that the
MAP decoder does not fail. This means that there is only one
remaining path at the end of the decoding process. Since there
are no more frozen bits, no more path cancellations can occur.
Therefore, only one path must be available at this point and no
new paths will be created while decoding the last M positions.
As a result, the SCL decoder also succeeds.
While we have proved Theorem 1 for the BEC, numerical
experiments suggest that the result holds for other important
channels such as the BAWGN.
Let us illustrate the importance of this result through the
analysis of a practical setting. Polar codes have been selected
for the transmission over the control channel in 5G. Such a
task requires codes of short lengths (≤ 1024) with rates as
low as 1/12 [18]. Consider a polar code of length 128 and
rate 1/12, which is optimized for SNR = 2 dB. This code has
10 information bits and 6 of them are located after the last
frozen bit. Therefore, SCL(16) can provide the same result
as the MAP decoder. This is illustrated in Fig. 11 when the
transmission takes place over the BAWGN channel.
Recall that PSCL results in polar codes of length N/P that
are decoded with SCL. Consider the decoding of a polar code
of length 1024 and rate 1/12 with PSCL with P = 2. The code
is constructed for SNR = 2 dB. The first partition contains 7
information bits and 3 of them are located after the last frozen
bit. Therefore, SCL(16) results in the same error performance
as a MAP decoder over that partition. Suppose now that we
decode the same code with PSCL with P = 4. Then, the

first partition contains only frozen bits; the second partition
contains 7 information bits and 3 are located after the last
frozen bit; and the third partition contains 9 information bits
and 3 of them are located after the last frozen bit. Therefore,
for the second and the third partitions, SCL(16) and SCL(64)
are respectively equivalent to the MAP decoder. In conclusion,
while running PSCL decoding, it is possible to perform MAP
decoding on some of the partitions with practical values of the
list size.
VI. C ONCLUSIONS
Partitioned successive-cancellation list (PSCL) decoding of
polar codes has been shown to be a good candidate for
applications requiring low memory usage and small area
occupation when implemented on hardware. The focus of this
paper concerns the finite length error-correction performance
of PSCL. First of all, we present a novel code construction
inspired by the interpolation method of [15], which results in
a remarkable performance improvement. Then, we propose a
successive CRC selection assignment scheme to choose the
lengths of the CRCs assigned to the different partitions. This
approach provides the optimal error-correction performance
among all possible CRC assignments. Finally, we prove a
simple upper bound on the list size required by the successivecancellation list (SCL) decoder in order to achieve an error
performance equal to that of the optimal MAP decoder. We
further argue that in certain practical applications where lowrate codes are used, this upper bound becomes effective in
choosing the appropriate list sizes to perform MAP decoding
with SCL.
Our analysis also indicates that there is still a gap between
the error-correction performance of PSCL and that of SCL
in certain high-SNR scenarios. Future work includes reducing
this gap by considering more sophisticated PSCL algorithms.
ACKNOWLEDGMENT
The work of M. Mondelli is supported by an Early Postdoc.
Mobility fellowship from the Swiss National Science Foundation. This work was done while S. H. Hassani was visiting the
Simons Institute for the Theory of Computing, UC Berkeley,
as a research fellow. The authors would like to thank Mr.
Furkan Ercan of McGill University for providing the LDPC
results.
R EFERENCES
[1] S. A. Hashemi, A. Balatsoukas-Stimming, P. Giard, C. Thibeault, and
W. J. Gross, “Partitioned successive-cancellation list decoding of polar
codes,” in Proc. of the IEEE Int. Conf. on Acoust., Speech and Signal
Process., Shanghai, China, Mar. 2016, pp. 957–960.
[2] E. Arıkan, “Channel polarization: A method for constructing capacityachieving codes for symmetric binary-input memoryless channels,” IEEE
Trans. Inform. Theory, vol. 55, no. 7, pp. 3051–3073, July 2009.
[3] I. Tal and A. Vardy, “How to construct polar codes,” IEEE Trans. Inform.
Theory, vol. 59, no. 10, pp. 6562–6582, Oct. 2013.
[4] R. Pedarsani, H. Hassani, I. Tal, and E. Telatar, “On the construction of
polar codes,” in Proc. of the IEEE Int. Symposium on Inform. Theory
(ISIT), St. Petersberg, Russia, Aug. 2011, pp. 11–15.
[5] M. Mondelli, S. H. Hassani, and R. Urbanke, “Construction of polar
codes with sublinear complexity,” in Proc. of the IEEE Int. Symposium
on Inform. Theory (ISIT), Aachen, Germany, June 2017, pp. 1853–1857.

[6] M. Mondelli, S. H. Hassani, and R. Urbanke, “Unified scaling of polar
codes: Error exponent, scaling exponent, moderate deviations, and error
floors,” IEEE Trans. Inform. Theory, vol. 62, no. 12, pp. 6698–6712,
Dec. 2016.
[7] E. Arıkan and I. E. Telatar, “On the rate of channel polarization,” in
Proc. of the IEEE Int. Symposium on Inform. Theory (ISIT), Seoul, South
Korea, July 2009, pp. 1493–1495.
[8] S. H. Hassani, K. Alishahi, and R. Urbanke, “Finite-length scaling for
polar codes,” IEEE Trans. Inform. Theory, vol. 60, no. 10, pp. 5875–
5898, Oct. 2014.
[9] D. Goldin and D. Burshtein, “Improved bounds on the finite length
scaling of polar codes,” IEEE Trans. Inform. Theory, vol. 60, no. 11,
pp. 6966–6978, Nov. 2014.
[10] I. Tal and A. Vardy, “List decoding of polar codes,” IEEE Trans. Inform.
Theory, vol. 61, no. 5, pp. 2213–2226, May 2015.
[11] “Final report of 3GPP TSG RAN WG1 #87 v1.0.0,” Reno, USA, Nov.
2016.
[12] A. Balatsoukas-Stimming, M. Bastani Parizi, and A. Burg, “LLR-based
successive cancellation list decoding of polar codes,” IEEE Trans. Signal
Process., vol. 63, no. 19, pp. 5165–5179, Oct. 2015.
[13] S. A. Hashemi, C. Condo, and W. J. Gross, “A fast polar code list
decoder architecture based on sphere decoding,” IEEE Trans. Circuits
Syst. I, vol. 63, no. 12, pp. 2368–2380, Dec. 2016.
[14] S. A. Hashemi, C. Condo, and W. J. Gross, “Fast simplified successivecancellation list decoding of polar codes,” in IEEE Wireless Commun.
and Netw. Conf., March 2017, pp. 1–6.
[15] M. Mondelli, S. H. Hassani, and R. Urbanke, “From polar to ReedMuller codes: A technique to improve the finite-length performance,”
IEEE Trans. Commun., vol. 62, no. 9, pp. 3084–3091, Sept. 2014.
[16] C. Leroux, A. J. Raymond, G. Sarkis, and W. J. Gross, “A semi-parallel
successive-cancellation decoder for polar codes,” IEEE Trans. Signal
Processing, vol. 61, no. 2, pp. 289–299, Jan. 2013.
[17] Q. Zhang, A. Liu, X. Pan, and K. Pan, “CRC code design for list
decoding of polar codes,” IEEE Commun. Lett., vol. 21, no. 6, pp. 1229–
1232, June 2017.
[18] “Evaluation on channel coding candidates for eMBB control channel,”
3GPP TSG RAN WG1 #87 R1-1611109, Reno, USA, Nov. 2016.

