第九章随机课件.ppt

1、第九章 差错控制编码 9.1 引言 9.2 纠错编码的基本原理 9.3 常用的简单编码 9.4 线性分组码 9.5 循环码 9.6 卷积码9.1引 言 一、信源编码与信道编码 数字通信中，根据不同的目的，编码分为信源编码与信道编码二大类。信源编码：提高数字信号的有效性，如，PCM编码，编码，图象数据压缩编码等。信道编码：提高传输的可靠性，又称抗干扰编码，纠错编码。从差错控制角度看：信道分三类：（信道编码技术）随机信道：由加性白噪声引起的误码，错 码是随机的，错码间统计独立。突发信道：错码成串，由脉冲噪声干扰引 起。混合信道：既存在随机错误，又存在突发错码，那一种都不能忽略不计的信道。二：差错控

2、制的工作方式 检错重发 前向纠错，不要反向信道 反馈校验法，双向信道 检错重发前向纠错反馈校验法检错误判决信号纠错码信息信号发发发收收收信息信号9.2 纠错编码的基本原理 一：分组码，码重，码距 （樊书P282 表9-1）将码组分段：分成信息位段和监督位段，称为分组码，记为（n,k）n编码组的总位数，简称码长（码组的长度）k 每组二进制信息码元数目（信息位段）n-k=r 监督码元数目，（监督位段）（见樊书P282，图9-2）在分组码中，有“1”的数目称为码组的重量，简称码重。例如，码组（1 1 0 1 0），码长n=5，码重为3。把两个码组对应位不同的数目称为这两个码组的距离，简称码距，又称H

3、amming（汉明）的距离。例如，码组（1 1 0 0 0）与（1 0 0 1 1）的距离为3。而码组集合中，全体码组之间的距离的最小值称为最小码距（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)恒比码(4)正反码(1)奇偶校验码 0021aaann

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

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

6、组合代表不同信息。若用1种组合表示无错,其余3种组合就可以用来表示一位错码的3种不同位置。同理，r个监督式能指示一位错码的 个可能位置。12 r 一般来说，若码长n，信息位数k，则监督位 ,汉明码n与r满足：knr12 rn 现以（n，k）=（7，4），r=3为例的汉明码来说明如何具体构造这些监督关系式。设码字（n，k）=0456aaaa信息位监督位456012aaaaaa321sss,校正子321sss,的值与错码位置的对应关系 如下表24561aaaas13562aaaas03463aaaas 只要（s1或s2，或s3）为“1”，就表示有错321,sss321sss,0a4a1a5a2a6

7、a3a错码位置错码位置001101010110100111011000无 错321sss,全为零，表示无错。在发端编码时，信息位 的值是随机的，监督位 应根据信息位按监督关系来确定，即监督位应使上面的 监督式为零。6543aaaa,012aaa,321sss,即要求：02456aaaa01356aaaa00346aaaa或写成监督码元在左边的形式：4562aaaa3561aaaa3460aaaa 信息位 一旦确定后，可直接按上式计算出监督位。（见樊书P289 图9-5）3456aaaa,接收端收到每个码字（码组）后，先计算出偶监督关系式，再按表9-4（樊书P288）判断错码情况。321sss,

8、如果 不全零，可判出在哪一位出错。321sss,查樊书表9-4，判错哪一位并纠正之265416530643aaaaaaaaaaaa654265316430000aaaaaaaaaaaa发送端，将信发送端，将信息位按此式加息位按此式加上监督位后发上监督位后发送送接收端，先计算校正为零否，接收端，先计算校正为零否，不为零则出错码，查表后，纠不为零则出错码，查表后，纠正改之正改之 汉明码最小距 =3（见樊书表9-5），能够纠正单个错误。0d三：线性分组码的一般原理(1)监督阵和生成矩阵 将上述汉明码（7，4）的监督关系式改写成：（见樊书P289，9.4-8）1654321011101000saaaa

9、aaa 2654321011010100saaaaaaa 3654321010110010saaaaaaa 上式中 简写为+，表示模2相加。写成矩阵形式：1001101010101100101110123456aaaaaaa000=（模2）简记 （H 监督矩阵）监督矩阵H为 （行，列）阶矩阵，H阵的每行之间彼此线性无关。也可将H矩阵分为两部分：0H anrrn H=36aa 012aaa 其中P为rk阶矩阵，为rr阶单位矩阵。rIrPI100010101010110010111若把监督关系式改写补充：34603561456233445566aaaaaaaaaaaaaaaaaaaa 可改写为矩阵

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

11、送码组与接收码组之差定义为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为校正子，也称伴随式。TTTTTEHEHAHHEAHBS )(零矩阵 由此可见，校正子S与错误图样E之间有确定的线性变换关系，若S和E之间一一对应，则S将能代表错码的位置。接收端译码器的任务就是从校正子S确定错误图样，然后，从接收到的码字中减去错误图样E

12、。上述（7，4）汉明码的校正子S与错误图样E的对应关系见下表：表中，校正子S的 种形式分别代表A码无错和 -1种有错的图样。r2r21b2b3b序号错误码位错误图样 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 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 循环码 一、特点：编码

13、和解码设备都不太复杂，且检（纠）错能力较强。具有线性和循环性，即循环码中任一码组循环一位（将最右端的码元移至左端，或反之）以后，仍为该码中的一个码组。将各码元当作是一个多项式的系数，樊书P293页，表96中的任一码组可表示为 这种多项式中，x仅是码元位置的标记。这种多项式有时称为码多项式。二、编码原理121210()nnnnT xaxaxa xa(1)、码多项式的按模运算 若一整数m可以表示为式中Q整数。则在模n运算下，有mpn模mpQpnnn在循环码中，若T(x)是一个长为n的许用码组，则 ixT x在按模1nx 运算下，也是一个许用码组，即若 1inxT xTxx模则 Tx也是一个许用码组

14、。例如65235327()1,11001013()mod(1)0101110codeiiT xxxxxxleftshiftxT xxxxxx (2)、循环码的生成矩阵G 在一个 循环码中有 个不同码组。若用 表示其中前（k1）位皆为0的码组，则 都是码组，而且这k个码组是线性无关的。因此他们可以用来构成此循环码的生成 矩阵G。Tab.9-6 Page 293,k=3,g(x)-0010111 x 43210 2k 421g xxxx 21,.,kg xxg xx g xxg x,n k g x 循环码的生成矩阵G可以写成 12()()()()kkxg xxg xG xxg xg x上式可作线性

15、变换成 的形式。kGI Q 循环码的生成多项式应该是 的一个 次因式。例如，可以分解为1nx nk71x 为了求（7，3）循环码的生成多项式g(x)，要从上式中找一个（n-k)=4次的因子。这样的因子有两个，即32432111xxxxxx3242111xxxxxx 以上两式都可作为生成多项式用。不过，选用的生成多项式不同，产生出的循环码码组也就不同。73231111xxxxxx(3)、寻找生成多项式三、循环码编、解码方法（1）编码步骤(代数方法）1、用 乘 。这一运算实际上是把信息码附加上（）个0。2、用 除 ，得到商Q（x）和余式 。3、编出的码组 为 (2)T=m G (matrix-op

16、eration)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 x9.6 卷积码一.卷积码的结构图D1D2km 1kc 2kckc由图可知，（2，1，2）卷积码的编码规则为 12212kkkkkkkcmmcmmm输出码字为 12,kkkccc二.卷积码的生成多项式

17、则相应的系统冲击响应为 1828101(5)111(7)gg1122120kkkkkkhh用生成多项式表示212211gxgxx 三.编码率与约束长度k输入，n输出,每时刻输出与过去(L-1)k个输入亦关编码率=k/n=1/2,约束长度=L=7L=5四.状态图0001101100/011/110/001/101/010/111/000/1D1D2km 1kc 2kckc 五五.网格图网格图 input=101+00output=11100010110010011110/011/111/110/000/111/0 Viterbi Decoding;output=101HARD:input=11110010110010011110111 11000111 10 01 01 1000201111113102012004,61,4114,3013,21100100131103