《通信原理 CH11 差错控制编码和线性分组码课件.ppt》由会员分享，可在线阅读，更多相关《通信原理 CH11 差错控制编码和线性分组码课件.ppt（63页珍藏版）》请在三一办公上搜索。
1、第十一章 差错控制编码和线性分组码,2,主要内容和重点,差错控制编码的基本概念线性分组码 性质、基本原理校正子监督矩阵生成矩阵汉明码循环码概念及性质生成多项式生成矩阵与监督矩阵编码器,3,2.1 引言,为什么要引入差错控制编码？什么是差错控制编码（信道编码）？差错控制编码的3种方式 信道发生差错的模式差错控制编码的基本原理差错控制编码的分类编码信道及香农编码定理,4,2.1 引言,为什么要引入差错控制编码？在实际信道上传输数字信号时，由于信道传输特性不理想及加性噪声的影响，接收端所收到的数字信号不可避免地会发生错误 为了在已知信噪比情况下达到一定的误比特率指标，应该合理设计基带信号，选择调制解
2、调方式，采用时域、频域均衡，使误比特率尽可能降低但若误比特率仍不能满足要求，则必须采用信道编码（即差错控制编码），将误比特率进一步降低,5,2.1 引言,什么是差错控制编码差错控制编码的基本思路：在发送端将被传输的信息附上一些监督码元，这些多余的码元与信息码元之间以某种确定的规则相互关联（约束）接收端按照既定的规则校验信息码元与监督码元之间的关系，一旦传输发生差错，则信息码元与监督码元的关系就受到破坏，从而接收端可以发现错误乃至纠正错误差错控制编码所要解决的问题：各种编码和译码方法,6,2.1 引言,差错控制的三种方式检错重发（ARQ）在接收端根据编码规则进行检查，如果发现规则被破坏，则通过反
3、向信道要求发送端重新发送，直到接收端检查无误为止ARQ系统的重发机制：停发等候重发、返回重发和选择重发需要反馈信道，效率较低，但是性能很好,7,2.1 引言,差错控制的三种方式（续）前向纠错（FEC） 发送端发送能纠正错误的编码，在接收端根据接收到的码和编码规则，能自动纠正传输中的错误不需要反馈信道，实时性好，但是随着纠错能力的提高，编译码设备复杂,8,2.1 引言,差错控制的三种方式（续）混合方式结合FEC和ARQ：在纠错能力范围内，自动纠正错误，超出纠错范围则要求发送端重新发送,9,2.1 引言,信道发生差错的模式随机差错：差错的出现是随机的，差错出现的位置是随机分布的一般由信道的加性随机
4、噪声引起这种信道称为随机信道 突发差错：差错的出现是一连串出现的。这种情况如移动通信中信号在某一段时间内发生衰落，造成一串差错；光盘上的一条划痕等等这样的信道称之为突发信道 混合差错：既有突发错误又有随机差错的情况这种信道称之为混合信道,10,2.1 引言,差错控制编码的基本原理 以差错重发编码来阐述差错编码在相同的信噪比情况下为什么会获得更好的系统性能？ 例1：假设发送的信息0、1等概，采用2PSK方式，则最佳接收的系统误比特率为 ，现假设如果将信息0编码成00，信息1编码成11，则在接收端：如果发送00，收到01、10，知道发生了差错，要求发送端重新传输，直到传送正确为止只有当收到11时，
5、我们才错误地认为当前发送的是1 因此在这种情况下发生译码错误的概率是 同理，如果发送的是11，只有收到00时才可能发生错误译码，因此在这种情况下发生译码错误的概率是故采用00、11编码的系统误比特率为,11,2.1 引言,差错控制编码的基本原理（续） 依此类推，可知：采用000、111编码的ARQ系统误比特率是多少？采用0000、1111编码的ARQ系统误比特率是多少？例2，如例1，如果0、1采用00000、11111编码，在接收端用如下的译码方法，每收到5个比特译码一次，采用大数判决，即5个比特中0的个数大于1的个数则译码成0，反之译码成1；不采用ARQ方式。那么，这种编码方式就变成了纠错编
6、码由于传输错误当接收端收到11000，10100，10010，10001，01100，01010，01001，00110，00101，00011中的任何一种时，都可以自动纠正成00000课外题：请计算在这种情况下的系统性能上述例1、例2的编码方式叫重复码,12,2.1 引言,差错控制编码的基本原理（续） 例3，2PSK系统中误比特率与Es/N0有关我们看到，重复码中假设传输时每个符号的Es/N0相等，因此才得到以上的性能分析对比但是如果我们以Eb/N0的指标进行比较，则我们看到例1的 例2的 如果要求各系统在Eb/N0相同的情况下进行比较（n重复码中用了n倍能量来传输一个比特，从每个比特能量的
7、角度来看），则可看到这2种系统性能相近（即获得相近的编码增益）,13,2.1 引言,差错控制编码的基本原理（续）当x1有2PSK系统： 2重重复码： 编码增益=,14,2.1 引言,差错控制编码的分类根据差错控制编码的功能不同检错码、纠错码、纠删码（兼检错、纠错）根据信息位和校验位的检验关系线性码（存在线性关系）和非线性码按信息码元在编码后是否保持原来的形式系统码：保持不变非系统码：信息码元改变了原有的信号形式按纠正错误的类型：纠正随机错误的码：用于随机错误的信道纠正突发错误的码：用于突发信道,15,2.1 引言,差错控制编码的分类（续）根据信息码元和监督码元的约束方式：分组码：监督码元仅与本
8、码组的信息码元有关卷积码：监督码元还与前面码组的信息码元有约束关系分组码：将k个信息比特编成n个比特的码字，共有2k个码字。所有个码字组成一个分组码。传输时前后码字之间毫无关系 卷积码：也是将k个信息比特编成n个比特的码字，但是前后的N个码字之间相互关联 编码速率=平均每个码字所携带的信息比特率,16,2.1 引言,编码信道所谓的编码信道就是将调制解调包括在信道内的一种模型上的等效。 即如果研究编码和译码，完全可以将调制、解调与信道合起来等效成一个等效的信道，这种信道就称之为编码信道,17,2.1 引言,编码信道（续）根据调制解调的不同输入和输出具有不同的类型 离散无记忆对称二进制输入二进制输
9、出信道（BSC）这种情况相应于2进制调制解调+判决离散无记忆二进制输入多进制输出信道对应于2进制输入，量化后输出的情况，即所谓的软译码离散无记忆多进制输入多进制输出对应于多进制输入、量化后输出离散无记忆二进制输入连续输出对应于二进制输入，模拟输出（未判决、未量化）,18,2.1 引言,香农有扰离散信道的编码定理对于一个给定的有扰信道，若信道的容量为C，只要发送端以低于C的速率R发送信息（R为编码器的输入二进制码元速率），则一定存在一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值，表示为其中E(R)称为误差指数 结论：n和R一定情况下，为减小P，可增大C 在C及R一定的情况
10、下，增加n，可以 使P指数下降。从实际的角度看，这时 设备复杂性和译码延时也随之增加,E（R） C0 C1 C2 R,19,2.2 纠错编码的基本原理,主要内容码重、码距最小码距码的纠错、检错性能,20,2.2 纠错编码的基本原理,分组码将k个比特编成n个比特一组的码字（码组），记为（n，k）码由于输入有 2k种组合，因此（n，k）码应该有2k个码字码重、码距码重：码字中1的个数。如码字11000的码重为2码距：码字C1与码字C2之间不同的比特数（又称汉明距）,21,2.2 纠错编码的基本原理,最小码距所用码字中任何两个码字之间的码距的最小值，用 dmin表示码的纠错、检错性能：由最小码距决定
11、 为了检测e个错误，要求最小码距为了纠正t个错误，要求最小码距为了纠正t个错误，同时检测e个错误，要求最小码距,22,纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越大，抗干扰能力就越强,2.2 纠错编码的基本原理,23,2.3 常用的简单编码,奇偶监督码（奇偶校验）设奇偶监督码的码字表示为： 则偶校验码： （即偶数个1） 奇校验码： （即奇数个1）可见这种码的最小码距为2，只能检1个错,24,奇偶监督码的编码可以用软件实现，也可用硬件电路实现 如果码组B无错，BA，则M0；如果码组B有单个（或奇数个）错误，则M1,2.3 常用的简单编码,25,2.3
12、常用的简单编码,二维奇偶监督码提高奇偶校验码对突发错误的检测能力 将若干奇偶校验码排成若干行，然后对每列进行奇偶校验，放在最后一行。传输时按照列顺序进行传输，在接收端又按照行的顺序检验是否差错 由于突发错误是成串发生的，经过传输后错误被分散（交织编码+奇偶校验） 移动通信中的信道衰落造成突发错误，因此传输前，先将输入的信息比特交织，将突发错误尽可能分散成随机错误，然后用其它编码方式来纠正随机的错误,26,2.3 常用的简单编码,恒比码每个码组中的1的个数都一样电传机传输汉字时每个汉字用4位阿拉伯数字表示，每个阿拉伯数字用5个比特的码字表示。由于阿拉伯数字只有10个，因此从32中可能的码字中挑出
13、 =10个1的个数为3的码字作为阿拉伯数字的编码方式译码可以采用查表方法，检错时检查1的个数是否为3一般用在电传、电报,27,2.3 常用的简单编码,ISBN国际统一图书编号国际图书的发行中，用编码的方式来防止书号在通信过程中发生错误 如通信原理的书号是ISBN 7-118-01429-X其中第一位数字“7”表示“中国”，“118”表示出版社，“01429”表示书名编号，最后一位“X”表示校验位（它是罗马数字10的表示）所采用的校验方式如下所示：7 1 1 8 0 1 4 2 9 X=107 8 9 17 17 18 22 24 33 437 15 24 41 58 76 98 122 155
14、 198 198 (模11)=0,28,2.4 线性分组码,差错编码的重点：各种编码和译码的方法主要内容性质基本原理校验矩阵（监督矩阵）生成矩阵校正子（伴随式）汉明码,29,2.4 线性分组码,定义：将信息码分组，为每组信息位附加若干监督位，且信息位和监督位间的关系可由线性方程组表示的编码即可用线性方程组表述码的规律性的分组码 线性分组码（n，k）的性质许用码字（组）为2k个定义线性分组码的加法为模2加，乘法为二进制乘法。即有1+1=0、1+0=1、0+1=1、0+0=0 1x1 = 1, 1x 0 =0, 0 x0 =0, 0 x1 =0且码字与码字的运算是各相应比特位上符合上述二进制加法运
15、算规则,30,2.4 线性分组码,线性分组码（n，k）的性质（续）群：集合G上定义了一种加法运算，如果该运算符合以下4条公理，则称G是该运算的一个群封闭性：任何a、b属于G，有a*b属于G单位元：G中存在一个元素e满足e*a=a有逆元：任何a属于G，存在b属于G满足a*b=e结合率成立：a*(b*c)=(a*b)*c线性分组码的性质：封闭性。任意两个许用码组的和仍是一个许用码组最小码距等于非零码的最小码重,31,2.4 线性分组码,基本原理(n, k)码：码长n，信息位数为k，则监督位数r=n-k校正子（伴随式）S：为了检测传输过程中是否有错，将接收到的码组代入监督方程式所得到的结果以（7，4
16、）线性分组码为例，说明（n，k）码的基本原理7码元a6a5a4a3a2a1a0，信息码元a6a5a4a3，监督码元a2a1a0校正子S1S2S3与信息码元及监督码元之间的关系为,32,2.4 线性分组码,基本原理（续）3个校正子可以指示23-1=7种错误图样，如表所示可知，（7，4）码可纠正一位错误在编码时a2a1a0应根据监督方程确定：,33,2.4 线性分组码,基本原理（续）由此可得16个许用码组,34,2.4 线性分组码,基本原理（续）接收端收到每个码组后，计算出S1、S2和S3，如不全为0，则查表确定误码的位置，予以纠正如，接收码组为0000011，可算得S1S2S3011，查表知a3
17、错（7，4）码：dmin=3，能纠正1个误码或检测2个误码(n, k)线性分组码：r=n-k个监督码元，有r个校正子，可以指示2r-1个误码图样当2r-1n（即2rk+r+1）时，就可纠正1位或1位以上的错误编码效率（编码速率）：k/n=(2r-r-1)/(2r-1)=1-r/n,35,2.4 线性分组码,校验矩阵（监督矩阵）监督码元与信息码元之间的关系可表示为监督方程形式，上例（7，4）码的监督方程为简记为 HAT0T 或 AHT0,36,2.4 线性分组码,校验矩阵（监督矩阵）（续）称H为监督矩阵设收到的码组为B，则校正子SHBT故可根据H及误码图样表构成差错控制译码器典型形式监督矩阵HP
18、 Ir 其中，P为rk阶矩阵，Ir为rr阶单位方阵各行线性无关非典型形式监督矩阵可以经过行运算化为典型形式由典型形式监督矩阵及信息码元可算出各监督码元,37,2.4 线性分组码,生成矩阵监督码元与信息码元之间的关系还可表示为生成方程形式上述（7，4）码的生成方程为称G为生成矩阵，由生成矩阵G可构造差错控制编码器,38,2.4 线性分组码,生成矩阵（续）典型生成矩阵GGIk Q 其中，QPT为kr阶矩阵，Ik为kk阶单位方阵PQT由典型生成矩阵G可以得到系统码各行线性无关非典型形式生成矩阵可以经过行运算化为典型形式,39,2.4 线性分组码,校正子（伴随式）发送码组A在传输过程中可能发生误码设接
19、收到的码组为Bbn-1 bn-2 b0则错误图样 E=B-A，或 B=A+E其中，E= en-1 en-2 e0校正子为S=BHT=(A+E)HT=AHT+EHT=EHTS与E间有确定的关系,40,2.4 线性分组码,汉明码上述方法构造的纠正单个错误的线性分组码特点码长：n2m1信息码位：k=2m-m-1监督码位：r=n-k=m最小码距：d=3纠错能力：t=1,41,2.5 循环码,概念、性质和多项式表示生成多项式生成矩阵与监督矩阵编码器,42,2.5 循环码,概念及性质线性分组码中最重要的一种子类，比较成熟特点代数结构清晰：有严格的代数理论基础性能较好：可纠随机错误和突发错误编译码简单：特殊
20、的代数性质有助于按照要求的纠错能力构造，并且简化译码算法易于实现：很容易用带反馈的移位寄存器实现目前的计算机纠错系统中广泛使用的线性分组码,43,2.5 循环码,概念及性质（续）例：设（7，4）汉明码C的校验矩阵和生成矩阵为 得到16个码组是：（1000101）（0001011）（0010110）（0101100）（1011000）（0110001）（1100010）（0100111）（1001110）（0011101）（0111010）（1110100）（1101001）（1010011）（1111111）（0000000）可以看到：如果Ci是C的码组，则它的左右移位都是C的码组，具有这种特
21、性的线性分组码称为循环码,44,2.5 循环码,概念及性质（续）循环码的性质：封闭性任何许用码组的线性和还是许用码组。由此性质可以得到：线性码都包含全零码最小码重就是最小码距循环性 任何许用的码组循环移位后的码组还是许用码组,45,2.5 循环码,概念及性质（续）多项式表示：目的：用代数理论的方法研究循环码的特性定义：码 的码多项式如下 其中，D为实变量、其幂次代表移位次数， GF（2）表示2元域，只有两种元素0、1，且0、1满足如下的运算规则：0+0=0，0+1=1，1+0=1，1+1=0 （加法）0 x0=0，0 x1=0，1x0=0，1x1=1。 （乘法） 例如：（1011000）的码多
22、项式为,46,左移一位左移 位,若 是长度为n的循环码组，则 在按模 进行运算后，也是一个循环码组，也就是 用 多项式除后所得之余式，即为所求的码组,2.5 循环码,47,2.5 循环码,生成多项式循环码完全由其码长n和生成多项式g（D）构成其中g（D）是一个能除尽Dn+1的r=n-k阶多项式阶数低于n并能被g（D）除尽的一组码多项式就构成一个（n，k）循环码即阶数小于或等于n-1且能被g（D）除尽的每个多项式都是循环码的许用码组 信息多项式为M(D),k 位，(k-1)次多项式 A(D)=M(D)g(D),48,2.5 循环码,生成多项式（续）例如，（7，4）循环码的生成多项式则阶数低于n-
23、1能被g（D）除尽的多项式为其中 ，i=0，1，2，3假设则对应的循环码多项式为故对应的循环码组为（1111111）,49,2.5 循环码,生成多项式的构造循环码多项式表示及循环性质 循环码中任何码组的循环移位还是许用码组，可以表示成码多项式的形式 定理一：码组 ，经过移位i位，得到码组 则可以证明： 即证明： 利用多项式的长除法：可以得证,50,2.5 循环码,生成多项式的构造（续）循环码多项式表示及循环性质 例：（7，4）循环码（1000101）的码多项式为 移位1位后变成 将它被 除，得到 因此，循环左移一位的余式为 其相对应的码组为（0001011），正好是（1000101）循环左移一
24、位的结果,51,2.5 循环码,生成多项式的构造（续）循环码多项式的构造定理二：（n，k）循环码的生成多项式g(D)一定是Dn+1的因式，即 反之，如果g(D)是一个n-k次多项式，且除尽Dn+1 ， 则此g(D)一定生成一个（n，k）循环码 证明：循环码的码组T（D）是g（D）的倍式，因此 而生成多项式g(D)本身也是一个码组，该码组的多项式次数为n-k次 由定理一，可以知道 也是循环码组 而 所以， 即g（D）是Dn+1的因式因式分解可以通过计算机分解的方式分解，也可以通过查表（已经作好的因式分解表）得到,52,2.5 循环码,生成多项式的构造（续）循环码多项式的构造例， 因此，（7，4）
25、循环码的生成多项式可以选择 或 而（7，3）循环码的生成多项式可以选择 或 练习：请验证以下结论（7，6）循环码的生成多项式为D+1，实际上就是简单的偶校验码（7，1）循环码的生成多项式为 ，实际上是7重重复码,53,2.5 循环码,生成矩阵根据循环码的码组多项式是生成多项式g（D）的倍式根据线性码的生成矩阵的特性，（n，k）码的生成矩阵实际上可以由（n，k）码中k个不相关的码组构成可以挑选出k个循环码组的码多项式形成非系统码的生成矩阵系统码的生成矩阵,54,2.5 循环码,生成矩阵非系统码的生成矩阵输入信息码元为 时， 相应的循环码组多项式为： 由上式得到的码组不是系统码,55,2.5 循环
26、码,生成矩阵系统码的生成矩阵系统码定义：（n，k）系统码的码组中前k个比特是信息比特，后n-k个比特是监督位问题：已知生成多项式g（D），如何构造系统码的生成矩阵？ 在系统码中，码组应该具备如下的形式： 同时有由上式可得 其中，r（D）的次数小于等于n-k-1实际上上式表示了如何生成系统码，即将信息码多项式升n-k次，然后以g（D）为模，求出余式r（D）,56,2.5 循环码,生成矩阵系统码的生成矩阵例： 已知（7，4）系统循环码的生成多项式为 求生成矩阵解：系统码的生成矩阵形式肯定是 因此选择信息多项式为 、1 将D3提升n-k=3次，得到D6 ，求D6除以g（D）的余式得到 因此，系统生成
27、矩阵为表示成矩阵形式，得到,57,2.5 循环码,监督矩阵由于g（D）能除尽Dn+1 ，即 （1式）这里， 称为生成多项式 h(D)称为监督多项式 由（1式）知道，,58,2.5 循环码,监督矩阵（续）所以，如果生成矩阵是 则监督矩阵为：可以看到，上述两者满足,59,2.5 循环码,监督矩阵（续）例如，已知（7，3）码的生成多项式为 求生成矩阵和监督矩阵解：监督多项式为 因此， 监督矩阵为 可以验证,60,2.5 循环码,编码器系统循环码的编码器（除法器电路）最容易实现的方式是将信息码多项式升n-k次幂后除以生成多项式，然后将所得余式置于升幂后的信息多项式后 例1：已知（7，4）系统循环码的生
28、成多项式g（D）= 若信息码为1001，求编码后的循环码 解：信息码多项式 因此，编码后的码组为（1001011）,61,2.5 循环码,编码器系统循环码的编码器（除法器电路）多项式除法可以用带反馈的线性移位寄存器来实现 例2：已知 信息码为 列出长除直式和除法电路的工作过程 解：除法器的寄存器初始值为000000，输入顺序为101100 10011011，经过6个时钟后，在第6时刻，开始计算长除式中的第一次除法，输出为商，寄存器中为余 可以从长除式看到，再经过8个时刻的计算可以得到该信息码被g（D）除的余式，在第14时刻，寄存器中的内容就是余式,62,2.5 循环码,编码器系统循环码的编码器（除法器电路）（续）故可通过该电路构造系统循环码的编码器电路如下,63,2.5 循环码,编码器循环码的译码用于纠错目的的循环码译码器原理：将接收到的码组进行除法运算，如果除尽，则说明正确传输如果未除尽，则在寄存器中的内容就是错误图样，根据错误图样可以确定一种逻辑，来确定差错的位置译码算法比较复杂，可参见其他参考书用于检错目的、然后用ARQ方式的循环码译码器原理：将接收到的码组进行除法运算，如果除尽，则说明传输无误如果未除尽，则表明传输出现差错，要求发送端重发用于这种目的的循环码经常被称为循环冗余校验码，即CRC码CRC码的编码、检错电路简单且易于实现，因此得到广泛的应用,
