ARIKAN: A METHOD FOR CONSTRUCTING CAPACITY-ACHIEVING CODES 3055
Proposition 2: For any B-DMC and any choice of the
parameters
(13)
Hence, for each
, there exists a frozen vector such
that
(14)
This is proved in Section V-B. This result suggests choosing
from among all -subsets of so as to minimize
the right-hand side (RHS) of (13). This idea leads to the defini-
tion of polar codes.
4) Polar Codes: Given a B-DMC
,a -coset code with
parameter
will be called a polar code for
if the information set is chosen as a -element subset of
such that for all
.
Polar codes are channel-specific designs: a polar code for one
channel may not be a polar code for another. The main result of
this paper will be to show that polar coding achieves the sym-
metric capacity
of any given B-DMC .
An alternative rule for polar code definition would be to
specify
as a -element subset of such that
for all . This alternative
rule would also achieve
. However, the rule based on the
Bhattacharyya parameters has the advantage of being connected
with an explicit bound on block error probability.
The polar code definition does not specify how the frozen
vector
is to be chosen; it may be chosen at will. This de-
gree of freedom in the choice of
simplifies the performance
analysis of polar codes by allowing averaging over an ensemble.
However, it is not for analytical convenience alone that we do
not specify a precise rule for selecting
, but also because
it appears that the code performance is relatively insensitive to
that choice. In fact, we prove in Section VI-B that, for symmetric
channels, any choice for
is as good as any other.
5) Coding Theorems: Fix a B-DMC
and a number .
Let
be defined as with selected in
accordance with the polar coding rule for
. Thus,
is the probability of block error under SC decoding for polar
coding over
with block length and rate , averaged over
all choices for the frozen bits
. The main coding result of
this paper is the following.
Theorem 3: For any given B-DMC
and fixed ,
block error probability for polar coding under successive can-
cellation decoding satisfies
(15)
This theorem follows as an easy corollary to Theorem 2 and
the bound (13), as we show in Section V-B. For symmetric chan-
nels, we have the following stronger version of Theorem 3.
Theorem 4: For any symmetric B-DMC and any fixed
, consider any sequence of -coset codes
with increasing to infinity,
chosen in accordance with the polar coding rule for , and
fixed arbitrarily. The block error probability under successive
cancellation decoding satisfies
(16)
This is proved in Section VI-B. Note that for symmetric chan-
nels
equals the Shannon capacity of .
6) Complexity: An important issue about polar coding is
the complexity of encoding, decoding, and code construction.
The recursive structure of the channel polarization construction
leads to low-complexity encoding and decoding algorithms for
the class of
-coset codes, and in particular, for polar codes.
Theorem 5: For the class of
-coset codes, the complexity
of encoding and the complexity of successive cancellation
decoding are both
as functions of code block
length
.
This theorem is proved in Sections VII and VIII. Notice that
the complexity bounds in Theorem 5 are independent of the
code rate and the way the frozen vector is chosen. The bounds
hold even at rates above
, but clearly this has no practical
significance.
As for code construction, we have found no low-complexity
algorithms for constructing polar codes. One exception is the
case of a BEC for which we have a polar code construction al-
gorithm with complexity
. We discuss the code construc-
tion problem further in Section IX and suggest a low-complexity
statistical algorithm for approximating the exact polar code con-
struction.
D. Relations To Previous Work
This paper is an extension of work begun in [2], where
channel combining and splitting were used to show that im-
provements can be obtained in the sum cutoff rate for some
specific DMCs. However, no recursive method was suggested
there to reach the ultimate limit of such improvements.
As the present work progressed, it became clear that polar
coding had much in common with Reed–Muller (RM) coding
[3], [4]. Indeed, recursive code construction and SC decoding,
which are two essential ingredients of polar coding, appear to
have been introduced into coding theory by RM codes.
According to one construction of RM codes, for any
and , an RM code with block length and
dimension
, denoted , is defined as a linear code
whose generator matrix
is obtained by deleting
of the rows of so that none of the deleted rows
has a larger Hamming weight (number of
’s in that row) than
any of the remaining
rows. For instance
and
This construction brings out the similarities between RM
codes and polar codes. Since
and have the same
set of rows (only in a different order) for any
,itis
clear that RM codes belong to the class of
-coset codes.
Authorized licensed use limited to: Southeast University. Downloaded on April 02,2022 at 12:40:26 UTC from IEEE Xplore. Restrictions apply.