1

Polar Code Construction for List Decoding

arXiv:1707.09753v1 [] 31 Jul 2017

Peihong Yuan, Tobias Prinz, Georg Böcherer

Abstract—A heuristic construction of polar codes for successive
cancellation list (SCL) decoding with a given list size is proposed
to balance the trade-off between performance measured in frame
error rate (FER) and decoding complexity. Furthermore, a
construction based on dynamically frozen bits with constraints
among the ”low weight bits” (LWB) is presented. Simulation
results show that the LWB-polar codes outperform the CRCpolar codes and the eBCH-polar codes under SCL decoding.

I. I NTRODUCTION
Polar codes were proposed in [1], [2] and they achieve the
capacity of binary input discrete memoryless channel asymptotically in the block length [2]. Under successive cancellation
list (SCL) decoding [3], the finite length performance of polar
codes can be improved by enhancing the distance spectrum.
Cyclic redundancy check (CRC)-polar codes [3] and ReedMuller (RM)-polar codes [4] are proposed to improve the
performance of polar codes with short and moderate length.
Polar codes with dynamically frozen bits and in particular
eBCH-polar codes are introduced in [5]. A construction for
multi-kernel polar codes based on the maximization of the
minimum distance is proposed in [6]. The authors in [7] analyze short concatenated polar and CRC codes with interleaving
and suggest careful optimization of the outer code.
In this work, we analyze methods to improve the distance
spectrum for polar codes. We propose a heuristic construction
to optimize the frame error rate (FER) for a given list size.
We achieve this by balancing the trade-off between FER
under successive cancellation (SC) decoding and maximum
likelihood (ML) decoding. A ”Low weight bits” (LWB) construction based on dynamically frozen bits is presented, which
outperforms CRC-polar codes and eBCH-polar codes for all
considered decoding list sizes.
This work is organized as follows. In Sec. II, polar codes
are reviewed and existing methods to improve their distance
spectrum are discussed. In Sec. III, the tool proposed in [8]
is used to analyze the distance spectrum of polar codes. In
Sec. IV, we balance the trade-off between distance spectrum
and the performance under SC decoding for a given list size.
In Sec. V, we discuss the new LWB polar code construction.
We conclude in Sec. VI.
II. P RELIMINARIES
A. Polar Codes
A binary polar code of block length n and dimension k
is defined by the polar transform F⊗ log2 n and n − k frozen
positions, where F denotes the Arıkan kernel


1 0
F=
(1)
1 1

and ⊗ denotes the Kronecker product and (·)⊗ denotes the
Kronecker power. Polar encoding can be represented by
c = uF⊗ log2 n .

(2)

The vector c is the code word. The vector u includes k
information bits and n − k predefined frozen bits. Polar
SC decoding uses the observation y and previous estimates
û1 , . . . , ûi−1 to decode ui . Both encoding and SC decoding
have complexity O(n log2 n) [2].
The polar code construction finds the most reliable bits
under SC decoding. The Monte Carlo (MC) construction was
introduced in [1], [2], and needs extensive simulations. In this
work, the Gaussian approximation [9] for density evolution
[10] with the J-function [11] and its numerical approximation
[12] are used, which has much lower complexity and performs
very close to the MC construction.
To improve the coding performance, an SCL decoding
algorithm was proposed in [3]. The SCL decoder provides
ML-performance for polar codes if the list size L is large
enough and can be performed with O(Ln log2 n) complexity.
For short and moderate lengths, the original polar codes with
SCL decoding still perform worse than Turbo and LDPC codes
because of the low minimum distance [3].
B. CRC and Polar Code Concatenation
The work in [3] enhance the distance spectrum of polar
codes by serial concatenating an error-detecting code and a
polar code. So far in literature, the distance property of CRCpolar codes can be found only through simulations.
We use CRC codes with ℓCRC check bits as outer codes
and the SCL decoder chooses the most likely codeword that
satisfies the CRC. The generator polynomials are described by
a hexadecimal number (Koopman Notation [13]), e.g., ’0x5b’
denotes the generator polynomial g(x) = x7 + x5 + x4 + x2 +
x + 1 (ℓCRC = 7).
Remark 1. An interleaver between the CRC encoder and polar
encoder affects the code performance significantly [7]. In this
work, conventional systematic CRC encoding is used without
interleaving. Instead, we optimize over the polynomial g(x).
No performance loss compared to interleaving is observed.
C. RM-polar Codes
The second idea is called Reed-Muller (RM)-polar codes
[4]. The RM-polar codes are constructed by combining the
code constructions of RM codes and polar codes. Both RM
and polar codes are obtained from the same polarization matrix
F⊗ log2 n .
While polar codes select information bits according to
the bit reliability under SC decoding, RM codes select the

2

u1 , u2 , u5 = 0 are statically frozen bits and since u1 , . . . , u6
are decoded successively, u3 is unfrozen. u4 = u3 is dynamically frozen and u6 is unfrozen. The construction of eBCHpolar codes is as follows:

information bits according to the row weight. The bits with
the largest weights of their corresponding rows are selected as
information bits, and the other bits are chosen as frozen bits.
The construction of RM-polar codes sacrifices some reliable
bits under SC decoding in order to guarantee a better minimum
distance:
• Freeze the bits with row weight smaller than a given
minimum weight w.
• Choose the most reliable remaining bits as information
bits.
An RM-polar code with guaranteed minimum distance (≥ d)
can be easily constructed by using this method. With large
decoding list, RM-polar codes outperform the original polar
codes because of the better distance property.
However, RM-polar codes are not very flexible, because the
minimum Hamming weight of RM codes has to be a power
of 2. Practically, RM-polar codes do not work well for short
block length. e.g., to design a (128, 64) RM-polar code, there
are only 2 options for the minimum distance d: 8 (equivalent
to the original polar code) or 16 (equivalent to the RM code).

Remark 3. CRC-polar codes are also a special case of polar
codes with dynamically frozen bits. Consider an ℓCRC bits
CRC outer code and an (n, k + ℓCRC ) polar code. At the
receiver, after the list decoding of the first k bits, the remaining
ℓCRC bits can be calculated just like dynamically frozen bits.
Therefore, an equivalent code construction of (n, k) CRC-polar
codes is as follows:

Remark 2. Polar codes designed for higher SNR (than the
operating points) can also improve the distance property by
sacrificing reliable bits under SC decoding [14].

1 Construct an original (n, k + ℓCRC ) polar code.
2 Dynamically freeze the last ℓCRC information bits with
the CRC rule.

D. eBCH Polar Subcodes
The third idea is a code construction based on extended
primitive binary BCH (eBCH) codes and polar codes by
using dynamically frozen bits [5]. Some of the frozen bits
in eBCH-polar codes are so-called dynamically frozen bits,
which are defined as linear combinations of previous (with
smaller indices) information bits instead of predetermined
values. Consider an (n, k ′ ) eBCH code with parity check
matrix H and an (n, k) polar code with matrix F⊗ log n , where
k ′ ≥ k. Let this (n, k) polar code be a subcode of the (n, k ′ )
eBCH code, i.e.,
(2)
cH T = uF⊗ log2 n H T = 0
(3)
where (·)T denotes the transpose of a matrix. Define a constraints matrix
V = Q(F⊗ log2 n H T )T .

(4)

We have uV T = 0, where the matrix Q describes elementary
row operations on (F⊗ log2 n H T )T , such that all rows of V
end with ”1” in distinct columns. The (n − k ′ ) × n matrix V
describes at most n − k ′ (static or dynamically) frozen bits.
The position of the last ”1” in every row denotes a frozen
position because of SC decoding. e.g.,


1 0 0 0 0 0
 0 1 0 0 0 0

(5)
V =
 0 0 1 1 0 0
0 1 0 0 1 0
means that u1 , u2 , u4 , u5 are frozen with constraints
u1 = 0,
u2 = 0,
u4 = u3 ,
u5 = u2 = 0.

•
•
•

Calculate reliabilities.
Freeze/dynamically freeze the bits according to V .
Freeze more bits according to reliabilities.

Due to the property of subcodes, (n, k, k ′ ) eBCH-polar codes
have a guaranteed distance spectrum not worse than (n, k ′ )
eBCH codes. k ′ is adjustable to construct a more polar-like
(with better SC-performance) code or a more eBCH-like (with
better ML-performance) code.

E. Distance Spectrum
Definition 1. For an (n, k) binary linear block code the
minimum distance dmin is the minimum Hamming distance
dH (c, c′ ) between two distinct codewords, c, c′ , i.e., we have
dmin (C) = min′ dH (c, c′ ) = min wH (c)
c6=c
c,c′ ∈C

(7)

where wH denote the Hamming weight of a codeword.
Definition 2. For an (n, k) binary linear block code (with code
book C) the multiplicity of codewords with a given Hamming
weight w is
Aw = |{c|c ∈ C, wH (c) = w}|.

(8)

The distance properties of a linear block code can be
described by the distance spectrum (or weight enumerator):
A0 , A1 , . . . , An .
Given a code distance spectrum, the code performance (FER)
under ML decoding can be estimated via the union bound
(UB). For the binary-input AWGN channel, the UB is
PB ≤ PUB =

n

√
1 X
Aw erfc wSNR .
2

(9)

w=dmin

For high SNR, the UB can be well approximated by
PUB ≈

(6)

c6=0
c∈C

p

1
Amin erfc dmin SNR
2

(10)

where Amin denotes the multiplicity of codewords with minimum Hamming weight.

3

1

1.5

2

SNR in dB
2.5

3

3.5

4

Table I
E STIMATED ML- AND SC- PERFORMANCE OF (128, 64) E BCH, RM AND
POLAR CODES (4 D B)

10−1
Design Parameter
polar

Approx. UB / FER

10−2

RM-polar
10−3

10−4
eBCH-polar

d=8
d = 16

10−6

6
(
(
(
(

8
,
,
,
,

10

12
14
16
log2 L
) polar codes.
) CRC-polar ’0x16‘ (5 bits).
) CRC-polar ‘0x18’ (5 bits).
) (128, 64, 99) eBCH-polar codes.

18

20

Figure 1. An example of AUBs for different (128, 64) codes (optimized for
4 dB). The solid lines describe the relation between FER and SNR of the
codes, while the dashed lines show the AUBs with list size L.

OF

0.002 150 7

0.001 154 1

0.002 150 7

1.0887 ×

10−5

0.022 155

0.001 154 1

0.002 150 7

k ′ = 99

1.0086 × 10−5

0.006 733 4

k′

= 92

1.0086 × 10−5

0.006 733 4

k ′ = 85

5.3637 × 10−6

0.008 54

10−6

0.020 806

= 78

7.445 ×

Table II
B EST CRC CODES FOR (128, 64) CRC- CODES ( OPTIMIZED FOR 4 D B)
ℓCRC

Polynomial

AUB

Estimated SC FER

3

0x5

1.9433 × 10−4

0.004 275

4

0xC

1.6791 ×

10−4

0.005 107 7

5

0x18

8.9280 × 10−5

0.006 402 9

6

0x2D

5.8441 ×

10−6

0.007 860 8

7

0x72

3.2828 × 10−6

0.009 586 8

0xA6

10−6

8

III. A NALYSIS

Estimated SC FER

k ′ = 106

k′

10−5

AUB
0.001 154 1

2.4525 ×

0.011 465

D ISTANCE S PECTRUM

In [8], the authors proposed a tool to analyze the distance
spectrum by using list decoding. Suppose the list contains only
the codewords with the least weights if the all zero codeword
is transmitted over a channel with very small noise variance.
The algorithm works as follows:
1. Transmit the all zero codeword with very high SNR.
2. Perform list decoding with a very large list size on the
received soft information.
3. (optional) Delete the codewords that do not satisfy the
outer code check.
4. Find all codewords with non-zero weight in the list and
the corresponding multiplicities.
5. Calculate the approximated UB (AUB) with (9).
We apply this method to polar codes, CRC-polar codes, RMpolar codes, eBCH-polar codes with SCL decoding.
Figure 1 is an AUBs (dashed lines) example for 4 different
polar codes (designed and operated at 4 dB). The list size
is doubled until the AUBs converge. Without convergence,
we would only get a lower bound of the UB. The simulation
results (solid lines) show clearly that the ML-performance (at
4 dB) can be well approximated by the converged AUB. All
AUBs shown in our work are based on experiments where the
AUBs converged.
Table I shows the AUB and estimated FER under SC
decoding of all options for (128, 64) polar, RM-polar and
eBCH-polar codes. For CRC-polar codes, the CRC polynomials are optimized for the AUB with exhaustive search. The
performance of the (128, 64) CRC-polar code with polynomial
’0x44’ by list size 32 is shown in [15]. This code has the AUB
3.5926 × 10−6 , which is very close to the best 3.2828 × 10−6 .

Remark 4. For the AUB of (128, 64) codes at 4 dB, (10)
is not a good approximation because 4 dB is not high
enough. Therefore, not only Amin and dmin are important.
For example, for (128, 64) codes at 4 dB, the CRC-polar code
with polynomial ’0x72’ has dmin = 12 and Amin = 117,
while the eBCH-polar code with k ′ = 85 has dmin = 16 and
Amin = 45592. However, Table I and Table II show that the
CRC-polar code has a lower AUB than the eBCH-polar code.
IV. D ESIGN RULES FOR L IST D ECODING
In Sec. II, we introduced three kinds of polar codes with
improved distance spectrum. Their SC- and ML-performance
could be adjusted via ℓCRC /d/k ′ . However, the FER estimation
for polar codes with list decoding is not easy. We use three
conjectures to simplify analysis:
Consider two polar codes A and B with the same code length
n and message length k. The SC- and ML-performance can
be described by FERSC (·) and FERML (·).
Conjecture 1. If one of the following conditions is fulfilled,
then code A outperforms code B by any list sizes L ∈ (1, 2k )
at high SNR.
1. FERSC (A) ≤ FERSC (B), FERML (A) < FERML (B).
2. FERSC (A) < FERSC (B), FERML (A) ≤ FERML (B).
An example is shown in Figure 2. The codes with similar AUB (≈ 10−5 at 4 dB) have similar ML-performance.
However, the codes with better SC-performance perform better
with small list size, i.e., the codes with better SC-performance
need smaller list size to achieve the same ML bound with
SCL decoding. The dashed curves denote the estimated SCperformance of the codes. Three different codes with similar

4

100

10−1

10−1

Est. SC FER

FER

FER

10−2

10−3

10−3

10−4

10−5

10−2

10−4
1

1.5

2

2.5

3

3.5

1

4

1.5

2

RM-polar, w = 16, L = 4
RM-polar, w = 16, L = 128
eBCH-polar, k ′ = 99, L = 4
eBCH-polar, k ′ = 99, L = 128
CRC-polar, ’0x4D’(7 bits), L = 4
CRC-polar, ’0x4D’(7 bits), L = 128

Conjecture 2. If code A has better SC-performance and worse
ML-performance, i.e., if

3.5

4

,
,

Figure 3. An example for conjecture 2, optimized for 4 dB, L = {1, 2, 4}
10−1

10−2

Figure 2. Three (128, 64) polar codes with same AUB, optimized for 4 dB

10−3
FER

AUB perform similar for a large list size (L = 128), while the
curves are sorted by the SC-performance for a small list size
(L = 4).

,
,

3

SNR in dB
) eBCH-polar codes, k ′ = 85.
) CRC-polar codes, ’0x18’.

SNR in dB
(
(

2.5

10−4

10−5

FERSC (A) < FERSC (B), FERML (A) > FERML (B)
then there is a list size L′ with the following property. Code
A outperforms code B for list size L where L < L′ , while
code B performs better for L > L′ at high SNR. An example
for (128, 64) codes is shown in Figure 3.
Conjecture 3. By list decoding with fixed L, the SCperformance of polar codes becomes more important for
larger code dimension k and vice versa, the SC-performance
becomes less important for smaller k.
We begin with short eBCH-polar codes. Figure 4 shows that
(128, 64, 99) and (128, 64, 85) codes perform similar for list
size 32, (4096, 2048, ≥ 3915) and (4096, 2048, 3903) codes
perform similar for list size 2. Using Conjecture 2, we know
for L ≤ L′ = 32, the (128, 64, 99) eBCH-polar code should
be used, and for L ≥ L′ = 2, the (4096, 2048, 3903) eBCHpolar code performs better. From Table I, we know that the
(128, 64, 99) eBCH-polar code is the most polar-like code
among the (128, 64, k ′) codes, that improve the minimum
distance. This result could be extended by using Conjecture 3:
For polar codes with dimension 64 ≤ k ≤ 2048 and decoding
list size 2 ≤ L ≤ 32, we should use the most polar-like codes
that improve the minimum distance. Some simulation results
are shown in Figure 5 and Figure 6 for eBCH-polar codes with

10−6

1

1.5

2

2.5

3

3.5

4

SNR in dB
(128, 64, ≥ 106) eBCH-polar codes, L = 32, dmin = 8
(128, 64, 99) eBCH-polar codes, L = 32, dmin = 12
(128, 64, 85) eBCH-polar codes, L = 32, dmin = 16
(4096, 2048, ≥ 3915) eBCH-polar codes, L = 2, dmin = 32
(4096, 2048, 3903) eBCH-polar codes, L = 2, dmin = 48
Figure 4. eBCH-polar codes by list size L′ , optimized for {4, 2.5} dB

n = {256, 1024}, code rate = {1/4, 1/2, 3/4} and decoding
list size 8.
V. L OW W EIGHT B ITS C ONSTRUCTION
We propose a simple construction of polar codes with
improved distance spectrum via dynamically frozen bits.
1. Design an (n, k + Ndf ) polar code.
2. Find the set Imin of information bits according to low
row weights in F⊗ log n .
3. Add Ndf linearly independent constraints among the bits
in Imin .

5

Table III
E STIMATED ML- AND SC- PERFORMANCE OF THE (128, 64) POLAR CODES
WITH DYNAMICALLY FROZEN BITS ( OPTIMIZED FOR 4 D B)

100
10−1

AUB

Estimated SC FER

Ndf = 7

7.1666e-06

0.0067334

eBCH-polar, k ′ = 99

1.0086e-05

0.0067334

FER

10−2
10−3
10−1
10−4
10−2
10−5
10−3
−2

0

2

4

6

SNR in dB

FER

10−6

10−4

(1024, 256, ≥ 873), dmin = 32 (original)
(1024, 256, 863), dmin = 48
(1024, 256, 783), dmin = 64
(1024, 512, ≥ 953), dmin = 16 (original)
(1024, 512, 943), dmin = 24
(1024, 512, 903), dmin = 32
(1024, 768, ≥ 993), dmin = 8 (original)
(1024, 768, 983), dmin = 12
(1024, 768, 963), dmin = 16

10−5

10−6
1.5

eBCH k ′ = 99, L = 8
Ndf = 7, L = 8
eBCH k ′ = 99, L = 32
Ndf = 7, L = 32
2

2.5

3

3.5

4

SNR in dB
Figure 7. Comparison between eBCH-polar code and our construction,
optimized for 4 dB

Figure 5. (1024, k, k ′ ) eBCH-polar codes with L = 8, optimized for
{−0.25, 3, 6} dB

The parameter Ndf denotes the number of dynamically frozen
bits and describes how many reliable bits (under SC decoding)
are sacrificed. Table III shows the SC-performance and the
AUB of polar codes (Ndf = 7) with constraints:

100
10−1

u85 = u99 = u113 = u57 ⊕ u83 ,
u89 = u101 = u57 ,

FER

10−2

(11)

u98 = u105 = u83 .
10−3

Using Conjecture 1, the polar codes with Ndf = 7 outperform
the (128, 64, 99) eBCH-polar code for any list sizes. Figure 7
shows the comparison between eBCH-polar codes and our
scheme by decoding list size 8 and 32. The gain is 0.1 dB
at FER 10−5 .

10−4
10−5
10−6

−2

0

2

4

6

SNR in dB
(256, 64, ≥ 199), dmin = 16 (original)
(256, 64, 191), dmin = 32
(256, 64, 127), dmin = 48
(256, 128, ≥ 199), dmin = 16 (original)
(256, 128, 191), dmin = 24
(256, 128, 159), dmin = 28
(256, 192, ≥ 231), dmin = 8 (original)
(256, 192, 223), dmin = 12
(256, 192, 207), dmin = 14
Figure 6. (256, k, k ′ ) eBCH-polar codes with L = 8, optimized for
{0.5, 3.5, 6.5} dB

VI. C ONCLUSIONS
In this work, we review state-of-the-art polar code constructions for distance improvement and analyze their distance
spectrum. A heuristic construction is proposed to optimize the
list decoding performance for a certain range of dimension k
and list size L. In addition, a polar code construction based
on dynamically frozen bits and ”low weight bits” is proposed,
which provides better performance than eBCH-polar codes.
R EFERENCES
[1] N. Stolte, “Rekursive Codes mit der Plotkin-Konstruktion und ihre
Decodierung,” Ph.D. dissertation, TU Darmstadt, 2002.
[2] E. Arıkan, “Channel polarization: A method for constructing capacityachieving codes for symmetric binary-input memoryless channels,” IEEE
Trans. Inf. Theory, vol. 55, no. 7, pp. 3051–3073, Jul. 2009.

6

[3] I. Tal and A. Vardy, “List decoding of polar codes,” IEEE Trans. Inf.
Theory, vol. 61, no. 5, pp. 2213–2226, May 2015.
[4] B. Li, H. Shen, and D. Tse, “A RM-polar codes,” arXiv preprint, 2014.
[Online]. Available: https://arxiv.org/abs/1407.5483
[5] P. Trifonov and V. Miloslavskaya, “Polar subcodes,” IEEE J. Sel. Areas
Commun., vol. 34, no. 2, pp. 254–266, Feb. 2016.
[6] V. Bioglio, F. Gabry, I. Land, and J.-C. Belfiore, “Minimumdistance based construction of multi-kernel polar codes,” arXiv preprint
arXiv:1701.07616, 2017.
[7] G. Ricciutelli, M. Baldi, F. Chiaraluce, and G. Liva, “On the error probability of short concatenated polar and cyclic codes with interleaving,”
arXiv preprint arXiv:1701.07262, 2017.
[8] B. Li, H. Shen, and D. Tse, “An adaptive successive cancellation list
decoder for polar codes with cyclic redundancy check,” IEEE Commun.
Lett., vol. 16, no. 12, pp. 2044–2047, Nov. 2012.
[9] S. ten Brink, G. Kramer, and A. Ashikhmin, “Design of low-density
parity-check codes for modulation and detection,” IEEE Trans. on
Commun., vol. 52, no. 4, pp. 670–678, May 2004.
[10] R. Mori and T. Tanaka, “Performance of polar codes with the construction using density evolution,” IEEE Commun. Lett., vol. 13, no. 7, pp.
519–521, Jul. 2009.
[11] D. Dosio, “Polar codes for error correction: analysis and decoding
algorithms,” Master’s thesis, University of Bologna, 2016.
[12] F. Brannstrom, L. K. Rasmussen, and A. J. Grant, “Convergence analysis
and optimal scheduling for multiple concatenated codes,” IEEE Trans.
Inf. Theory, vol. 51, no. 9, pp. 3354–3364, Aug. 2005.
[13] P. Koopman, “Best CRC Polynomials.” [Online]. Available:
https://users.ece.cmu.edu/∼ koopman/crc/
[14] N. Hussami, S. B. Korada, and R. Urbanke, “Performance of polar codes
for channel and source coding,” IEEE Int. Symp. Inf. Theory (ISIT), pp.
1488–1492, Jun. 2009.
[15] G. Liva, L. Gaudio, T. Ninacs, and T. Jerkovits, “Code design for
short blocks: A survey,” arXiv preprint, 2016. [Online]. Available:
https://arxiv.org/pdf/1610.00873v1.pdf

