信息论与编码民大11-卷积码

1卷积码2卷积码的特点：监督码元不仅和当前的k比特信息段有关，而且还同前面m=(N–1)个信息段有关。将N称为码组的约束长度。将卷积码记作(n,k,m)，其码率为k/n。3卷积码的编码一般原理方框图编码输出每次输入k比特1k…1k…1k…1k…………1…k…2k3kNk………………………12nNk级移存器n个模2加法器每输入k比特旋转1周4卷积码编码器的实例方框图：(n,k,m)=（3,1,2）每当输入1比特时，此编码器输出3比特c1c2c3：编码器的工作状态123b3b1输入b2编码输出c2c1c3321331211bbbcbbcbcb11101000b3b200011110011000c1c2c3111110010100001011000状态abdcbca5000111001110011100010101000111001110011100010101c1c2c3000100111011001101110010c1c2c3111000001110c1c2c3信息位1101ba起点信息位000111c1c2c3abcdabcdabcdabcd上半部下半部10a状态b3b2a00b01c10d11abcdabcdcdab↑0↓1↓1↑0↑0↓1卷积码的解码码树搜索法：(3,1,2)卷积码的码树图此法不实用：因为随信息位增多，分支数目按指数规律增长6状态图和网格图移存器状态和输入输出码元的关系状态图前一状态b3b2当前输入b1输出c1c2c3下一状态b3b2a(00)01000111a(00)b(01)b(01)01001110c(10)d(11)c(10)01011100a(00)b(01)d(11)01010101c(10)d(11)321331211bbbcbbcbc123b3b1输入b2编码输出c2c1c3abcd0001111011100100111000017(3,1,2)卷积码网格图网格图中的编码路径举例输入信息位为11010时输出编码序列是：111110010100001…110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100abcd000111101110010011100001abcdabcd1100100011111008维特比算法基本原理：将接收到的序列和所有可能的发送序列作比较，选择其中汉明距离最小的序列当作是现在的发送序列例：设卷积码为(n,k,m)=(3,1,2)码现在的发送信息位为1101为了使移存器中的信息位全部移出，在信息位后面加入了3个“0”，即1101000编码后的发送序列：111110010100001011000接收序列：111010010110001011000(红色为错码)由于这是一个(3,1,2)卷积码，发送序列的约束长度为N=m+1＝3，所以首先需考察3个信息段，即考察3n＝9比特，即接收序列前9位“111010010”。9解码第1步由网格图可见，沿路径每一级有4种状态a,b,c和d。每种状态只有两条路径可以到达。故4种状态共有8条到达路径。比较网格图中的这8条路径和接收序列之间的汉明距离。例如，由出发点状态a经过3级路径后到达状态a的两条路径中上面一条为“000000000”。它和接收序列“111010010”的汉明距离等于5；下面一条为“111001011”,它和接收序列的汉明距离等于3。110110110110011011011010010010101101101001001001001abcdabcd00000000000000011111111111111110010010010将这8个比较结果列表如下：比较到达每个状态的两条路径的汉明距离，将距离小的一条路径保留，称为幸存路径。这样，就剩下4条路径了，即表中第2,4,6和8条路径。序号路径对应序列汉明距离幸存否？1aaaa0000000005否2abca1110010113是3aaab0000001116否4abcb1110011004是5aabc0001110017否6abdc1111100101是7aabd0001111106否8abdd1111101014是11解码第2步：继续考察接收序列中的后继3个比特“110”计算4条幸存路径上增加1级后的8条可能路径的汉明距离。计算结果列于下表中。表中总距离最小为2，其路径是abdc+b，相应序列为111110010100。它和发送序列相同，故对应发送信息位1101。序号路径原幸存路径的距离新增路径段新增距离总距离幸存否？1abca+a3aa25否2abdc+a1ca23是3abca+b3ab14否4abdc+b1cb12是5abcb+c4bc37否6abdd+c4dc15是7abcb+d4bd04是8abdd+d4dd26否12按照上表中的幸存路径画出的网格图示于下图中。图中粗线路径是距汉明离最小（等于2）的路径。abcd011010010101001abcd11110010011011013在编码时，信息位后面加了3个“0”。若把这3个“0”仍然看作是信息位，则可以按照上述算法继续解码。这样得到的幸存路径网格图示于下图中。图中的粗线仍然是汉明距离最小的路径。110011010010101101001001abcdabcd00011110010000001101100110114若已知这3个码元是（为结尾而补充的）“0”，则在解码时就预先知道在接收这3个“0”码元后，路径必然应该回到状态a。而由图可见，只有两条路径可以回到a状态。所以，这时上图可以简化成：110011010010101101001001abcdabcd000111100100000011011001110011010010101101001001abcdabcd00011110010000001101100110115在上例中卷积码的约束长度为N=3，需要存储和计算8条路径的参量。由此可见，维特比算法的复杂度随约束长度N按指数形式2N增长。故维特比算法适合约束长度较小（N10）的编码。维特比译码算法的演示