Error Control Coding

Lecture Notes

Prof. Dr.-Ing. Volker Kühn

University of Rostock
Institute of Communications Engineering
Error Control Coding
Table of Contents

Basics of Digital Communications – A Summary

Two Lessons of Information Theory

Forward Error Correcting Codes – The Classics

Modern Error Correcting Codes

Concatenated Codes
Turbo Decoding Principle
EXIT Charts
LDPC codes
Polar Codes
V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 263 / 385
Motivation of Polar Codes
• Polar codes invented by Erdal Arikan

• Polar coding converts any binary-input channel to binary-input

extreme channels (polarization)

• Polarization is information lossless, i.e. rate of ideal sub-channels

equals the symmetric capacity of the physical channel

• Coding scheme achieves capacity (can be mathematically

guaranteed)

• Low encoding and decoding complexity, increases proportional to

n · log2 n with the code length n
• Low polarization rate n−1/2 requires very long codes for low error
rates
V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 264 / 385
Motivation of Polar Codes
Some Literature

[E. Arikan: "Channel polarization: A method for constructing

capacity-achieving codes", IEEE International Symposium on Information
Theory, July 2008]
[E. Arikan: "Channel Polarization: A Method for Constructing
Capacity-Achieving Codes for Symmetric Binary-Input Memoryless
Channels", IEEE Transactions on Information Theory, vol. 55, no. 7, pp.
3051-3073, July 2009]
[E. Arikan: "Channel polarization: A method for constructing
capacity-achieving codes", IEEE International Symposium on Information
Theory, July 2008]
[E. Arikan: "Systematic Polar Coding", IEEE Communication Letters, vol.
15, no. 8, pp. 860-862, August 2011]
V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 265 / 385
Basic Principle of Polar Codes
Combining and Splitting, W denotes original binary input channel

original channels polarized channels

W vector channel W1

W Wvector W2

W Wn

combine split

V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 266 / 385
Basic Principle of Polar Codes
Combining Step leads to Vector Channel
x1
u1 W y1
x2
u2 W y2
Gn

xn
un W yn
Wvector

• 1-to-1 mapping Gn : {0, 1}n → {0, 1}n generates vector x

• Vector channel Wvector maps u onto y

• Lossless combining: C(Wvector ) = I(U; Y) = I(X ; Y) = nC(W )

V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 267 / 385
Basic Principle of Polar Codes
Splitting Step exploits Chain Rule of Mutual Information
• Chain rule of mutual information
u1
C(Wvector ) = I(U; Y) ui−1
X
= I(Ui ; Y | u1i−1 )
i u1 y1
X  
= C Wn(i) ui−1
i
yi
• Vector-channel is transformed into n
ui Wvector
(i)
bit-channels Wn : ui → (y, u1i−1 ) ui+1
(i)
• Obviously, splitting of Wvector into Wn
does not change total capacity un yn
• Now determination of bit-channel
(i) (i)
capacities Wn Wn
V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 268 / 385
Basic 2-Channel Module
Analysis of Bit-Channel Capacities
x1
u1 W y1
x2
u2 W y2
G2

• Mapping G2 is performed by x1 = u1 ⊕ u2 and x2 = u2

(1) (2)
• Basic module results into 2 bit-channels W2 and W2
(1)
• Bit-Channel W2 : u1 → (y1 , y2 )
(2)
• Bit-Channel W2 : u2 → (y1 , y2 | u1 )

• Following analysis performed for binary erasure channels (BEC) W

V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 269 / 385
Basic 2-Channel Module
(1)
Analysis of Bit-Channel W2 : u1 → (y1 , y2 )
x1
u1 BEC y1 input-output
combinations
x2 y1 y2 u1
random u2 BEC y2
0 0 0
• Bit u1 can only be detected if none of both 1 0 1
BECs outputs an erasure ? 0 ?
(1)
• Bit-channel W2 = W − is again a BEC with 0 1 1
erasure probability 1 1 0
? 1 ?
Pe (W − ) = 1−(1−Pe (W ))2 = 2Pe (W )−Pe (W )2 0 ? ?
1 ? ?
• Bit-channel capacity amounts to ? ? ?
C(W − ) = 1 − Pe (W − ) = (1 − Pe (W ))2
V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 270 / 385
Basic 2-Channel Module
(2)
Analysis of Bit-Channel W2 : u2 → (y1 , y2 | u1 )
x1 input-output
u1 BEC y1 combinations
x2
u2 BEC y2 y1 y2 u1 u2
0 0 0 0
• Bit u2 is only erased if both BECs output
1 0 1 0
erasures
(2) ? 0 ? 0
• Bit-channel W2 = W + is again a BEC with
0 1 1 1
erasure probability
1 1 0 1
Pe (W + ) = Pe (W )2 ? 1 ? 1
0 ? 0, 1 0, 1
• Bit-channel capacity amounts to 1 ? 0, 1 1, 0
C(W + ) = 1 − Pe (W + ) = 1 − Pe (W )2 ? ? ? ?

V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 271 / 385
Basic 2-Channel Module
Summary of Bit-Channel Capacities
(1) (2)
• Vector channel is mapped onto bit-channels W2 and W2

• W2(1) = W − is worse than original W (larger erasure probability)

Pe (W − ) = 2Pe (W ) − Pe (W )2 > Pe (W )

• W2(2) = W + gains diversity and is better than original W (smaller

erasure probability)
Pe (W + ) = Pe (W )2 < Pe (W )

• Entire capacity of vector channel does not change

C(W2 ) = C(W + ) + C(W − )=(1−Pe (W )2 )+(1−2Pe (W )+Pe (W )2 )
= 2 (1 − Pe (W )) = 2C(W )
V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 272 / 385
Extension to 4 Basic Channels
Construction of Bit-Channels

• Duplicate channel W2 and transform each pair into bit-channels W −

and W +

• Apply basic transform again and decode in indicated order to obtain

new bit-channels W −− , W −+ , W +− and W ++
x1
u1 W
WW≠≠
≠ y1
x2
u3 W
WW+≠
+ y2
x3
u2 W
W ≠
W≠+ y3
x4
u4 W
WW++
+ y4
V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 273 / 385
Extension to 4 Basic Channels
Final Structure

• Final structure for size-4 construction (W − channel always decoded

first)

• Final structure after reordering of nodes

x1 x1
u1 W y1 u1 W y1
x3 x2
u3 W y3 u2 W y2
x2 x3
u2 W y2 u3 W y3
x4 x4
u4 W y4 u4 W y4
V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 274 / 385
Extension to 8 Basic Channels
x1
u1 W y1
x2
u2 W y2
x3
u3 W y3
x4
u4 W y4
x5
u5 W y5
x6
u6 W y6
x7
u7 W y7
x8
u8 W y8

V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 275 / 385
Mathematical Description of Polar codes
• Polar codes are linear block codes related to Reed-Muller codes

• Generator matrices can be constructed recursively

" #
1 1
G2 =
0 1
 
1 1 1 1 " #
0 1 0 1 1 · G2 1 · G2
 
G4 =  = = G2 ⊙ G2
0 0 1 1 0 · G2 1 · G2
0 0 0 1
Gn = G2 ⊙ Gn/2

• Codeword length n is power of 2

• Kronecker product ⊙
V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 276 / 385
Effect of Polarization
Generalization of Results for W2 (see slide 272)

x1 (1)
u1 W1 y1
x2 (2)
u2 W1 y2
G2
(i)
• For original BEC channels W all bit-channels Wn are BECs as well
• Each combining step for 2 BECs with erasure probabilities ϵ1 and ϵ2
delivers 2 kinds of channels
• W − = u1 → (y) : Pe (W − ) = 1 − (1 − ϵ1 )(1 − ϵ2 ) = ϵ1 + ϵ2 − ϵ1 ϵ2

• W + = u2 → (y, u1 ) : Pe (W + ) = ϵ1 ϵ2

V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 277 / 385
Effect of Polarization x1
Results for W4 u1 W y1
x2
u2 W y2
x3
u3 W y3
x4
u4 W y4

• W4(1) = u1 → (y) : Pe (W4(1) ) = 2Pe (W − ) − Pe (W − )2

• W4(2) = u2 → (y, u1 ) : Pe (W4(2) ) = Pe (W − )2
• W4(3) = u3 → (y, u1 , u2 ) : Pe (W4(3) ) = 2Pe (W + ) − Pe (W + )2
• W4(4) = u4 → (y, u13 ) : Pe (W4(4) ) = Pe (W + )2
V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 278 / 385
Effect of Polarization
Generalization to Arbitrary Channel Numbers

• Channels with odd superscript have higher erasure rate than

preceding channels
 
(2i−2)
Wn(2i−1) : u2i−1 → y, u1
     
(2i−1) (2i)
Pe Wn(2i−1) = Pe Wn/2 + Pe Wn/2
   
(2i−1) (2i)
− Pe Wn/2 Pe Wn/2

• Channels with even superscript have lower erasure rate due to

diversity gain
 
(2i−1)
Wn(2i) : u2i → y, u1
     
(2i−1) (2i)
Pe Wn(2i) = Pe Wn/2 · Pe Wn/2
V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 279 / 385
Effect of Polarization
Numerical Results for BEC with Pe = 0.2

1
n = 22 = 4 n = 23 = 8
0.8
0.6
Pe

0.4
0.2
0
1 2 3 4 2 4 6 8
1
n = 24 = 16 n = 25 = 32
0.8
0.6
Pe

0.4
0.2
0
5 10 15 10 20 30
V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 280 / 385
Effect of Polarization
Numerical Results for BEC with Pe = 0.2
1
n = 26 = 64 n = 27 = 128
0.8
0.6
Pe

0.4
0.2
0
20 40 60 50 100
1 8 9
n = 2 = 256 n = 2 = 512
0.8
0.6
Pe

0.4
0.2
0
100 200 200 400
V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 281 / 385
Effect of Polarization
Error Probabilities for n = 220 ≈ 106 and BEC with different Pe
1
Pe = 0.1
Pe = 0.2
0.8 Pe = 0.3
Pe = 0.4
P e Wn →

= 0.5
0.6 Pe


Pe = 0.6
(i)

Pe = 0.7
0.4 = 0.8


Pe
Pe = 0.9

0.2

0
0 0.2 0.4 0.6 0.8 1
i/n →
V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 282 / 385
Effect of Polarization
Histogram of error probabilities for n = 220 ≈ 106 and BEC with Pe = 0.2

100
→

10−1
o
(i)
Pr Pe Wn

10−2

n

10−3

10−4
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
 
(i)
Pe Wn →
V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 283 / 385
Polarization Theorems
Theorem (Polarization, Arikan 2007)
(i)
The bit-channel capacities C(Wn ) polarize for any δ ∈ (0, 1) as the
construction size n grows, i.e.

(i) (i)
no. of channels Wn with C(Wn ) > 1 − δ
−−−→ C(W )
n n→∞
(i) (i)
no. of channels Wn with C(Wn ) < δ
−−−→ 1 − C(W )
n n→∞

holds.

Theorem (Rate of Polarization, Arikan, Telatar 2008)

√
Above theorems hold with δ ≈ 2− n .

V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 284 / 385
Encoding of Polar Codes of length n = 8
BEC with Pe = 0.2 → C = 0.8, code rate Rc = 86 = 0.75
! (i) "
I W8 ) rank

0.1678 8 frozen 0 1 1 1x1 W y1

0.8493 5 data 1 1 1 0x2 W y2

0.7576 6 data 0 0 0 0x3 W y3

0.9968 2 data 0 0 0 1x4 W y4

0.6514 7 frozen 0 0 0 0x5 W y5

0.9939 3 data 0 0 1 1x6 W y6

0.9832 4 data 1 0 0 0x7 W y7

1.0000 1 data 1 1 1 1x8 W y8

V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 285 / 385
Encoding of Polar Codes
Code word length n = 8, BEC with Pe = 0.5 → code rate Rc = 1/2
! (i) "
I W8 ) rank

0.0039 8 frozen 0 0 0 0x1 W y1

0.3164 5 frozen 0 0 0 1x2 W y2

0.1914 6 frozen 0 0 0 0x3 W y3

0.8789 2 data 0 0 0 1x4 W y4

0.1211 7 frozen 0 0 0 0x5 W y5

0.8086 3 data 0 0 1 1x6 W y6

0.6836 4 data 1 0 0 0x7 W y7

0.9961 1 data 1 1 1 1x8 W y8

V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 286 / 385
Decoding Approaches of Polar Codes
• Successive cancellation decoding (SCD)
• depth-first search method with complexity roughly N log N

• Belief propagation algorithms (message passing) based on graphs

• graph is not sparse as for LDPC codes

• Performance is still better than that of SCD

• List decoding
• Breadth-first search algorithm with limited branching and complexity
O(LN log N )
• First produce L candidate decisions and pick the most likely word
from the list

• Sphere-decoding
V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 287 / 385
Successive Cancellation Decoding of Polar Codes

• Successive cancellation decoding (SCD) is simplest algorithm

• Sufficient to prove that polar codes achieve capacity

• Not powerful enough to challenge LDPC and turbo codes for short to
moderate lengths

• For N → ∞, only ideal (error-free) and useless bit-channels exist

• Error-free channels allow detection of associated information bits

• Useless channels are frozen, i.e. frozen dummy bits known to

decoder have been inserted

• Even bit positions require knowledge of corresponding odd bit

positions

V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 288 / 385
Successive Cancellation Decoding of Polar Codes
Decoding of bit u1
a1 b1 x1
û1 W y1
a2 b2 x2
W y2
b3 x3
W y3
b4 x4
W y4
x5
W y5
x6
W y6
x7
W y7
x8
W y8

V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 289 / 385
Successive Cancellation Decoding of Polar Codes
Decoding of bit u1
p(y|u =0)
• Decoding rule based on LLR L(u1 | y) = log p(y|u1 =1)
1


u1 position is frozen

û1 = 0 L(u1 | y) > 0


1 L(u1 | y) ≤ 0

• LLR L(u1 | y) can be calculated recursively

L(u1 | y) = L(a1 ) ⊞ L(a2 )
= L(b1 ) ⊞ L(b3 ) ⊞ L(b2 ) ⊞ L(b4 )
= L(x1 ) ⊞ L(x5 ) ⊞ · · · ⊞ L(x4 ) ⊞ L(x8 )

(1)
• Associated bit-channel W8 is likely to be frozen
V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 290 / 385
Successive Cancellation Decoding of Polar Codes
Decoding of bit u2 given u1
a1 b1 x1
û1 W y1
a2 b2 x2
û2 W y2
b3 x3
W y3
b4 x4
W y4
x5
W y5
x6
W y6
x7
W y7
x8
W y8

V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 291 / 385
Successive Cancellation Decoding of Polar Codes
Decoding of bit u2

• Decoding u2 requires knowledge of u1 (to be detected before)

p(y,û |u =0)
• Decoding rule based on LLR L(u2 ) = log p(y,û1 |u2 =1)
1 2


u2 position is frozen

û2 = 0 L(u2 ) > 0


1 L(u2 ) ≤ 0

• LLR L(u2 ) can be calculated successively

L(u2 ) = (−1)û1 · L(a1 ) + L(a2 )
 
= (−1)û1 L(y1 | x1 ) ⊞ L(y5 | x5 ) ⊞ L(y3 | x3 ) ⊞ L(y7 | x7 )
 
+ L(y2 | x2 ) ⊞ L(y6 | x6 ) ⊞ L(y4 | x4 ) ⊞ L(y8 | x8 )
V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 292 / 385
Successive Cancellation Decoding of Polar Codes
Decoding of bit u3 given bits u1 and u2
â1 b1 x1
û1 W y1
â2 b2 x2
û2 W y2
a3 b3 x3
û3 W y3
a4 b4 x4
W y4
x5
W y5
x6
W y6
x7
W y7
x8
W y8

V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 293 / 385
Successive Cancellation Decoding of Polar Codes
Decoding of bit u3 given bits u1 and u2
• Decoding u3 requires knowledge of u1 and u2 (to be detected first)
• Decoding rule equivalent to rules for u1 and u2
• Intermediate steps
 
L(a3 ) = (−1)â1 · L(b1 ) = (−1)â1 · L(x1 ) ⊞ L(x5 )
 
L(a4 ) = (−1)â2 · L(b2 ) = (−1)â2 · L(x2 ) ⊞ L(x6 )

• Decoding u3 exploits diversity (parallel branches a3 ∥b3 and a4 ∥b4 )

L(u3 ) = L(a3 ) + L(b3 ) ⊞ L(a4 ) + L(b4 )
h   i
= (−1)â1 · L(x1 ) ⊞ L(x5 ) + L(x3 ) ⊞ L(x7 )
h   i
⊞ (−1)â2 · L(x2 ) ⊞ L(x6 ) + L(x4 ) ⊞ L(x8 )

V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 294 / 385
Successive Cancellation Decoding of Polar Codes
Decoding of bit u4 given bits u1 to u3
â1 b1 x1
û1 W y1
â2 b2 x2
û2 W y2
a3 b3 x3
û3 W y3
α4 a4 b4 x4
û4 W y4
x5
W y5
x6
W y6
x7
W y7
x8
W y8

V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 295 / 385
Successive Cancellation Decoding of Polar Codes
Decoding of bit u4 given bits u1 to u3

• Decoding u4 requires knowledge of u1 , u2 and u3 (to be detected

before)

• Intermediate steps
L(a3 ) = (−1)â1 · L(b1 )
L(a4 ) = (−1)â2 · L(b2 )
 
L(α4 ) = (−1)û3 · L(a3 ) + L(b3 )

• Decoding u4 exploits diversity due to parallel branches

L(u4 ) = L(α4 ) + L(a4 ) + L(b4 )

• With each step, less ⊞ and more + operations (diversity) occur

V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 296 / 385
Error Rate Performance of Polar Codes
Transmission over BEC and code lengths N = 213 and N = 216

V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 297 / 385
Error Rate Performance of Polar Codes
Transmission over AWGN and different code lengths N = 2n

V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 298 / 385
Error Rate Performance of Polar Codes
Transmission over AWGN and N = 212 and Rc = 0.5

V. Kühn | Error Control Coding | Modern Error Correcting Codes → Polar Codes 299 / 385