Channel Codes, Decoders and

Implementation Architecture

Saikat Majumder

Department of Electroncis and Telecommunicaiton

National Institute of Technology Raipur

Saikat Majumder (NIT Raipur) Channel Codes & Decoders Sept 11th, 2017 1 / 18
Outline

1 Introduction

2 Low Density Parity Check Codes

Saikat Majumder (NIT Raipur) Channel Codes & Decoders Sept 11th, 2017 2 / 18
Outline

FEC based
MDC
Multiple Soft RS decoder Hard RS decoder
Description based (Ch. 3) based (Ch. 4)
Coding
Pt. to pt. link LDPC-RS

Opportunistic n/w DSTBC-RSCC-RS

Application
of Iterative Acc. aided source-channel coding
Decoding MDSQ based MDC
(Ch. 5)
Source-channel decoding of MDC

MARC with NC
Network Network coding for
Coding MARC (Ch. 6)
MARC with NC & STC

Saikat Majumder (NIT Raipur) Channel Codes & Decoders Sept 11th, 2017 3 / 18
 Introduction

Outline

1 Introduction

2 Low Density Parity Check Codes

Saikat Majumder (NIT Raipur) Channel Codes & Decoders Sept 11th, 2017 4 / 18
 Introduction

Introduction

1 Channel codes improve the detection performance in digital

communication links.
2 Earliest application was in deep space communication.
3 Satellite communication systems and microwave radio links require
very simple channel codes due to their smaller propagation losses.
4 Digital mobile telephony and wireless data communications has
changed this situation dramatically.
5 Advanced channel codes has become essential, since they can
provide both improved detection performance and better
bandwidth efficiency.

Saikat Majumder (NIT Raipur) Channel Codes & Decoders Sept 11th, 2017 5 / 18
 Introduction Iterative Decoding

What is Iterative Decoding ?

1 Shannon in The Mathematical Theory of Communication [?] gave

fundamental limit of reliable communication.
2 Possible to transmit digital data with arbitrary high reliability,
over noise-corrupted channels, by encoding the message with
sufficient redundancy.
3 Reliable communication possible only when for information rate R
and channel capacity C(H),

R < C(H) (1)

4 Two questions faced by communication system designer [?]:

• How much redundancy is required?
• What is the kind of redundancy and how to get it ?

Saikat Majumder (NIT Raipur) Channel Codes & Decoders Sept 11th, 2017 6 / 18
 Introduction Iterative Decoding

Algebraic Coding

1 Shannon answered the first question by giving a limit on capacity.

2 The second question posed tries to investigate which coding
scheme would bring us close to the channel capacity R < C(H) in
a practical and efficient way.
3 Algebraic coding paradigm dominated the pre 90’s decade of
channel coding.
4 Algebraic coding theory is mainly concerned with linear (n, k, d)
block code over a q-ary field Fq .
5 The principal objective of algebraic coding theory is to maximize
the minimum distance dmin for a given code.
6 Can decode any error pattern of weight t = b(dmin − 1)/2c.

Saikat Majumder (NIT Raipur) Channel Codes & Decoders Sept 11th, 2017 7 / 18
 Introduction Iterative Decoding

Performance Comparison of Selected Codes

Saikat Majumder (NIT Raipur) Channel Codes & Decoders Sept 11th, 2017 8 / 18
 Introduction Iterative Decoding

Turbo Revolution

1 Algebraic codes have not proved to be the way towards channel

capacity, even for BSC and AWGN channels.
2 Berrou, Glavieux, and Thitimajshima [?] introduced “turbo
codes” to achieve near Shannon limit performance.
3 Random coding gave wonders, not the elegance of algebra !
4 Use of soft decisions, not only at the input, but also in the internal
working of decoder.
5 “A SISO decoder is a kind of SNR amplifier” - Hagenauer.
6 Key to achieving good iterative decoding performance is removal
of “intrinsic information” from the output of APP decoder,
resulting in “extrinsic” APP.
7 Extrinsic information represents additional knowledge learned
after decoding.

Saikat Majumder (NIT Raipur) Channel Codes & Decoders Sept 11th, 2017 9 / 18
 Introduction Iterative Decoding

Turbo Encoder

u v
(0)

(1)
Encoder 1 v
g2(D)/g1(D)
(1) (2)
Puncturing v ,v
P Mechanism

u' Encoder 2 v
(2)

g2(D)/g1(D)

1 Turbo encoder consists of two RSCC is parallel concatenated

configuration.
2 RSCC as component encoder
h i
GR (D) = 1 gg12 (D)
(D)
(2)

Saikat Majumder (NIT Raipur) Channel Codes & Decoders Sept 11th, 2017 10 / 18
 Introduction Iterative Decoding

Turbo Decoder

1 Constituent decoders are maximum a posteriori (MAP) decoders.

2 Received signal vector r consists of three components: systematic
(0) (1)
bits rl , output from first encoder rl , and output from second
(2)
encoder rl .
3 For received signal r, each constituent decoder computes log a
posteriori probability (LAPP) ratio L(ul )
 
P (ul = +1|r)
L(ul ) = log (3)
P (ul = −1|r)

4 Output of MAP decoder 1 can be written as

(0)
L(ul ) = Lc rl + L(1) (1)
a (ul ) + Le (ul ) (4)

Saikat Majumder (NIT Raipur) Channel Codes & Decoders Sept 11th, 2017 11 / 18
 Introduction Iterative Decoding

Turbo Decoder

(0) (1) (0) (2)

Lcrl Lcrl Lcrl Lcrl

P (2)
L (ul)
(1)
Le (ul) (2)
La (ul) P
-1
Decoder 1 Decoder 2
(1)
+ +- P Decision
(1) L (ul) - Lcrl(0)
La (ul)
-1
-
P (2)
++ (2)
L (ul) - Lcrl(0)
Le (ul)

5 Hard decision is made on APP: ul = +1 if

P (ul = +1|r) > P (ul = −1|r), and it decides ul = −1 otherwise.

Saikat Majumder (NIT Raipur) Channel Codes & Decoders Sept 11th, 2017 12 / 18
 Introduction Iterative Decoding

Iterative Decoding of LDPC Code

1 LDPC parity check matrix is sparse

 
1 0 ... 0 1
0 0 . . . 1 0
H = . . . (5)
 
.
 .. .. . . ..


0 1 ... 0 0

Saikat Majumder (NIT Raipur) Channel Codes & Decoders Sept 11th, 2017 13 / 18
 Introduction Iterative Decoding

Turbo-Like Decoding Schemes

1 Iterative decoding techniques also apply to numerous other

algorithm found in digital communication.
2 Concatenated schemes can be classified into two major categories
• Parallel concatenated schemes
• Serial concatenated schemes
3 Two stage serial concatenation

u1 c1 u2 c2
Encoder I P Encoder II

e a
a L (u2) L (c1) e
L (c2) P-1 L (u1)
Decoder II Decoder I
a P e
L (u2) L (c1)

Saikat Majumder (NIT Raipur) Channel Codes & Decoders Sept 11th, 2017 14 / 18
 Introduction Iterative Decoding

Different serial concatenated systems with iterative

decoding

Saikat Majumder (NIT Raipur) Channel Codes & Decoders Sept 11th, 2017 15 / 18
 Introduction Iterative Decoding

Research Potential

Research potential for design and improvement of decoding schemes by

exploiting iteration principle
1 Source-channel coding
2 FEC based multiple description codes
3 Network-channel coding
4 MIMO systems

Saikat Majumder (NIT Raipur) Channel Codes & Decoders Sept 11th, 2017 16 / 18
 Low Density Parity Check Codes

Outline

1 Introduction

2 Low Density Parity Check Codes

Saikat Majumder (NIT Raipur) Channel Codes & Decoders Sept 11th, 2017 17 / 18
 Low Density Parity Check Codes

Low Density Parity Check Codes

1 LDPC codes are linear block codes.

2 Set of all codewords, x ∈ C, spans the null space of a parity check
matrix H, i.e.
HxT = 0, ∀x ∈ C. (6)
3 H for LDPC code is sparse binary matrix.

Saikat Majumder (NIT Raipur) Channel Codes & Decoders Sept 11th, 2017 18 / 18