Code Characterization - Trellis Diagrams
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.
- 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, C1C2C3, where from the figure we see that C1 = S1 S2, C2 = S1 S2 S3, and C3 = S3.
- A bit sequence U shifted into the encoder generates a sequence of coded symbols, which we denote by C
- The encoder state as S = S2S3, i.e. the contents of the last two stages of the encoder, and there are 22 = 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
- 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 S1, S2and S= in each stage of the encoder
- If S = 00 and S1 = 1 then the encoder output C1C2C3 has C1 = S1 S2 = 1, C2 = S1 S2 S3 = 1, and C3 = S3 = 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 S1 = 0 and S = 00 is always the all-zero codeword regardless of the addition operations that form the codeword C1C2C3
- The portion of the trellis between time ti and ti 1 is called the ith branch of the trellis.
Steady state: The point where all states can be entered from either of two preceding states, at time t3
- 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 tK.