Understanding Convolutional Codes in Digital Communication
Convolutional codes provide an efficient alternative to linear block coding by grouping data into smaller blocks and encoding them into output bits. These codes are defined by parameters (n, k, L) and realized using a convolutional structure. Generators play a key role in determining the connections and output bits of the convolutional encoder. Explore examples and code rates to grasp the structure and functionality of convolutional codes.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Convolutional codes In previous linear block coding, each k data digits are encoded into n digits to generate (n,k) code by adding the r parity digits. An alternative scheme that groups the data stream into much smaller blocks k digits and encode them into n digits with order of k say 1, 2 or 3 digits at most is the convolutional codes. Such code structure can be realized using convolutional structure for the data digits. Structure of the convolutional codes A convolutional code is specified by three parameters : ( n, k, L) where : k input bit(s) to the encoder (k bit at a time) n no. of output bits for each k input L is the constraint length of the convolutinal code (no. of groups each group has k shift register) The code rate is k/n Convolutional code is defined by giving it s generators. These are n vectors[ ?1 , ?2,?3 ??]each of Lk length describing the selected taps from the shift register to be mod- 2 summed
Output bits Structure of the convolutional codes
Example1: Consider the convolutional encoder with L=3, k=1, n=3 [g1]=[100], [g2]=[101], [g3]=[111] Since k=1 then we have one bit at a time (one shift register in each group). L=3, then we have 3 groups each with one stage( k=1), so we have 3 shift registers. n=3 so we have 3 output bits C1,C2 and C3 and the 3 generator vectors are: [g1]=[100], [g2]=[101], [g3]=[111] describing the connections for C1,C2 and C3 output (in octal form, these generators are given as 4, 5, 7). Q1 Q2 Q3 [g1]=[1 0 0], C1=Q1 [g2]=[1 0 1] , C2=Q1+Q3 [g3]=[1 1 1 ], C3=Q1+Q2+Q3
Example2: Consider the 2/3 rate convolutional encoder with generators [g1]=[1011], [g2]=[1101], [g3]=[1010](in octal these generators are 13,15,12). Since k=2 then we have two input bits at a time (two shift register in each group). n=3 so we have 3 output bits C1,C2 and C3 and the 3 generator vectors are: [g1]=[1011], [g2]=[1101], [g3]=[1010 ]describing the connections for C1,C2 and C3 output (in octal form, these generators are given as 13,15,12). C1=Q1+Q3+Q4 C2=Q1+Q2+Q4 C3=Q1+Q3 Since the generator vectors have 4 bits then L=2, then we have 2 groups each with two stages( k=2), so we have 4 shift registers.
There are 3 methods that are used to describe a convolutional code. 1) tree diagram 2) state diagram 3) trellis diagram. 1) Tree diagram: To draw the tree diagram of the coder described in example1. Here, we make a simple tree structure starting with Q1Q2Q3=[000] L=3, k=1, n=3 [g1]=[100], [g2]=[101], [g3]=[111] C1=Q1; C2=Q1+Q3; C3=Q1+Q2+Q3 If say the data input is 1011 , then the output sequence will be: 111 001 100 110
Example2: Draw the tree diagram of the convolutional encoder given in example2 L=2, k=2, n=3 convolutional encoder g1 = (1011) g2 = (1101) g3 = (1010) The state of the first (L-1)k stages of the shift register: a=00; b=01; c=10; d=11 If the input bits 1011 Then the output bits 111000
2) State diagram: An alternative picture to the convolutional encoder is to draw the state diagram of the encoder as a finite state machine. 1) Determine the following parameters: *no. of states = 2?(? 1)states depending on the content of the last L-1 groups. *no. of branches= 2? branches leaving each state and 2? branches entering into each state. 2) Prepare the transition table 3) Draw the state diagram Example1: Draw the state diagram of the convolutional encoder given in example1. Here L=3, k=1, [g1]=[100],[g2]=[101],[g3]=[111]. Solution: 1) no. of states= 2?(? 1)= 21(3 1) = 22 =4 states which are the same states a,b,c,d no. of branches= 2?= 21 =2 branches leaving from or entering into each node( state) 2) we will prepare the transition table that gives the present state of Q2Q3, next state of Q2Q3 and the output for each possible two inputs:
3) draw the state diagram ). For example, for data sequence : 1011 . The output will be: 111 001 100 110
Example2: Draw the state diagram of the encoder of example2. L=2, k=2, n=3 convolutional encoder, g1 = (1011) ; g2 = (1101); g3 = (1010) 1) no. of states= 2?(? 1)= 22(2 1) = 22 =4 states which are the same states a,b,c,d no. of branches= 2?= 22=4 branches leaving from or entering into each node( state) 2) Prepare the transition table : input bitsQ1Q2 present states of Q3Q4 next state of Q3Q4 output C1C2C3 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 a b c d
3) Trellis diagram: This is a very important diagram for the convolutional encoder since the very powerful decoder depends on this diagram. This diagram is directly obtained from the same transition table already obtained when we draw the state diagram. The only difference is that transitions between states are given as levels between the possible states Example: Draw the trellis diagram of the encoder of example1
Example2 : Draw the trellis diagram of the encoder of example2
