分组码与卷积信道码.ppt

分组码与卷积信道码读书报告,专业：通信与信息系统学号：0820080087姓名：顾杰,第八章：分组码与卷积信道码,本章主要内容：1、线性分组码2、卷积码3、*带限信道的编码调制-网格编码调制,什么是线性分组码？,若编码规则仅局限在本码组之内，即本码组的校验元仅与本码组的信息元相关，则称这类码为分组码。对于分组码，如果校验元和信息元的关系是一种线性关系，即能够用一线性代数方程表示，那么称这种分组码为线性分组码。,线性分组码的表示,线性分组码一般用符号(n,k)表示，其中n为码字的长度，k为每个码字中信息码元的数目。定义为线性分组码的码率，即,线性分组码的基本特性,设是某(n,k)分组码的任意两个码字，这两个码字的差别是用对应元素上不相同元素的个数来衡量的，这种度量称为码字间的Hamming距离，记作。个码字集合中的最小值称为该码的最小Hamming距离，用表示。定义一个码字中所有非零元素的个数为该码字的Hamming重量。线性分组码的最小Hamming距离等于最小Hamming重量。,线性分组码的生成矩阵和奇偶校验矩阵,在(n,k)线性分组码中，假设为编码器的输入信息码元序列，为编码器的输出序列，则编码器的输入输出关系可以表示为：式中，G为该线性分组码的生成矩阵。任何矩阵都可以表示成生成矩阵行向量的线性组合。生成矩阵可化成“系统形式”：,线性分组码的生成矩阵和奇偶校验矩阵,校验矩阵常用符号H表示，一种码的校验矩阵等于该码的对偶码的生成矩阵，因此对于(n,k)线性分组码，它的校验矩阵H和生成矩阵G满足这里的0代表一个由全零元素组成的维矩阵。假定(n,k)线性分组码是系统码，则其校验矩阵可表示为：式中为P的转置矩阵。,几种特殊的线性分组码,Hamming码Hadamard码Golay码,循环码,在线性分组码中，有一种重要的码称为循环码。它除了具有线性分组码的一般特点外，还具有循环性：循环码中任一码字的码元循环移位（左移或右移）后仍是该码的一个码字。其编码和译码的电路较简单，且检、纠错能力较强，目前已成为研究最深入、理论最成熟、应用最广泛的一类线性分组码。,循环码,理论研究时常用多项式来表示循环码，即有：式中：为循环码的任一码字。对于二进制码，多项式的每个系数不是0就是1。可以用一个n-k次的生成多项式产生一个循环码。(n,k)循环码的生成多项式一定是多项式的因子，其通式为：,循环码,定义一个消息多项式如下：这里代表k位信息比特。则由该k位信息比特生成的码字为：可以证明上式满足循环特性。BCH是循环码中一种重要的码型，能够纠正多比特错误。,线性分组码的最佳软判决译码,线性分组码的最佳软判决译码是通过使用匹配率滤波器作为最佳接收机并后接一个译码器实现的，译码器用来生成与M种码字对应的M个判决变量。令表示发送任一指定码字后匹配滤波器的n个输出取样。假设信号采用BPSK传输，则当码字的第j比特是1时：当码字的第j比特是0时：其中表示传输码字的一个比特所需的信号能量，变量表示取样瞬间的高斯白噪声。,线性分组码的最佳软判决译码,根据已知的M中可能发送的码字和接收到值，最佳译码器形成M个相关度：式中：便是第i个码字第j个位置上的比特。最佳译码器选择相关度均值最大的码字作为译码输出。最佳软判决译码的算法比较简单，但当码字数量很大时计算量就会变得无法接受，巨大的计算量降低了其在工程中适用度。,线性分组码的硬判决译码,针对软判决译码巨大的计算量，硬判决译码将模拟样值量化，然后用数字方式实现译码，这种方法的一种实现方式是最小距离译码，也称最大似然译码。译码方案：来自解调器的与接收码字对应的n个比特被送往译码器，译码器将接收的码字和M种可能发送的码字进行比较，把与接收码字汉明距离最小的判决为译码码字。,线性分组码的硬判决译码,使用校验矩阵H是一种有效的硬判决译码方法。假定是发送码字，Y是解调器输出的接收码字，一般Y可以表示为：其中，e代表一个任意的二进制差错矢量，那么式中，(n-k)维矢量S叫做差错图案的伴随式。由于S,H,Y是可知的，所以最终可以求出发送码字。,硬判决译码和软判决译码的性能比较,软判决译码和硬判决译码码字差错概率比较软判决译码差错概率上边界：硬判决译码差错概率精确值：在范围内，硬判决译码和软判决译码的码字差错概率性能约相差2dB，且软判决译码性能较好。,硬判决译码和软判决译码的性能比较,软判决译码和硬判决译码单位比特最小信噪比比较在码率趋近于零的极限时，硬判决译码和软判决译码的信噪比值相差约为2dB。随着码率的增大，两种译码技术的单位比特最小信噪比差值越来越小，当时，差值约为1.5dB。,卷积码的定义,线性码分为分组码和卷积码，卷积码又称连环码，由埃里亚斯于1955年首次提出。若本码组的校验元不仅与本码组的信息元相关，而且还与本码组相邻的前几个码组的信息元相关，则称这类码为卷积码。,卷积码的表示,卷积码一般用符号表示，称m为编码存贮，它表示输入信息子组在编码器中滞留的单元时间；称m+1为编码约束度，表示编码过程中相互约束的子码个数；称为编码约束长度，表示编码过程中互相约束的码元个数。,卷积码的描述方法,解析表示法1、离散卷积法2、生成矩阵法3、码多项式法图形表示法1、树图法2、网格图法3、状态图法,卷积码的树图表示,码率为1/3，K=3卷积码的树图,卷积码的网格图和状态图表示,码率为1/3，K=3卷积码的网格图,码率为1/3，K=3卷积码的状态图,卷积码的编码,卷积码编码器,卷积码的译码,卷积码有三种主要的译码方法：序列译码、门限译码和最大似然译码。1957年伍成克拉夫(Wozencraft)提出了一种有效的译码方法，即序列译码。1963年梅西(Massey)提出了一种性能稍差，但比较实用的门限译码方法。1967年维特比(Viterbi)提出了最大似然译码法，它又称为维特比译码。门限译码是一种代数译码法，序列译码和维特比最大似然译码都是概率译码。代数译码利用编码本身得代数结构进行解码，并不考虑信道的统计特性。比如门限译码，它以分组码理论为基础，其主要特点是算法简单，易于实现，但是它的误码性能要比概率译码差。它的译码方法是从线性码的监督子出发，找到一组特殊的能够检查信息位置是否发生错误的方程组，从而实现纠错译码。概率译码的基本思想是：把已经接收到的序列与所有可能的发送序列相比较，选择其中汉明距离最小的一个序列作为发送序列。维特比译码是目前用得较多的一种译码方法。它是一种最大似然译码，其译码的复杂性均随m按指数增长。最大似然译码对存储器级数较小的卷积码很容易实现，被广泛地应用于现代通信中。随着大规模集成电路技术的发展，对存储器级数较大的卷积码也可以采用最大似然译码。目前维特比译码已经得到了广泛的应用。,卷积码的最佳译码-维特比算法,不像分组码那样有固定的长度n，卷积码基本是一个有限状态机，因此它的最佳译码器是一个最大似然序列估计器。卷积码的译码就是遍历网格图找出最可能的序列。根据解调器后的译码器执行软判决或硬判决，遍历网格图时所用的度量可以是Hamming距离，也可以是欧氏距离。,维特比译码算法的实现,基本原理：译码器将接收到的序列和所有可能的发送序列作比较，选择其中汉明距离最小的序列当作是现在的发送序列。例：假设卷积码为(n,k,m)=(3,1,2)码现在的发送信息位为1101为了使移存器中的信息位全部移出，在信息位后面加入了3个“0”，即1101000编码后的发送序列：111110010100001011000接收序列：111010010110001011000(红色为错码)对于(3,1,2)卷积码，发送序列的约束长度，所以首先需考察3个信息段，即考察接收序列的前3n=9位“111010010”。,维特比译码算法的实现,解码第1步由网格图可见，沿路径每一级有4种状态a,b,c和d。每种状态只有两条路径可以到达。故4种状态共有8条到达路径。比较网格图中的这8条路径和接收序列之间的汉明距离。例如，由出发点状态a经过3级路径后到达状态a的两条路径中上面一条为“000000000”。它和接收序列“111010010”的汉明距离等于5；下面一条为“111001011”,它和接收序列的汉明距离等于3。,维特比译码算法的实现,将这8个比较结果列表如下：比较到达每个状态的两条路径的汉明距离，将距离小的一条路径保留，称为幸存路径。这样，就剩下4条路径了，即表中第2,4,6和8条路径。,维特比译码算法的实现,解码第2步：继续考察接收序列中的后继3个比特“110”计算4条幸存路径上增加1级后的8条可能路径的汉明距离。计算结果列于下表中。表中总距离最小为2，其路径是abdc+b，相应序列为111110010100。它和发送序列相同，故对应发送信息位1101。,维特比译码算法的实现,按照上表中的幸存路径画出的网格图示于下图中。图中粗线路径是距汉明离最小(等于2)的路径。,维特比译码算法的实现,在编码时，信息位后面加了3个“0”。若把这3个“0”仍然看作是信息位，则可以按照上述算法继续解码。这样得到的幸存路径网格图示于下图中。图中的粗线仍然是汉明距离最小的路径。,维特比译码算法的实现,若已知这3个码元是（为结尾而补充的）“0”，则在解码时就预先知道在接收这3个“0”码元后，路径必然应该回到状态a。而由图可见，由于只有两条路径可以回到a状态，所以这时上图可以简化成：,维特比译码算法的实现,在上例中卷积码的约束长度为N=3，需要存储和计算8条路径的参量。由此可见，维特比算法的复杂度随约束长度N按指数形式增长。故维特比算法适合约束长度较小的编码。对于约束长度大的卷积码，可以采用其他解码算法。,卷积码软判决译码的差错概率,加性高斯白噪声信道中