EE-355 Digital Communication

Systems
[Ch – 06]
CHANNEL CODING: Part - I

Instructor: Engr. Furqan Haider

DEE, NUST College of E & ME Digital Communication Systems

 Block Diagram of DCS

DEE, NUST College of E & ME Digital Communication Systems

 Channel Coding
• Channel coding refers to the class of signal
transformation designed to improve communication
performance by enabling the transmitted signals to
better withstand the effects of various channel
impairments.

• Channel coding can be partitioned into two areas:

– waveform (or signal design) coding
– structured sequences (or structured redundancy.)

DEE, NUST College of E & ME Digital Communication Systems

 Channel Coding
• Waveform coding deals with transforming waveforms
into “better waveforms,” to make the detection
process less subject to errors.
• Structured sequence deals with transforming data
sequences into “better sequences,” having
structured redundancy.

DEE, NUST College of E & ME Digital Communication Systems

 Orthogonal Signals
• The aim of the encoding is to improve the
distance properties

DEE, NUST College of E & ME Digital Communication Systems

DEE, NUST College of E & ME Digital Communication Systems
 Antipodal Signals

DEE, NUST College of E & ME Digital Communication Systems

 Orthogonal Codes

DEE, NUST College of E & ME Digital Communication Systems

DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems
 Biorthogonal Codes

DEE, NUST College of E & ME Digital Communication Systems

 Types of error control using structured
redundancy

• Error detection and retransmission  ARQ

• Forward Error Correction  FEC

DEE, NUST College of E & ME Digital Communication Systems

 Automatic Repeat Request
• Automatic Retransmission Query
• Stop and Wait ARQ
– Half Duplex

DEE, NUST College of E & ME Digital Communication Systems

 • Continuous ARQ with pull-back
(Full Duplex)

• Continuous ARQ with selective repeat

(Full Duplex)

DEE, NUST College of E & ME Digital Communication Systems

 Forward Error Correction
• Require simplex link.
• 1st objective  to detect the error
• 2nd objective  and if possible, then correct
that error.

DEE, NUST College of E & ME Digital Communication Systems

 Structured Sequences
• Linear Block Codes (CH – 6)
• Convolutional Codes (CH – 7)
• Turbo Codes (CH – 8)

DEE, NUST College of E & ME Digital Communication Systems

 Code Rate and Redundancy
• Source data is segmented into blocks of k bits
• Encoder transforms k into n bits. C(n,k)
• (n-k) extra or redundant bits (check bits)
• ((n-k)/k ) is called redundancy of the code
• ( k/n ) is the code rate

DEE, NUST College of E & ME Digital Communication Systems

 Parity Check Codes

• Single parity check code

• Code rate = k/(k+1)
• Even or odd parity

• Example: even-parity check for k=3 bit data.

DEE, NUST College of E & ME Digital Communication Systems

 Parity Check codes
• Rectangular Codes
k MN

n  M  1 N  1

DEE, NUST College of E & ME Digital Communication Systems

 Hamming Distance
• Number of bit positions in which two code
words differ
• If two codewords are d distance apart, d single
bit errors are required to convert one
codeword into other.
• w(A)
• d(A,B)=w(A+B)

DEE, NUST College of E & ME Digital Communication Systems

 • To detect d bit error
– Minimum Hamming Distance = d+1
• To correct t bit error
– Minimum Hamming Distance = 2t+1

DEE, NUST College of E & ME Digital Communication Systems

 Error Correction
Codewords

001 011

101 111

010
000

100 110

DEE, NUST College of E & ME Digital Communication Systems

 • Codewords with d=5; can correct 2 errors
0000000000, 0000011111, 1111100000,
1111111111
• If 0000000111 arrives the receiver decides
0000011111 which is correct one
• If triple error changes 0000000000 to
0000000111 the error will not be corrected
properly (this one goes undetected)

DEE, NUST College of E & ME Digital Communication Systems

 Linear block codes
• C(n,k)
• 2^k k-tuples
• 2^n n-tuples
• Assign 2^k k tuples (message) to 2^k n tuples(
codeword)
• Look up table

DEE, NUST College of E & ME Digital Communication Systems

 Vector spaces
• Set of all binary n-tuples is called vector space,
Vn.
• Addition and Multiplication for binary n-tuples

DEE, NUST College of E & ME Digital Communication Systems

 Vector subspaces
• Subset S of vector space Vn
• All zeros vector is included in S
• Sum of two code vectors is also in S
• Vi and Vj are two code vectors, code is linear if
Vi+Vj is also a code vector

DEE, NUST College of E & ME Digital Communication Systems

 16 4-tuples and subspace
e.g. C(4,2)

Subspace i) all zero vector

ii) holds closure w.r.t addition
DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems
 A (6,3) linear block code
2^3=8 message vectors or codewords that
form subspace and 2^6=64 6-tuples in
vector space

• Unique mapping do
not exists.

DEE, NUST College of E & ME Digital Communication Systems

 Generator matrix
• For large values Look Up table requires too
much memory, i.e (127,92) code requires 2^92
code vectors
• Solution is to generate code words using
generator matrix
• Generator matrix can generate all the code
words using a fewer number of linearly
independent vectors

DEE, NUST College of E & ME Digital Communication Systems

DEE, NUST College of E & ME Digital Communication Systems
 C(6,3) example

m = [1 1 0]
(1 x n) = (1 x k) x (k x n)

U = [1 0 1 1 1 0]
DEE, NUST College of E & ME Digital Communication Systems
 Advantage of G – Matrix:

• Code is totally defined by the generator

matrix
• Store only k rows of G instead of total 2^k
vectors

DEE, NUST College of E & ME Digital Communication Systems

DEE, NUST College of E & ME Digital Communication Systems
 Systematic linear block codes

• (n,k) mapping such that part of sequence

generated coincides with the message

Ik = (k x k) identity martix

DEE, NUST College of E & ME Digital Communication Systems

DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems
 Parity Check Matrix

• Used for decoding received vectors

• For each G there exists a parity check matrix
H, such that rows of G are orthogonal to rows
of H.

H = (n-k) x n matrix

DEE, NUST College of E & ME Digital Communication Systems

DEE, NUST College of E & ME Digital Communication Systems
 • Where, order of 0 is  k x (n-k)

• H is used to test whether a received vector is a valid

member of the codeword set.

DEE, NUST College of E & ME Digital Communication Systems

 Syndrome Testing

DEE, NUST College of E & ME Digital Communication Systems

DEE, NUST College of E & ME Digital Communication Systems
 Error correction (standard array)

• No. of rows = 2^(n-k) cosets.

• No. of columns = 2^k

DEE, NUST College of E & ME Digital Communication Systems

DEE, NUST College of E & ME Digital Communication Systems
 Error correction decoding

DEE, NUST College of E & ME Digital Communication Systems

DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems
 Reading Assignment
• Article 6.6.3
• Article 6.6.4

DEE, NUST College of E & ME Digital Communication Systems

 Channel models
• Channel modeling approaches
– Waveform level channel model
– Discrete Channel model
• Motivation for replacing waveform level
model by discrete channel model is the speed
of simulation

DEE, NUST College of E & ME Digital Communication Systems

 Data source Encoder

Modulation and Waveform

transmitter Channel

Discrete channel
Receiver
model

Decoder

DEE, NUST College of E & ME Digital Communication Systems

 Discrete memory less channel
• Discrete input and output (i,j)
• A set of conditional probabilities P(j|i)
• Output depends only on corresponding input,
i.e channel noise effects independently
• U=u1,u2…uN; Z=z1,z2…zN

DEE, NUST College of E & ME Digital Communication Systems

 Binary Symmetric Channel

• Input and output are binary alphabets 0 and 1

• The conditional probabilities are symmetric

1-p
1 1
p
Modulator Demodulator pp
(1)
|0 p
(0|1
)
input output
p 
1pp
(1)
|1 p
(0|0
)
0 1-p 0

DEE, NUST College of E & ME Digital Communication Systems

 • Transition probabilities

DEE, NUST College of E & ME Digital Communication Systems

 Probability of error for channel coding

DEE, NUST College of E & ME Digital Communication Systems

DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems
 Probability of message error for a code that can correct t or fewer errors

p is the probability that a channel symbol is received in error

When the code can correct 1 bit error in block of 36 bits

DEE, NUST College of E & ME Digital Communication Systems

 Why use error correction coding
• Error performance versus bandwidth

DEE, NUST College of E & ME Digital Communication Systems

 Why use error correction coding
• power versus bandwidth

DEE, NUST College of E & ME Digital Communication Systems

 Coding gain
For a given bit error probability coding gain is defined as the reduction in Eb/No that
can be achieved by the use of coding

DEE, NUST College of E & ME Digital Communication Systems

 Why use error correction coding
• datarate versus bandwidth

DEE, NUST College of E & ME Digital Communication Systems

 Why use error correction coding
• capacity versus bandwidth

DEE, NUST College of E & ME Digital Communication Systems

 Block diagram of the DCS

Information
Modulator
source Conv. encoder
m  (m1 , m2 ,..., mi ,...) U  G(m)


Channel
Input sequence

Information
Demodulator
sink Conv. decoder
ˆ  (mˆ 1 , mˆ 2 ,..., mˆ i ,...)
m
Z  ( Z1 , Z 2 , Z 3 ,..., Z i ,...)
 
received sequence

DEE, NUST College of E & ME Digital Communication Systems

DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems
 State diagram
• A finite-state machine only encounters a finite
number of states.
• State of a machine: the smallest amount of
information that, together with a current
input to the machine, can predict the output
of the machine.
• In a Convolutional encoder, the state is
represented by the content of the memory.
• Hence, there are states.
2 K 1
DEE, NUST College of E & ME Digital Communication Systems
 State diagram – cont’d
• A state diagram is a way to represent the
encoder.
• A state diagram contains all the states and all
possible transitions between them.
• Only two transitions initiating from a state.
• Only two transitions ending up in a state.

DEE, NUST College of E & ME Digital Communication Systems

 State diagram – cont’d
Current input Next output
0/00 Output state state
Input (Branch word)
S0 S0 0 S0 00
1/11 0/11 S2
00
00 1 11
1/00 S1 0 S0 11
S2 S1
10 01 01 1 S2 00
0/10 0 S1 10
S2
1/01 S3 0/01 10 1 S3 01
11
S3 0 S1 01
1/10 11 1 S3 10
DEE, NUST College of E & ME Digital Communication Systems
 Trellis – cont’d
• Trellis diagram is an extension of the state diagram
that shows the passage of time.
– Example of a section of trellis for the rate ½ code
State
S 0  00 0/00
1/11
S2  10 0/11
1/00

S1  01 1/01
0/10

0/01
S 3  11 1/10
ti ti 1 Time

DEE, NUST College of E & ME Digital Communication Systems

 Trellis –cont’d
• A trellis diagram for the example code Tail bits
Input bits
1 0 1 0 0
Output bits
11 10 00 10 11
0/00 0/00 0/00 0/00 0/00
1/11 1/11 1/11 1/11 1/11
0/11 0/11 0/11 0/11 0/11
1/00 1/00 1/00 1/00 1/00
0/10 0/10 0/10 0/10 0/10
1/01 1/01 1/01 1/01 1/01
0/01 0/01 0/01 0/01 0/01

t1 t2 t3 t4 t5 t6

DEE, NUST College of E & ME Digital Communication Systems

 Path metric used in Viterbi Decoding
Hamming Distance
• Number of elements in which two code words
differ.
• U=100101101
• V=011110100
• D(U,V)=6

DEE, NUST College of E & ME Digital Communication Systems

 ML Decoding Rule

Choose the path with minimum Hamming distance

from the received sequence.

DEE, NUST College of E & ME Digital Communication Systems

DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems
DEE, NUST College of E & ME Digital Communication Systems