Course information

CHANNEL CODING
Monday, 15:05-17:30, Room 403B4
Dr. Ho Van Khuong
Office: Telecom. Dept., HCMUT
Tel.: 012 289 05178
Email: khuongho2001@[Link]
 Course outline
The course is intended to provide solid
knowledge on encoding, decoding, error
probability analysis, and applications of
channel codes such as linear block
codes, convolutional codes, Turbo
codes, LDPC codes, etc. Additionally,
some new codes such as RA codes,
Fountain codes, Raptor codes, etc. are
also presented.
2
Course Information – 2008 – Dr. Ho Van Khuong
 Requirement & References
„ Prerequisite: No
„ Grading:
• Presentation (20%)
• Discussion (20%)
• Report/Assignment (30%)
• Term paper (30%)
„ References:
„ M. Puser, Introduction to error-correcting codes, Artech
House, 1995.
„ R.H.M Razagoza, The art of error-correcting coding, John
Wiley & Sons, 2002.
„ J.G. Proakis, Digital communications, 3rd edition, McGraw-
Hill, 1995.
„ Papers on RA, Fountain codes.

3
Course Information – 2008 – Dr. Ho Van Khuong
 Contents
„ Chapter 1: Introduction
„ Error correcting coding: Basic concepts
„ Linear block codes
„ Encoding and decoding of linear block
codes
„ Weight distribution and error performance
„ General structure of a hard-decision
decoder of linear codes

4
Course Information – 2008 – Dr. Ho Van Khuong
 Contents
„ Chapter 2: Binary convolutional
codes
„ Basic structure
„ Connections with block codes
„ Weight enumeration and performance
bounds
„ Decoding: Viterbi algorithm with Hamming
metrics
„ Punctured convolutional codes
5
Course Information – 2008 – Dr. Ho Van Khuong
 Contents
„ Chapter 3: Modifying and
combining codes
„ Modifying codes
„ Combining codes

6
Course Information – 2008 – Dr. Ho Van Khuong
 Contents
„ Chapter 4: Iteratively decodable
codes
„ Iterative decoding
„ Product codes
„ Parallel concatenation: turbo codes
„ Serial concatenation
„ Low-density parity-check codes

7
Course Information – 2008 – Dr. Ho Van Khuong
 Contents
„ Chapter 5: Advanced channel
codes
„ Repeat-Accumulate codes
„ LT codes
„ Online codes
„ Raptor codes
„ Tornado codes
„ Fountain codes
8
Course Information – 2008 – Dr. Ho Van Khuong
 Contents
„ Presentation and discussion
„ Term paper
„ Due date: December 12, 2008
„ Don’t accept late submission
„ Send your term paper to my email box

9
Course Information – 2008 – Dr. Ho Van Khuong
Schedule
„ Weeks 1-5: Lectures (C1 and C2)
„ Weeks 6-10: Presentation and
discussion
„ Weeks 11-15: Term paper

10
Additional information
„ Email: channelcoding2008@[Link]
„ PW: class2008

11
Noisy Channel Coding
Theorem
„ Claude Shannon, “A mathematical theory of
communication,” Bell Systems Technical Journal,
1948.
„ Every channel has associated with it a capacity C.
„ Measured in bits per channel use (modulated symbol).
„ The channel capacity is an upper bound on
information rate r.
„ There exists a code of rate r < C that achieves reliable
communications.
„ Reliable means an arbitrarily small error probability.

12
Computing Channel Capacity
„ The capacity is the mutual information
between the channel’s input X and output
Y maximized over all possible input
distributions:
k p
C = max I ( X ; Y )
p( x )

R
= max Sz z pa x, yf log
p( x, y) UV
T
p( x )
2
p( x ) p( y)
dxdy
W
13
 Capacity of AWGN
with Unconstrained Input
„ Consider an AWGN channel with 1-dimensional input:
„ y = x + n

where n is Gaussian with variance No/2

x is a signal with average energy (variance) Es
„ The capacity in this channel is:
k p 1 FG
C = max I( X; Y ) = log2
2Es IJ 1 FG
+ 1 = log2
2rEb IJ
+1
p( x ) 2 H No K 2 H No K
where Eb is the energy per (information) bit.
„ This capacity is achieved by a Gaussian input x.
„ This is not a practical modulation.
14
 Capacity of AWGN with
BPSK Constrained Input
„ If we only consider antipodal (BPSK)
modulation, then
X = ± Es

„ and the capacity is:

la
C = m ax I X ; Y
p( x )
fq maximized when

= Ia X;Y f
two signals are equally likely

p ( x ): p = 1 / 2

= H (Y ) − H ( N )

z
∞

= af
p y log 2 p ( y ) dy −
1
2
b
log 2 π eN o g
−∞ 15
 Capacity of AWGN with 1-D
Signaling
It is theoretically ound
1.0 impossible to operate PSK Capacity B
B
in this region.

nd
Bou
city
Spectral Efficiency

a
Cap
Code Rate r

n
nno

It is theoretically
Sha

0.5 possible to operate

in this region.

-2 -1 0 1 2 3 4 5 6 7 8 9 10

Eb/No in dB 16
 Finding Good Codes
• Ingredients of Shannon’s proof:
• Random code
• Large block length
• Optimal decoding

• Problem
Randomness + large block length + optimal decoding =

COMPLEXITY!
17
 State-of-the-Art
„ Solution
„ Long, structured, “pseudorandom” codes

„ Practical, near-optimal decoding algorithms

„ Examples
„ Turbo codes (1993)

„ Low-density parity-check (LDPC) codes (1960, 1999)

„ State-of-the-art
„ Turbo codes and LDPC codes have brought Shannon

limits to within reach on a wide range of channels.

18
 Power Efficiency of Standard
Binary Channel Codes
d
1.0 K Capacity Boun
BPS Uncoded
BPSK
nd
Bou
city

Iridium
Spectral Efficiency

1998
a
Cap
Code Rate r

n
nno

Pioneer
Turbo Code 1968-72
Sha

0.5 1993
LDPC Code IS-95
2001 1991 Odenwalder
Chung, Forney, Voyager Convolutional
Richardson, Urbanke 1977 Codes 1976

Galileo:BVD
Galileo:LGA 1992
1996
Mariner
1969
arbitrarily low
BER: Pb = 10 −5
-2 -1 0 1 2 3 4 5 6 7 8 9 10
19
Eb/No in dB
 Evolution of Coding
Technology

LDPC
codes from Trellis and Turbo Coding,
Schlegel and Perez, IEEE Press, 2004 20