Error Control coding

Information Theory & Coding
Unit V :
Measure of Information, Source Encoding, Error Free Communication over a Noisy Channel capacity of a
discrete and Continuous Memoryless channel Error Correcting codes: Hamming sphere, Hamming
distance and Hamming bound, relation between minimum distance and error detecting and correcting
capability, Linear block codes, encoding & syndrome decoding; Cyclic codes, encoder and decoders for
systematic cycle codes; convolution codes, code tree & Trellis diagram, Viterbi and sequential decoding,
burst error correction, Turbo codes.
4/2/2018 1
NEC 602 by Dr Naim R Kidwai, Professor, F/o Engineering,
JETGI, (JIT Jahangirabad)

Error Correcting Coding
4/2/2018 2
In Digital Communication, two important parameters in design are SNR Eb/No and
bandwidth B and objective is to achieve acceptable reliability (error rate) of
transmission.
For a given Eb/No only coding (adding systematic redundancy) can ensure acceptable
error rate of transmission.
Error Control can be done by
• FEC: forward error correction (Error detection and correction)
• ARQ: Automatic request for retransmission (Error detection)
Error control coding is systematic addition redundancy for error detection and correction.

Hamming sphere, Hamming distance, Hamming weight,
Hamming bound, and error correcting capability
4/2/2018 3
Let a pair of code vectors are x and y that have same number of elements
• Hamming distance d(x,y) between such pair of code vectors is defined as number of
locations in which their respective locations.
• Hamming weight w(x) of a code vector x is defined as the number of non zero
elements of the code vector
• Minimum distance dmin of linear code block is smallest hamming distance between
any pair of code vectors in the code.
• For the (n,k) linear block code, to be able to correct upto t bits of error (all error
patterns of t bits or less) if and only if d(xi, xj) ≤ 2t+1 for all xi and xj
• Hamming bound (n,k) block code can correct upto t errors provided Hamming bound
is satisfied. For equality code is said to be perfect
0
2
t
n k
i
n
i


 
  
 


Linear Block Codes
4/2/2018 4
(n,k) linear block has n code bits of which consists of k message bits and n-k parity bits.
b0, b1, ------------------, bn-k-1, m0, m1, ------------------, mk-1,
N-k Parity bits K Message bits
,0 ,1 1 , 1 1
0,1, , 1
code where are parity bits and are message bits
, 1, , 1
parity bits (all arithmatic in coding are modulo 2
i
i i i
i k n
i i o i i k k
b i n k
x b m
m i n k n k n
b p m p m p m
 
 
     
 
       
        
,
0 1 1 0 1 1
k
k
operations)
1 if depends on
where
0 otherwise
Let message [ , , ] and parity [ , , ]
code [ ] [ ] [ I ]
Let us define Generator Matrix =[ I ]
i j
i j
k k
b m
p
m m m m b b b b m p
x b m m p m m p
G p
 

 

        
  

Linear Block Codes
4/2/2018 5
n-k
n-k n-k n-k
n-k
then code vector
Let us define parity cheker Matrix =[I ]
then = I I I 0=
I
Again received vector = + where e is error vector added due to noise
Synd
T
T
T T T T T
x m G
H p
p
HG p p p GH
y x e

 
         
 rome = + [ 0]T T T T
s y H x e H eH GH  
• Syndrome depends on error pattern and not on codeword sent
• All error pattern that differs by a codeword have same syndrome
• A syndrome is sum of those columns of parity check matrix corresponding to error location
• (n,k) block code can correct upto t errors provided Hamming bound is satisfied.
• A code (n,k) is said to be perfect, if equality holds in Hamming bound

Cyclic codes
4/2/2018 6
Cyclic codes are subclass of linear block codes and are easy to encode. A cyclic code exhibits
• Linearity property: Sum of two codewords is also a codeword.
• Cyclic property: Cyclic shift of any codeword is also a codeword.
If (x0, x1,--- xn-1) is codeword of (n,k) linear block code and is cyclic then
(xn-1, x0,--- xn-2)
(xn-2, xn-1,--- xn-3)
.
.
(x1, x2,----- x0) are all valid codewords

Cyclic codes
4/2/2018 7
Codeword polynomial for code (x0, x1,-- ,xn-1) is codeword is written as
x(D)= x0+ x1D+x2D+--------+ xn-1Dn-1
where D is a real variable, s.t Dn =1
The condition Dn =1 ensures
• Codeword polynomial is of the order n-1 for a multiplication with D
• Multiplication by D to the polynomial makes circular right shift
• This leads to multiplication modulo Dn -1
D x(D) modulo (Dn-1) = xn-1+ x0D+x1D2+--------+ xn-2Dn-1
D2 x(D) modulo (Dn-1) = xn-2+ xn-1D+x0D2+--------+ xn-2Dn-1
Di x(D) modulo (Dn-1) is codeword polynomial for a cyclic shift i.

Cyclic codes
4/2/2018 8
Generator Polynomial g(D)
g(D) is a factor of (Dn+1) having minimum degree n-k
X(D)= a(D) g(D) modulo (Dn-1) where a(D) is polynomial
Encoding Procedure:
• Multiply message polynomial m(D) by Dn-k
• Divide Dn-k m(D) by g(D) and obtain remainder b(D)
• Add b(D) Dn-k m(D) giving codeword
Parity Check polynomial h(D)
h(D) g(D) modulo (Dn-1)=0 [like HGT=0]
or h(D) g(D) =Dn+1

Cyclic codes
4/2/2018 9
(7,4) Hamming Code Ex. 1+Dn= (1+D)(1+D2+D3)(1+D+D3)
Let g(D)= 1+D+D3
then h(D)= (1+D)(1+D2+D3)= 1+D+D2+D3+D3+D4=1+D+D2+D4
G matrix can be constructed using
g(D)= 1+ D+0D2+ D3+0D4+0D5+0D6
Dg(D)= 0+ D+ D2+0D3+ D4+0D5+0D6
D2g(D)=0+0D+ D2+ D3+0D4+ D5+0D6
D3g(D)=0+0D+0D2+ D3+ D4+0D5+ D6
1 1 0 1 0 0 0
0 1 1 0 1 0 0
0 0 1 1 0 1 0
0 0 0 1 1 0 1
G
 
 
 
 
 
 
1 1 0 1 0 0 0
0 1 1 0 1 0 0
1 1 1 0 0 1 0
1 0 1 0 0 0 1
G
 
 
 
 
 
 
G can be made systematic by using
row operations make 4x4 identity
matrix in last columns
R3→R3+R1 and R4→R1+R2 +R4

Encoder for Cyclic codes:
Ex. (7,4) Hamming Code Encoder
4/2/2018 10
Let g(D)= 1+D+D3
Then encoder can be easily made using Flip
Flops as shown in figure
It requires 3 FF, input/ output to each FF is
marked. mod 2 addition is done for terms.
For message 1001
Parity bits generated are 011
Code : 0111001
FFFFFF
Gate
D0=1 D D2 D3
message bits
Parity
bits
Encoded
bits
Shift input Register
output
0 0 0
1 1 1 1 0
2 0 0 1 1
3 0 1 1 1
4 1 0 1 1

Syndrome calculation for Cyclic codes:
Ex. (7,4) Hamming Code Syndrome
4/2/2018 11
Let g(D)= 1+D+D3
Then parity checker (syndrome) can be made
using Flip Flops as shown in figure
It requires 3 FF, input/ output to each FF is
marked. mod 2 addition is done for terms.
For message 1001, Parity is 011
Transmitted Code: 0111001
If received vector : 0111001
Syndrome 000 No error
If received vector : 0110001
Syndrome 110 error vector 0001000
output
0 0 0
1 1 1 0 0
2 0 0 1 0
3 0 0 0 1
4 1 0 1 0
5 1 1 0 1
6 1 0 0 0
7 0 0 0 0
FFFFFF
Gate
D0=1 D D2 D3
Syndrome for no error
output
0 0 0
1 1 1 0 0
2 0 0 1 0
3 0 0 0 1
4 0 1 1 0
5 1 1 1 1
6 1 0 0 1
7 0 1 1 0
Syndrome for error vector
0001000

Important cyclic codes
4/2/2018 12
• Cyclic Redundancy check codes (CRC):
▪ (18,6) CRC-12 g(D)=1+D+D2+D3+D11+D12
▪ (24,8) CRC-16 g(D)=1+D2+D15+D16
▪ (24,8) CRC-CCITT g(D)=1+D5+D12+D16
• Golay codes: Three error correcting perfect cyclic code
▪ (23,12) g(D)=1+D+D5+D6+D7+D9+D11
• Bose- Chaudhuri Hocquenqhem (BCH):
▪ Each BCH code is t error correcting code
▪ (15,7) 2 error corrrection g(D)=1+D4+D6+D7+D8

convolution codes
4/2/2018 13
• Block codes are produced on block by block basis, thus
requires a buffer.
• For serial inputs, convolutional codes are preferred
• Convolution coding operates on serial incoming bits
• A binary convolutional code with rate 1/n, measured in
bit per symbol, produces a coded sequence of n(L+M)
bits for a message of L bits and M stage sift register.
• Thus Code rate r=L/ n(L+M) bits/ symbol
• For L>>M, r 1/n
• Constraint length: number of shifts over which a single
message bit can influence encoder output. For M stage
shift register, constraint length is M+1
FFFF
Mod 2
adder
Convolutional coder
Constraint length 3, Rate =1/2
Impulse response
top adder output: (g0
(1), g1
(1), g1
(1)) =(1,1,1)
bottom adder output: (g0
(2), g1
(2), g1
(2))=(1,0,1)

convolution codes: Time domain approach
4/2/2018 14
Let generator sequences of convolutional coder are
• Input top adder output: (g0
(1), g1
(1), g1
(1)) =(1,1,1)
• Input bottom adder output: (g0
(2), g1
(2), g1
(2))=(1,0,1)
And let message (m0,m1,m2,m3,m4)=(10011)
1 1
0
2 2
0
top output sequence 0,1,2,
bottom output sequence 0,1,2,
M
i l i l
l
M
i l i l
l
x g m i
x g m i




    
    


By calculating above convolution we get pair of outputs for message sequence as xi=(11,
10, 11, 11, 01, 01, 11)

Convolution codes: Transform domain
approach
4/2/2018 15
Let generator sequences of convolutional coder are
• Input top adder output: g(1)(D)=1+D+D2
• Input bottom adder output: g(2)(D)=1+D2
• And let message is 10011 then m(D)= 1+D3+D4
• Then x1= g(1)(D) m(D) mod (D7-1)=(1+D+D2)(1+D3+D4)
x1= 1+D3+D4+D+D4+D5+D2+D5+D6
=(1111001)
• Then x2= g(2)(D) m(D) mod (D7-1)=(1+D2)(1+D3+D4)
x2= 1+D3+D4+D2+D5+D6
=(1011111)
Combining the two outputs we get pair of outputs for message sequence as xi=(11, 10, 11,
11, 01, 01, 11)

Convolutional coder: State diagram
4/2/2018 16
Structural properties of a convolutional coder is given by one
of the three diagrams: Code tree, trellis and state diagram
With two FF’s, 4 possible states are Let a (00), b (10), c (01)
and d (11)
State table
FFFF
top output: g(1)=(1,1,1)
bottom output g(2)=(1,0,1)
state input Next state output
a 0 a 00
a 1 b 11
b 0 c 10
b 1 d 01
c 0 a 11
c 1 b 00
d 0 c 01
d 1 d 10
d
b c
a
0/00
1/10
1/11
0/10
1/00
0/11
1/01 0/01
State diagram

Convolutional coder: Code tree
4/2/2018 17
• Each branch of tree represent an input symbol, with
corresponding pair of output on the branch.
• Input ‘0’ specifies upper branch, while ‘1’ represents
lower branch
• repetitive after first three branches
• Represents all possible sequence, thus expands
b
c
d
a
b
c
d
a
b
c
d
a
b
c
d
a
b
a
d
c
b
a
d
c
a
b
c
d
a
b
a
00
0
1
0
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
1
0
1
0
1
0
1
1
0
1
00
11
10
01
11
00
01
10
00
11
10
01
11
00
01
10
01
10
11
00
10
01
00
11
00
11
10
01
11
FFFF

Convolutional coder: Trellis diagram
4/2/2018 18
• trellis is representation which do not expand
• It uses state of the coder to represent all possible sequences
• It is compact: number of nodes at any level is 2k-1, k→
constraint length
FFFF
a
b
c
d
00 00 00 00
11 11 11 11
10
01
10
01
10
01
11
00
11
00
10
01
10
01
00
10
01
11
00
10
01
11
00
10
01
11
00
10
01
11
00
10
01
11
00
10
01
11
Encode bit 11 10 11 11 01 01 11
Message bit 1 0 0 1 1 0 0

Viterbi and Sequential decoding
4/2/2018 19
Decoding of convolutional codes can be categorized into two groups
• Sequential decoding –Fano coding
• Maximum likelihood decoding –Viterbi coding
a
b
c
d
00 00 00 00
11 11 11 11
10
01
10
01
10
01
11
00
11
00
10
01
10
01
00
10
01
11
00
10
01
11
00
10
01
11
00
10
01
11
00
10
01
11
00
10
01
11
Encode bit 11 10 11 11 01 01 11

Sequential decoding - Fano Algorithm
4/2/2018 20
• First proposed by Wozencraft and improved by Fano.
• Fano coding operates on code tree (may be trellis) and It allows forward or backward
movement
• At each stage of decoding Fano coding retains only three information
• Current path
• Immediate predecessor path
• One of its successor path
• Based on the information Fano algorithm can move from its current state to either its
selected successor path or its predecessor path.
• It starts with the root node and tally with the output it finds on the way. If an output
does not matches, it retraces back to the previous ambiguous state.

Sequential decoding – Fano Algorithm
4/2/2018 21
a
b
c
d
00 00 00 00
11 11 11 11
10
01
10
01
10
01
11
00
11
00
10
01
10
01
00
10
01
11
00
10
01
11
00
10
01
11
00
10
01
11
00
10
01
11
00
10
01
11
Encode bit 11 10 11 11 01 01 11
Received bit 11 10 11 10 01 01 11

Convolution decoding - Viterbi Algorithm
4/2/2018 22
• Developed by Andrew J. Viterbi who founded Qualcomm.
• Viterbi decoder examines entire received sequence of given length.
• Works on trellis diagram created level by level.
• Algorithm works by computing a ‘metric’ for each path.
• Metric is hamming distance between received bits and coded sequence of that path
• At any level, for each node, path with lower metric is retained (survivor path).
• If paths entering a node have equal metric, anyone may be retained.
• Small list of survivors are guaranteed to contain maximum likelihood choice
• If a condition arises that there is no path for the corresponding sequence then the
Viterbi decoding helps to detect the best path based on the subsequent sequence.

4/2/2018 23
Encode bit 11 10 11 11 01 01 11
Received bit 11 10 11 10 01 01 11
a
b
c
d
00
11
2
0
-
-
Received bit 11 Metric
a
b
c
d
00 00
11 11
10
01
11
00
10
01
0
2
3
3
Received bit 11 10 11 Metric
a
b
c
d
00 00
11 11
10
01
3
3
0
2
Received bit 11 10 Metric
Level 1 Level 2 Level 3
1
1
2
3
Received 11 10 11 10 Metric
bit
a
b
c
d
00 00
11 11
10
01
11
00
10
01
00
11
10
10
Level 4
2
2
3
1
Received 11 10 11 10 01 Metric
bit
a
b
c
d
00 00
11 11
10
01
11
00
10
01
00
11
10
10
00
11
10
01
Level 5

4/2/2018 24
11
00
10
01
3
3
1
2
Received 11 10 11 10 01 01 Metric
bit
a
b
c
d
00 00
11 11
10
01
11
00
10
01
00
11
10
10
00
11
10
01
00
11
01
01
1
3
3
3
Received 11 10 11 10 01 01 11 Metric
bit
a
b
c
d
00 00
11 11
10
01
11
00
10
01
00
11
10
10
00
11
10
01
00
11
01
01
Received bit 11 10 11 11 01 01 11 Metric
Level 7
Level 7

Burst error correction
4/2/2018 25
Burst errors are errors that occur in many consecutive bits rather than occurring in bits
independently of each other. Burst errors are localized in a short interval. methods to
correct random errors are inefficient to correct burst errors.
Examples:
• errors in CD, due to physical damage such as scratch on a disc
• Errors due to stroke of lightning in case of wireless channels.
Error vector E={010000110} is a burst of length 7. It can be said as cyclic burst of length 5
{11001}
Every (n,k) cyclic code with generator polynomial of degree r (=n-k) can detect all bursts
of length ≤r. However cyclic codes can detect most of the bursts of the length >r

Few points on Turbo codes
4/2/2018 26
Turbo codes are a class of high-performance FEC codes developed around 1990–91,
which closely approach the channel capacity, and are use to achieve reliable information
transfer in the presence of data-corrupting noise.
Applications:
• 3G/4G mobile communication ; ex. HSPA, EV-DO and LTE.
• satellite communication systems.
• NASA’s Mars Reconnaissance Orbiter use turbo codes,
• block /convolutional turbo coding are used in IEEE 802.16 (WiMAX)
Turbo codes are nowadays competing with LDPC codes, which provide similar
performance.

Few points on Turbo codes
4/2/2018 27
The classic turbo encoder have two RSC
(Recursive systematic coder) and a bit
interleaver.
Encoder generates m bits of message X, n/2
bits of parity Y1 by RSC 1 and n/2 bits of
parity Y2 by RSC 2 thus generating m+n bits,
i.e. code rate is m/(m+n).
Permutation of payload data is carried by
interleaver.
Decoder of turbo coding is similar to that of
encoder
RSC
RSC
Interleaver
X
Y1 Y2
Input
Turbo encoder
Decoder 2Decoder 1X
Y1
Y2
Turbo decoder
Interleaver
Y

Error Control coding

Recommended

More Related Content

What's hot (20)

Similar to Error Control coding (20)

More from Dr Naim R Kidwai (20)

Recently uploaded (20)

Error Control coding