差错控制编码(传媒05级).ppt

第8章 差错控制编码 第8章 差错控制编码 8.1 差错控制编码的基本概念 8.2 差错控制方式 8.3 差错控制编码分类 8.4 检错和纠错原理 8.5 几种常用的检错码 8.6 线性分组码 8.7 循环码 Date1 第8章 差错控制编码 8.1 差错控制编码的基本概念 不管是模拟通信系统还是数字通信系统，都存 在 因干扰和信道传输特性不好对信号造成的不良影 响。 它使模拟信号波形会发生畸变，一旦失真很难 纠正。因此，在模拟系统中只能采取抗干扰、防干 扰措施,尽量将干扰降到最低程度以保证通信质量 。 Date2 第8章 差错控制编码 在数字系统中，干扰也会使信号产生变 形，但一定程度的信号畸变不会影响接收， 因 为我们只关心数字信号的电平状态（是高电 平 还是低电平），而不太在乎其波形的失真。 也 就是说，数字系统对干扰或信道特性不良的 宽 容度比模拟系统大。 Date3 第8章 差错控制编码 数字通信系统除了可采取与模拟系统同样的 措 施抗干扰外，还可对所传数字信息进行特殊的处 理（即差错控制编码），对误码进行检错和纠 错，进一步降低误码率。 因此，数字通信系统可从硬件上采用抗干扰措 施，软件上采用信道编码对信息传输中出现的错 误进行控制和纠正。 Date4 第8章 差错控制编码 图81 两种通信系统干扰示意图 Date5 第8章 差错控制编码 香农提出了有扰信道中信息传输的重要理 论香农第二定理：对于一个给定的有扰 信 道，若该信道容量为C，则只要信道中的R 小 于C，就一定存在一种编码方式，使编码后 的误码率随着码长n的增加按指数下降到任 意 小的值。或者说只要Rk 分组码元（n位）= 信息码元（k位）+监督 码 元（n-k位） 2k个不同码组用矩阵C表示。 有时把监督码元称为或校验码元。 Date58 第8章 差错控制编码 k值越大，编码设备越复杂，因为编码设 备必须储存2k个码长为n的码组。因此，我 们需要构造码组之间有某种关系的分组码， 以降低编码的复杂性，线性分组码就是满足 这一条件的一种分组码。 Date59 第8章 差错控制编码 线性分组码：是一种长度为n，其中2k个 许 用码组（代表信息的码组）中的任意两个码 组的模2和仍为一个许用码组的分组码。称 为 线性（n，k）码。 重要性质：封闭性，即任意两个许用码 组之模2和仍为一许用码组；码组的最小 码 距等于非零码的最小码重。 Date60 第8章 差错控制编码 图84 线性分组码格式 具有这种结构的线性分组码又叫做线性分组 系统码。 Date61 第8章 差错控制编码 相应的信息码组行向量和分组码码组行向 量为 C =c1, c2, , cn (8.61) D =d1, d2, , dk (8.62) 一个分组码组的前k位是信息码元，后n-k 位是监督码元（设监督码元位数为m，则有 m=n-k），每一个分组码组可以由信息码元 线性组合而成，即： Date62 第8章 差错控制编码 Date63 第8章 差错控制编码 式中,hmidi表示模2乘，也可表示为hmidi。其运 算规则是：10=01=00=0；11=1。可见，在 线性分组码中，信息码元和监督码元可以用线性方 程联系起来。 将上述C与D的n个关系式用矩阵表示为 Date64 第8章 差错控制编码 即 C=DG (8.63) 式中, G称为生成矩阵，是一个kn阶矩 阵，具体形式为 Date65 第8章 差错控制编码 该矩阵又可分解为两个子矩阵: Date66 第8章 差错控制编码 其中Ik是kk阶单位阵，P为km阶矩 阵，即： Date67 第8章 差错控制编码 这样，分组码C又可表示为 C = DIk P （8.64） 需要说明的是，上述各式中的C和D可以是 由一个码组构成的一个行向量，也可以是由 2k个行向量构成的2kn阶分组码矩阵或2kk 阶信息码矩阵。 Date68 第8章 差错控制编码 式（8.63）说明：（n，k）线性码完全由 生 成矩阵G的k行元素决定，即任意一个分组码码组 都是G的线性组合。（n，k）线性码中的任何k 个线性无关的码组都可用来构成生成矩阵，所以 ， 生成矩阵G的各行都线性无关。G的各行本身就是 一个码组。如果已有k个线性无关的码组，则可 用其直接构成G矩阵，并由此生成其余码组。 Date69 第8章 差错控制编码 综上所述，由于可用一个kn阶矩阵G生 成2k个不同的码组，因此，编码器只需储存 G矩阵的k行元素（而不是一般分组码的2k码 组），就可根据信息向量构造出相应的一个 分组码码组（或根据信息码矩阵构造出相应 的一个分组码矩阵），从而降低了编码的复 杂性，并提高了编码效率。 Date70 第8章 差错控制编码 【例题81】给定一个（7，4）线性分组码 的生成矩阵 若信息码为d=1101，求该信息码的线 性分组编码C。 Date71 第8章 差错控制编码 解: 根据式（8.63）可得 Date72 第8章 差错控制编码 即对信息码1101的线性分组编码为 1101000。注意在矩阵乘法中，是模2 乘和模2加。上式也可写成 Date73 第8章 差错控制编码 以上讨论可知，编码前的信息码组共有2k 种组合，编码后的码组在k位信息码元之外 还 附加了m位校验码元，共有2n种组合， 2n2k，这就是说C与D的关系不惟一。 因此，选择适当的矩阵P，就可得到既具 有较强检错或纠错能力，又较简单且编码效 率较高的线性分组码。目前已经找到不少性 能较好的矩阵P。 Date74 第8章 差错控制编码 【例题82】 已知线性（6，3）码的生成 矩阵为 求线性分组码、各码组的码重、最小码距 和该码的差错控制能力。 解：因为k=3，故信息码组矩阵（38）为 Date75 第8章 差错控制编码 Date76 第8章 差错控制编码 则由式（8.63）可得出分组码码组 矩阵（68阶）为 Date77 第8章 差错控制编码 表88 例82编码表 Date78 第8章 差错控制编码 从表中可见非零码组的最小码重为3，则 分组码的最小码距dmin=3，根据式（8.41） 、 （8.42）和（8.43）可知该分组码能够检2 位错，纠1位错，或同时纠1位错检1位错。 需要说明的是，任何线性分组码都包含全 零码组。因任一码组与其本身模2加都会得到 全零码组。 Date79 第8章 差错控制编码 下面我们简要介绍译码原理。从式（8.47）可 得 （8.66 ） （8.65） 式中，Cm是km阶监督码元矩阵。将式(8.66) 改写为: (8.67) (8.68 ) Date80 第8章 差错控制编码 该式说明线性分组码中任一码组与校验矩 阵H的转置相乘，其结果为m位全零向量，因 此，用校验矩阵检查二元序列是不是给定分 组码中的码组非常方便，“校验”由此而来。 可以推导出校验矩阵H与生成矩阵G满足 GHT = HGT = 0 (8.69) Date81 第8章 差错控制编码 设行向量R=r1，r2，rn是收信端 收 到的码组。由于信道干扰产生误码，接收向 量R和发送向量C就有差别，用向量E=e1， e2，en表示这种差别。由此定义三者 之 间的关系为 （8.610） Date82 第8章 差错控制编码 若R中的某一位ri与C中的相同位ci一样 时，E中的ei=0；若不同（即出现误码）， 则 ei=1。可见向量E能够反映误码状况，故称 之 为错误向量或错误图样。可见，E的码重就 是误码的个数，因此E的码重越小越好。 Date83 第8章 差错控制编码 式（8.610）也可写为 R = E C （8.611） 定义矩阵S为伴随式 S = RHT （8.612） S是长度为m=n-k的二元序列，有2m种组合。由式 （8.68）、（8.611）和（8.612）得 S =（E C）HT = E HT C HT = E HT （8.6-13） Date84 第8章 差错控制编码 式（8.613）表明伴随式S只与错误图样 E 有关，与发送码组无关。S称为R的伴随式或 称校正子。 当S为零矢量时，说明R没有错，R是码组 C；否则，说明R有错，R不是码组C。 当通信双方确定了信道编码后，生成矩阵G 和监督矩阵H也就随之而定。收端可以知道 G、H和R。 Date85 第8章 差错控制编码 译码方法： 收端先求出伴随式 S 解出错误图样 E 解出发送码组 C Date86 第8章 差错控制编码 需要说明的是，上述步骤只是一个概念上 的解释，具体方法还比较麻烦。因为对于一 个 伴随式S，有2k个错误图样与之对应，换句话 说，就是式(8.613)的解不唯一，真正的错 误 图样只是2k个错误图样中的一个。 Date87 第8章 差错控制编码 【例题83】 已知一线性(6，3)码的生成矩 阵G、S和E的对照表分别为： Date88 第8章 差错控制编码 SE 000000000 101100000 011010000 110001000 100000100 010000010 001000001 111100010 求当接收端收到码组R=111011时，所对应的 信息码组D。 Date89 第8章 差错控制编码 解： 根据前面HT的定义式可得 将接收码组R=111011代入(8.612)式，可得： Date90 第8章 差错控制编码 Date91 第8章 差错控制编码 从SE关系表中可知，S=011所对应的错误 图样为E =010000。将R =111011 和E=010000代入式 (813)或式(814)可得 C = R E =101011 从C中分出信息码组为 D=101 信息码组为D =101 Date92 第8章 差错控制编码 8.7 循 环 码 定义：对于一个（n，k）线性码C，若其 中 的任一码组向左或向右循环移动任意位后仍 是C中的一个码组，则称C是一个循环码。 循 环码是一种分组码，前k位为信息码元，后m 位为监督码元。 优点：纠错能力强，编解码简单。 Date93 第8章 差错控制编码 若c=c1，c2，cn是一个循环码组，左循环 移位一次，得到c（1）=c2，c3，cn，c1也是 许 用码组，移位i次得到c(i)=ci+1，ci+2，cn，c1， ci还是许用码组。 在代数编码理论中，可以把循环码组中各码元 当 作一个多项式的系数，即把一个长为n的码组表示 c(x) = c1xn-1 + c2xn-2 + + cn Date94 第8章 差错控制编码 式中，c(x)称为码多项式，变量x称为元素，其幂 次对应元素的位置，它的系数即为元素的取值（我 们不关心x本身的取值），系数之间的加法和乘法 仍 服从模2规则。比如一个（7，3）循环码（见表 89）中第7个码组为（1100101），则该码组可表 示为 c7(x) =1x6 + 1x5 + 0x4 + 0x3 + 1x2 + 0x + 1 = x6 + x5 + x2 + 1 Date95 第8章 差错控制编码 表89 一种（7，3）循环码的全部码组 Date96 第8章 差错控制编码 举例说明系统码与非系统码的区别。对一组4位 信 息码组，附加3位监督码元可编成两种（不只两种 ） 循环码，见表810所示。 系统码的前4位对应的都是信息码，而后3位都是 监督码元，且编码前后信息码形式保持不变。 非系统码从第5组开始信息码就“乱”了，没有系 统 码那种前后一致的信息码结构。 Date97 第8章 差错控制编码 另外，还需说明的是，对于一个（n，k）线性 码C，根据不同的方法（生成矩阵）可以有多种编 码形式，其中包含系统码和非系统码，但系统码 是惟一的，其余的都是非系统码。 小结：简要地了解了数字（数据）通信中信 道编码的基本概念和常用的检纠错编码，编码所 研究的主要问题是： Date98 第8章 差错控制编码 (1) 根据系统对纠错能力的要求，寻找合适 的码型。要求该码型可在数学上证明具有满 足要求的纠错能力，并具有数学结构，且能 够根据此结构具体实现编码和译码。 (2) 寻找实用的编码方法，提高编码效率。 (3) 寻找实用的译码方法