第九章差错控制编码

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 监督码元数目，（监督位段）（见樊监督码元数目，（监督

4、位段）（见樊书书P282，图，图9-2） 在分组码中，有在分组码中，有“1”的数目称为码组的重的数目称为码组的重量，简称码重。量，简称码重。例如，码组（例如，码组（1 1 0 1 0），码长），码长n=5，码重为，码重为3。 把两个码组对应位不同的数目称为这两个把两个码组对应位不同的数目称为这两个码组的距离，简称码距，又称码组的距离，简称码距，又称Hamming（汉明）的距离。（汉明）的距离。例如，码组（例如，码组（1 1 0 0 0）与（）与（1 0 0 1 1）的距）的距离为离为3。 而码组集合中，全体码组之间的距离的而码组集合中，全体码组之间的距离的最小值称为最小码距（最小值称为最小码距

5、（d0 ）。）。 检测检测e个错，个错， 纠正纠正t个错个错, 纠正纠正t个错同时检测个错同时检测e个错个错 码长码长n发生发生r个错的概率个错的概率 纠纠1，2个错误码率也下降几个数量级个错误码率也下降几个数量级01de021dt01,detet !( )(1)(1)!()!rrn rrn rnneeeenp rC ppppr nr3357710 ,(1)7.*10 ,(2)2.*10eppp9.3常用的简单编码常用的简单编码 纠错码的分类纠错码的分类 ： (1) 奇偶校验码奇偶校验码“1”的数目应为偶或奇数）的数目应为偶或奇数） (2) 二维奇偶校验码二维奇偶校验码 (3) 恒比码恒比码

6、(4) 正反码正反码(1) 奇偶校验码奇偶校验码 0021aaann0110011偶校验位信息位1 1 0 0 1 1(2) 二维奇偶校验码01000100110011列监督位， 行监督位， /0/1/0/1对称出现4个错码也检不出来001111100001110011111001010111110011 (3) 恒比码恒比码 例如，我国电传机传输阿拉伯数字时，例如，我国电传机传输阿拉伯数字时，用用5位代码表示，其中恒有位代码表示，其中恒有3个个“1”，称，称为为 “5中取中取3” 恒比码。恒比码。 阿拉伯数字阿拉伯数字保护电码保护电码阿拉伯数字阿拉伯数字保护电码保护电码12345010111

7、1001101101101000111678901010111100011101001101101(4) 正反码正反码 正反码的正反码的信息位段长与监督位段长相同，信息位段长与监督位段长相同，如如正反码组：正反码组： 信息位段有奇数个信息位段有奇数个1：1100111001 （监督位与监督位与信息位重复信息位重复） 信息位段有偶数个信息位段有偶数个1：1000101110 （监督位是监督位是信息位反码信息位反码）信息位 监督位信息位 监督位9.4 线性分组码线性分组码 一：基本概念一：基本概念 可用线性方程组（代数关系）表述可用线性方程组（代数关系）表述码的规律性的分组码称为线性分组码码的规律

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

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

10、码字（设码字（n n，k k）= 0456aaaa321sss,校正子校正子321sss, 的值与错码位置的对应关系的值与错码位置的对应关系 如下表如下表24561aaaas13562aaaas03463aaaas 只要（只要（s s1 1或或s s2 2，或，或s s3 3）为）为“1”，就表示，就表示有错有错信息位aa36321,sss321sss,0a4a1a5a2a6a3a错码位置错码位置001101010110100111011000无 错321sss,全为零，表示无错。 在发端编码时，信息位在发端编码时，信息位 的值是随机的，监的值是随机的，监督位督位 应根据信息位按监督关系来确定

11、，即监督位应根据信息位按监督关系来确定，即监督位应使上面的应使上面的 监督式为零。监督式为零。 6543aaaa,012aaa,321sss, 即要求： 02456aaaa01356aaaa00346aaaa或写成监督码元在左边的形式：或写成监督码元在左边的形式： 4562aaaa3561aaaa3460aaaa 信息位信息位 一旦确定后，可直接按上式计算一旦确定后，可直接按上式计算出监督位。出监督位。（见樊书（见樊书P289 图图9-5）3456aaaa, 接收端收到每个码字（码组）后，先计算出偶监督关接收端收到每个码字（码组）后，先计算出偶监督关系式，系式， 再按表再按表9-4（樊书（樊书

12、P288）判断错码情况。判断错码情况。 321sss, 如果如果 不全零，可判出在哪一位出错。不全零，可判出在哪一位出错。321sss,查樊书表9-4，判错哪一位并纠正之265416530643aaaaaaaaaaaa654265316430000aaaaaaaaaaaa发送端，将信发送端，将信息位按此式加息位按此式加上监督位后发上监督位后发送送接收端，先计算校正为零否，接收端，先计算校正为零否，不为零则出错码，查表后，纠不为零则出错码，查表后，纠正改之正改之 汉明码最小距汉明码最小距 =3（见樊书表（见樊书表9-5），能够纠正单个错误。），能够纠正单个错误。 0d三：线性分组码的一般原理三：

13、线性分组码的一般原理 (1) 监督阵和生成矩阵监督阵和生成矩阵 将上述汉明码（将上述汉明码（7，4）的监督关系式）的监督关系式改写成：改写成：（见樊书（见樊书P289，9.4-8） 1654321011101000saaaaaaa 2654321011010100saaaaaaa 3654321010110010saaaaaaa 上式中上式中 简写为简写为+，表示模，表示模2相加。相加。 写成矩阵形式：写成矩阵形式： 1001101010101100101110123456aaaaaaa000=（模2） 简记简记 （H 监督矩阵监督矩阵） 监督矩阵监督矩阵H为为 （ 行，行， 列）阶矩阵，列）

14、阶矩阵，H阵阵的每行之间彼此线性无关。的每行之间彼此线性无关。 也可将也可将H矩阵分为两部分：矩阵分为两部分：0H anrrn H = 36aa 012aaa 其中其中P为为rk阶矩阵，阶矩阵， 为为rr阶单位矩阵。阶单位矩阵。rIrPI100010101010110010111若把监督关系式改写补充：若把监督关系式改写补充： 34603561456233445566aaaaaaaaaaaaaaaaaaaa 可改写为矩阵形式：可改写为矩阵形式： 656453423101000010000100001111011011011aaaaaaaaaaa65432106543aaaaaa aa a a

15、aG1101000101010001100101110001GkIQ=PT G称为称为生成矩阵生成矩阵，如果找到，如果找到G，则纠错编码方法就确，则纠错编码方法就确定了，可由信息组和定了，可由信息组和G可产生全部码字。可产生全部码字。 也称也称典型生成矩阵典型生成矩阵，其中，其中 QIGk 为kk方阵 ， kI1000010000100001 由典型生成矩阵得出的码组由典型生成矩阵得出的码组A中，信息位不变，监督中，信息位不变，监督位附加其后，这种码称为位附加其后，这种码称为系统码系统码。 110101011111Q(2) 校正子校正子S（伴随式）（伴随式） 设发送码组设发送码组设接收码组设接

16、收码组0121aaaaAnn,0121bbbbBnn, 则发送码组与接收码组之差定义为则发送码组与接收码组之差定义为E（也称错（也称错误图样）：误图样）：（模（模2）ABE0121eeeeEnn,iiiiiababe当当 1 0, 因此，若因此，若 , ,表示该位接收码元无错；表示该位接收码元无错；若若 ，则表示有错。，则表示有错。 0ie1ieABE,也可改写为也可改写为 EAB 例如：发送例如：发送A = 1 0 0 0 1 1 1 错误错误E = 0 0 0 0 1 0 0 接收接收B = 1 0 0 0 0 1 1THBS 令令 称称S为校正子，也称伴随式。为校正子，也称伴随式。 TT

17、TTTEHEHAHHEAHBS )(零矩阵零矩阵 由此可见，校正子由此可见，校正子S与错误图样与错误图样E之间有确定的线性之间有确定的线性变换关系，若变换关系，若S和和E之间一一对应，则之间一一对应，则S将能代表错码的位将能代表错码的位置。置。 接收端译码器的任务就是从校正子接收端译码器的任务就是从校正子S确定错误图样，确定错误图样，然后，从接收到的码字中减去错误图样然后，从接收到的码字中减去错误图样E。 1b2b3b序号错误码位错误图样 E校正子 S 0 0 0 0 0 0 0 00 0 01 0 0 0 0 0 0 10 0 12 0 0 0 0 0 1 00 1 03 0 0 0 0 1

18、 0 01 0 04 0 0 0 1 0 0 00 1 15 0 0 1 0 0 0 01 0 16 0 1 0 0 0 0 01 1 07 1 0 0 0 0 0 01 1 10b4b5b6b e6 e5 e4 e3 e2 e1 e02s1s0s9.5 循环码循环码 一、特点：一、特点： 编码和解码设备都不太复杂，且检编码和解码设备都不太复杂，且检（纠）错能力较强。具有线性和循环性，（纠）错能力较强。具有线性和循环性，即循环码中任一码组循环一位（将最右即循环码中任一码组循环一位（将最右端的码元移至左端，或反之）以后，仍端的码元移至左端，或反之）以后，仍为该码中的一个码组。为该码中的一个码组。

19、 将各码元当作是一个多项式的系数，樊书P293页，表96中的任一码组可表示为 这种多项式中，x仅是码元位置的标记。这种多项式有时称为码多项式。二、编码原理121210( )nnnnT xaxaxa xa(1)、码多项式的按模运算、码多项式的按模运算 若一整数若一整数m可以表示为可以表示为式中式中Q整数。整数。则在模则在模n运算下，有运算下，有mpn模mpQpnnn在循环码中，若在循环码中，若T(x)是一个长为是一个长为n的许用码组，则的许用码组，则 ixT x在按模在按模1nx 运算下，也是一个许用码组，即若运算下，也是一个许用码组，即若 1inxT xTxx模则则 Tx也是一个许用码组。也是

20、一个许用码组。 例如例如65235327( )1,11001013( )mod(1)0101110codeiiT xxxxxxleftshiftxT xxxxxx 65235327( )1,11001013( )mod(1)0101110codeiiT xxxxxxleftshiftxT xxxxxx ) 1mod(.17235235273589xxxxxxxxxxxxxxxx(2)、循环码的生成矩阵、循环码的生成矩阵G 在一个在一个 循环码中有循环码中有 个不同码个不同码组。若用组。若用 表示表示其中前（其中前（k1）位皆）位皆为为0的码组的码组，则，则 都是码组，而且这都是码组，而且这k个

21、码组是线性无关的。个码组是线性无关的。 因此他们可以用来构成此循环码的生成因此他们可以用来构成此循环码的生成 矩阵矩阵G , k=3, 表见下页。表见下页。 g(x)-0010111 x 43210 2k 421g xxxx 21,.,kg xxg xx g xxg x, n k g x码组编号信息位监督位1000000020010111301011104011100151001011610111007110010181110010 循环码的生成矩阵循环码的生成矩阵G可以写成可以写成 12( )( )( )( )kkxg xxg xG xxg xg x上式可作上式可作线性变换线性变换成成 的形

22、式。的形式。kGI Q 循环码的生成多项式应该是循环码的生成多项式应该是 的一个的一个 次因式。例如，次因式。例如， 可以分解为可以分解为1nx nk71x 为了求（为了求（7，3）循环码的生成多项式）循环码的生成多项式g(x)，要从上式中找一个，要从上式中找一个（n-k)=4次的因子。这样的因子有两个，即次的因子。这样的因子有两个，即32432111xxxxxx3242111xxxxxx 以上两式都可作为生成多项式用。不过，选用的生成多项式不以上两式都可作为生成多项式用。不过，选用的生成多项式不同，产生出的循环码码组也就不同。同，产生出的循环码码组也就不同。73231111xxxxxx(3)

23、、寻找生成多项式、寻找生成多项式三、循环码编、解码方法三、循环码编、解码方法（1）编码步骤）编码步骤 (代数方法）代数方法） 1、用、用 乘乘 。这一运算实际上是把。这一运算实际上是把信息码附加上（信息码附加上（ ）个）个0。 2、用、用 除除 ，得到商，得到商Q（x）和）和余式余式 。 3、编出的码组、编出的码组 为为 (2) T=m G (matrix-operation) n kx( )m xnk( )g x( )n kxm x( )r x( )T x ( )n kT xxm xr x（2）解码步骤）解码步骤 1、用生成多项式用生成多项式 除接收码组除接收码组 得出余式得出余式 ； 2、按余式、按余式 用查表的方法或通过某种运算得用查表的方法或通过某种运算得 到错误图样到错误图样 就可以确定错码的位置；就可以确定错码的位置； 3、从、从 中减去中减去 ，变得到已纠正错误的，变得到已纠正错误的原发送码组原发送码组 。 ( )g x( )( )( )R xT xE x( )r x( )r x( )E x( )R x( )E x( )T xBCH码 BCH码是一种线性分组码，也是循环码 它由多个循环码的生成多项