0.1.

Module 5 Convolutional Codes (Chapter 10)

0.1 Module 5 Convolutional Codes (Chapter 10)

Syllabus

A convolutional coder generates redundant bits by using modulo-2 convolutions; hence the name
convolutional codes.
The encoder of a binary convolutional consists of a finite-state machine that consists of an M-stage
shift register with prescribed connections to n modulo-2 adders and a multiplexer. A sequence of message
bits produces a coded output sequence of length n(L + M ) bits, where L is the length of the message
sequence. The code rate is given by

L
r =
n(L + M )
L
= bits/symbol
n(1 + M/L)

1
r = bits/symbol
n

Constraint length:
defined as follows:
The constraint length of a convolutional code, expressed in terms of message bits, is the
number of shifts over which a single incoming message bit can influence the encoder output.
In an encoder with an M-stage shift register, the constraint length, denoted by ν, equals M + 1 shifts
that are required for a message bit to enter the shift register and finally come out.
The block diagram of convolutional encoder with constraint length = 3 is as shown in Figure 1. In
this example, the code rate of the encoder is 21 . The encoder operates on the incoming message sequence,
one bit at a time, through a convolution process; it is therefore said to be a nonsystematic code.

Path 1

V (0)
Input
Output
Flip-flop
V (1)

Modulo 2
adder Path 2

Figure 1: convolutional encoder:Constraint length-3, rate -1/2

• Convolutional codes are commonly specified by three parameters: (n,k,m) where

n = number of outputs
k = number of inputs
m = number of memory registers
• The quantity k/n called the code rate, is a measure of the efficiency of the code commonly k and n
parameters range from 1 to 8 and m from 2 to 10.
• The constraint length ν represents the number of bits in the encoder memory that affect the
generation of the n output bits.
Constraint Length, ν = (m + 1)

Dr. Manjunatha P Prof., Dept of ECE, JNN College of Engg Shimoga [email protected] 1
0.1. Module 5 Convolutional Codes (Chapter 10)

The generator polynomial of the ith path is defined by

(i) (i) (i) (i)
g (i) (D) = g0 + g1 D + g2 D2 . . . + gM DM

where D denotes the unit-delay variable. The complete convolutional encoder is described by the set of
generator polynomials
The impulse response of path 1 (upper path) is (1, 1, 1). The generator polynomial of this path is

g (1) (D) = 1 + D + D2

The impulse response of path 2 (lower path) is (1, 0, 1). The generator polynomial of this path is

g (2) (D) = 1 + D2

The polynomial representation for an incoming message sequence of (10011) is

m(D) = 1 + D3 + D4

The convolution in the time domain is transformed into multiplication (with Fourier transformation) in
the D-domain. The output polynomial of path 1 is given by

c(1) (D) = g (1) (D)m(D)

c(1) (D) = g (1) (D)m(D)

= (1 + D + D2 )(1 + D3 + D4 )
= 1 + D3 + D4 + D + D4 + D5 + D2 + D5 + D6
= 1 + D + D2 + D3 + D6
= (1111001)

The output polynomial of path 2 is given by

c(2) (D) = g (2) (D)m(D)

= (1 + D2 )(1 + D3 + D4 )
= 1 + D3 + D4 + D2 + D5 + D6
= 1 + D2 + D3 + D4 + D5 + D6
= (1011111)

Multiplexing the two output sequences of paths 1 and 2, we get the encoded sequence is

c = (11, 10, 11, 11, 01, 01, 11)

The message sequence of length L = 5 bits produces an encoded sequence of length n(L + ν − 1) =
2(5 + 3 − 1) = 14 bits. Note also that for the shift register to be restored to its initial all-zero state, a
terminating sequence of nu − 1 = 3 − 1 = 2 zeros is appended to the last input bit of the message sequence.
The terminating sequence of +nu − 1 zeros is called the tail of the message.

Matrix method
• L Number of message bits

• n Number of adders (output)

• m Number of shift registers

• If the generator sequence g (0) and g (1) are interlaced and then arranged in the matrix

Dr. Manjunatha P Prof., Dept of ECE, JNN College of Engg Shimoga [email protected] 2
0.1. Module 5 Convolutional Codes (Chapter 10)

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

 
g0 g0 g1 g1 g2 g2 ... g m gm
 (0) (1) (0) (1) (0) (2) (0) (1) 

 g0 g0 g1 g1 g2 g2 ... g m gm 

G= (0) (1) (0) (1) (0) (2) (0) 1)
g0 g0 g1 g1 g2 g2 ... g m gm

 
 
 . . 
. .
. ... .

• where the blank areas are all zeros, the encoding equations can be rewritten in matrix form as v =
uG.

• G is called the generator matrix of the code.

• Note that each row of G is identical to the preceding row but shifted n = 2 places to right, and the
G is a semi-infinite matrix, corresponding to the fact that the information sequence u is of arbitrary
length.

• The order of the matrix is L × [n(L + m)]

g (1) = (1, 1, 1) g (2) = (1, 0, 1)

The input sequence (10011)
The order of the matrix is l × [n(l + m)] = 5 × [2(5 + 2)] = 5 × 14
No of rows for G are 5. The code word corresponding to the information sequence u = (1 0 0 1 1) is:
 
11 10 11 00 00 00 00
 00 11 10 11 00 00 00 
 
G=  00 00 11 10 11 00 00 

 00 00 00 11 10 11 00 
00 00 00 00 11 10 11
 
11 10 11 00 00 00 00

 00 11 10 11 00 00 00 

V = UG = (1 0 0 1 1) 
 00 00 11 10 11 00 00  = (11, 10, 11, 11, 01, 01, 11)

 00 00 00 11 10 11 00 
00 00 00 00 11 10 11

c = (11, 10, 11, 11, 01, 01, 11)

Example 2
g (1) = (1, 0, 1) g (2) = (1, 1, 1)
The input sequence (10111)
The order of the matrix is L × [n(L + m)] = 5 × [2(5 + 2)] = 5 × 14
No of rows for G are 5. The code word corresponding to the information sequence u = (1 0 1 1 1 ) is:
 
11 01 11 00 00 00 00
 00 11 01 11 00 00 00 
 
G=  00 00 11 01 11 00 00 

 00 00 00 11 01 11 00 
00 00 00 00 11 01 11
 
11 01 11 00 00 00 00

 00 11 01 11 00 00 00 

V = UG = (1 0 1 1 1) 
 00 00 11 01 11 00 00  = (11, 01, 00, 10, 01, 10, 11)

 00 00 00 11 01 11 00 
00 00 00 00 11 01 11

g (1) (D) = 1 + D2

Dr. Manjunatha P Prof., Dept of ECE, JNN College of Engg Shimoga [email protected] 3
0.1. Module 5 Convolutional Codes (Chapter 10)

g (2) (D) = 1 + D + D2
The polynomial representation for an incoming message sequence of (1 0 0 1 1) is

m(D) = 1 + D3 + D4

The convolution in the time domain is transformed into multiplication (with Fourier transformation)
in the D-domain. The output polynomial of path 1 is given by

c(1) (D) = g (1) (D)m(D)

c(1) (D) = g (1) (D)m(D)

= (1 + D + D2 )(1 + D3 + D4 )
= 1 + D3 + D4 + D + D4 + D5 + D2 + D5 + D6
= 1 + D + D2 + D3 + D6
= (1111001)

The output polynomial of path 2 is given by

c(2) (D) = g (2) (D)m(D)

= (1 + D2 )(1 + D3 + D4 )
= 1 + D3 + D4 + D2 + D5 + D6
= 1 + D2 + D3 + D4 + D5 + D6
= (1011111)

c(1) (D) = (1111001) c(2) (D) = (1011111)

C=(11, 10, 11, 11, 01, 01, 11)

Problem 11.1 Consider the (3,1,2) nonsystematic feed forward convolutional encoder with

g (0) = [1 1 0] g (1) = [1 0 1] g (2) = [1 1 1]

a. Draw the encoder block diagram.

b. Find the time-domain generator matrix G.

c. Find the codeword V corresponding to the information sequence u=(1 1 1 0 1).

Solution:

n = 3, k = 1, m = 2
a.

V (0)

Input U
SR SR V (1)

Output

V (2)

Figure 2: 11.1 R=1/2 convolutional encoder with memory m=3

b.
The order of the matrix is L × [n(L + m)] = 5 × [3(5 + 2)] = 5 × 21

Dr. Manjunatha P Prof., Dept of ECE, JNN College of Engg Shimoga [email protected] 4
0.1. Module 5 Convolutional Codes (Chapter 10)

 
111 101 011 000 000 000 000

 000 111 101 011 000 000 000 

G=
 000 000 111 101 011 000 000 

 000 000 000 111 101 011 000 
000 000 000 000 111 101 011
c. No of rows for G are 5. The code word corresponding to the information sequence u = (1 1 1 0 1)
is:

 
111 101 011 000 000 000 000

 000 111 101 011 000 000 000 

V = UG = (1 1 1 0 1) 
 000 000 111 101 011 000 000  = (111 010 001 110 100 101 011)

 000 000 000 111 101 011 000 
000 000 000 000 111 101 011
The impulse response of path 1 is (1, 1, 0). The generator polynomial of this path is

g (1) (D) = 1 + D

The impulse response of path 2 is (1, 0, 1). The generator polynomial of this path is

g (2) (D) = 1 + D2

The impulse response of path 3 is (1, 1, 1). The generator polynomial of this path is

g (3) (D) = 1 + D + D2

The polynomial representation for an incoming message sequence of (11101) is

m(D) = 1 + D + D2 + D4

The convolution in the time domain is transformed into multiplication (with Fourier transformation) in
the D-domain. The output polynomial of path 1 is given by

c(1) (D) = g (1) (D)m(D)

c(1) (D) = g (1) (D)m(D)

= (1 + D)(1 + D + D2 + D4 )
= 1 + D + D2 + D4 + D + D2 + D3 + D5
= 1 + D3 + D4 + D5
= (1001110)

The output polynomial of path 2 is given by

c(2) (D) = g (2) (D)m(D)

= (1 + D2 )(1 + D + D2 + D4 )
= 1 + D + D2 + D4 + D2 + D3 + D4 + D6
= 1 + D + D3 + D6
= (1101001)

The output polynomial of path 3 is given by

c(3) (D) = g (3) (D)m(D)

= (1 + D + D2 )(1 + D + D2 + D4 )
= 1 + D + D2 + D4 + D + D2 + D3 + D5 + D2 + D3 + D4 + D6
= 1 + D2 + D5 + D6
= (1010011)

Dr. Manjunatha P Prof., Dept of ECE, JNN College of Engg Shimoga [email protected] 5
0.1. Module 5 Convolutional Codes (Chapter 10)

Multiplexing the two output sequences of paths 1 and 2, we get the encoded sequence is

c = (111, 010, 001, 110, 101, 101, 011)

Also

c(D) = c(1) (D3 ) + Dc(2) (D3 ) + D2 c(3) (D3 )

c(1) (D3 ) = 1 + D3 + D4 + D5
Dc(2) (D3 ) = D + D4 + D10 + D5
D2 c(3) (D3 ) = 1 + D3 + D4 + D5

2022 March 10 a) For a (2,1,3) convolutional encoder with

g (1) = [1 0 1 1] g (2) = [1 1 1 1]

Find the codeword V corresponding to the information sequence u=(1 0 1 1 1) using the two following
approaches

i. Time domain approach

ii. Transform domain approach

iii. Also draw the encoder diagram

Solution:

i.] Time domain approach

g (1) = [1 0 1 1] g (2) = [1 1 1 1]
The order of the matrix for the input message u = (1 0 1 1 1 ) is: L × [n(L + m)] = 5 × [2(5 + 3)] = 5 × 16
No of rows for G are 5.  
11 01 11 11 00 00 00 00
 00 11 01 11 11 00 00 00 
 
G=  00 00 11 01 11 11 00 00  
 00 00 00 11 01 11 11 00 
00 00 00 00 11 01 11 11

 
11 01 11 11 00 00 00 00

 00 11 01 11 11 00 00 00 

V = UG = (1 0 1 1 1) 
 00 00 11 01 11 11 00 00  = (11, 01, 00, 01, 01, 01, 00, 11)

 00 00 00 11 01 11 11 00 
00 00 00 00 11 01 11 11

The code word corresponding to the information sequence u = (1 0 1 1 1 ) is: [11, 01, 00, 01, 01, 01, 00, 11]
ii.] Transform domain approach

• For (2,1,3) convolutional code,g (0) = [1 0 1 1] and g (1) = [1 1 1 1] the generator polynomials are

g (0) (D) = 1 + D2 + D3
g (1) (D) = 1 + D + D2 + D3

Dr. Manjunatha P Prof., Dept of ECE, JNN College of Engg Shimoga [email protected] 6
0.1. Module 5 Convolutional Codes (Chapter 10)

• For the information sequence u(D) = 1 + D2 + D3 + D4 , then

v (0) (D) = (1 + D2 + D3 + D4 )(1 + D2 + D3 )

v (0) (D) = (1 + D2 + D3 + D4 + D2 + D4 + D5 + D6 + D3 + D5 + D6 + D7 )
v (0) (D) = (1 + D2 + D2 + D3 + D3 + D4 + D4 + D5 + D5 + D6 + D6 + D7 )
v (0) (D) = (1 + D7 )
v (1) (D) = (1 + D2 + D3 + D4 )(1 + D + D2 + D3 )
v (1) (D) = (1 + D2 + D3 + D4 + D + D3 + D4 + D5 + D2 + D4 + D5 + D6
= +D3 + D5 + D6 + D7 )
v (1) (D) = 1 + D + D3 + D4 + D5 + D7

• and the code word is

v(D) = [1 + D7 , 1 + D + D3 + D4 + D5 + D7 ].

• After multiplexing, the code word become

v(D) = v (0) (D2 ) + Dv (1) (D2 )

v (0) (D2 ) = (1 + D14 )

v (1) (D2 ) = Dv (1) (D2 ) = D(1 + D2 + D6 + D8 + D10 + +D14 )
v (1) (D2 ) = Dv (1) (D2 ) = D + D3 + D7 + D9 + D11 + +D15

v(D) = v (0) (D2 ) + Dv (1) (D2 )

v(D) = 1 + D + D3 + D7 + D9 + D11 + D14 + D15

• The sequence is [11 01 00 01 01 01 00 11]

• The result is the same as time domain (matrix) multiplication.

iii.) Also draw the encoder diagram

V (0)

Input U
SR SR SR Output

V (1)

Figure 3: 11.1 R=1/2 convolutional encoder with memory m=3

Dr. Manjunatha P Prof., Dept of ECE, JNN College of Engg Shimoga [email protected] 7
0.2. Module 5 Convolutional Codes (Chapter 10)

0.2 Module 5 Convolutional Codes (Chapter 10)

Constraint length:
defined as follows:

The block diagram of convolutional encoder with constraint length = 3 is as shown in Figure 1. In
this example, the code rate of the encoder is 21 . The encoder operates on the incoming message sequence,
one bit at a time, through a convolution process; it is therefore said to be a nonsystematic code.

Path 1

V (0)
Input
Output
Flip-flop
V (1)

Modulo 2
adder Path 2

Figure 4: convolutional encoder:Constraint length-3, rate -1/2

The generator polynomial of the ith path is defined by

(i) (i) (i) (i)
g (i) (D) = g0 + g1 D + g2 D2 . . . + gM DM

where D denotes the unit-delay variable. The complete convolutional encoder is described by the set of
generator polynomials
The impulse response of path 1 (upper path) is (1, 1, 1). The generator polynomial of this path is

g (1) (D) = 1 + D + D2

The impulse response of path 2 (lower path) is (1, 0, 1). The generator polynomial of this path is

g (2) (D) = 1 + D2

The convolutional encoder consists of 2 Flip-flops. The content of the Flip-flops are 00 01 10 11.

Binary description State

00 a
01 c
10 b
11 d

Dr. Manjunatha P Prof., Dept of ECE, JNN College of Engg Shimoga [email protected] 8
0.2. Module 5 Convolutional Codes (Chapter 10)

Table 1: State transition table for the g (1) (D) = 1 + D + D2 g (2) (D) = 1 + D2

Input Present State Next State Output

0 00 00 00
1 00 10 11
0 01 00 11
1 01 10 00
0 10 01 10
1 10 11 01
0 11 01 01
1 11 11 10

State b 0(10)
10
1(11)

1(00)

1(01)

State a 0(11) State c

0(00) 00 01

0(01)

State d
1(10) 11

Figure 5: State graph of the convolutional encoder

00 00 00 00 00 00 00 00
a
11
11 11 11 11 11

b 11 11 11 11 11 11
00 00 00
10
c
01 01 01 01 01

01 01 01 01 01 01
d 10 10 10 10 10
Level J= 0 1 2 3 4 5 L-1 L L+1 L+2

Figure 6: Trellis graph of the convolutional encoder

Dr. Manjunatha P Prof., Dept of ECE, JNN College of Engg Shimoga [email protected] 9
0.2. Module 5 Convolutional Codes (Chapter 10)

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

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

Figure 7: Tree graph of the convolutional encoder

Dr. Manjunatha P Prof., Dept of ECE, JNN College of Engg Shimoga [email protected] 10
0.2. Module 5 Convolutional Codes (Chapter 10)

1
2021 Feb 10 a) Consider the rate 2 and constraint length K=2 convolutional encoder as shown in
Figure

i. Draw the state diagram

ii. Draw the code tree

iii. Find the encoder output produced using sequence 10111 verify using time domain approach.

Solution:

Table 2: State transition table for the g (1) (D) = 1 + D g (2) (D) = 1

Input Present State Next State Output

0 0 0 00
1 0 1 11
0 1 0 10
1 1 1 01

1(11)

1(01)

0(00) S0 S1

0(10)

Figure 8: State graph of the convolutional encoder

From the code tree the output code is 11 10 11 01 01

iii.) Find the encoder output produced using sequence 10111 verify using time domain approach.
 
11 10 00 00 00 00
 00 11 10 00 00 00 
 
G=  00 00 11 10 00 00 

 00 00 00 11 10 00 
00 00 00 00 11 01
 
11 10 00 00 00 00
 00 11 10 00 00 00 
 
V = (10111) 
 00 00 11 10 00 00 

 00 00 00 11 10 00 
00 00 00 00 11 10
=[11 10 11 01 01 10]

Dr. Manjunatha P Prof., Dept of ECE, JNN College of Engg Shimoga [email protected] 11
0.2. Module 5 Convolutional Codes (Chapter 10)

00
00
S0 11
00
S0
10
11
S1 01
00
S0 00
10 S
0 11
11
S1
10
01
S1 01
00 S0
00
00 S
0 11
10 S
0
10
11 S
1 01
11
S1 00
10 S
0 11
0 01
S1
10
01 S
1 01
S0 00
00
S0 11
00
1 S0 10
11
S1 01
10
S0 00
10 S
0 11
11
S1
10
01 S
1 01
11
S1 00
11 S
0 11
10
S0 10
00 S
1 01
01
S1 00
10 S
0 11
01
S1
10
01 S
1 01

Figure 9: Tree graph of the convolutional encoder

Dr. Manjunatha P Prof., Dept of ECE, JNN College of Engg Shimoga [email protected] 12