《信息论与编码》课件1第5章.ppt

将Hamming界推广到非二进制码，即(5.57)另一个最小距离的上边界是普洛特金（Plotkin）1960年推出的，后人称之为Plotkin限。说明如下：在一个(n,k)线性分组码中，为了达到最小距离dmin，所需的校验位数目必须满足不等式：(5.58)其中,q是字符集大小。对二进制编码来说，式(5.58)可表示为在dmin/n≤1/2而n→∞的极限情况下，式(5.58)简化为(5.59)最后一个紧的最小距离上边界是埃利斯（Elias，1968年）发现的，以渐近线形式表示为(5.60)式中,参数A与码率有关，两者之间的关系式为(5.61)(n,k)分组码最小距离的下边界同样存在，特别是具有归一化最小距离的二进制分组码，它们渐近地满足不等式:(5.62)式中，α通过下列等式与码率建立联系:(5.63)这个下边界是吉尔伯特（Gilbert，1952年）和乌沙莫夫（Varsharmov，1957年）提出的下边界的一个特例，适用于非二进制和二进制分组码，简称V-G限。上述三个性能限中，前两个是必要条件，即想让dmin达到某值，n－k必须大于某值，或者说对于一定冗余度n－k，dmin最大能达到多少，所以Hamming限和Plotkin限给出的是上边界。V-G限是充分条件，它说明只要满足这个条件，就一定存在最小距离为dmin的码，所以V-G限给出的是下边界。然而，V-G限指出的“存在”并不一定能被找到。如图5-3所示，斜线区是可能实现的区域，双重斜线区是必能实现的区域。图5-3几种码限的比较5.6卷积码卷积码convolutionalcode）是1955年由P.Elias提出的一种记忆码，在二十世纪六七十年代开始广泛使用。它与分组码不一样，不仅是输入k0位信息码元的函数，还是前面m个k0位信息码元的函数。卷积码由n0、k0、m描述，n0为每组输出码元数，k0为每组输入码元数，k0/n0表示卷积码的编码效率，m称为编码约束度，表示k0组移位寄存器中最大的级数。由于卷积码各组之间相互有关，因此在卷积码的分析过程中，未找到像分组码那样有效的数学工具，性能分析比较困难，从分析上得到的成果不像分组码那样多，往往要借助计算机的搜索来寻找好码。【例5.5】一个简单的卷积码如图5-4所示。初始状态为00。设输入m=101100…，则输出与输入的关系为输入：1011000状态：00100110110100输出：11010010101100图5-4卷积码生成器卷积码的特点如下：（1）当前码分组输出不仅与当前信息分组输入有关，还与前面m个信息分组有关。（2）尚没有完善的数学工具有效地分析其结构和性能，必须借助计算机搜索来寻找好码。（3）研究表明：卷积码是渐近好码，相同码率、相同译码复杂性条件下，卷积码的性能要好于分组码。（4）卷积码仍是线性码，满足线性叠加关系。例5.5中的编码器一共有4个状态：00、10、01、11，分别记为：S0、S1、S2、S3，该编码器的状态转移图如图5-5所示。卷积码的状态图只表示编码状态之间的转移关系，无法表示状态转移与时间节拍的关系。为了表示状态转移与时间节拍的关系，引入卷积码的格图(TrellisDiagram)表示。卷积码的格图也称为篱笆图。图5-5状态转移图从初始状态出发，格图上的每一条路径都对应着一个输入信息序列所对应的编码序列。给定信息序列，可在格图上找到一条路径，进而得到所对应的编码序列。反过来，给定编码序列，也可在格图上找到一条路径，进而得到所对应的信息序列。例5.5中，(2，1，2)卷积码将状态转移图按时间节拍展开，如图5-6所示。图5-6(2,1,2)卷积码的网格图Shannon在证明Shannon第二编码定理时引用了如下3个基本条件：（1）采用随机性编译码。（2）编码长度趋于无穷，即分组的码组长度无限。（3）译码过程采用最佳的最大似然译码（ML）方案。在信道编码的研究与发展过程中，基本上以后两个条件为主要方向，如卷积码使得码长变得很长，并采用次最优的最大似然译码(viterbi算法)。对于条件（1），虽然随机选择编码码字可以使获得好码的概率增大，但是最大似然译码器的复杂度随码字数目的增大而加大，当