通信原理 CH8编码课件.ppt

通信原理,第八章 差错控制编码,2/45,差错控制编码,数字通信系统,数字通信系统的主要指标是有效性和可靠性提高可靠性的措施 针对加性干扰调制解调方式、增大发射功率、加强天线方向性、提高接收机灵敏度等信道编码（差错控制编码）信道编码用适合信道传输的码进行传输，或对源码进行重编码，使不带规律性(或规律性不强)的数字信号变成带上规律性(或加强规律性)的数字信号信道译码器则利用这些规律性来鉴别是否发生错误，或进而纠错信道编码与信道的统计特性有关,在信息序列中加入监督码元,3/45,差错控制编码,信道根据加性干扰引起错码的分布规律进行分类,随机信道信道中错码是随机的, 且统计独立；（如高斯白噪声引起错码）突发信道信道中错码成串集中出现；（如脉冲干扰引起错码）混合信道信道中同时存在随机错误和突发错码，且都不能忽略不计,常用的差错控制技术,检错重发,前向纠错,反馈校验法,不同类型的信道应该采用不同的差错控制技术,（典型为ARQ）,检错删除,4/45,本章的主要内容,8.1 纠错编码的基本原理8.2 常用的简单编码8.3 线性分组码8.4 循环码8.5 卷积码,5/45,本章的主要内容,8.1 纠错编码的基本原理8.2 常用的简单编码8.3 线性分组码8.4 循环码8.5 卷积码,6/45,8.1 纠错编码的基本原理,许用码组中，只要错一位(不管哪位错)，就是禁用码组，故这种编码能发现任何一位出错，但不能发现的二位出错，二位出错后又产生许用码。,其中的任一码组在传输中若发生一个或多个错码，就会变成另一信息码，接收端无法发现错误。,这样的码组也不能纠正错误，因为“晴”“雨”“阴”错一位，都可能变成“100”,若把8种组合（3位编码）中，只取2种为许用码，其它6种为禁用码，则可纠错,例：收到禁用码组“100”时，如认为只有一位错，则可判断此错码发生在第1位，从而纠正为“000”(晴)，因为“111”(雨)发生任何一个错误都不会变成“100”。,信息位,监督位,这种将信息码分组，为每组信码附加若干监督码的编码集合，称为分组码。,信息位,监督位,7/45,8.1 纠错编码的基本原理,几个重要的参数,分组码一般用符号 (n,k) 表示，k是每个码组二进制信息码元的数目，n是编码组的总位数，又称为码组长度（码长）。n-k=r为每码组中的监督码元数目，称监督位数目。,码重：在分组码中， “1”的数目称为码组的重量，简称码重。,例如，码组（1 1 0 1 0），码长 n =5，码重为3。,码距：把两个码组对应位不同的数目称为这两个码组的距离，简称码距，又称汉明（ Hamming ）距离。,例如，码组（1 1 0 0 0）与（1 0 0 1 1）的距离为 3。,最小码距：码组集合中，全体码组之间的距离的最小值称为最小码距(d0)。,8/45,圆上离 B 距离最近的码组是A 。,8.1 纠错编码的基本原理,分组码的检错、纠错能力与最小码距的关系,分组码能检测 e 个错码，所要求的最小码距 d0 ？,设有两个许用码A、B，它们的码距为d0。,若 A 发生 e 个错误，则得到的码组与A的距离为e，即该码组落在以A为圆心，半径为 e 的圆上。,若要译码器不将A 错判成B，必须有：,为检测 e 个错码，要求最小码距 d0 应不小于 e+1,9/45,8.1 纠错编码的基本原理,分组码能纠正 t 个错码，所要求最小码距 d0 ？,设有两个许用码A、B，它们的码距为d0。,若 A 发生 t 个错误，则得到的码组与A的距离为t，即该码组落在以A为圆心，半径为 t 的圆上。,这时，离 B 距离最近的码组是A 。,根据最大似然的译码准则，要想使译码器将A正确译成A，必须A 离A比离B近。,为纠正 t 个错码，要求最小码距 d0 应不小于 2t+1,分组码的检错、纠错能力与最小码距的关系,10/45,8.1 纠错编码的基本原理,分组码能纠正 t 个错码，同时检 e 个错码，所要求的最小码距 d0？,设有两个许用码A、B，它们的码距为d0。,若 A 发生 e 个错误，则得到码组落在以A为圆心，半径为 e 的圆上。这时，离 B 距离最近的码组是A 。,A离B的距离必须至少为t+1，否则， A将进入B的纠错能力范围内，而被错纠为B。,为纠正 t 个错码，同时检测 e 个错码，最小码距 d0 应不小于 e+t+1,分组码的检错、纠错能力与最小码距的关系,在某些情况下，要求对于出现较频繁但错码数很少的码组，按前向纠错方式工作，以节省反馈重发的时间。同时又希望对一些错码数较多的码组，在超过该码的纠错能力后，能检测出来，再按检错重发方式工作。这种工作方式称为纠检结合。,11/45,8.1 纠错编码的基本原理,结论：分组码纠错、检错能力决定于最小码距d0,检错能力：,纠错能力：,能检一位错码,能检 2 位错码,能纠 1 位错码,12/45,8.1 纠错编码的基本原理,纠错编码的效用,设随机信道中发送“0”、“1”时的错误概率均为 p (p1)，则在码长为 n 的码组中有r 位发生错码的概率为：,可见，采用纠错编码，即使仅能纠正（或检测）码组中 12 个错误，也可以使误码率下降几个数量级。,13/45,本章的主要内容,8.1 纠错编码的基本原理8.2 常用的简单编码8.3 线性分组码8.4 循环码8.5 卷积码,14/45,8.2 常用的简单编码,奇偶校验码,奇偶校验码分为奇校验码、偶校验码两种编码规则 无论信息位有多少，只有一位监督位，且对an-1 an-2 a1 a0的码组，有如下监督关系：,如：对信息码组 11001 进行偶校验编码,校验位,信息位,检错能力能检测奇数位错误。,1,15/45,8.2 常用的简单编码,二维奇偶校验码,行监督位,列监督位,检纠错能力能检测奇数位错误及部分偶数位错误（如：4位错码构成矩形不能检测）当码组中仅在一行有奇数个错误时，能够确定错码的位置，从而实现纠错适于检测突发错误,又称方阵码，将奇偶校验码按行组成矩阵，然后在列方向增加第二维奇偶校验位。,16/45,8.2 常用的简单编码,恒比码,每个码组均含有相同数目的“1”和“0”。由于“1”的数目与“0”的数目之比保持恒定，所以称为恒比码。,例如，我国电传机传输阿拉伯数字时，用5位代码表示，每个码组的长度为5，其中恒有3个“1”，称为 “5中取3” 恒比码。,主要优点 简单，适于用来传输电传机或其它键盘设备产生的字母和符号。,检错能力 能检测所有奇数个错误和部分偶数个错误（除去“0”、“1”对换外的偶数个错误都可检测）。,17/45,8.2 常用的简单编码,正反码,正反码的监督位与信息位数目相同。监督码元与信息码元相同或相反，由信息码中“1”的个数决定。,正反码是一种简单的能纠错的编码，长度为10的正反码具有纠正1位错码的能力，并能检测全部两位以下的错码和大部分两位以上的错码。,电报通信中的正反码,信息位段有奇数个1 1 1 0 0 1 1 1 0 0 1 （监督位与信息位重复）,信息位段有偶数个1 1 0 0 0 1 0 1 1 1 0 （监督位是信息位反码）,18/45,本章的主要内容,8.1 纠错编码的基本原理8.2 常用的简单编码8.3 线性分组码8.4 循环码8.5 卷积码,19/45,8.3 线性分组码,基本概念,代数码和线性分组码建立在代数关系基础上的编码称代数码 可用线性方程组（代数关系）表述码的规律性的分组码称为线性分组码,编码与监督偶校验码在接收端实际上计算代数关系式 S = an-1an-2a0如果监督位增加到二位，就能增加一个类似于偶校验码的新的监督式两个监督式的两个校正子有4种可能的组合：00, 01, 10, 11。若用1种组合表示无错，其余3种组合就可以用来表示一位错码的3种不同位置。同理，r个监督式能指示一位错码的2r-1个可能位置。对于线性分组码(n,k)，监督位数r=n-k，如果希望用r个监督关系式指示一位错码的n种可能的位置，则要求,监督关系式,校正子,只能发现错误，不能指示错误位置,汉明码的诞生,20/45,8.3.1 汉明码,基本概念,线性分组码(n,k)，监督位r=n-k，若满足n=2r-1，则称其为汉明码汉明码是能够纠正一位错码且编码效率最高的一种线性分组码。监督关系式的构造以(n,k)=(7,4)的汉明码(r=3)为例，现规定3个校正子的组合,监督位的取值应使： S1S2S3=000，所以监督关系式为,用码率R衡量，Rk/n,21/45,8.3.1 汉明码,编码原理,给定信息位后，根据监督关系可以算出监督位。,接收端收到码组后，先计算出校正子S1S2S3，再按规定判断有无错码或错码位置，最后纠正错码。,a3出错,22/45,8.3.1 汉明码,(7,4)汉明码,最小码距 d0=3,检错能力 e=d01=2,纠错能力 t=int(d01)/2=1,编码效率,23/45,8.3.2 线性分组码的一般原理,监督矩阵和生成矩阵线性分组码的编码,将上述汉明码(7, 4)的监督关系式改写,“+”均为模2加,rk 阶矩阵P,rr 阶单位方阵Ir,具有PIr形式的H 矩阵称为典型监督矩阵,H,AT,监督矩阵,24/45,8.3.2 线性分组码的一般原理,监督矩阵和生成矩阵,把监督关系式改写为：,kr 阶矩阵Q Q=PT,kk 阶单位方阵Ik,具有IkQ形式的G 矩阵称为典型生成矩阵,GT,生成矩阵,这种前k位是信息码元，后r位是监督码元(附加于信息码元之后)的码称为系统码。,25/45,8.3.2 线性分组码的一般原理,校正子S（伴随式） 线性分组码的译码,设发送码组为：A=an-1,an-2,a1,a0 接收码组为：B=bn-1,bn-2,b1,b0,发送码组与接收码组之差(称错误图样)为：E = AB = en-1,en-2,e1,e0,模2操作,bi=ai 时, ei=0, 正确biai 时, ei=1, 错码,令S=BH T，S为校正子，也称伴随式,由此可见，校正子S与错误图样E 间有确定的线性变换关系，若S和E之间一一对应，则S将能代表错码的位置。,接收端译码器的任务根据接收码组 B 计算校正子 S=BHT；从校正子S 确定错误图样；从接收到的码字中减去错误图样E。 线性分组码具有封闭性,码集中任两个码字模二加后仍在码集中,26/45,本章的主要内容,8.1 纠错编码的基本原理8.2 常用的简单编码8.3 线性分组码8.4 循环码8.5 卷积码,27/45,8.4 循环码,循环码的特点,循环码是一种分组的线性系统码,循环码除了有线性分组码的封闭性外，还有循环性,码集中任一码循环移位后仍在码集中,是一类重要的线性分组码，比较方便用移位寄存器实现编码和译码,(7, 3)循环码的码集通常为了研究方便，我们用代数多项式来表示码字。,右移1位,28/45,8.4.1 码多项式,码多项式的基本概念用以表示码字的一个代数多项式称为码多项式。,多项式的系数ai对应于码元的值。,码左移一位，对应于码多项式乘以 x,码多项式的按模运算,若一任意多项式F(x)被一个n 次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即,则称R(x)为F(x) 关于N(x)按模运算的结果，,例,最高次幂为x n-1,左移一位,29/45,8.4.2 生成多项式与生成矩阵,生成多项式在(n,k)循环码码集所对应的码多项式中，唯一的一个常数项不为0的(n-k)次多项式g(x) 称为该循环码的生成多项式,例：(7,3)循环码的生成多项式,循环码的码多项式都是生成多项式的倍式,生成矩阵G将生成多项式逐次移位，得到k个线性无关的码多项式，将它们构成矩阵，称为生成多项式矩阵G(x)，其系数就是生成矩阵G。,例：(7,3)循环码的生成多项式矩阵和生成矩阵,30/45,8.4.3 如何寻找(n,k)循环码的生成多项式,对于(n,k)循环码，将xn+1因式分解(系数模二运算)，其中最高幂次数为r=n-k，且常数项为1的因子多项式，就是(n,k)循环码的生成多项式。,例：x7+1因式分解,为了求(7,3)循环码的生成多项式，就要在上式中找一个最高幂次数为r=n-k=4，且常数项为1的因子。这样的因子有两个：,这两个多项式都可以作为生成多项式用，但不同生成多项式所产生的循环码码组也不同。,31/45,8.4.4 系统循环码的编码电路,若k位信息码为： M=mk-1,mk-2,m1,m0，则信息码多项式为：,码多项式,系统码（前k 位是信息码元，后r 位是监督码元）的生成矩阵是典型生成矩阵，具有IkQ的形式。由生成多项式矩阵直接得到的生成矩阵不具有这样的形式，不是系统码。,r(x)的最高次是r 1，g(x)的最高次是r，所以，r(x) mod g(x)=r(x),r(x)是监督码多项式,32/45,8.4.4 系统循环码的编码电路,编码电路原理,以(7,3)循环码为例,移位寄存器,除法电路，完成mod g(x)操作,工作步骤, 所有移存器清零；, 开关S 倒向下，输入信码一方面送入除法电路进行运算，一方面直接输出。, 在信息位全部进入除法器后，开关转向上，切断反馈线，除法电路停止，同时输出端接到移存器，将除法电路计算得到的监督位依次输出。,33/45,8.4.5 系统循环码的译码电路,伴随多项式,以(7,3)循环码为例,工作步骤：, 所有移存器清零；, 假定接收码组为“1000101”，此码组进入除法电路后，移位寄存器各级的状态变化过程如左表。当此码组的7个码元全部进入除法电路后，除法结果（自右向左）为“0100”，表明接收码组的第二位是错码。, 保持输入恒为“0”，将缓冲寄存器中暂存的信码逐位移出。在信码的第2位移出时，反馈移位寄存器的状态为“1000”，与门输出“1”，纠正错码，并对寄存器清零。,一般情况下，码组不是孤立的，因此需要两套除法电路。,34/45,本章的主要内容,8.1 纠错编码的基本原理8.2 常用的简单编码8.3 线性分组码8.4 循环码8.5 卷积码,35/45,8.5 卷积码,卷积码的概念又称连环码，其监督位由当前码组及其前 N1 个码组的信息位决定，即由 N 个码组的信息位决定卷积码记作(n,k,N)n码组的码元数，即码字的字长；k一个码组中的信息位的个数；N卷积码的编码约束度（nN称为编码约束长度），即确定一个监督位所关联的码组的组数；通常k和N较小。卷积码和分组码的比较分组码的监督位由当前码组的信息位决定；而卷积码的监督位由当前码组及其前 N1 个码组的信息位决定卷积码利用了前后码段之间的相关性，在相同码率、设备复杂性条件下，其纠错性能优于分组码,36/45,8.5 卷积码,编码原理 以(3,1,3)卷积码为例,码长：n=3码组中信息位个数：k=1码组中监督位个数：r =2码的编码约束度：N=3，所以有二级移存器,信息位y1j的生成多项式为：,监督位y2j的生成多项式为：,监督位y3j的生成多项式为：,寄存器初始状态：“000”,输入序列：,输出序列：,卷积码的编码可以用图形来描述，如树状图、网格图和状态图等,37/45,8.5 卷积码,卷积码的树状图,(3,1,3)卷积码编码器有2个移位寄存器。对应有四个状态：状态“a”：M1M2=00；状态“b”：M1M2=01；状态“c”：M1M2=10；状态“d”：M1M2=11。,每输入一个码元，2个移位寄存器的状态就发生一次变化，同时输出一个码组（3位）。规定：输入“0”，状态变化走上支路；输入“1”，状态变化走下支路。,输入序列：,输出序列：,38/45,8.5 卷积码,卷积码的网格图,卷积码的树状图对第 j 个输入信息比特，有 2j 条支路。j越大，图的纵向尺寸越大。且在 j N 时出现重复现象。,网格图把码树中具有相同状态的节点合并在一起。码树中的上支路用红线表示，下支路用蓝线表示。,网格图中有2N-1种状态，从第N个节点开始，图形开始重复,输入序列：,输出序列：,39/45,8.5 卷积码,卷积码的状态图,当网格图达到稳定状态后，取出两个节点间的一段网格图，得到状态转移图。,把目前状态与下一节拍状态合并，得卷积码的状态图。,40/45,8.5 卷积码,生成矩阵与生成多项式,生成多项式与生成序列,将生成序列按以下顺序排列得生成矩阵,41/45,8.5 卷积码,基本生成矩阵,截短生成矩阵,基本生成矩阵决定卷积码，由基本生成矩阵可得到生成矩阵，也可得到生成多项式，即可画出编码器框图。,42/45,8.5 卷积码,基本监督矩阵与监督矩阵,基本生成矩阵的一般形式,基本监督矩阵的一般形式,截短监督矩阵,监督矩阵,43/45,8.5 卷积码,卷积码的译码大数逻辑译码法，利用码代数结构的代数译码。 序列译码，基于码树图结构上的一种准概率译码。Viterbi（VB）算法，基于码的网图基础上的一种最大似然译码算法，是一种最佳概率译码。,44/45,作业,P.371 11-5P.371 11-7P.372 11-13,45/45,本章的内容小结,8.1 纠错编码的基本原理几个重要的参数、分组码的检错纠错能力与最小码距的关系8.2 常用的简单编码奇偶校验码、二维奇偶校验码、恒比码、正反码8.3 线性分组码汉明码线性分组码的一般原理（监督矩阵和生成矩阵线性分组码的编码、线性分组码的译码）8.4 循环码码多项式、生成多项式与生成矩阵、如何寻找(n,k)循环码的生成多项式、系统循环码的生成矩阵、编码电路、译码电路8.5 卷积码,