Convolutional code卷积码

1 2 n
2
K
K+1
L-1
L
A rate k/n linear convolutional encoder
Convolutional Codes
K information 1 bits h0
1 2
n
2
K
K+1
L-1
L
A rate k/n linear convolutional encoder •The n channel bits depend not only on the current K bit information, but also on the previous L-K bits. Therefore, the convolutional code has memory M = L-K.
{Ci(1) } 100100 {Ci( 2) } 101101 {Ci(3) } 111111 {Ci(1) , Ci( 2) , Ci(3) } : 111 001 011 111 001 011
Example 2: L=4, K=2, and n=3
{Ci(1) }
{mi}
{Ci(1) , Ci(2) , Ci(3) }
A rate 1/3 linear binary convolutional encoder
g (1) (1, 0, 0) g ( 2 ) (1, 0,1) g (3) (1,1,1) Ci(1) mi Ci( 2 ) mi mi 2 Ci(3) mi mi 1 mi 2
•It is uniquely specified by the n linear algebraic function generators or the n generator sequences
( ( () g (i ) ( g0,i ) g1,i ) gLi1 ), 1 i n
g是三个寄存器的线性 C 组合函数，例如：i(1) 只与第一个寄存器连接 Ci( 2 ) 与第一和第三个 连接
Example 1: L=3, K=1, and n=3
{Ci(1) }
{mi}
{C }
(2) i
{Ci(1) , Ci(2) , Ci(3) }
{Ci(3) }
A rate 1/3 linear binary convolutional encoder mi-j=0 for any j>i. Thus with input (m0, m1, m2, m3 )= (1, 0, 0, 1), we have
{Ci(2) }
g (1) (1,0,1,1) g (2) (1,1,0,1) g (3) (1,0,1,0)
{Ci(3) }
•As in the case of linear block codes, there are two types of linear convolutional codes: binary and nonbinary convolutional codes. •For nonbinary linear convolutional codes, the input sequence, the generator sequences, are all over GF(q) for some q>2.
Alternative Representation
{Ci(1) }
输出的计算：当第一个一位寄存器 输入1或者0以后，马上计算输出， 然后再向右移位，取后两个寄存器 的值作为下一个状态。
{mi}
{C }
(2) i
{Ci(1) , Ci(2) , Ci(3) }
{Ci(3) }
如果输入是每次x位 的话，状态机的位 数就是L-x,L是寄存 器总个数
000 000 000 000 000 000
a b
c
d Level 0
1
2
3
4
Trellis Diagram and State Diagram
•The transitions among all possible state repeat themselves after level 2. Thus one can use a compact diagram to represent the convolutional code.
Convolutional Codes
• Convolutional codes distinguish themselves from linear block codes in the sense that the encoding process of convolutional codes have memory.
b 011 111 a 010 110 d 101 100 001 000
c
Different representations give us different insights. When we discuss the maximum likelihood decoding of convolutional codes, the trellis structure is convenient.
Viterbi Algorithm
•A brute force algorithm would require computation complexity that grows exponentially with T. For the trellis diagram shown in the last page, the brute force algorithm requires 2(T-2) comparisons. •On the other hand, the dynamic programming technique (or the Viterbi algorithm) requires computation complexity that grows only linearly with T, and still finds the optimal path. •At the heart of Viterbi algorithm is the concept of survivors. •A survivor to a state s at level j is a path starting from the initial state at level 0 and ending at the state s at level j that has the minimal total metric among all paths ending at the state s at level j. •The minimum total metric is called the metric of the survivor.
Alternative Representation
{Ci(1) }
{mi}
{C }
(2) i
{Ci(1) , Ci(2) , Ci(3) }
{Ci(3) }
L=3, K=1, n=3
•The n channel bits depend not only on the current K information bits, but also on the previous L-K inform bits. •If we regard the contents of the last L-K SR cells as a state, then the shift register shown in the previous diagrams acts like a finite-state machine.
1
2
3
T-2
T-1
T
•Consider a trellis diagram with a length T and a state S={s1,s2, · ,s|s|} · · •Suppose each transition from a state at level j to a state at level j+1 is associated with a metric. We want to find a path through the trellis so that its total metric is a minimum among all paths from the initial state at level 0 and ending at the final state at level T
Trellis Diagram
•There is a one-to-one correspondence between paths through the trellis and the inform. sequences {mi}. The labels on the path are the corresponding encoded outputs. For example, when (m0, m1, m2, m3) = (1, 0, 0, 1), we get the path a>c->b->a->c and outputs 111 001 011 111.
which specify the connections of the L SR cells to each modulo adder.
Example 1: L=3, K=1, and n=3
{Ci(1) }
{mi}
{C }
(2) i
{Ci(1) , Ci(2) , Ci(3) }
{Ci(3) }