Branch : Computer Science and Engineering
Subject : Wireless Communication
Unit : Cellular System Design
Code Characterization - Trellis Diagrams
Introduction:
In In order to characterize a convolutional code, we must characterize how the codeword generation depends both on the k input bits and the encoder state, which has 2K−1 possible values. There are multiple ways to characterize convolutional codes, including a tree diagram, state diagram, and trellis diagram .The trellis diagram simplifies the tree representation by merging nodes in the tree corresponding to the same encoder state.
Trellis diagram
- Consider the convolutional encoder shown in Figure 6.7 with n = 3, k = 1, and K = 3. In this encoder, one bit at a time is shifted into Stage 1 of the 3-stage shift register
- At a given time t we denote the bit in Stage I of the shift register as Si. The 3 stages of the shift register are used to generate a codeword of length 3, C_{1}C_{2}C_{3}, where from the figure we see that C_{1} = S_{1} S_{2}, C_{2} = S_{1} S_{2} S_{3}, and C_{3} = S_{3}.
- A bit sequence U shifted into the encoder generates a sequence of coded symbols, which we denote by C
- The encoder state as S = S_{2}S_{3}, i.e. the contents of the last two stages of the encoder, and there are 2^{2} = 4 possible values for this encoder state.
- To characterize the encoder, we must show for each input bit and each possible encoder state what the encoder output will be, and how the new input bit changes the encoder state for the next input bit
Figure Encoder |
- The trellis diagram for this code is shown in Figure
Figure trellis diagram |
- The solid lines in Figure above indicate the encoder state transition when a 0 bit is input to Stage 1 of the encoder, and the dashed lines indicate the state transition corresponding to a 1 bit input.
- Starting at state S = 00, if a 0 bit is input to Stage 1 then, when the shift register transitions, the new state will remain as S = 00 On the other hand, if a 1 bit isinput to Stage 1 then, when the shift register transitions, the new state will become S = 10 .
- The encoder output corresponding to a particular encoder state S and input S1 is written next to the transition lines in Figure 8.7.
- This output is the encoder output that results from the encoder addition operations on the bits S_{1}, S_{2}and S= in each stage of the encoder
- If S = 00 and S_{1} = 1 then the encoder output C_{1}C_{2}C_{3} has C_{1} = S_{1} S_{2} = 1, C_{2} = S_{1} S_{2} S_{3} = 1, and C_{3} = S_{3} = 0. This output 110 is drawn next to the dashed line transitioning from state S = 00 to state S = 10 in Figure 6.8
- The encoder output for S_{1} = 0 and S = 00 is always the all-zero codeword regardless of the addition operations that form the codeword C_{1}C_{2}C_{3}
- The portion of the trellis between time t_{i} and t_{i 1} is called the i^{th} branch of the trellis.
Steady state: The point where all states can be entered from either of two preceding states, at time t_{3}
- After this steady state is reached, the trellis repeats itself in each time interval.
- In general trellis structures starting from the all-zero state at time t0 achieve steady-state at time t_{K}.