Linear Block codes

 Linear block codes are a class of parity check codes

that can be characterized by (n,k) notation.
 Consider (n,k) linear block code in which k bits of the n
code bits are always identical to the message sequence
to be transmitted.
 A code is said to be linear if any two code words in the
code can be added in modulo-2 arithmetic to produce a
third code word in the code.

00  0 0 1  1 1 0  1 11  0
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 1
 The n-k bits are computed from the message bits,
these n-k bits are referred to parity bits.
 Block codes in which the message bits are
transmitted in unaltered form are called systematic
code.
 Let m0, m1, ………mk-1 constitute a block of k
arbitrary message bits. Thus we have 2k distinct
message blocks.
 sequence of message bits be applied to a linear
block encoder, producing an n-bit code word whose
elements are denoted by c0, c1, …..,cn-1 .
 Let b0, b1, ……. Bn-k-1 denote the (n-k) parity bits in
the code word.
 code word is divided into two parts, one is message
bits and other by the parity bits.

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 2

 b0,b1,….bn-k-1 m0,m1,….mk-1

Parity bits Message bits

The (n-k) left most bits of a code word are identical to

the parity bit, and the k right-most bit of the code word
are identical to the message bits.

Define the 1-by-k message vector m, the 1-by-(n-k)

Parity vector b and the 1-by-n code vector c as follows

m  m0, m1 .............., mk 1 
b  b0, b1 .............., bn  k 1 
c  c0, c1 .............., c n 1  3
Defining the Parity bits in the compact matrix form

b  mP
Where P is the k-by(n-k) coefficient matrix

 p 00 p 01 .......... .p 0, n - k - 1 
 
 p 10 p 11 .......... p 1, n - k -1 
Pk 
   
 
 p k  1 , 0 p k - 1,1 .......... p k -1, n - k -1 

Code vector c may be expressed as partitioned row

vector in terms of the vectors m and b

c  b  m (or) c  mP  I k 
c  mG 4
Generator Matrix

Define the k-by-n generator matrix G  P  I k 

Where Ik is the k-by-k identity matrix

1 0 ......... 0
0 1 .......... 0 
Ik  
   
 
0 0 ........ 1 

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 5

 A ( 6,3) Linear Block Code example

The are 23 = 8 message vectors and therefore eight code

word vectors.

The are 2n = 26 = sixty four 6 tuples

The encoding equation for this code is given by
c0 = m0
c1 = m1
c2 = m2
c3= m0  m1
c4= m1  m2
c5 = m0  m2

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 6

Message vector Code word
000 000000
100 1 0 0 101
010 010110
110 110011
001 001 0 1 1
101 101 1 1 0
011 011 10 1
111 111000

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 7

The generator matrix for a (7,4) block code is given below.
Find all code vectors of this code.

1 0 0 0 1 0 1
0 1 0 0 1 1 1 
G  
0 0 1 0 1 1 0
 
0 0 0 1 01 1 

c0 = m0
c1 = m1
c2 = m2
c3 = m3
c4 = m0  m1  m2
c5 = m1  m2  m3
c6 = m0  m1  m3

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 8

The code vector for the message 1111

1 0 0 0 1 0 1
0 1 0 0 1 1 1 
c  1111  
0 0 1 0 1 1 0
 
0 0 0 1 01 1 

C= ( 1 1 1 1 1 1 1)

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 9

Message vector Code word
0000 0000000
0001 0001011
0010 0010110
0011 0011101
0100 0100111
0101 0101100
0110 0110001
0111 01 1 1 0 1 0
1000 1000101
1001 1001110
1010 1010011
1011 1011000
1100 1100010
1101 1101001
1110 1110100

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 10

Consider a pair of code vectors ci and cj corresponding to a
pair of message vectors mi and mj respectively.
We may express the sum of ci and cj as

c i  c j  mi G  mi G
 mi  mi G
The modulo-2 sum of mi and mj represents a new message
vector. Correspondingly, the modulo-2 sum of ci and cj
represent a new code vector.
Another way of expressing the relationship between the
message bits and parity-check bits of a linear block code
using Parity Check matrix H.
Let H denote an (n-k)- by-n matrix, defined as


H  I n -k  P T
 11
Where PT is an (n-k)-by k matrix, representing the
transpose of the coefficient matrix P, and In-k is the (n-
k)-by-(n-k) identity matrix.

Multiplication of partitioned matrices

 PT 
T

HG  I n  k  P T
  
 Ik 
P P T T

In modulo-2 arithmetic, we have PT + PT = 0

Where 0 denotes an (n-k)-by-k null matrix.

HG  0 T

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 12

 Code vector c  mG
Post multiplying both sides by HT cH  m GH
T T

0
The matrix H is called the parity-check matrix of the code
Block diagram representations of the code vector

Message vector Generator Code vector

m matrix G c

Block diagram representations of the parity-check

Code vector Parity check Null vector

c matrix H 0

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 13

 Hamming Codes
Hamming code are defined as the (n,k) linear block codes
that have the following parameters

Block length n=2m-1

Number of message bits k=2m-m-1

Number of parity bits n-k
Where m ≥3. these are the so called Hamming codes

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 14

 Minimum distance dmin :The minimum distance of linear
block code is the smallest Hamming distance between the
Valid code vectors
Hamming distance: Hamming distance between the two
code vectors is equal to the number of elements in which
they differ.
Number of errors that can be detected is given by
d min  e  1
3  e 1 e  2
Hence is the most two errors can be detected
Number of errors that can be corrected is given by

d min  2t  1
t 1
3  2t  1
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 15
The parity check matrix of a particular (7,4) linear block
Code is given by,

1 1 1 0 1 0 0 
H   1 1 0 1 0 1 0 
 1 0 1 1 0 0 1 
(i)Find the generator matrix G
(ii) List the all the code vectors
(iii) What is the minimum distance between the code vectors
(iv) How many errors can be detected ? How many errors
can be corrected

H P T
 I n -k 
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 16
The transpose matrix PT

1 1 1 0 
P T
  1 1 0 1 
 1 0 1 1 

The coefficient matrix P from PT

1 1 1 
1 1 0 
P  
1 0 1 
 
0 1 1 

Define the k-by-n generator matrix G  P  I k 

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 17
 1 1 1 1 0 0 0 
1 1 0 0 1 0 0 
G  
1 0 1 0 0 1 0 
 
0 1 1 0 0 0 1 

P Ik
The encoding equation for this code is
c7 = m0  m1  m2
c6= m0  m1  m3
c5 = m0  m2  m3
c4 = m0
c3 = m1
c2 = m2
c1 = m3

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 18

Message vector Code word
0000 0000000
0001 0110001
0010 1010010
0011 1100011
0100 1100100
0101 1010101
0110 0110110
0111 0 0 0 01 1 1
1000 1 11 1 0 0 0
1001 1001001
1010 0101010
1011 0011011
1100 0011100
1101 0101101
1110 1001110
1111 1111111
19
Number of errors that can be detected is given by

d min  e  1
3  e 1
e  2
Hence is the most two errors can be detected

Number of errors that can be corrected is given by

d min  2t  1
t 1
3  2t  1
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 20
Syndrome Decoding
The generator matrix G is used in the encoding operation
at the transmitter. The parity-check matrix H is used in
the decoding operation at the receiver.
The received vector ‘r’ as the sum of the original code
vector ‘c’ and a error vector ‘e’.

r ce
The ith element of e equals 0 if the corresponding element
of r is the same as that of c. On the other hand the ith
element of e equals 1 if the corresponding element of r is
different from that of c.

1 if an error has occurred in the ith location

ei  
0 otherwise
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 21
The algorithm used to perform the task of decoding the
code vector c from the received vector r called the
syndrome.
Syndrome is formally defined as s  rH T

Syndrome has the important properties

Syndrome depends only on the error pattern, and not on
the transmitted code work

s  (c  e) H  cH  eH
T T T

s  eH T

All error pattern that differ by a code word have the

same Syndrome.

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 22

**Consider a (7,4) linear block whose parity check matrix
is given by,

1 1 1 0 1 0 0 
H   1 1 0 1 0 1 0 
 1 0 1 1 0 0 1 

(i) Find the generator matrix G

(ii) How many errors this code can detect
(iii) How many errors can this code corrected
(iv) Draw circuit for encoder and syndrome computation

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 23

The transpose matrix PT

1 1 1 0 
P T
  1 1 0 1 
 1 0 1 1 

The coefficient matrix P from PT

1 1 1  1 1 1 1 0 0 0 
1 (i)
1 0  1 1 0 0 1 0 0 
P   G  
1 0 1  1 0 1 0 0 1 0 
   
0 1 1  0 1 1 0 0 0 1 

Define the k-by-n generator matrix G  P  I k 

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 24
Message vector Code word
0000 0000000
0001 0110001
0010 1010010
0011 1100011
0100 1100100
0101 1010101
0110 0110110
0111 0 0 0 01 1 1
1000 1 11 1 0 0 0
1001 1001001
1010 0101010
1011 0011011
1100 0011100
1101 0101101
1110 1001110
1111 1111111
25
 d min  3
(ii)

Number of errors that can be detected is given by

d min  e  1 3  e 1

e  2
(iii)
Number of errors that can be corrected is given by
d min  2t  1
t 1
3  2t  1
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 26
(iv) 1 1 1 
1 1 0 
b  m 0 m 1 m 2 m 3  b0  m 0  m 1  m 2
1 0 1 
 
0 1 1 

b1  m 0  m 1  m 3 b2  m 0  m 2  m 3

Message bits
Input m3 m2 m1 m0
sequence

Modulo-2
   Code bits
adders
parity bits
b2 b1 b0

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 27

 1 1 1 
1 1 0 
 
1 0 1 
 
H T
 0 1 1 
1 0 0 
 
0 1 0 
0 0 1 
 

Syndrome is given by s  eH T

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 28

 1 1 1 
1 1 0 
 
1 0 1  s  1 1 1 
 
s  1 0 0 0 0 0 0  0 1 1 
1 0 0 
 
0 1 0 
0 0 1 
 

Error Vectors with single bit errors Syndrome

1 0 0 0 0 0 0 1 1 1
0 1 0 0 0 0 0 1 1 0
0 0 1 0 0 0 0 1 0 1
0 0 0 1 0 0 0 0 1 1
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 1 0 0 1 29
**The parity check matrix of a linear block code is given
by
1 0 1 1 0 0 
H   0 1 1 0 1 0 
 1 1 0 0 0 1 

Determine the generator matrix 

H  I n -k  P T

The transpose matrix PT

1 0 1 
P T
  0 1 1 

 1 1 0 

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 30

The coefficient matrix P from PT

1 0 1 
P   0 1 1 

 1 1 0 
Define the k-by-n generator matrix G = [P  I k ]

1 0 1 1 0 0 
G   0 1 1 0 1 0 
 1 1 0 0 0 1 

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 31

**The generator matrix for a (6,3) block code is given
below. Find all code vectors of this code.

1 0 0 0 1 1
 
G  0 1 0 1 0 1
 
0 0 1 1 1 0

The message block size k for this code is 3, and the length
of the code vector n is 6.

There are eight possible message blocks:

( 0,0,0) (0,0,1) (0,1,0) (0,1,1)(1,0,0)(1,0,1)

(1,1,0)(1,1,1)

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 32

The code vector for the message 111

1 0 0 0 1 1 
c  mG  1 1 1   0 1 0 1 0 1
 
 0 0 1 1 1 0 

c  1 1 1 0 0 0 
The remaining code vector
Message vector Code word
000 000000
001 001110
010 010101
011 011011
100 100011
101 101101
110 110110 33
**The generator matrix for (7,4) linear block code is given
below
1 0 0 0 1 1 1
0 1 0 0 0 1 1 
G  
0 0 1 0 1 1 0
 
0 0 0 1 1 0 1 

(i)Find the parity check matrix H of this code

(ii) Show that these two matrices satisfy the condition
C HT=0

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 34

 (i) the parity check matrix H of this code

1 0 0 1 0 1 1
H   0 1 0 1 1 1 0 
 0 0 1 1 1 0 1 
(ii) CHT= mGHT
1 1 1 
0 0 0 0 
1 0 0 0 1 1 1 1 1  0
0 0 1 1 
 0 0 
GH T
 
1 0 0 1 1 0   
0   0 0 0 
0 1 0 1 1 0 1 0 1   
  0 0 0 
0 0 01 10 1  1 0 0 
 
0 1 0 
0 0 1 
∴ CH T
= 0 
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 35
**A (7,4) linear block code of which generator matrix is
given by
1 0 0 0 1 0 1 
0 1 0 0 1 1 1 
G   
0 0 1 0 1 1 0 
 
0 0 0 1 0 1 1 
(i) Find the code vectors of this code
(ii) Find the parity check matrix of this code
(iii) Find the minimum weight of this code
(iv) If the received code word is 0001110, find the
transmitted code word
1 0 1 
b 0 = m 0 ⊕ m 1 ⊕ m 2 b = mP 1 1 1 
P  
b1 = m 1 ⊕ m 2 ⊕ m 3 1 1 0 
 
b2 = m 0 ⊕m 1 ⊕m 3 0 1 1 
36
Message vector Code word
0000 0000000
0001 0001011
0010 0010110
0011 0011101
0100 0100111
0101 0101100
0110 0110001
0111 01 1 1 0 1 0
1000 1 0 0 0 1 01
1001 1001110
1010 1010011
1011 1011000
1100 1 1 0 0 010
1101 1 1 0 1 0 01
1110 1110100
1111 1111111
37
The transpose matrix PT

1 1 1 0 
P T
  0 1 1 1 

 1 1 0 1 

Parity check matrix

1 0 0 1 1 1 0 
H   0 1 0 0 1 1 1 
 0 0 1 1 1 0 1 

d min = 3

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 38

 T 1 0 0 
Syndrome is given by s = rH 0 
 1 0 
0 0 1 
 
H T
 1 0 1 
1 0 0  1 
0  1 1
 1 0   
0  1 1 0 
0 1 0 
   1 1 
s  rH T
 0 0 0 1 1 1 0   1 0 1 
1 1 1 
 
1 1 0 
0 1 1 
 
s = [1 0 0 ]

Error occur in 1st bit position there fore the transmitted

code is 1001110
39
For a (6,3) code, the generator matrix G is given by

1 0 0 1 0 1 
G   0 1 0 0 1 1 

 0 0 1 1 1 0 

(i) Realize an encoder for this code.

(ii) Verify that this code is a single error-correcting
code.
(ii) If the received codeword is 100011, find the
syndrome
1 0 1 
G  P  I k    0 1 1
P 

 1 1 0 

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 40

 1 0 1 
[ p 0, p 1 , p 2 ]  m 0 , m 1 , m 2  0 1 1 
 p0  m0  m 2
 1 1 0 
p1  m 1  m 2 p 2  m 0  m1
(ii)
Message bits
Input m2 m1 m0
sequence

Modulo-2
  
adders
parity bits
p2 p1 p0

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 41

Message vector Code word
000 000000
001 001110
010 0 10011
011 011101
100 100101
101 101011
110 110110
111 111000

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 42

(ii) It can be proved that the minimum distance for the
(6,3) code is given by dmin =3

d min  2t  1
t 1
3  2t  1
Thus at the most one error can be corrected

(ii) To obtain the syndrome, s  rH T

let us obtain the transpose matrix HT

1 0 1 
P T
  0 1 1 

 1 1 0 
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 43
 1 0 1 | 1 0 0 

H  I n -k  P T
 H   0 1 1 | 0 1 0 
 1 1 0 | 0 0 1 

1 0 1  1 0 1 
0 0 1 
 1 1   1
1 1 0  1 1 0 
H T
   s  1 0 0 0 1 1  
1 0 0  1 0 0 
0 1 0  0 1 0 
   
 0 0 1   0 0 1 

s  1 1 0 

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 44

A (7,4) linear block code of which generator matrix is
given by
1 0 0 0 1 0 1 
0 1 0 0 1 1 1 
G   
0 0 1 0 1 1 0 
 
 0 0 0 1 0 1 1 

(i) Find code vector for any six messages

(ii)Write the parity check matrix of this code

1 0 1 
b  mP 1 1 1 
P  
1 1 0 
 
0 1 1 

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 45

b0  m 0  m 1  m 2 b1  m 1  m 2  m 3
b2  m 0  m1  m 3
Message Code word
vector
0 0 00 0000000
100 0 1000101
1 0 0 1 1 1 0 
H   0 1 0 0 1 1 1 
0100 0100111
0010 0010110
0001 0001011  0 0 1 1 1 0 1 
0101 0101100

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 46

For a systematic linear block code, the three parity
check bits, c4 , c5 , and c6 are given

c4  m1  m 2  m 3
c5  m1  m 2
c6  m1  m 3
(i) Construct generator matrix
(ii) Construct code generated by this matrix
(iii) Determine error correcting capability

(iv) Decode the received words 101100 and 000110

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 47

 1 1 1 
P   1 1 0 
 1 0 1 

1 1 1 1 0 0 
G   1 1 0 0 1 0 
 1 0 1 0 0 1 

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 48

Message vector Code word
000 000000
001 001101
010 010110
011 011011
100 100111
101 101010
110 110001
111 1 1 11 0 0

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 49

Number of errors that can be detected is given by

d min  e  1
3  e 1 e  2
Hence is the most two errors can be detected
Number of errors that can be corrected is given by

d min  2t  1
t 1
3  2t  1

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 50

Error Vectors with single bit errors Syndrome
1 0 0 0 0 0 0 1 1 1
0 1 0 0 0 0 0 1 1 0
0 0 1 0 0 0 0 1 0 1
0 0 0 1 0 0 0 0 1 1
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 1 0 0 1
1 1 1 
1 1 0 
 
1 0 1 
s  1 0 1 1 0 0   s  1 1 0 
1 0 0 
0 1 0 
 
 0 0 1 
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 51
 1 1 1 
1 1 0 
 
1 0 1 
s  0 0 0 1 1 0  
s  1 1 0 
 1 0 0 
0 1 0 
 
 0 0 1 
Correct code can be obtained c  re
c  1 0 1 1 0 0   0 1 0 0 0 0   1 1 1 1 0 0 

c  0 0 0 1 1 0   0 1 0 0 0 0   0 1 0 1 1 0 

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 52

Consider a systematic block code whose parity check
equation are

p1 = m 1 + m 2 + m 4
p 2 = m1 + m 3 + m 4
p3 = m1 + m 2 + m 3
p4 = m2 + m3 + m4
Where mi are message digits and pi are check digits
(a) Find the generator matrix and parity check matrix
for this code
(b) How many errors can the code correct
(c) Is the vector 10101010 a codeword
(d) Is the vector 01011100 a codeword
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 53
(a)
1 0 0 0 1 1 1 0
0 1 0 0 1 0 1 1
G =
0 0 1 0 0 1 1 1
0 0 0 1 1 1 0 1

1 0 0 0 1 1 0 1
0 1 0 0 1 0 1 1
H =
0 0 1 0 1 1 1 0
0 0 0 1 0 1 1 1

d min = 4

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 54

(b)
d min -1
t ≤ = 1
2

(c) s = rH T s = 0011

It is not a codeword

(d) s = rH T s = 0000
Yes it is a codeword

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 55

Consider the (5,1) repetition code. Evaluate the
syndrome S for the following error pattern

G  1 1 1 1 1 

(a) All five possible single error pattern

(b) All ten possible double error pattern

 1 0 0 0 1 
 0 1 0 0 1 
H   
 0 0 1 0 1 
 
 0 0 0 1 1 

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 56

 1 0 0 0 
0 1 0 0 
 
H T
 0 0 1 0 
  s  e.H T

0 0 0 1 
 1 1 1 1 

Single error pattern

57
Double error pattern

58
Consider the (7,4) hamming code has the following
generator matrix

Show that HGT =0

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 59

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 60
61
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 62
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 63
 CYCLIC CODES
 Cyclic codes form a subclass of linear block
codes.
 1 Linearity property: The sum of any two
code words in the code is also a code word
 2 Cyclic property: Any cyclic shift of a code
word in the code is also a code word.
 Property1 restates that a cyclic code is a
linear block code.

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 64

 Property2 restates in mathematical terms, let
the n-tuple ( c0, c1, . . . cn-1 ) denote a
code word of an (n,k) linear block code.

The code is a cyclic code if the n-tuples

( cn-1, c0, . . . cn-2 )
( cn-2, cn-1, . . . cn-3 )
. . .

( c1, c2, . . . cn-1, c0 )

are all code words in the code

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 65

 Code Word Polynomial
 To develop the algebraic properties of cyclic
codes, we use the elements c0, c1, . . . cn-1
of a code word to define the code polynomial
2 n 1
c( X ) = c0 + c1 X + c 2 X + . . . . . . . + c n-1 X
where X is an indeterminate
 Some important conclusions from the code
polynomial
 For binary codes, the coefficients X, X2 . .
are 1’s and 0’s
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 66
 Each power of X in the polynomial c(X)
represents a one bit cyclic shift in time.
 Single shift can be obtained by multiplying
c(X) by X
n 1
X c( X )  c n 1  c0 X  c1 X  . . . . . . .  c n -2 X
2

 In order to have two cyclic shifts we must

multiplying c(X) by X2

X 2 c ( X )  cn - 2  cn 1 X  . . . . . . .  c n -3 X n 1

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 67

 Generator Polynomial
 The polynomial Xn + 1 and its factors play a major
role in the generation of cyclic codes.
 Let g(X) be a polynomial of degree n-k that is a
factor of Xn + 1.
 The generator polynomial g(X) may expressed as
n  k 1
g( X )  1   i
g X
i 1
i
 X n k

where the coefficient gi is equal to 0 or 1.

 The polynomial g(X) has two terms with coefficient
1 separated by n-k-1
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 68
Generator of Non –systematic code words
It can be obtained by multiplication of message polynomial
with the generator polynomial

c ( X )  m( X ) g ( X )
m(X) is message signal a polynomial degree ≤ k.
g(X) is generator polynomial degree n- k.

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 69

Generator of systematic code words
There are three steps involved in the encoding process for a
systematic (n,k) cyclic code.

1 Multiply the message polynomial m(X) by Xn-k

2 Divide Xn-k m(X) by the generator polynomial g(X).
Obtaining the remainder b(X).

X n  k m( X ) b( X )
 a( X ) 
g( X ) g( X )
3. Add b(X) to Xn-k m(X), obtaining the code polynomial
c(X).

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 70

The generator polynomial for a(7,4) cyclic Hamming code is
given by g(X)=1+X+X3 determine all the systematic and
non-systematic code vectors. Determine the generator
matrix, Parity chcek matirx

This is (7,4) cyclic hamming code. The message vectors are

going to be 4 bit long. Therefore 24 =16 message words
Let us consider any message code word

m( X )  (m0 m1 m 2 m 3 )  (1 0 1 0)
Message polynomial is given by

m( X )  m0  m1 X  m2 X  m3 X
2 3

Substituting the values of m0 m1 m2 m3

m( X )  1  X 2
71
The non-systematic cyclic code is given by

c( X )  m( X ).g ( X )
c( X )  (1  X )(1  X  X )
2 3

c( X )  1  X  X  X  X  X 3 2 3 5

c( X )  1  X  X  0 X  0 X  X  0 X
2 3 4 5 6

The degree of the code word polynomial n-1 is 6

c( X )   111 0 0 1 0 

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 72

16 code words nonsystematic of the code

73
The systematic cyclic code

Multiply m(X) by Xn-k

nk
X m( X )  X (1  X ) 3 2

 X3  X 5

We divide by Xn-k m(X) by the generator polynomial

nk
X m( X ) X X 3 5

g( X ) 1 X  X 3
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 74
 X2
3 5 3
X + X +1 X + X
5 3 2
X +X +X
_________________
2
X
2
remainder polynomial b(X) = X

the code polynomial c(X) obtain Add b(X) to Xn-k m(X),

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 75

 c(X)  X n -k
m( X )  b(X)

= X3 + X 5 ⊕ X 2
2 3 5
= X +X + X

The code word vector is given by c( X )   0 0 11 0 1 0 

001 1010

Parity bits Message bits

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 76

0000 0000000
0001 1010001
0010 1110010
0011 0100011
0100 0110100
0101 1100101
0110 1000110
0111 0010111
1000 1101000
1001 0111001
1010 0011010
1011 1001011
1100 1011100
1101 0001101
1110 0101110
1111 1111111
77
We multiply both the sides of g(X) by Xi
where i=(k-1) . . . 1,0 there fore i=3,2,1,0

g(X)  1  X  X 3

X g(X)  X  X  X 2 4

X g(X)  X  X  X
2 2 3 5

X g(X)  X  X  X
3 3 4 6

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 78

 1 1 0 1 0 0 0
0 1 1 0 1 0 0 
G 
0 0 1 1 0 1 0 
 
0 0 0 1 1 0 1
We can put it into a systematic form by adding the first
row to the third row, and adding the sum of the first two
rows to the fourth row.

1 1 0 1 0 0 0
0 1 1 0 1 0 0 
G 
1 1 1 0 0 1 0 
 
1 0 1 0 0 0 1 

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 79

Parity-check Polynomial
An (n,k) cyclic code is uniquely specified by another
polynomial of degree k, which is called the parity-check
polynomial defined by
k 1
h(X)  1   hi X  X i k

i 1

Where the coefficients hi are 0 or 1. the parity check

polynomial h(X) has a form similar to the generator
polynomial in that there are two terms with coefficient 1,
but separated by k-1 terms
The generator polynomial g(X) is equivalent to the
generator matrix G. the parity-check polynomial, denoted
by h(X), is equivalent representation of the parity-check
matrix H
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 80
 find the matrix relation H GT =0 for linear block code
corresponding to the relations
h(X)g(X) mod (Xn + 1)=0
property 3
the generator polynomial g(X) and the parity-check
polynomial h(X) are factor of the polynomial 1 + Xn
h(X)g(X)=1+Xn
h(X) is polynomial of degree(k) and it is factor of 1 + Xn
the h(X) is the Parity check polynomial of an (n,k) cyclic
code
Find the parity check matrix H
First take the reciprocal of h(X),namely X4 h(X-1),
X5 h(X-1 ), and X6 h(X-1 )
Using the coefficients of these three polynomials as the
elements of the rows of the 3-by-7 parity check matrix 81
 2 3
h(X) = (1 + X)(1 + X + X )

2 4
= 1+ X + X + X
4 2 3 4
X h(X) = 1 + X + X + X
5 -1 3 4 5
X h(X ) = X + X + X + X
6 -1 2 4 5 6
X h(X ) = X + X + X + X

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 82

 1 0 1 1 1 0 0

H  0 1 0 1 1 1 0 
0 0 1 0 1 1 1
To put it into a systematic form, we add the third row to
the first row to obtain

1 0 0 1 0 1 1

H  0 1 0 1 1 1 0 
0 0 1 0 1 1 1

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 83

Encoder for cyclic codes
These three steps can be implemented by means of the
encoder shown in figure consisting of a linear feedback
shift register with (n-k) stages.

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 84

The flip-flops are used to construct a shift register.
operation of all these flip-flops is governed by an
external clock, which is not shown in figure.
The flip-flop contents will get shifted in the direction
of the arrow corresponding to each clock pulse.

The encoder includes a second set of logic elements, is

adders which compute the modulo-2 sums of their
respective inputs. Finally the multipliers multiply their
respective inputs by the associated coefficients.

If the coefficient gi =1, the multiplier is just a direct

connection. If on the other hand, the coefficient gi =0
the multiplier is no connection.

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 85

Let us take generator polynomial g(X)= ( 1 + X + X3 )

Shift Input Register value

0 0 0
1 1LSB 1 1 0
2 1 1 0 1
3 0 1 0 0
4 1 1 0 0

The code word is therefore 1001011

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 86

 Convolution Codes
A convolution encoder operates on the incoming message
sequence continuously in a serial manner.
An L-bit message sequence produces a coded output
sequence of length n(L+M) bits. The code rate is given by

L L  M
r= b/s
n( L + M )
1
r bits/symbol
n
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 87
The constraint length of a convolution code expressed in
terms of message bits, is defined as the number of shifts
over which a single message bit can influence the encoder
output.
In an encoder with an M-stage shift register, the
memory of the encoder equals M message bits and K=M+1
shifts are required for a message bit to enter the shift
register and finally come out.
Hence the constraint length of the encoder is K.

Generator polynomial defined as the unit-delay transform

of the impulse response to be specific let the generator
sequence g0(i) , g1(i) , g2(i) ,. . . . gM(i) denote the
impulse response of the ith path, where the coefficients
g0(i) , g1(i) , g2(i) ,. . . . gM(i) equal to 0 or 1
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 88
Generator polynomial of ith path defined
g(i) (D)= g0(i) + g1(i) D+ g2(i) D2 + g3(i) D3 + . . .+ gM(i) DM
where D denotes the unit-delay variable.

Example

Figure shows a convolutions encoder with n=2 and K=3

code rate of this encoder is 1/2.
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 89
Consider the convolution encoder of figure which has two
paths numbered 1 and 2.

The impulse response of path 1 is (1,1,1). Hence , the

corresponding generator polynomial is given by

g (1) ( D )  1  D  D 2

The impulse response of path 2 is (1 0 1). Hence ,

the corresponding generator polynomial is given by

g ( 2) ( D)  1  D 2
For the message sequence (10011) we have the polynomial
representation
m ( D)  1  D 3  D 4

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 90

As with Fourier transformation, convolution in the time
domain is transformed into multiplication in the D domain.
Hence, the output polynomial of path 1 is given by

c (1) ( D)  g (1) ( D)m( D)

c (1) ( D)  1  D  D 2  D 3  D 6
the output sequence of path 1 is ( 1111001).
The output polynomial of path 2 in figure is

c ( 2 ) ( D )  g ( 2 ) ( D ) m( D )
c ( 2) ( D)  1  D 2  D 3  D 4  D 5  D 6
the output sequence of path 2 is ( 1011111).
Finally multiplexing the two output sequences of path 1
and 2 we get encoded sequence
c=(11,10,11,11,01,01,11)
91
state diagraM
 State diagram of the encoder shown in
figure.
 The nodes of the figure represent the
four possible states of the encoder,
with each node having two incoming
branches and two outgoing branches.
 A transition from one state to another
in response to input 0 is represented
by a solid branch, where as a transition
in response to input 1 is represented
by a dashed branch.
 The binary label on each branch
represents the encoder’s output as it
moves from one state to another.

92
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication
 Code Tree,

93
 trellis diagraM rePresentation
 In drawing the trellis diagram, we use he same convention
that we introduce with the state diagram.
 A solid line denotes the output generated by an input bit
zero, and a dashed line denotes the output generated by an
input bit one.
 The nodes of the trellis characterize the encoder states the
first row nodes correspond to the state a=00 the second
and subsequent rows correspond to the states b=10, c=01
and d=11


Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 94

 Expansion of state diagram in time.

a= 00
b= 10
c= 01
d= 11

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 95

A rate 1/3 convolution code is described by g1 =[ 100]
g2 =[101], g3 = [ 111]. Draw the encoder, code tree, code
trellis and state diagram. Corresponding to this code.

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 96

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 97
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 98
Consider the rate e=1/2 constraint length k=2
convolutional encoder of Fig shown. The code is
systematic. Find the encoder output produced by the
message sequence 10111 . .. . .
Construct the code tree for the encoder

The generator polynomials are

The message polynomial

99
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 100
101
Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 102
Consider the generator polynomial g(x)= 1 +X2 + X3

1 0 1 1 0 0 0
0 1 0 1 0 1 0 
G 
0 0 1 0 1 1 0 
 
0 0 0 1 0 1 1

Dr J. Ravindranadh/ Professor / ECE Dept / Digital Communication 103