Scribd
Upload
271 views13 pages

Module 5 Convolutional Codes Code Tree

The document discusses convolutional codes, focusing on the design and analysis of (2,1,2) and (3,1,2) convolutional encoders. It includes state transition tables, state diagrams, trellis diagrams, and code trees for various configurations. Additionally, it addresses a problem involving the Viterbi algorithm for decoding a received sequence.

Uploaded by

Anitha Nagesh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
271 views13 pages

Module 5 Convolutional Codes Code Tree

The document discusses convolutional codes, focusing on the design and analysis of (2,1,2) and (3,1,2) convolutional encoders. It includes state transition tables, state diagrams, trellis diagrams, and code trees for various configurations. Additionally, it addresses a problem involving the Viterbi algorithm for decoding a received sequence.

Uploaded by

Anitha Nagesh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 13

Module 5 Convolutional Codes

Manjunatha. P
[email protected]

Professor
Dept. of ECE

J.N.N. College of Engineering, Shimoga

November 13, 2024


Module 5 Convolutional Codes Convolutional Codes

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


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

i. Draw the state transition table


ii. Draw the State diagram
iv. Draw the Trellis diagram
iii. Draw the code tree.

Solution:
(n,k,m) n=number of output=2, k=number of input=1, and m = number of memory
registers=2
V1

Input
FF FF

V2

Figure 1: Encoder for g (1) = [1 1 1] g (2) = [1 0 1]


Manjunatha. P (JNNCE) Module 5 Convolutional Codes November 13, 2024 2 / 13
Module 5 Convolutional Codes Convolutional Codes

The convolutional encoder consists of 2 Flip-flops.


The content of the Flip-flops are 00 01 10 11.
Table 1: State transition table
g (1) (D) = 1 + D + D 2 g (2) (D) = 1 + D 2

Input Present State Next State Output


Binary description State 0 00 00 00
00 a 1 00 10 11
01 c 0 01 00 11
10 b 1 01 10 00
11 d 0 10 01 10
1 10 11 01
0 11 01 01
1 11 11 10

Manjunatha. P (JNNCE) Module 5 Convolutional Codes November 13, 2024 3 / 13


Module 5 Convolutional Codes Convolutional Codes

Table 2: State transition table State b


10
0(10)
g (1) (D) = 1 + D + D 2 g (2) (D) = 1 + D 2 1(11)

1(00)
Input Present State Next State Output
1(01)
0 00 00 00
1 00 10 11 0(00)
State a
00
0(11) State c
01

0 01 00 11
1 01 10 00
0(01)
0 10 01 10
1 10 11 01 1(10)
State d
11
0 11 01 01
1 11 11 10 Figure 2: State graph

Binary description State


00 a
01 c
10 b
11 d

Manjunatha. P (JNNCE) Module 5 Convolutional Codes November 13, 2024 4 / 13


Module 5 Convolutional Codes Convolutional Codes

Table 3: State transition table a


00 00 00 00 00 00 00 00
g (1) (D) = 1 + D + D 2 g (2) (D) = 1 + D 2 11 11 11 11 11
11

Input Present State Next State Output b 11 11 11 11 11 11


0 00 00 00 00 00 00

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

0 11 01 01
1 11 11 10 Figure 3: Trellis graph

Binary description State


00 a
01 c
10 b
11 d

Manjunatha. P (JNNCE) Module 5 Convolutional Codes November 13, 2024 5 / 13


Module 5 Convolutional Codes Convolutional Codes

00
00 a
11
00 a
10
11 b
01
00 a
Binary description State 10 c
11

11 00
00 a b
01
01 d
01 c 10
00 a
00
10 b 11 a
11
10
11 d c
10
00 b
01
11 b
11
01 c
00
01
Table 4: State transition table
0
d
10 d
01

g (1) (D) = 1 + D + D 2 g (2) (D) = 1 + D 2 10

00
00 a
11
11 a
Input Present State Next State Output 1
11 b
10

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

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

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

00
1 11 11 10 10
d
01
10 d
10

Figure 4: Tree graph


Manjunatha. P (JNNCE) Module 5 Convolutional Codes November 13, 2024 6 / 13
Module 5 Convolutional Codes Convolutional Codes

For a (3,1,2) convolutional encoder with


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

i. Draw the encoder diagram


ii. Draw the state transition table
iii. Draw the State diagram
iv. Draw the Trellis diagram

Solution:
(n,k,m) n=number of output=3, k=number of input=1, and m = number of memory
registers=2
V (0)

Input U
SR SR V (1)

Output

V (2)

Figure 5: Encoder for g (1) = [1 1 0] g (2) = [1 0 1] g (3) = [1 1 1]


Manjunatha. P (JNNCE) Module 5 Convolutional Codes November 13, 2024 7 / 13
Module 5 Convolutional Codes Convolutional Codes

G(D) = [1 + D, 1 + D 2 , 1 + D + D 2 ]

Table 5: State transition table for the (3,1,2)encoder


V (0)

Input Present State Next State Output


Input U
0 00 00 000
SR SR V (1) 1 00 10 111
Output 0 01 00 011
1 01 10 100
V (2) 0 10 01 101
1 10 11 010
0 11 01 110
Figure 6: R=1/3 convolutional encoder with 1 11 11 001
memory m=2

S1

0(101)
1(010)

1(111)
Tuple State 1(100)
00 s0
0(011)
01 s2 0(000) S0 S2
10 s1
11 s3

0(110)

1(001) S3

Manjunatha. P (JNNCE) Module 5 Convolutional Codes November 13, 2024 8 / 13


Module 5 Convolutional Codes Convolutional Codes

001 001 001


S3 S3 S3 S3

110 110 110


110
Table 6: State transition table
010 010 010 010
g (1) (D) = 1 + D + D 2 g (2) (D) = 1 + D 2
S1 S1 S1 S1 S1

Input Present State Next State Output 101 101 101 101 101
0 00 00 000 100 100
1 00 10 111 S2 S2 S2 S2 S2
0 01 00 011 011 011 011
011 011
1 01 10 100

111

111
111

111
111
0 10 01 101
S0 S0 S0 S0 S0 S0 S0 S0
1 10 11 010 000 000 000 000 000 000 000
0 11 01 110 0 1 2 3 4 5 6 7
Time units
1 11 11 001

Figure 7: Trellis graph

Binary description State


00 s0
01 s2
10 s1
11 s3

Manjunatha. P (JNNCE) Module 5 Convolutional Codes November 13, 2024 9 / 13


Module 5 Convolutional Codes Convolutional Codes

Problem 9.41 Proakis A convolutional code is described by

g1 = [1 0 0] g2 = [1 0 1] g3 = [1 1 1]

a. Draw the encoder diagram and find the output using time domain for the input sequence (1 1 1 0 1).
b. Draw the state-transition diagram.
c. Draw the trellis diagram.
d. If the received sequence is r =(110, 110, 110, 111,010, 101, 101), using the Viterbi algorithm find the transmitted bit
sequence.
Solution:

a.

V (0)
 
111 001 011
Input U
 111 001 011 
V (1) G= 
 111 001 011 
Output
111 001 011
V (2)

111 001 011


 
 111 001 011 
V = UG = (1 1 1 0 1)  111 001 011  = (111 110 101 010 100 100 001 011 )
 
 111 001 011 
111 001 011

Manjunatha. P (JNNCE) Module 5 Convolutional Codes November 13, 2024 10 / 13


Module 5 Convolutional Codes Convolutional Codes

b.
V (0) Table 7: State table g1 = [1 0 0] g2 = [1 0 1] g3 = [1 1 1]

Input Present State Next State Output


Input U 0 00 00 000
V (1) 1 00 10 111
Output 0 01 00 011
1 01 10 100
0 10 01 001
V (2) 1 10 11 110
0 11 01 010
1 11 11 101
Figure 8:
g1 = [1 0 0] g2 = [1 0 1] g3 = [1 1 1]

S1

0(101)
1(010)

1(111)
1(100)

Tuple State 0(000) S0


0(011)
S2
00 a
01 b
10 c
11 d
0(110)

1(001) S3

Manjunatha. P (JNNCE) Module 5 Convolutional Codes November 13, 2024 11 / 13


Module 5 Convolutional Codes Convolutional Codes

S1

0(101)
1(010)

1(111) Tuple State


1(100)
00 a
c. 0(000) S0
0(011)
S2 01
10
b
c
11 d

0(110)

1(001) S3

000 000 000 000 000


a
011 011 011
111 111 111 111 111

b
100 100 100
001 001 001 001
c 011
110 110 110 110
010 010 010
d
101 101 101

Steady State

Figure
Manjunatha. P 10:
(JNNCE) Trellis diagram for rateModule
1/3 m=2 convolutional
5 Convolutional Codes code (3,1,2) November 13, 2024 12 / 13
Module 5 Convolutional Codes Convolutional Codes

110 110 110 111 010 101 100


2 4 6 3 4 6 7
000 000 000 000 000 000 000
a X
011 011 011 X 011 011
111 111 111 111 111
X
4 2 5 4 6
b X
001 100 100 X 100 001
001
X 001 001
4 5
1 3 5
c 011
110 110 110 110
010 010
010 X 010
1 3 4 5
d
101 101 101 101

Steady State

The path traced by the Viterbi is (111, 110, 010, 011, 000, 000, 000) and the
decoded sequence is (1 1 0 0 0 0 0)
Manjunatha. P (JNNCE) Module 5 Convolutional Codes November 13, 2024 13 / 13

You might also like