> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) <

1

Capacity-Achievability of Polar Codes and
Precoded Polar Codes under List Decoding:
They are Good both Practically and
Theoretically
Zhuo Li, Lijuan Xing, and Ba-Zhong Shen


≜

Abstract—Polar codes under successive cancellation decoding
proposed by Arıkan provably achieve the symmetric capacity of
any given binary-input discrete memoryless channel. The
successive cancellation list decoder for polar codes was described
by Tal and Vardy as a generalization of the successive cancellation
decoder of Arıkan. The performance of the successive cancellation
list decoder is encouraging in practice. In this paper, we formalize
the successive cancellation list decoder in our notation and prove
that polar codes under successive cancellation list decoding
achieve the symmetric capacity of any given binary-input discrete
memoryless channel in theory as well. We also formalize the polar
codes with CRC precoding of Tal and Vardy. In fact, we propose a
family of more general codes, namely, precoded polar codes and
prove that precoded polar codes under successive cancellation list
decoding can achieve the symmetric capacity of any given
binary-input discrete memoryless channel under some conditions.
Index Terms—Capacity-achieving
successive cancellation list decoding.

codes,

polar

codes,

∈

:

and
≜

.
∈

,

The maximum probability of error of the code
, ,

.

≜ max
∈

,

The average probability of error of the code
, ,

≜

1
|

|

is

is

.
∈

A channel : →
is called a binary-input discrete
memoryless channel (B-DMC) if the input alphabet
0,1
:
→
has transition
and the uses of the channel
probabilities
|

|

.

I. INTRODUCTION AND PRELIMINARIES

L

ET and be finite sets. A discrete channel with input
alphabet and output alphabet is defined as : →
| , ∈ , ∈ .
with transition probabilities
A code for channels with input alphabet
and output
alphabet is a pair of mappings , , where maps some
into and maps into
⊇ . The
finite set
elements of
are called messages, the mapping is the
encoder and is the decoder. The images of the messages
under are called codewords.
Given a channel : → , a code for channel
is any
code
,
as above. The probability of erroneous
transmission of message is
, ,

≜1

where

This work was supported in part by the National Natural Science Foundation
of China under Grant 61372072, in part by the 111 Project under Grant B08038,
and in part by the Fundamental Research Funds for the Central Universities.
The authors are with the State Key Laboratory of Integrated Services
Networks, Xidian University, Xi’an, Shannxi 710071, China (e-mail:
lizhuo@xidian.edu.cn; ljxing@mail.xidian.edu.cn; bzshen@xidian.edu.cn).

This B-DMC is denoted by
: →
or simply
. An
-length block code for a B-DMC
is a code ,
for the
. The rate of such a code is log
.
channel
In this paper, the base of the logarithm is assumed to be 2
unless otherwise stated. We use the notation
as shorthand
for denoting a row vector
,…,
. Given such a vector ,
we write , 1
,
, to denote the subvector
,…, ;
and ⊆ 1, … , ,
if
, is regarded as void. Given
we write
to denote the subvector
: ∈
; if
∅,
is regarded as void. The notation 0 is used to denote the
all-zero vector. We write | | to denote the number of elements
in a set . Unless specified otherwise, all vectors, matrices,
and operations on them in this paper will be over the binary
field.
Given a binary-input channel , the symmetric capacity of
is
≜
∈

∈

1
2

|

|

log

and the Bhattacharyya parameter of

0
is

1

> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) <

|0

≜

∈

|1 .

ii)
iii)

∈

Channel polarization is a method proposed by Arıkan [1] to
construct code sequences that achieve the symmetric capacity
of any given B-DMC
. Channel polarization is an
operation by which one manufactures out of
uses of a
B-DMC
a second set of channels
:1
that show a polarization effect in the sense that, as becomes
tend towards 0
large, the symmetric capacity terms
or 1 for all but a vanishing fraction of indices . This operation
consists of a channel combining phase and a channel splitting
phase.
⊗
≜
the generator matrix of order for
We call
0, where
is a permutation matrix known
any
2 ,
1 0
⊗
as bit-reversal and
is the Kronecker power of ≜
1 1
with the convention that ⊗ ≜ 1 . Then the channel
combining phase combines uses of a given B-DMC
in a
recursive manner to produce a channel
:
→
defined
by the transition probabilities
|

|

∈

2

|

where
,
denotes the output of
and
its input.
Then we have the following two results about channel
polarization and the rate of polarization.
Theorem 1 [1]: For any B-DMC
, the channels
polarize in the sense that, for any fixed ∈ 0,1 , as goes to
infinity through powers of two, the fraction of indices ∈
1, … ,
for which
∈ 1
, 1 goes to
and the
fraction for which
∈ 0, goes to 1
.
Theorem 2 [1]: For any B-DMC
with
0, fixed
, there exists a sequence of sets
, and fixed
⊆ 1, … , , ∈ 1,2, … , 2 , … , such that | |
and
2
for all ∈
and sufficiently large.
We can now take advantage of the polarization effect to
construct codes that achieve the symmetric channel capacity
.
Definition 1: Given a B-DMC
: → , let
2 for
| |
some
0 and let ⊆ 1, … ,
and
∈
be fixed,
an
-length
-coset code
,
under successive
cancellation (SC) decoding for
with respect to and
is an -length code for
such that
i)
≜

;

≜
∈
for all
∈
is the generator matrix of order ;
∈
for all
∈
≜
is generated by computing
vector
,

≜

where
where the

if ∈
, if ∈

,

in the order from 1 to with decision functions
:
→ , ∈ defined as
,

0, if

≜

,

|

,

|

1, otherwise
for all
∈
,
∈
.
We refer to as the information set and to
or vector.

as frozen bits

The rate of this code is | |⁄ . We will use the notation
, ,
to denote the average probability of error of this
code, i.e.,
,

1

≜

:

;

|

≜

∈
,
∈
.
for all
Having synthesized the channel
out of
, the channel
splitting phase is to split
back into a set of binary-input
coordinate channels
: →
,1
,
defined by the transition probabilities
,

iv)

≜

2

The average of
denoted by
,
,

,
, ,
, i.e.,
≜

,

≜

.

over all choices for

1
2|

,

,

|
∈ |

,

will be
.

|

Then we have the bound [1]
.

,
∈

This result suggests choosing
so as to minimize the
right-hand side of above bound. This idea leads to the definition
of polar codes.
Definition 2: An information set is called a polar set for
for all ∈
, ∈
. An
if
-coset code under SC decoding for
with
-length
is called an -length polar code under
respect to and
SC decoding for
with respect to and
if is a polar
set for
.
,
be defined as
,
For a number
0 , let
where is a polar set with | |
. Thus,
,
is the
average probability of error of an -length polar code for
.
with rate , averaged over all choices for the frozen bits
Then we have the following coding theorem.
Theorem 3 [1]: For any given B-DMC
, fixed
,
and fixed
, average error probability for -length polar
code under SC decoding satisfies
,
for

sufficiently large.

2

> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) <
This theorem shows that the polar codes under SC decoding
can achieve the symmetric capacity
of any given B-DMC
.
The symmetric capacity
equals the Shannon capacity
when is a symmetric channel, i.e., a channel for which there
exists a permutation
on the output alphabet such that
|1
|0 for all ∈ . Let
and
be the identity permutation on . Clearly, the permutations
,
form an Abelian group under function composition.
For a compact notation, we will write ⋅ to denote
for
∈ , ∈ . For
∈
,
∈
, let
⋅

≜

⋅

,…,

⋅

.

a permutation on
This associates to each element of
If a B-DMC
is symmetric, then the channels
are also symmetric in the sense that [1]
|
,

|

⋅

|

⋅

,

⨁
⨁

.
and

,

(1)
|

⨁
(2)

for all
,
∈
,
∈
,
2 ,
0,1
.
For symmetric channels, we have the following stronger
version of Theorem 3.
Theorem 4 [1]: For any symmetric B-DMC
, fixed
, and fixed
, consider any sequence of polar codes
,
under SC decoding with increasing to infinity,
| |
, and
fixed arbitrarily. The average error
probability satisfies
,
for

,

2

sufficiently large.

Note that for symmetric channels
equals the Shannon
capacity. This theorem shows that, for symmetric channels, any
is as good as any other.
choice for
Although the polar codes under SC decoding achieve
capacity asymptotically, empirical studies indicate that for
short and moderate block lengths, they do not perform as well
as turbo codes or low density parity check (LDPC) codes. Thus,
either the encoder or the decoder is weak. In fact, the two
causes are complementary and both contribute to the problem.
Tal and Vardy proposed two improvements respectively to the
encoder and the decoder in [2].
Improvement 1 [2]: A successive cancellation list (SCL)
decoder is proposed which is a generalization of the SC decoder
of [1]. The SCL decoder is governed by a single integer
parameter , which denotes the list size. As in the SC decoder,
the input bits are decoded successively one-by-one. However,
in the SCL decoder,
decoding paths are considered
concurrently at each decoding stage. Specifically, the SCL
decoder doubles the number of decoding paths for each
information bit, and then uses a pruning procedure to discard all
but the most likely paths. At the end of the decoding process,
the most likely among the decoding paths is selected as the
decoder output. Simulation results show that for a wide range of
polar codes of various lengths, SCL decoding effectively

3

bridges the performance gap between SC decoding and
maximum-likelihood (ML) decoding.
Improvement 2 [2]: It has been observed in simulations that
even under ML decoding, the performance of polar codes falls
short in comparison to LDPC and turbo codes of comparable
length, which demonstrates the weakness of the encoder. It has
been noticed in simulations that, under SCL decoding, with
high probability, the transmitted message is on the list, but it is
not the most likely message on the list. It is therefore not
selected as the decoder output. This means that performance
could be further improved if we had a genie aided decoder
capable of identifying the transmitted message whenever it is
on the list. But such a genie can be easily implemented, for
example using cyclic redundancy check (CRC) precoding. It
has been confirmed in numerous simulations that the
performance of polar codes under SCL decoding with CRC is
comparable to state-of-the-art turbo and LDPC codes.
Although the performance of the codes in [2] is encouraging
in practice, it is not known whether they are good in theory as
well. Some thought shows that the likelihood probability of the
decoding output of the SC decoder is not necessarily less than
or equal to that of the SCL decoder. So the problem is not trivial.
In this paper we address this problem. We will show that the
codes in both Improvement 1 and Improvement 2 can achieve
the symmetric capacity
of any given B-DMC
asymptotically.
The rest of the paper is organized as follows. In Section II,
we formalize the codes in Improvement 1, i.e., the polar codes
under SCL decoding, with our notation and prove that they
achieve the symmetric capacity
of any given B-DMC
asymptotically, which is our one main result. In Section III,
we consider the polar codes under SCL decoding for symmetric
B-DMCs and prove a stronger result. In Section IV, we
formalize the codes in Improvement 2. In fact, we will propose
a family of more general codes, i.e., precoded polar codes under
SCL decoding and prove that they achieve the symmetric
capacity
of any given B-DMC
asymptotically under
some conditions, which is our another main result. In Section V,
we give some extensions about our results and draw a
conclusion.

II. SUCCESSIVE CANCELLATION LIST DECODING
In this section, we recast the SCL decoder using our notation,
for future proof. Let denote the positive integer set. For a
finite set , let
denote the collection of all nonempty
subsets of .
Definition 3: Given any discrete channel : → , a
most-likely mapping
:
→
is defined as
, ,
∈

≜

, ∈ , ∈ , where ∈
satisfies that
|
, then
;
|
, then is chosen as the -element subset of
|
| for all , ∈ and
such that
, ∈
\ . In addition, since and are finite,
there exists a strict total order ≺ on the set
. Then for

for all
if |
if |

> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) <
all

, ∈ and ,
| , , ≺ ,

∈
holds.

\

|

such that

-length polar code under -SCL decoding for
if is a polar set for
.
respect to and

Thus, in word, what a most-likely mapping does is to select
from |
| input-output pairs most likely ones, giving it
the name. The purpose of introducing the strict total order
relation to Definition 3 is just to guarantee that the mapping is
well-defined.
Definition 4: Given a B-DMC
: → , let
2 for
some
0 and ∈ be fixed, an -length
-coset code
,
under -SCL decoding for
with respect to
and
is an -length code for
where , ,
, ,
are defined as in Definition 1 and the decoder
and
consists of a successive-cancellation-list generating phase and a
local-maximum-likelihood selecting phase.
1) Successive-Cancellation-List Generating (SCLG): For any
∈
, this phase produces a vector set
channel output
,
⊆
in a recursive manner by computing
,
:
≜

∈

:

,

,

,

if ∈

∈

,

,

,

if ∈
≜
∩ 1, … , .
in the order from 1 to where
Note that
.
2) Local-Maximum-Likelihood Selecting (LMLS): Having
generated the vector set
,
from the channel
output , this phase of the decoder selects a most likely
vector from
,
by computing
,

∈

≜

Then

,

,

≜

for all

∈

,1 .

Given an -length code
,
for
with respect
to an information set and some frozen bits
, we will use
the notation
, , ,
to denote the average probability
of error of the code, i.e.,
,

The average of
, , ,
denoted by
, ,
, i.e.,
, ,

≜

,

≜

.

Theorem 5: For any given B-DMC
, fixed
,
, average error probability for -length polar
1, and
code under -SCL decoding satisfies
, ,
for

Consider an -length
-coset code
,
under
-SCL decoding for
: →
with respect to and
.
Let a message
be encoded into a codeword , let
be
sent over the channel
, let a channel output
be received,
and let
,
be the output of the SCLG phase of the
decoder, see Definition 4. We will use the notation
∉
, , ,
to denote the average probability of
,
, assuming that each message
is sent with
probability 2 | | . More precisely,
, ,

,
1
2|

≜
∈

, ,
∈

|

,

|

|
∈

:

∉

, ,

1
2|

≜
∈ |

|

, ,

|

,

will
.

4

First, we will prove the following bound.
Proposition 1: For any B-DMC
parameters , ,

and any choice of the
.

, ,
∈

Proof. From (3) and (4), we know
, ,
|

1
2|

, ,

|

,

will be
∈

:

∉

,

.

|

∈

Definition 5: An -length
-coset code under -SCL
decoding for
with respect to
and
is called an

. 3

,

, , ,
over all choices for
, ,
, i.e.,

∈
|

2

sufficiently large.

∈ |

over all choices for

1
2|

,

with

For a number
0, let
, , be defined as
, ,
, , is
where is a polar set with | |
. Thus,
the average probability of error of an -length polar code under
-SCL decoding for
with rate , averaged over all choices
.
for the frozen bits
Now our first main result is to show that polar codes under
-SCL decoding can achieve the symmetric capacity
of
any given B-DMC
.

The average of
be denoted by

.

Remark: One can verify readily that the decoder
defined above is indeed the SCL decoder with list size
described in [2]. Specifically, the SCLG phase formalizes the
process that doubles the number of decoding paths for each
information bit, and then uses a pruning g procedure to discard
all but the most likely paths. The LMLS phase formalizes the
last step of the decoding process, i.e., the most likely among the
decoding paths is selected as the decoder output.

, ,

4

∈

:

∉

,

1
2

|

1
2

|

> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) <

∈

1
2

∈

where the set

Therefore, by (9) and (10), we have

|

,

is defined as
≜

∈

:

∉

∈

,

,

:

∈

,
∉

(5)

∈

∈

∈

For any ∈
partition the set
,

≜

,

,
≜

∉

|

,

,

1
2

,

,0 ∈

,

∈

∈

∈

1
2

:

∈

,

|

,

,
(6)

∈

1
2

:

∈

,

| ′

,

,

:

,
,

,

∈

, ⨁1 ∈

∈

,

|

,

,
(7)

∈

∈

∈

:

∈

≜

(13)

. Thus,

∈

and
,

| ′

∈

,

:

,

,

∈

∈

,1 ∉

∈
,

.

, and
∈
, we can
into three subsets, i.e.,

,

(12)

, ,

∈

,0 ∉
,

|
1
2

, frozen bits
,

(11)

| ⨁1 .

| ′
,

and all ′, ′ ∈

∈

,

∈

for all

∈

|

,
.

Then it is clear that
, ,

.

From (6), (8), Definition 4, and Definition 3, it holds that

,

,

1
2

,

From (7), Definition 4, and Definition 3, it holds that, for all
∈
,
,

for all
∈
.
For every ∈ , define
≜

5

,1 ∈

,

. (8)

,

|0

⋅

,

|1

,

:
∈

1
2

,

|0

,

|1

,

|0

,

|1

:

∈

,

It is obvious that they are disjoint with each other and
,
,

∪

,

∪

,

.

Thus, we have

∈

∈

,

∈

∈

,

,
,

,

.

(9)

where the second equality is due to (5), (6), (7), and (8), the first
inequality follows from (11), (12), and (13), and the second
inequality is obtained by noting that
∈

In addition, from (6), (7), and (8), we also know
,

:

∈

∩
,

2

,

.

,

.

∈

:

∈

,

∅

and
∈

From Definition 4 and Definition 3, it holds that
,

(10)

,

∪

:

∈
∈

,
:

∈

,

⊆

.

> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) <
This completes the proof of Proposition 1.
Second, we will prove the following bound.
Proposition 2: For any B-DMC
parameters , ,
, ,

∈ |

|

∈

and any choice of the
∈

.

2

|

|

∈

∈

Proof: Given a B-DMC
: → , let
2 for some
,
be an -length -coset code under
0 and
. Define
-SCL decoding for
with respect to and
≜

∈

:

∈

,

∈
.
for all messages
We note that among all
1,
. Thus,
that
for all messages
the sets
Proposition 1
1

, 1,

∈ |

∈

|

1

|

1
2

∈

|

∈

, 1,

1
2

|

15

⊆
, the sets
are pairwise disjoint
As
. On the other hand,
and the union of them is a subset of
∈
since
⊆
, by (14) and Definition 4, for all
∈
, we have
which implies

|

|

1
2

1

|

|

|

∈ |

∑∈
as desired.
, 1,
1, it is obvious that
⊇
,
but are not necessarily pairwise
cover

∈

1
2

|

1

1
2

∈

|

∈ |

|

1

∈

∈

∈

|

1
∈

1
∈

|

1
2

∈

|

2

where the first inequality is due to the fact that the sets
,
are pairwise disjoint and the union of them is a subset of
the second inequality is due to (16), and the last inequality is
due to (15). This completes the proof of Proposition 2.

17

∈

. Then, by Proposition 1,
1
2

1
2

2

∩

∈

|

Proof of Theorem 5: By Theorem 2, for any given rate
and fixed
, there exists a sequence of information
with size | |
such that
sets

from which we cannot obtain what we want.
For any fixed
1, define
≜

|

1
2

∈

1
2

∈

∈ |

|

, ,

for all messages

(16)

|

∈

, ,

∈ |

.

, ,

∈ |

|

|

.

.

∈ |

|

∈

, 1,

Thus we get
But when
the sets
disjoint, and

|

∪

, ,

2

∈

∈ |

1
2

Hence, it follows that

∈

1

1

∈

|

1
2

(14)

1 is special in the sense
is a disjoint union of
and by
∈

|

|

1
2

6

|

for sufficiently large. In particular, the bound (17) still holds
is chosen as the polar set because by definition the polar
if
set minimizes the sum in (17). Combining this fact with
Proposition 1, it follows that

> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) <

, ,

and

2

sufficiently large where
, ,
is defined as
, ,
for a polar set with | |
. That is to say,
using polar codes, with very high probability, the transmitted
message will be on the list generated by the -SCL decoder,
provided that the rate is less than the symmetric capacity. Next,
combining this fact with Proposition 2, it follows that

,

for

, ,

7

≜

for sufficiently large. That is to say, also with very high
probability, the transmitted message is the most likely message
on the list. This completes the proof of Theorem 5.
Remark: One extreme case of Theorem 5 is when
1. In
this case, it can be verified readily that the SCLG phase does all
the jobs of an -SCL decoder, the LMLS phase does nothing,
and an -SCL decoder degrades to an SC decoder. That is to
say, SC decoders are special instances of -SCL decoders.
Remark: Intuitively, an -SCL decoder should behave better
than an SC decoder. And the simulations in [2] have
demonstrated this intuition. However, our proof cannot give out
an exact order between
, , and
, , 1 in general.
This is because there is no exact inclusion relation between
and
.

∈

,

:
∈

If ∈

,

.

, let
:

∈

∈

For any

2

:

,

,

,

∈

.

, let

:

∈

,

∈

and
:

,

∈

,
∈

be such a set that either

Let

,
∈

for some

.

and

,
\

, or

∈

\

,

and

,

∈

for some

,

. Let
\

and
\

.

III. SYMMETRIC CHANNELS
The main goal of this section is to prove the following result,
which is a strengthened version of Theorem 5 for symmetric
channels.
Theorem 6: For any symmetric B-DMC
, any fixed
,
1 , and
, every sequence of polar codes
,
for
with
increasing to infinity, | |
, and
fixed arbitrarily satisfy
, ,
for

,

Then
,

:| |

≜

,

\

⊆

,

2

Proof of Theorem 6: Consider an -length -coset code
,
under -SCL decoding for
: →
with
respect to and
, only this time assuming that
is a
symmetric channel.
∈
, define a collection
For any channel output
,
of subsets of
and
,
⊆
recursively in the order from 1 to
where
≜
∩
1, … , in the following way.
If ∈
, then
≜

:

,

∈

≜

∈

,

,

,

∩

.
∈

Remark: Recall that, by Theorem 5, there exists some choice
such that the code
,
can achieve the
of
symmetric capacity
. However, Theorem 6 tells us that,
for symmetric channels, this is so for any choice of
. Note
also that, for symmetric channels,
equals the Shannon
capacity.

,
.

Define

sufficiently large.

,

⊇

18

,

Then
,

≜

\

,

1, … , , from the definition of

For every

is obvious that |

,

|

.
,

. Hence, for each ∈

, it
,

from (18), we know that |
,
| 2 and for any
∈
,
there exists some
∈
,
such
that
∈
. Moreover, by the definition of
, some
thought shows that there must exists some
∈
such
that
,
,

|0

,

|1

> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) <

,
∈

|0

,

, we have

∈

,

. Then, it holds by (20) and
|

|

,
∈

:

∈

for all messages
(22) that

Therefore, for any ∈

∈

≜

|1 .

:

8

:

,

∈

,

23

2

,
∈

|0

,

|1 . 19

:

∈

∈
for all
For any fixed

.
1, define
≜

Now, define
≜

,

∈

:

∉

,

(20)

∈

for all messages

. Then, by (23),

|

and
≜
for all ∈

,

∈

:

∈

,

∈
,

for each

∈

,

∈

,

⋅

∈

1
2

. Thus, we have

,

1
2

∈

∈

,

∈

∈

∈

∈

1
2

,

∈

∈

,

∈

1
2|

|1
∈

∈

for all
∈
where the first equality is due to (1), the
second equality is due to (21), and the inequality follows by
(19).
, we obtain
Since ⊆ ⋃ ∈
|
,

|

|

,

|0

∈

22
∈

for all
∈
.
Next, as in the proof of Proposition 2, define

(25)

,
1
2|

⨁

1

:

|

|

:

,

|

∈

,
∈

, ,

1
⋅

:

|
for all
∈
.
Hence, it follows that

∈

∈

∈
for all
.
In addition, as in the proof of Proposition 2, we know that the
sets
are pairwise disjoint and the union of them is a
subset of
and

(21)

|
,

24
∈

and (2), it follows directly

⨁

implies

|

2

.

Moreover, from the definition of
that

|

|

,

∈

:

∪

. Then, it is not difficult to show that
⊆

∩

|

1
2| |

|

1
2| |

|

|

2
∈

where the first inequality is due to the fact that the sets
,
are pairwise disjoint and the union of them is a subset of
the second inequality is due to (25), and the last inequality is
due to (24).
This bound on
, , ,
is independent of the frozen
. Theorem 6 is now obtained by combining Theorem
vector
2 with the above bound, as in the proof of Theorem 5. This
completes the proof of Theorem 6.

> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) <
and

IV. PRECODED POLAR CODES
In this section, we formalize the codes in Improvement 2. In
fact, we will formalize more general codes, i.e., precoded polar
codes under SCL decoding, with our notation and prove that
they achieve the symmetric capacity
of any given
B-DMC
asymptotically.
,
be an
Given a B-DMC
: →
, let
with
-length -coset code under -SCL decoding for
such that | |
. We will use notation
respect to and
:
→
to denote a permutation mapping on
. For any
→
such permutation and
, a -to- precoder :
induced by is defined as
,0

≜
for all

∈

.

Definition 6: An -length precoded
-coset code ,
for
with respect to the
-coset code
,
and
the precoder above is an -length code for
such that
≜
;
i)
ii)
≜
∪ ∗;
iii)
for all
∈
where
≜
∈
and
;
→
is defined as follows.
iv)
The decoder :
∈
, set
For all

∩

1:

,

1

,

,

,
If
code.

,

∈

1

and

,

,

.
→ ∞ for some
Moreover, if
is a symmetric channel, any sequence of
-length precoded polar codes ,
can achieve the channel
capacity
asymptotically no matter which strategy has
been adopted provided that

as

⁄

,

for

.

Proof. The rate result is obvious.
For any
with
∈
, from the definition of
,
and

and
, we have

,

,
∈

and
and
⊆

∈

,1 .

,

,
,
,1
.
∈
. That is to say,
for all strategies, which proves (26).
∅.

:

In Failure Strategy,
∗
and
1

, ,

|

In Retransmission Strategy, as
∈ and retransmission occurs when
that
, ,

.
when
, it follows

∈
|

1

,

|

, ,

1

∈

(27)

when

∈

|

,

|
,

(26)

,

→∞

→ 1 and

→ ∞ for some

as

which proves (27).
, ,

(29)

which proves (28).
In Non-Failure Strategy, as
, it follows that

,
, ,

→∞

→ 1 and

∈

then
≜
.
∅, we can adopt at least three strategies.
If
≜∗.
Failure Strategy: The decoder fails with
to denote the decoder with this
We will also use
strategy.
Non-Failure Strategy: Let
. Let
.
. The decoder outputs
≜
We will also use
to denote the decoder with
this strategy.
Retransmission Strategy: The decoder requests the
encoder to retransmit the message. We will also use
to denote the decoder with this strategy.
is a polar code, we call ,
a precoded polar

, ,

(28)

Let

With above formalization, we have the following result.

with

⁄

,1 ,

Theorem 7: The -length precoded -coset code
defined above has the following properties.
The rate is ⁄ ;
The error probabilities

, ,

∈ .
for all
Therefore, there exists a sequence of -length precoded
polar codes ,
that can achieve the symmetric capacity
asymptotically no matter which strategy has been
adopted provided that

.

∅, let

If

, ,

Hence,
Thus,

,

≜

9

∩

> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) <
To prove the last claim, we note that, by Theorem 5, for the
given and for any fixed
, there exists a sequence of
,
such that
-length polar codes

and
,

,

2

(30)

for sufficiently large. Now construct a sequence of -length
precoded polar codes ,
for
with respect to these polar
,
and some precoder . Then, provided that
codes
⁄ → 1 and
→ ∞, we have the rate
→

, ,
∈

∈

1
2

, ,

1
2

,
1
2

2
∈

2
2

,

V. SOME EXTENSIONS AND CONCLUSION
First, the result of Theorem 5 is proven for binary DMC and
2 2 polarization matrix. In fact, polarization results have
been proven for DMC over any finite field and
polarization matrix with any
2, see [3] for details. It is
,
and the proof
obvious that the definition of codes
of Theorem 5 can be generalized to DMC over finite field and
polarization matrix straightforwardly. Thus, in fact, we
have obtained the following more general result.
Theorem 8: For any DMC
over any finite field and any
polarization matrix with any
2 , let
be the
for
0. Then for any fixed
1,
exponent of and
, and
, there exists a sequence of -length
polar codes
,
for
with respect to and
such that | |
sufficiently large.

and the average error probability

10

and

,

,

2

for

Second, in Theorem 5, the list size is fixed. If we let , be
the list size at step of the SCL decoder of an -length polar
code where belongs to the polar set , i.e., we let the list size
depend on the length and the step , it is obvious that the
proof of Theorem 5 is still valid provided that , dose not
decrease as increasing for each .

,

,

,

,
→0

as → ∞ where the first inequality is due to (26) and the last
inequality is due to (30).
The result for a symmetric channel follows similarly by
using Theorem 6.
This completes the proof of Theorem 7.
Remark: One can verify that the CRC code used in [2] is one
example of the precoder defined in this section. Moreover, as
CRC codes have constant
, they satisfy the condition (29)
in Theorem 7. Therefore, the precoded polar codes ,
for
with respect to CRC precoders using Non-Failure Strategy,
which indeed are the codes described in Section V of [2], can
achieve the symmetric capacity
. But the result of
Theorem 7 is more general, which states that the precoded polar
codes can achieve the symmetric capacity as long as the
precoders satisfy the condition (29). Based on this, one may try
to find out some other better precoders in future researches.
Remark: We know from (26) that the error probability of a
message in ,
is no greater than that of the corresponding
,
, which has been confirmed by
message in
simulations with respect to CRC precoders in [2].
Remark: About the three strategies mentioned above, we
know from (27) and (28) that both Non-Failure Strategy and
Retransmission Strategy have better performance than Failure
Strategy. But Retransmission Strategy can cause extra latency.
In these senses, Non-Failure Strategy is the best.

Remark: One extreme case of this extension is when ,
2| | . In this case, it can be verified readily that the SCLG phase
does nothing, the LMLS phase does all the jobs of an SCL
decoder, and an SCL decoder upgrades to an ML decoder. That
is to say, ML decoders are special instances of SCL decoders.
Hence, in fact, we have proved that polar codes under ML
decoding can achieve the symmetric capacity, although it is
trivial.
In conclusion, Arıkan proposed polar codes and proved that
polar codes under SC decoding achieve the symmetric capacity
of any given B-DMC
asymptotically in theory. But,
in practice, simulation results show that there is a considerable
performance gap between SC decoding and optimal ML
decoding. That is to say, SC decoding is good in theory but not
very good in practice. Then Tal and Vardy described SCL
decoding and demonstrated in practice that SCL decoding can
effectively bridge the proceeding performance gap between SC
decoding and ML decoding. That is to say, SCL decoding is
good in practice. But it was not known whether SCL decoding
is good in theory or not, although SCL decoding includes SC
decoding and ML decoding as special cases. In this paper, we
have proven that polar codes under SCL decoding can achieve
the symmetric capacity
of any given B-DMC
asymptotically in theory. So, in fact, we have answered the
proceeding question, i.e., SCL decoding is good in theory as
well. All these together tell us that indeed SCL decoding can
replace SC decoding as a common decoding method for polar
codes both in practice and in theory.

REFERENCES

> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) <
[1]

[2]
[3]

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.
I. Tal and A. Vardy, “List decoding of polar codes,” IEEE Trans. Inf.
Theory, vol. 61, no. 5, pp. 2213–2226, May 2015.
R. Mori and T. Tanaka, “Source and channel polarization over finite
fields and Reed-Solomon matrices,” IEEE Trans. Inf. Theory, vol. 60, no.
5, pp. 2720–2736, May 2014.

Zhuo Li was born in Shannxi Province, China, in 1980. He
received the B.S. degree (with highest honors) in mathematics,
the M.S. degree in computer science, and the Ph.D. degree in
information and communication engineering all from Xidian
University, Xi’an, China, in 2002, 2005, and 2008, respectively.
During the years 2016 and 2017 he was a Visiting Scholar at
the Texas A&M University, in College Station, TX. Since 2005
he has been with the school of telecommunication engineer of
Xidian University, Xi’an, China, where he is presently a
Professor. His research interests include information theory,
coding theory, and quantum information and computing.

Lijuan Xing received the B.E. and Ph.D. degrees in
information and communication engineering from Xidian
University, Xi’an, China, in 2004 and 2008, respectively.
Since 2010 she has been with the school of
telecommunication engineer of Xidian University, Xi’an,
China, where she is presently an Associate Professor. Her
research interests include communication systems, channel
coding, and quantum information and computing.

Ba-Zhong Shen received his M.S. degree from Xidian
University, China and his Ph.D. degree from Eindhoven
University of Technology, the Netherlands.
From July 1993 to February 1996 he was with the
Department of Electrical Engineering and Computer Science at
Lehigh University, Bethlehem, PA, USA, becoming a Research
Scientist in August 1993, and Adjunct Assistant Professor in
January 1994. During 1996-1999, he was with Technology and
Engineering of Quantum Corporation as principle design
engineer. In 1999 he joined Broadcom Corporation, USA and
later he became a technical director. Since May 2017 he has
been with Xidian University, where he is a distinguished
professor and dean of the school of telecommunication
engineer.
He has more than 185 issued US patents. He contributes
numerous industry standards including IEEE 802.3, IEEE
802.11, 3GPP LTE, ITU G.hn, MoCA, MPEG HEVC and
DOCSIS. Many of his inventions have been adopted to the
standards and built into the wire or wireless communication
products. His interests include information theory, source and
channel coding theory and technique, computing network and
communication system.

11

