第九章差错控制编码.

《第九章差错控制编码.》由会员分享，可在线阅读，更多相关《第九章差错控制编码.（50页珍藏版）》请在金锄头文库上搜索。

1、第九章第九章 差错控制编码差错控制编码9.1 引言引言9.2 纠错编码的基本原理纠错编码的基本原理9.3 常用的简单编码常用的简单编码9.4 线性分组码线性分组码9.5 循环码循环码9.6 卷积码卷积码9.1引引 言言一、信源编码与信道编码一、信源编码与信道编码 数字通信中，根据不同的目的，编码分为数字通信中，根据不同的目的，编码分为信源编码与信道编码二大类。信源编码与信道编码二大类。 信源编码信源编码：提高数字信号的有效性，如，：提高数字信号的有效性，如，PCM编码，编码，图象数据压缩编码等。编码，编码，图象数据压缩编码等。 信道编码：信道编码：提高传输的可靠性，又称抗干扰编提高传输的可靠性

2、，又称抗干扰编码，纠错编码码，纠错编码 。从差错控制角度看：信道分三类：（信从差错控制角度看：信道分三类：（信道编码技术）道编码技术）随机信道：随机信道：由加性白噪声引起的误码，错由加性白噪声引起的误码，错 码是随机的，错码间统计独立。码是随机的，错码间统计独立。突发信道：突发信道：错码成串，由脉冲噪声干扰引错码成串，由脉冲噪声干扰引 起。起。混合信道：混合信道：既存在随机错误，又存在突发既存在随机错误，又存在突发错码，那一种都不能忽略不计的信道。错码，那一种都不能忽略不计的信道。二：差错控制的工作方式二：差错控制的工作方式检错重发检错重发前向纠错，不要前向纠错，不要反向信道反向信道反馈校验法

3、，双反馈校验法，双向信道向信道 9.2 纠错编码的基本原理纠错编码的基本原理一：分组码，码重，码距一：分组码，码重，码距 （樊书（樊书P282 表表9-1） 将码组分段：分成信息位段和监督位段，将码组分段：分成信息位段和监督位段，称为分组码，记为（称为分组码，记为（n, k）n编码组的总位数，简称码长（码组的长度）编码组的总位数，简称码长（码组的长度）k 每组二进制信息码元数目（信息位段）每组二进制信息码元数目（信息位段）n-k=r 监督码元数目，（监督位段）（见樊监督码元数目，（监督位段）（见樊书书P282，图，图9-2）在分组码中，有在分组码中，有“1”的数目称为码组的重的数目称为码组的重

4、量，简称码重。量，简称码重。例如，码组（例如，码组（1 1 0 1 0），码长），码长n=5，码重为，码重为3。把两个码组对应位不同的数目称为这两个把两个码组对应位不同的数目称为这两个码组的距离，简称码距，又称码组的距离，简称码距，又称Hamming（汉明）的距离。（汉明）的距离。例如，码组（例如，码组（1 1 0 0 0）与（）与（1 0 0 1 1）的距）的距离为离为3。而码组集合中，全体码组之间的距离的而码组集合中，全体码组之间的距离的最小值称为最小码距（最小值称为最小码距（d0 ）。）。检测检测e个错，个错，纠正纠正t个错个错,纠正纠正t个错同时检测个错同时检测e个错个错码长码长n发生

5、发生r个错的概率个错的概率纠纠1，2个错误码率也下降几个数量级个错误码率也下降几个数量级9.3常用的简单编码常用的简单编码纠错码的分类纠错码的分类 ： (1) 奇偶校验码奇偶校验码“1”的数目应为偶或奇的数目应为偶或奇数）数） (2) 二维奇偶校验码二维奇偶校验码(3) 恒比码恒比码(4) 正反码正反码(1) 奇偶校验码奇偶校验码偶 校验位信息位110011(2)二维奇偶校验码列监督位，行监督位，/0/1/0/1对称出现4个错码也检不出来(3) 恒比码恒比码 例例如如，我我国国电电传传机机传传输输阿阿拉拉伯伯数数字字时时，用用5位位代代码码表表示示，其其中中恒恒有有3个个“1”，称称为为 “5

6、中取中取3” 恒比码。恒比码。阿拉伯数字阿拉伯数字保护电码保护电码阿拉伯数字阿拉伯数字保护电码保护电码123450101111001101101101000111678901010111100011101001101101(4) 正反码正反码正正反反码码的的信信息息位位段段长长与与监监督督位位段段长长相相同同，如如正反码组：正反码组： 信息位段有奇数个信息位段有奇数个1：1100111001 （监督位与监督位与信息位重复信息位重复） 信信息息位位段段有有偶偶数数个个1：1000101110 （监监督督位位是是信息位反码信息位反码）信息位 监督位信息位 监督位9.4 线性分组码线性分组码一：基本

7、概念一：基本概念 可可用用线线性性方方程程组组（代代数数关关系系）表表述述码的规律性的分组码称为线性分组码码的规律性的分组码称为线性分组码 。 在在代代数数码码中中，常常见见的的是是线线性性码码，即即编编码码中中的的信信息息位位和和监监督督位位是是由由一一些些线线性性代代数数方方程程联联系系着着，或或者者说说可可用用线线性性代代数数方程表述编码的规律性。方程表述编码的规律性。二：线性分组码的一种二：线性分组码的一种 汉明码汉明码构造原理构造原理 先回顾偶校验码先回顾偶校验码 在接收端实际上计算监督关系式：在接收端实际上计算监督关系式：无错 有错 称校正子 两个监督式就有两个校正子，其可能值有两

8、个监督式就有两个校正子，其可能值有4种组合：种组合：0 0，0 1，1 0，1 1，这，这4种组合代表不同信息。种组合代表不同信息。 若若用用1种种组组合合表表示示无无错错, ,其其余余3种种组组合合就就可可以以用用来来表表示示一一位位错错码码的的3种不同位置。种不同位置。 同理，同理，r r个监督式能指示一位错码的个监督式能指示一位错码的 个可能位置。个可能位置。 一一般般来来说说，若若码码长长n n，信信息息位位数数k k，则则监监督督位位 , ,汉汉明明码码n n与与r r满足：满足：现现以以（n，k）=（7，4），r r=3为为例例的的汉汉明明码码来来说说明明如如何何具具体体构构造这些

9、监督关系式。造这些监督关系式。设码字（设码字（n n，k k）= 校正子校正子 的值与错码位置的对应关系的值与错码位置的对应关系 如下表如下表 只只要要（s s1 1或或s s2 2，或或s s3 3）为为“1”，就就表表示示有错有错错码位置错码位置001101010110100111011000无错全为零，表示无错。 在发端编码时，信息位在发端编码时，信息位 的值是随机的，监的值是随机的，监督位督位 应根据信息位按监督关系来确定，即监督位应根据信息位按监督关系来确定，即监督位应使上面的应使上面的 监督式为零。监督式为零。 即要求： 或写成监督码元在左边的形式：或写成监督码元在左边的形式： 信

10、信息息位位 一一旦旦确确定定后后，可可直直接接按按上上式式计计算算出出监督位。监督位。（见樊书（见樊书P289 图图9-5） 接收端收到每个码字（码组）后，先计算出偶监督关接收端收到每个码字（码组）后，先计算出偶监督关系式，系式， 再按表再按表9-4（樊书（樊书P288）判断错码情况。判断错码情况。 如果如果 不全零，可判出在哪一位出错。不全零，可判出在哪一位出错。查樊书表9-4，判错哪一位并纠正之发发送送端端，将将信信息息位位按按此此式式加加上上监监督督位位后后发发送送接收端，先计算校正为零否，接收端，先计算校正为零否，不不为为零零则则出出错错码码，查查表表后后，纠纠正改之正改之汉明码最小距

11、汉明码最小距 =3（见樊书表（见樊书表9-5），能够纠正单个错误。），能够纠正单个错误。 三：线性分组码的一般原理三：线性分组码的一般原理(1) 监督阵和生成矩阵监督阵和生成矩阵 将将上上述述汉汉明明码码（7，4）的的监监督督关关系系式式改写成：改写成：（见樊书（见樊书P289，9.4-8） 上式中上式中 简写为简写为+，表示模，表示模2相加。相加。 写成矩阵形式：写成矩阵形式：=（模2） 简记简记 （H 监督矩阵监督矩阵） 监监督督矩矩阵阵H为为 （ 行行， 列列）阶阶矩矩阵阵，H阵阵的每行之间彼此线性无关。的每行之间彼此线性无关。 也可将也可将H矩阵分为两部分：矩阵分为两部分：H= 其中其

12、中P为为rk阶矩阵，阶矩阵， 为为rr阶单位矩阵。阶单位矩阵。若把监督关系式改写补充：若把监督关系式改写补充： 可改写为矩阵形式：可改写为矩阵形式： Q=PT G称称为为生生成成矩矩阵阵，如如果果找找到到G，则则纠纠错错编编码码方方法法就就确确定了，可由信息组和定了，可由信息组和G可产生全部码字。可产生全部码字。也称也称典型生成矩阵典型生成矩阵，其中，其中 为kk方阵 ， 由典型生成矩阵得出的码组由典型生成矩阵得出的码组A中，信息位不变，监督中，信息位不变，监督位附加其后，这种码称为位附加其后，这种码称为系统码系统码。 (2) 校正子校正子S（伴随式）（伴随式）设发送码组设发送码组设接收码组设

13、接收码组 则则发发送送码码组组与与接接收收码码组组之之差差定定义义为为E（也也称称错错误图样）：误图样）：（ 模模 2） 因此，若因此，若 , ,表示该位接收码元无错；若表示该位接收码元无错；若 ，则表示有错。，则表示有错。 ,也可改写为也可改写为 例如：发送例如：发送A = 1 0 0 0 1 1 1 错误错误E = 0 0 0 0 1 0 0 接收接收B = 1 0 0 0 0 1 1令 令令 称称S为校正子，也称伴随式。为校正子，也称伴随式。 零矩阵零矩阵由由此此可可见见，校校正正子子S与与错错误误图图样样E之之间间有有确确定定的的线线性性变变换换关关系系，若若S和和E之之间间一一一一对

14、对应应，则则S将将能能代代表表错错码码的的位位置。置。 接收端译码器的任务就是从校正子接收端译码器的任务就是从校正子S确定错误图样，确定错误图样，然后，从接收到的码字中减去错误图样然后，从接收到的码字中减去错误图样E。 序号错误码位错误图样E校正子S0000000000010000001001200000100103000010010040001000011500100001016010000011071000000111 e6 e5 e4 e3 e2 e1 e09.5 循环码循环码一、特点：一、特点： 编码和解码设备都不太复杂，且检编码和解码设备都不太复杂，且检（纠）错能力较强。具有线性和循

15、环性，（纠）错能力较强。具有线性和循环性，即循环码中任一码组循环一位（将最右即循环码中任一码组循环一位（将最右端的码元移至左端，或反之）以后，仍端的码元移至左端，或反之）以后，仍为该码中的一个码组。为该码中的一个码组。将各码元当作是一个多项式的系数，樊书P293页，表96中的任一码组可表示为这种多项式中，x仅是码元位置的标记。这种多项式有时称为码多项式。二、编码原理(1)、码多项式的按模运算、码多项式的按模运算若一整数若一整数m可以表示为可以表示为式中式中Q整数。整数。则在模则在模n运算下，有运算下，有在循环码中，若在循环码中，若T(x)是一个长为是一个长为n的许用码组，则的许用码组，则在按模

16、在按模运算下，也是一个许用码组，即若运算下，也是一个许用码组，即若则则也是一个许用码组。也是一个许用码组。 例如例如(2)、循环码的生成矩阵、循环码的生成矩阵G在一个在一个 循环码中有循环码中有 个不同码个不同码组。若用组。若用 表示表示其中前（其中前（k1）位皆为）位皆为0的码组的码组，则，则 都是码组，而且这都是码组，而且这k个码组是线性无关的。个码组是线性无关的。 因此他们可以用来构成此循环码的生成因此他们可以用来构成此循环码的生成 矩阵矩阵G , k=3, 表见下页。表见下页。 g(x)-0010111 x 43210 码组编号信息位监督位10000000200101113010111

17、04011100151001011610111007110010181110010 循环码的生成矩阵循环码的生成矩阵G可以写成可以写成上式可作上式可作线性变换线性变换成成 的形式。的形式。循环码的生成多项式应该是循环码的生成多项式应该是 的一个的一个 次因式。例如，次因式。例如， 可以分解为可以分解为为了求（为了求（7，3）循环码的生成多项式）循环码的生成多项式g(x)，要从上式中找一个，要从上式中找一个（n-k)=4次的因子。这样的因子有两个，即次的因子。这样的因子有两个，即以上两式都可作为生成多项式用。不过，选用的生成多项式不以上两式都可作为生成多项式用。不过，选用的生成多项式不同，产生出

18、的循环码码组也就不同。同，产生出的循环码码组也就不同。(3)、寻找生成多项式、寻找生成多项式三、循环码编、解码方法三、循环码编、解码方法（1）编码步骤）编码步骤 (代数方法）代数方法）1、用、用 乘乘 。这一运算实际上是把。这一运算实际上是把信息码附加上（信息码附加上（ ）个）个0。2、用、用 除除 ，得到商，得到商Q（x）和）和余式余式 。3、编出的码组、编出的码组 为为 (2) T=m G (matrix-operation) （2）解码步骤）解码步骤1、用生成多项式用生成多项式 除接收码组除接收码组 得出余式得出余式 ；2、按余式、按余式 用查表的方法或通过某种运算得用查表的方法或通过某

19、种运算得 到错误图样到错误图样 就可以确定错码的位置；就可以确定错码的位置；3、从、从 中减去中减去 ，变得到已纠正错误的，变得到已纠正错误的原发送码组原发送码组 。BCH码BCH码是一种线性分组码，也是循环码它由多个循环码的生成多项式构成它在给定要求纠正t个错误条件下，可以找到其相应的生成多项式BCH分本原BCH和非本原BCH本原BCH的g(x)含最高次数为m的本原多项式非本原BCH码则不含对于正整数m（m大于等于3）和正整数t(tm/2),必然存在一个码长，监督位能纠正所有小于或等于t个随即错误的BCH码BCH码生成多项式：t-可纠正的随即错误个数mi(x)-最小多项式，每个可以生成循环码

20、LCM（）取最小公倍数9.6 卷积码卷积码一一.卷积码的结构图卷积码的结构图D1D2由图可知，（由图可知，（2，1，2）卷积码的编码规则为）卷积码的编码规则为输出码字为二.卷积码的生成多项式则相应的系统冲击响应为用生成多项式表示三三.编码率与约束长度编码率与约束长度k输入，输入，n输出输出,每时刻输出与过去每时刻输出与过去(L-1)k个输入亦关个输入亦关编码率编码率=k/n=1/2,约束长度约束长度=L=7四四.状态图状态图0001101100/011/110/001/101/010/111/000/1D1D2 五五. 网格图网格图 input=101+00output=11100010110010011110/011/111/110/000/111/0Viterbi Decoding;output=101HARD:input=11110010110010011110111110001111001011000201111113102012004,61,4114,3013,21100100131103