Polarization

Encoding

Decoding

Construction

Polar Coding Tutorial

Erdal Arkan
Electrical-Electronics Engineering Department
Bilkent University
Ankara, Turkey

Jan. 15, 2015

Simons Institute
UC Berkeley

Performance

Polarization

Encoding

Decoding

Construction

The channel
Let W : X Y be a binary-input discrete memoryless channel
X

input alphabet: X = {0, 1},

output alphabet: Y,

transition probabilities:
W (y |x),

x X,y Y

Performance

Polarization

Encoding

Decoding

Construction

The channel
Let W : X Y be a binary-input discrete memoryless channel
X

input alphabet: X = {0, 1},

output alphabet: Y,

transition probabilities:
W (y |x),

x X,y Y

Performance

Polarization

Encoding

Decoding

Construction

The channel
Let W : X Y be a binary-input discrete memoryless channel
X

input alphabet: X = {0, 1},

output alphabet: Y,

transition probabilities:
W (y |x),

x X,y Y

Performance

Polarization

Encoding

Decoding

Construction

The channel
Let W : X Y be a binary-input discrete memoryless channel
X

input alphabet: X = {0, 1},

output alphabet: Y,

transition probabilities:
W (y |x),

x X,y Y

Performance

Polarization

Encoding

Decoding

Construction

Symmetry assumption
Assume that the channel has input-output symmetry.

Performance

Polarization

Encoding

Decoding

Construction

Symmetry assumption
Assume that the channel has input-output symmetry.
Examples:
BSC()
1

Performance

Polarization

Encoding

Decoding

Construction

Performance

Symmetry assumption
Assume that the channel has input-output symmetry.
Examples:
BSC()
1

BEC()
0

0
?
1

Polarization

Encoding

Decoding

Construction

Performance

Capacity

For channels with input-output symmetry, the capacity is given by

C (W ) = I (X ; Y ),

with X unif. {0, 1}

Polarization

Encoding

Decoding

Construction

Performance

Capacity

For channels with input-output symmetry, the capacity is given by

C (W ) = I (X ; Y ),

with X unif. {0, 1}

Use base-2 logarithms:

0 C (W ) 1

Polarization

Encoding

Decoding

Construction

The main idea

Channel coding problem trivial for two types of channels

Perfect: C (W ) = 1
Useless: C (W ) = 0

Transform ordinary W into such extreme channels

Performance

Polarization

Encoding

Decoding

Construction

The main idea

Channel coding problem trivial for two types of channels

Perfect: C (W ) = 1
Useless: C (W ) = 0

Transform ordinary W into such extreme channels

Performance

Polarization

Encoding

Decoding

Construction

The main idea

Channel coding problem trivial for two types of channels

Perfect: C (W ) = 1
Useless: C (W ) = 0

Transform ordinary W into such extreme channels

Performance

Polarization

Encoding

Decoding

Construction

The main idea

Channel coding problem trivial for two types of channels

Perfect: C (W ) = 1
Useless: C (W ) = 0

Transform ordinary W into such extreme channels

Performance

Polarization

Encoding

Decoding

Construction

The method: aggregate and redistribute capacity

Original channels
(uniform)
W

W
W

Performance

Polarization

Encoding

Decoding

Construction

The method: aggregate and redistribute capacity

Original channels
(uniform)
W

Vector
channel

Wvec
b

W
W

Combine

Performance

Polarization

Encoding

Decoding

Construction

The method: aggregate and redistribute capacity

Original channels
(uniform)
W

New channels
(polarized)
W1

Vector
channel

Wvec
b

WN1

WN

Combine

Split

Performance

Polarization

Encoding

Decoding

Construction

Performance

Combining

Begin with N copies of W ,

use a 1-1 mapping
GN : {0, 1}N {0, 1}N

X1
X2

W
W

Y1
Y2

to create a vector channel

Wvec : U N Y N

XN

YN

Polarization

Encoding

Decoding

Construction

Performance

Combining

Begin with N copies of W ,

U1

X1

U2

X2

use a 1-1 mapping

GN : {0, 1}N {0, 1}N

W
W

Y1
Y2

GN

to create a vector channel

Wvec : U N Y N

UN

XN

YN

Polarization

Encoding

Decoding

Construction

Performance

Combining

Begin with N copies of W ,

U1

X1

U2

X2

use a 1-1 mapping

GN : {0, 1}N {0, 1}N

W
W

Y1
Y2

GN

to create a vector channel

Wvec : U N Y N

UN

XN
Wvec

YN

Polarization

Encoding

Decoding

Construction

Performance

Conservation of capacity
Combining operation is lossless:

Take U1 , . . . , UN i.i.d. unif. {0, 1}

then, X1 , . . . , XN i.i.d. unif. {0, 1}

and

U1

X1

U2

X2

C (Wvec ) = I (U N ; Y N )

W
W

Y1
Y2

GN

= I (X N ; Y N )
= NC (W )

UN

XN
Wvec

YN

Polarization

Encoding

Decoding

Construction

Performance

Conservation of capacity
Combining operation is lossless:

Take U1 , . . . , UN i.i.d. unif. {0, 1}

then, X1 , . . . , XN i.i.d. unif. {0, 1}

and

U1

X1

U2

X2

C (Wvec ) = I (U N ; Y N )

W
W

Y1
Y2

GN

= I (X N ; Y N )
= NC (W )

UN

XN
Wvec

YN

Polarization

Encoding

Decoding

Construction

Performance

Conservation of capacity
Combining operation is lossless:

Take U1 , . . . , UN i.i.d. unif. {0, 1}

then, X1 , . . . , XN i.i.d. unif. {0, 1}

and

U1

X1

U2

X2

C (Wvec ) = I (U N ; Y N )

W
W

Y1
Y2

GN

= I (X N ; Y N )
= NC (W )

UN

XN
Wvec

YN

Polarization

Encoding

Decoding

Construction

Performance

Splitting
C (Wvec ) = I (U N ; Y N )

U1

Y1

Ui1
Ui

Wvec

Yi

Ui+1

UN

YN

Polarization

Encoding

Decoding

Construction

Performance

Splitting
C (Wvec ) = I (U N ; Y N )
=

N
X

U1
N

I (Ui ; Y , U

i1

Y1

i=1

Ui1
Ui

Wvec

Yi

Ui+1

UN

YN

Polarization

Encoding

Decoding

Construction

Splitting

Performance

U1
Ui1

C (Wvec ) = I (U N ; Y N )
=

N
X

U1
N

I (Ui ; Y , U

i1

Y1

i=1

Ui1
Ui
Define bit-channels

Wvec

Yi

Ui+1

Wi : Ui (Y N , U i1 )
UN

YN
Wi

Polarization

Encoding

Decoding

Construction

Splitting

Performance

U1
Ui1

C (Wvec ) = I (U N ; Y N )
=

N
X

i=1
N
X

U1
N

I (Ui ; Y , U

C (Wi )

i=1

Define bit-channels

i1

Y1

)
Ui1
Ui

Wvec

Yi

Ui+1

Wi : Ui (Y N , U i1 )
UN

YN
Wi

Polarization

Encoding

Decoding

Construction

Performance

Polarization is commonplace

Polarization is the rule not the

exception

A random permutation
GN : {0, 1}N {0, 1}N

U1

X1

U2

X2

W
W

Y1
Y2

GN
is a good polarizer with high
probability

Equivalent to Shannons random

coding approach

UN

XN

YN

Polarization

Encoding

Decoding

Construction

Performance

Polarization is commonplace

Polarization is the rule not the

exception

A random permutation
GN : {0, 1}N {0, 1}N

U1

X1

U2

X2

W
W

Y1
Y2

GN
is a good polarizer with high
probability

Equivalent to Shannons random

coding approach

UN

XN

YN

Polarization

Encoding

Decoding

Construction

Performance

Polarization is commonplace

Polarization is the rule not the

exception

A random permutation
GN : {0, 1}N {0, 1}N

U1

X1

U2

X2

W
W

Y1
Y2

GN
is a good polarizer with high
probability

Equivalent to Shannons random

coding approach

UN

XN

YN

Polarization

Encoding

Decoding

Construction

Random polarizers: stepwise, isotropic

1

0.9

0.8

0.7

Capacity

0.6

0.5

0.4

0.3

0.2

0.1

10

15

20

Bit channel index

25

30

Performance

Polarization

Encoding

Decoding

Construction

Random polarizers: stepwise, isotropic

1

0.9

0.8

0.7

Capacity

0.6

0.5

0.4

0.3

0.2

0.1

10

15

20

25

30

Bit channel index

Isotropy: any redistribution order is as good as any other.

Performance

Polarization

Encoding

Decoding

Construction

Performance

The complexity issue

Random polarizers lack structure, too complex to implement

Need a low-complexity polarizer

May sacrifice stepwise, isotropic properties of random

polarizers in return for less complexity

Polarization

Encoding

Decoding

Construction

Performance

The complexity issue

Random polarizers lack structure, too complex to implement

Need a low-complexity polarizer

May sacrifice stepwise, isotropic properties of random

polarizers in return for less complexity

Polarization

Encoding

Decoding

Construction

Performance

The complexity issue

Random polarizers lack structure, too complex to implement

Need a low-complexity polarizer

May sacrifice stepwise, isotropic properties of random

polarizers in return for less complexity

Polarization

Encoding

Decoding

Construction

Basic module for a low-complexity scheme

Combine two copies of W
X1

Y1

X2

Y2

Performance

Polarization

Encoding

Decoding

Construction

Basic module for a low-complexity scheme

Combine two copies of W
U1

U2

G2

X1

Y1

X2

Y2

Performance

Polarization

Encoding

Decoding

Construction

Basic module for a low-complexity scheme

Combine two copies of W
U1

U2

X1

Y1

X2

Y2

G2
and split to create two bit-channels
W1 : U1 (Y1 , Y2 )
W2 : U2 (Y1 , Y2 , U1 )

Performance

Polarization

Encoding

Decoding

Construction

The first bit-channel W1

W1 : U1 (Y1 , Y2 )

U1
random U2

Y1

Y2

Performance

Polarization

Encoding

Decoding

Construction

The first bit-channel W1

W1 : U1 (Y1 , Y2 )

U1
random U2

Y1

Y2

C (W1 ) = I (U1 ; Y1 , Y2 )

Performance

Polarization

Encoding

Decoding

Construction

The second bit-channel W2

W2 : U2 (Y1 , Y2 , U1 )

U1

U2

Y1

Y2

Performance

Polarization

Encoding

Decoding

Construction

The second bit-channel W2

W2 : U2 (Y1 , Y2 , U1 )

U1

U2

Y1

Y2

C (W2 ) = I (U2 ; Y1 , Y2 , U1 )

Performance

Polarization

Encoding

Decoding

Construction

Capacity conserved but redistributed unevenly

U1

U2

X1

Y1

X2

Y2

Conservation:
C (W1 ) + C (W2 ) = 2C (W )

Extremization:
C (W1 ) C (W ) C (W2 )
with equality iff C (W ) equals 0 or 1.

Performance

Polarization

Encoding

Decoding

Construction

Capacity conserved but redistributed unevenly

U1

U2

X1

Y1

X2

Y2

Conservation:
C (W1 ) + C (W2 ) = 2C (W )

Extremization:
C (W1 ) C (W ) C (W2 )
with equality iff C (W ) equals 0 or 1.

Performance

Polarization

Encoding

Decoding

Construction

Notation
The two channels created by the basic transform
(W , W ) (W1 , W2 )
will be denoted also as
W = W1

and

W + = W2

Performance

Polarization

Encoding

Decoding

Construction

Performance

Notation
The two channels created by the basic transform
(W , W ) (W1 , W2 )
will be denoted also as
W = W1

and

W + = W2

Likewise, we write W , W + for descendants of W ; and W + ,

W ++ for descendants of W + .

Polarization

Encoding

Decoding

Construction

For the size-4 construction

+

W
W

Performance

Polarization

Encoding

Decoding

Construction

... duplicate the basic transform

+

W
W

W
W

Performance

Polarization

Encoding

Decoding

Construction

... obtain a pair of W and W + each

W
W+
W
W+

Performance

Polarization

Encoding

Decoding

Construction

... apply basic transform on each pair

+
+

W
W+
W
W+

Performance

Polarization

Encoding

Decoding

Construction

... decode in the indicated order

+

U1
U3

W
W+

U2

U4

W+

Performance

Polarization

Encoding

Decoding

Construction

... obtain the four new bit-channels

U1

U3

W +

U2

W +

U4

W ++

Performance

Polarization

Encoding

Decoding

Construction

Overall size-4 construction

+

U1
U3
U2
U4

+
+

X1

Y1

X3

Y3

X2

Y2

X4

Y4

Performance

Polarization

Encoding

Decoding

Construction

Rewire for standard-form size-4 construction

U1

+
+

U2
U3
U4

X1

Y1

X2

Y2

X3

Y3

X4

Y4

Performance

Polarization

Encoding

Decoding

Construction

Size 8 construction
U1

U2
U3

+
+

U4
U5

+
+

U6
U7
U8

+
+

X1

Y1

X2

Y2

X3

Y3

X4

Y4

X5

Y5

X6

Y6

X7

Y7

X8

Y8

Performance

Polarization

Encoding

Decoding

Construction

Performance

Demonstration of polarization
Polarization is easy to analyze when W is a BEC.

If W is a BEC(), then so are W

and W + , with erasure probabilities

= 2 2
and

+ = 2
respectively.

?
1

Polarization

Encoding

Decoding

Construction

Performance

Demonstration of polarization
Polarization is easy to analyze when W is a BEC.

If W is a BEC(), then so are W

and W + , with erasure probabilities

= 2 2
and

+ = 2
respectively.

0
?
1

Polarization

Encoding

Decoding

Construction

Performance

Demonstration of polarization
Polarization is easy to analyze when W is a BEC.

If W is a BEC(), then so are W

and W + , with erasure probabilities

= 2 2
and

1 +
+
+

+ = 2
respectively.

W+

1 +

0
?
1

Polarization

Encoding

Decoding

Construction

Performance

Polarization for BEC( 21 ): N = 16

Capacity of bit channels
1

0.9

0.8

0.7

Capacity

0.6

0.5

0.4

0.3

0.2

0.1
N=16
0

10

Bit channel index

12

14

16

Polarization

Encoding

Decoding

Construction

Performance

Polarization for BEC( 21 ): N = 32

Capacity of bit channels
1

0.9

0.8

0.7

Capacity

0.6

0.5

0.4

0.3

0.2

0.1
N=32
0

10

15

20

Bit channel index

25

30

Polarization

Encoding

Decoding

Construction

Performance

Polarization for BEC( 21 ): N = 64

Capacity of bit channels
1

0.9

0.8

0.7

Capacity

0.6

0.5

0.4

0.3

0.2

0.1
N=64
0

10

20

30

40

Bit channel index

50

60

Polarization

Encoding

Decoding

Construction

Polarization for BEC( 21 ): N = 128

Capacity of bit channels
1

0.9

0.8

0.7

Capacity

0.6

0.5

0.4

0.3

0.2

0.1
N=128
0

20

40

60

80

Bit channel index

100

120

Performance

Polarization

Encoding

Decoding

Construction

Performance

Polarization for BEC( 21 ): N = 256

Capacity of bit channels
1

0.9

0.8

0.7

Capacity

0.6

0.5

0.4

0.3

0.2

0.1
N=256
0

50

100

150

Bit channel index

200

250

Polarization

Encoding

Decoding

Construction

Performance

Polarization for BEC( 21 ): N = 512

Capacity of bit channels
1

0.9

0.8

0.7

Capacity

0.6

0.5

0.4

0.3

0.2

0.1
N=512
0

50

100

150

200

250

300

Bit channel index

350

400

450

500

Polarization

Encoding

Decoding

Construction

Performance

Polarization for BEC( 21 ): N = 1024

Capacity of bit channels
1

0.9

0.8

0.7

Capacity

0.6

0.5

0.4

0.3

0.2

0.1
N=1024
0

100

200

300

400

500

600

Bit channel index

700

800

900

1000

Polarization

Encoding

Polarization martingale
1

C (W )

Decoding

Construction

Performance

Polarization

Encoding

Polarization martingale
1

C (W2 )

C (W )

C (W1 )

Decoding

Construction

Performance

Polarization

Encoding

Polarization martingale
1
C (W ++ )
C (W2 )

C (W + )
C (W )

C (W + )

C (W1 )
C (W )

Decoding

Construction

Performance

Polarization

Encoding

Polarization martingale
1
C (W ++ )
C (W2 )

C (W + )
C (W )

C (W + )

C (W1 )
C (W )

Decoding

Construction

Performance

Polarization

Encoding

Decoding

Polarization martingale
1
C (W ++ )
C (W2 )

C (W + )
C (W )

C (W + )

C (W1 )
C (W )

Construction

Performance

Polarization

Encoding

Decoding

Polarization martingale
1
C (W ++ )
C (W2 )

C (W + )
C (W )

C (W + )

C (W1 )
C (W )

Construction

Performance

Polarization

Encoding

Decoding

Construction

Polarization martingale
1
C (W ++ )
C (W2 )

C (W + )
C (W )

C (W + )

C (W1 )
C (W )

Performance

Polarization

Encoding

Decoding

Construction

Polarization martingale
1
C (W ++ )
C (W2 )

C (W + )
C (W )

C (W + )

C (W1 )
C (W )

Performance

Polarization

Encoding

Decoding

Construction

Polarization martingale
1
C (W ++ )
C (W2 )

C (W + )
C (W )

C (W + )

C (W1 )
C (W )

Performance

Polarization

Encoding

Decoding

Construction

Performance

Polarization martingale
1
C (W ++ )
C (W2 )

C (W + )
C (W )

C (W + )

C (W1 )
C (W )

Polarization

Encoding

Decoding

Construction

Theorem (Polarization, A. 2007)

Performance

1
1

The bit-channel capacities {C (Wi )} polarize: for any

(0, 1), as the construction size N grows


no. channels with C (Wi ) > 1
C (W )
N
and



no. channels with C (Wi ) <
1 C (W )
N

Theorem (Rate of polarization,

A. and Telatar (2008))
Above theorem holds with

2 N .

Polarization

Encoding

Decoding

Construction

Theorem (Polarization, A. 2007)

Performance

1
1

The bit-channel capacities {C (Wi )} polarize: for any

(0, 1), as the construction size N grows


no. channels with C (Wi ) > 1
C (W )
N
and



no. channels with C (Wi ) <
1 C (W )
N

Theorem (Rate of polarization,

A. and Telatar (2008))
Above theorem holds with

2 N .

Polarization

Encoding

Decoding

Construction

Performance

Polar code example: W = BEC( 12 ), N = 8, rate 1/2

I (Wi )
0.0039

U1

0.1211

U2

0.1914

U3

0.6836

U4

0.3164

U5

0.8086

U6

0.8789

U7

0.9961

U8

+
+

+
+

Y1

Y2

Y3

Y4

Y5

Y6

Y7

Y8

Polarization

Encoding

Decoding

Construction

Performance

Polar code example: W = BEC( 12 ), N = 8, rate 1/2

I (Wi )

Rank

0.0039

U1

0.1211

U2

0.1914

U3

0.6836

U4

0.3164

U5

0.8086

U6

0.8789

U7

0.9961

U8

+
+

+
+

Y1

Y2

Y3

Y4

Y5

Y6

Y7

Y8

Polarization

Encoding

Decoding

Construction

Performance

Polar code example: W = BEC( 12 ), N = 8, rate 1/2

I (Wi )

Rank

0.0039

U1

0.1211

U2

0.1914

U3

0.6836

U4

0.3164

U5

0.8086

U6

0.8789

U7

0.9961

data U8

+
+

+
+

Y1

Y2

Y3

Y4

Y5

Y6

Y7

Y8

Polarization

Encoding

Decoding

Construction

Performance

Polar code example: W = BEC( 12 ), N = 8, rate 1/2

I (Wi )

Rank

0.0039

U1

0.1211

U2

0.1914

U3

0.6836

U4

0.3164

U5

0.8086

U6

0.8789

data U7

0.9961

data U8

+
+

+
+

Y1

Y2

Y3

Y4

Y5

Y6

Y7

Y8

Polarization

Encoding

Decoding

Construction

Performance

Polar code example: W = BEC( 12 ), N = 8, rate 1/2

I (Wi )

Rank

0.0039

U1

0.1211

U2

0.1914

U3

0.6836

U4

0.3164

U5

0.8086

data U6

0.8789

data U7

0.9961

data U8

+
+

+
+

Y1

Y2

Y3

Y4

Y5

Y6

Y7

Y8

Polarization

Encoding

Decoding

Construction

Performance

Polar code example: W = BEC( 12 ), N = 8, rate 1/2

I (Wi )

Rank

0.0039

U1

0.1211

U2

0.1914

U3

0.6836

data U4

0.3164

U5

0.8086

data U6

0.8789

data U7

0.9961

data U8

+
+

+
+

Y1

Y2

Y3

Y4

Y5

Y6

Y7

Y8

Polarization

Encoding

Decoding

Construction

Performance

Polar code example: W = BEC( 12 ), N = 8, rate 1/2

I (Wi )

Rank

0.0039

frozen U1

0.1211

frozen U2

0.1914

frozen U3

0.6836

data U4

0.3164

frozen U5

0.8086

data U6

0.8789

data U7

0.9961

data U8

+
+

+
+

Y1

Y2

Y3

Y4

Y5

Y6

Y7

Y8

Polarization

Encoding

Decoding

Construction

Performance

Polar code example: W = BEC( 12 ), N = 8, rate 1/2

I (Wi )

Rank

0.0039

frozen

0.1211

frozen

0.1914

frozen

0.6836

0.3164

0.8086

data U6

0.8789

data U7

0.9961

data U8

+
+

+
+

data U4
frozen

+
+

Y1

Y2

Y3

Y4

Y5

Y6

Y7

Y8

Polarization

Encoding

Decoding

Construction

Performance

Encoding complexity
Theorem
Encoding complexity for polar coding is O(N log N).
Proof:

Polar coding transform can be represented as a graph with

N[1 + log(N)] variables.

The graph has (1 + log(N)) levels with N variables at each

level.

Computation begins at the source level and can be carried out

level by level.

Space complexity O(N), time complexity O(N log N).

Polarization

Encoding

Decoding

Construction

Performance

Encoding complexity
Theorem
Encoding complexity for polar coding is O(N log N).
Proof:

Polar coding transform can be represented as a graph with

N[1 + log(N)] variables.

The graph has (1 + log(N)) levels with N variables at each

level.

Computation begins at the source level and can be carried out

level by level.

Space complexity O(N), time complexity O(N log N).

Polarization

Encoding

Decoding

Construction

Performance

Encoding complexity
Theorem
Encoding complexity for polar coding is O(N log N).
Proof:

Polar coding transform can be represented as a graph with

N[1 + log(N)] variables.

The graph has (1 + log(N)) levels with N variables at each

level.

Computation begins at the source level and can be carried out

level by level.

Space complexity O(N), time complexity O(N log N).

Polarization

Encoding

Decoding

Construction

Performance

Encoding complexity
Theorem
Encoding complexity for polar coding is O(N log N).
Proof:

Polar coding transform can be represented as a graph with

N[1 + log(N)] variables.

The graph has (1 + log(N)) levels with N variables at each

level.

Computation begins at the source level and can be carried out

level by level.

Space complexity O(N), time complexity O(N log N).

Polarization

Encoding

Decoding

Construction

Encoding: an example
frozen

frozen

frozen

free

frozen

free

free

free

+
+

+
+

Y1

Y2

Y3

Y4

Y5

Y6

Y7

Y8

Performance

Polarization

Encoding

Decoding

Construction

Encoding: an example
W

Y1

Y2

Y3

Y4

Y5

Y6

+1

Y7

Y8

frozen

+0

frozen

frozen

+1

free

frozen

+1

free

free

free

+
+
+
+

Performance

Polarization

Encoding

Decoding

Construction

Encoding: an example
W

Y1

Y2

Y3

Y4

Y5

Y6

+1

Y7

Y8

frozen

+0

frozen

frozen

+1

free

frozen

+1

free

free

free

+
+

+
+
+

Performance

Polarization

Encoding

Decoding

Construction

Encoding: an example
1

Y1

Y2

Y3

Y4

Y5

Y6

+1

Y7

Y8

frozen

+0

frozen

frozen

+1

free

frozen

+1

free

free

free

+
+

+
+
+
+

Performance

Polarization

Encoding

Decoding

Construction

Performance

Successive Cancellation Decoding (SCD)

Theorem
The complexity of successive cancellation decoding for polar codes
is O(N log N).
Proof: Given below.

Polarization

Encoding

Decoding

Construction

SCD: Exploit the x = |a|a + b| structure

u1
u2
u3

u7

u8

+
+

y1

x2

y2

x3

y3

b4 +

x4

y4

a1

x5

y5

a2

x6

y6

a3

x7

y7

a4

x8

y8

b3

u6

b2

u4
u5

x1

+ b1

+
+

Performance

Polarization

Encoding

Decoding

Construction

First phase: treat a as noise, decode (u1 , u2 , u3 , u4 )

u1
u2
u3
u4

x1

y1

x2

y2

x3

y3

x4

y4

noise a1

x5

y5

noise a2

x6

y6

noise a3

x7

y7

noise a4

x8

y8

+ b1

+
+
+

b2
b3
b4 +

+
+

Performance

Polarization

Encoding

Decoding

Construction

End of first phase

u1
u2
u3

+ b1

u7

u8

+
+

y1

x2

y2

x3

y3

b4 +

x4

y4

a1

x5

y5

a2

x6

y6

a3

x7

y7

a4

x8

y8

b3

u6

b2

u4
u5

x1

+
+
+

Performance

Polarization

Encoding

Decoding

Construction

Performance

as known, decode (u5 , u6 , u7 , u8 )

Second phase: Treat b
known b1

y1

y2

y3

y4

a1

y5

a2

y6

a3

y7

a4

y8

known b2
known b3
known b4 +
u5

u6
u7
u8

+
+

+
+

Polarization

Encoding

Decoding

Construction

First phase in detail

u1
u2
u3
u4

x1

y1

x2

y2

x3

y3

x4

y4

noise a1

x5

y5

noise a2

x6

y6

noise a3

x7

y7

noise a4

x8

y8

+ b1

+
+
+

b2
b3
b4 +

+
+

Performance

Polarization

Encoding

Decoding

Construction

Equivalent channel model

x1

y1

x2

y2

x3

y3

x4

y4

noise a1

x5

y5

noise a2

x6

y6

noise a3

x7

y7

noise a4

x8

y8

b1

b2
b3
b4 +

+
+

Performance

Polarization

Encoding

Decoding

Construction

First copy of W
x1

y1

x2

y2

x3

y3

x4

y4

noise a1

x5

y5

noise a2

x6

y6

noise a3

x7

y7

noise a4

x8

y8

b1

b2
b3
b4 +

+
+

Performance

Polarization

Encoding

Decoding

Construction

Second copy of W
x1

y1

x2

y2

x3

y3

x4

y4

noise a1

x5

y5

noise a2

x6

y6

noise a3

x7

y7

noise a4

x8

y8

b1

b2
b3
b4 +

+
+

Performance

Polarization

Encoding

Decoding

Construction

Third copy of W
x1

y1

x2

y2

x3

y3

x4

y4

noise a1

x5

y5

noise a2

x6

y6

noise a3

x7

y7

noise a4

x8

y8

b1

b2
b3
b4 +

+
+

Performance

Polarization

Encoding

Decoding

Construction

Fourth copy of W
x1

y1

x2

y2

x3

y3

x4

y4

noise a1

x5

y5

noise a2

x6

y6

noise a3

x7

y7

noise a4

x8

y8

b1

b2
b3
b4 +

+
+

Performance

Polarization

Encoding

Decoding

Construction

Decoding on W

u1

u2
u3
u4

+
+

+ b1

(y1 , y5 )

b2

(y2 , y6 )

b3

(y3 , y7 )

b4

(y4 , y8 )

Performance

Polarization

Encoding

Decoding

Construction

b = |t|t + w|

u1
u2

+ w1
w2 +

+ b1

(y1 , y5 )

b2

(y2 , y6 )

u3

+ t1

b3

(y3 , y7 )

u4

t2

b4

(y4 , y8 )

Performance

Polarization

Encoding

Decoding

Construction

Decoding on W

u1

+ w1

(y1 , y3 , y5 , y7 )

u2

w2

(y2 , y4 , y6 , y8 )

Performance

Polarization

Encoding

Decoding

Construction

Performance

Decoding on W

u1

(y1 , y2 , . . . , y8 )

Polarization

Encoding

Decoding

Construction

Performance

Decoding on W

u1

(y1 , y2 , . . . , y8 )

Compute

L =

W (y1 , . . . , y8 | u1 = 0)
.
W (y1 , . . . , y8 | u1 = 1)

Polarization

Encoding

Decoding

Construction

Performance

Decoding on W

u1

(y1 , y2 , . . . , y8 )

Compute

L =
Set

W (y1 , . . . , y8 | u1 = 0)
.
W (y1 , . . . , y8 | u1 = 1)

u1
u1 = 0

if u1 is frozen
else if L > 0
else

Polarization

Encoding

Decoding

Construction

Performance

Decoding on W

u1

(y1 , y2 , . . . , y8 )

Compute

L =
Set

W (y1 , . . . , y8 | u1 = 0)
.
W (y1 , . . . , y8 | u1 = 1)

u1
u1 = 0

if u1 is frozen
else if L > 0
else

Polarization

Encoding

Decoding

Construction

Performance

Decoding on W

u1

(y1 , y2 , . . . , y8 )

Compute

L =
Set

W (y1 , . . . , y8 | u1 = 0)
.
W (y1 , . . . , y8 | u1 = 1)

u1
u1 = 0

if u1 is frozen
else if L > 0
else

Polarization

Encoding

Decoding

Construction

Decoding on W +

known u1
u2

(y1 , y3 , y5 , y7 )

(y2 , y4 , y6 , y8 )

Performance

Polarization

Encoding

Decoding

Construction

Performance

Decoding on W +

u2

W +

(y1 , . . . , y8 , u1 )

Polarization

Encoding

Decoding

Construction

Performance

Decoding on W +

u2

W +

(y1 , . . . , y8 , u1 )

Compute

L+ =

W + (y1 , . . . , y8 , u1 | u2 = 0)
.
W + (y1 , . . . , y8 , u1 | u2 = 1)

Polarization

Encoding

Decoding

Construction

Performance

Decoding on W +

u2

W +

(y1 , . . . , y8 , u1 )

Compute

L+ =
Set

W + (y1 , . . . , y8 , u1 | u2 = 0)
.
W + (y1 , . . . , y8 , u1 | u2 = 1)

u2
u2 = 0

if u2 is frozen
else if L+ > 0
else

Polarization

Encoding

Decoding

Construction

Performance

Decoding on W +

u2

W +

(y1 , . . . , y8 , u1 )

Compute

L+ =
Set

W + (y1 , . . . , y8 , u1 | u2 = 0)
.
W + (y1 , . . . , y8 , u1 | u2 = 1)

u2
u2 = 0

if u2 is frozen
else if L+ > 0
else

Polarization

Encoding

Decoding

Construction

Performance

Decoding on W +

u2

W +

(y1 , . . . , y8 , u1 )

Compute

L+ =
Set

W + (y1 , . . . , y8 , u1 | u2 = 0)
.
W + (y1 , . . . , y8 , u1 | u2 = 1)

u2
u2 = 0

if u2 is frozen
else if L+ > 0
else

Polarization

Encoding

Decoding

Construction

Performance

Complexity for successive cancelation decoding

Let CN be the complexity of decoding a code of length N

Decoding problem of size N for W reduced to two decoding

problems of size N/2 for W and W +

So
CN = 2CN/2 + kN
for some constant k

This gives CN = O(N log N)

Polarization

Encoding

Decoding

Construction

Performance

Complexity for successive cancelation decoding

Let CN be the complexity of decoding a code of length N

Decoding problem of size N for W reduced to two decoding

problems of size N/2 for W and W +

So
CN = 2CN/2 + kN
for some constant k

This gives CN = O(N log N)

Polarization

Encoding

Decoding

Construction

Performance

Complexity for successive cancelation decoding

Let CN be the complexity of decoding a code of length N

Decoding problem of size N for W reduced to two decoding

problems of size N/2 for W and W +

So
CN = 2CN/2 + kN
for some constant k

This gives CN = O(N log N)

Polarization

Encoding

Decoding

Construction

Performance

Complexity for successive cancelation decoding

Let CN be the complexity of decoding a code of length N

Decoding problem of size N for W reduced to two decoding

problems of size N/2 for W and W +

So
CN = 2CN/2 + kN
for some constant k

This gives CN = O(N log N)

Polarization

Encoding

Decoding

Construction

Performance

Performance of polar codes

Theorem
For any rate R < I (W ) and block-length N, the probability of
frame error for polar codes under successive cancelation decoding is
bounded as


Pe (N, R) = o 2 N+o( N)
Proof: Given in the next presentation.

Polarization

Encoding

Decoding

Construction

Performance

Construction complexity

Theorem
Given W and a rate R < I (W ), a polar code can be constructed in
O(Npoly(log (N))) time that achieves under SCD the performance


Pe = o 2 N+o( N)
Proof: Given in the next presentation.

Polarization

Encoding

Decoding

Construction

Performance

Polar coding summary

Summary
Given W , N = 2n , and R < I (W ), a polar code can be constructed
such that it has

construction complexity O(Npoly(log (N))),

encoding complexity N log N,

successive-cancellation decoding complexity N log N,



frame error probability Pe (N, R) = o 2 N+o( N) .

Polarization

Encoding

Decoding

Construction

Performance

Polar coding summary

Summary
Given W , N = 2n , and R < I (W ), a polar code can be constructed
such that it has

construction complexity O(Npoly(log (N))),

encoding complexity N log N,

successive-cancellation decoding complexity N log N,



frame error probability Pe (N, R) = o 2 N+o( N) .

Polarization

Encoding

Decoding

Construction

Performance

Polar coding summary

Summary
Given W , N = 2n , and R < I (W ), a polar code can be constructed
such that it has

construction complexity O(Npoly(log (N))),

encoding complexity N log N,

successive-cancellation decoding complexity N log N,



frame error probability Pe (N, R) = o 2 N+o( N) .

Polarization

Encoding

Decoding

Construction

Performance

Polar coding summary

Summary
Given W , N = 2n , and R < I (W ), a polar code can be constructed
such that it has

construction complexity O(Npoly(log (N))),

encoding complexity N log N,

successive-cancellation decoding complexity N log N,



frame error probability Pe (N, R) = o 2 N+o( N) .

Polarization

Encoding

Decoding

Construction

List decoder for polar codes

Developed by Tal and Vardy (2011); similar to Dumers list

decoder for Reed-Muller codes.

First produce L candidate decisions

Pick the most likely word from the list

Complexity O(LN log N)

Performance

Polarization

Encoding

Decoding

Construction

List decoder for polar codes

Developed by Tal and Vardy (2011); similar to Dumers list

decoder for Reed-Muller codes.

First produce L candidate decisions

Pick the most likely word from the list

Complexity O(LN log N)

Performance

Polarization

Encoding

Decoding

Construction

List decoder for polar codes

Developed by Tal and Vardy (2011); similar to Dumers list

decoder for Reed-Muller codes.

First produce L candidate decisions

Pick the most likely word from the list

Complexity O(LN log N)

Performance

Polarization

Encoding

Decoding

Construction

Tal-Vardy list decoder performance

Length n = 2048, rate R = 0.5, BPSK-AWGN channel, list-size L.

Performance

Polarization

Encoding

Decoding

Construction

Tal-Vardy list decoder performance

Length n = 2048, rate R = 0.5, BPSK-AWGN channel, list-size L.

Performance

Polarization

Encoding

Decoding

Construction

Tal-Vardy list decoder performance

Length n = 2048, rate R = 0.5, BPSK-AWGN channel, list-size L.

Performance

Polarization

Encoding

Decoding

Construction

Tal-Vardy list decoder performance

Length n = 2048, rate R = 0.5, BPSK-AWGN channel, list-size L.

Performance

Polarization

Encoding

Decoding

Construction

Tal-Vardy list decoder performance

Length n = 2048, rate R = 0.5, BPSK-AWGN channel, list-size L.

Performance

Polarization

Encoding

Decoding

Construction

Tal-Vardy list decoder performance

Length n = 2048, rate R = 0.5, BPSK-AWGN channel, list-size L.

Performance

Polarization

Encoding

Decoding

Construction

Tal-Vardy list decoder performance

Length n = 2048, rate R = 0.5, BPSK-AWGN channel, list-size L.

List-of-L performance quickly approaches ML performance!

Performance

Polarization

Encoding

Decoding

Construction

List decoder with CRC

Same decoder as before but data contains a built-in CRC

Selection made by CRC and relative likelihood

Performance

Polarization

Encoding

Decoding

Construction

List decoder with CRC

Same decoder as before but data contains a built-in CRC

Selection made by CRC and relative likelihood

Performance

Polarization

Encoding

Decoding

Construction

Tal-Vardy list decoder with CRC

Length n = 2048, rate R = 0.5, BPSK-AWGN channel, list-size L.

Performance

Polarization

Encoding

Decoding

Construction

Tal-Vardy list decoder with CRC

Length n = 2048, rate R = 0.5, BPSK-AWGN channel, list-size L.

Performance

Polarization

Encoding

Decoding

Construction

Tal-Vardy list decoder with CRC

Length n = 2048, rate R = 0.5, BPSK-AWGN channel, list-size L.

Polar codes (+CRC) achieve state-of-the-art performance!

Performance

Polarization

Encoding

Decoding

Construction

Performance

Summary

Polarization is a commonplace phenomenon almost

unavoidable

Polar codes are low-complexity methods designed to exploit

polarization for achieving Shannon limits

Polar codes with some help from other methods perform

competitively with the state-of-the-art codes in terms of
complexity and performance

Polarization

Encoding

Decoding

Construction

Performance

Summary

Polarization is a commonplace phenomenon almost

unavoidable

Polar codes are low-complexity methods designed to exploit

polarization for achieving Shannon limits

Polar codes with some help from other methods perform

competitively with the state-of-the-art codes in terms of
complexity and performance

Polarization

Encoding

Decoding

Construction

Performance

Summary

Polarization is a commonplace phenomenon almost

unavoidable

Polar codes are low-complexity methods designed to exploit

polarization for achieving Shannon limits

Polar codes with some help from other methods perform

competitively with the state-of-the-art codes in terms of
complexity and performance