通信原理--第9章-差错控制编码

1欢迎各位同学光临《通信原理》课程禹思敏2第9章差错控制编码信道编码,纠错码,差错控制编码提高了可靠性,但降低了有效性39.1概述9.1.1差错控制编码的概念是一种有效的方法信道编码技术降低误码率提高信噪比加大发射功率提高可靠性的方法提高可靠性加入的码元称监督码元按一定规则加入多余度信道编码提高有效性去掉信源的多余度信源编码编码,,,),(:,:49.1.2差错控制方式1、检错重发式：发送端发出能检错的码，接收端收到后，首先进行检测，当发现错误时,通知发送端重发一次，直到正确。如奇偶校验等。特点：译码简单，实时性差，双向传输。2、前向纠错：发送能自动纠错的码,在接收端能自动纠错。特点：实时性好，单向传输。3、混合方式：上述两者的组合。在接收端若能自动纠正，则不必重发，若超出自动纠错的范围，则通知对方重发，取各自的优点。59.1.3纠错码的分类1、线性码：监督码与信息码之间的关系是线性的2、非线性码：监督码与信息码间的关系是非线性的3、分组码：属于线性码的一种4、循环码：属于线性码的一种5、卷积码：属于非线性码的一种6、其它类型的纠错码69.1.4纠错码的基本原理一、分组码：把信息码按k个码元一组，并按一定的规律编码，产生r个监督码元，形成长度为n=k+r组码，称为码字，用(n,k)表示，其特点是：1、共有2k个不同的码字，称为许用码组；2、共有2n-2k个码字未用，称为禁用码组。正是存在禁用码组，使得(n,k)码具有纠错能力，禁用码越多，纠错能力越强。72、汉明距离d0的概念:（1）两个码字A,B之间的距离定义为:3),(:011110111100:),(,,),(nnnnbaBAdBAmBAdmBAbaBAd得例则其距离为个码元不同之间有即若两个码字81,)(,)3(12,)2(1,)1(:,,,,)3(1110101010000:,,)2(00000etdteettdtededdDCBA则要求随机错误个同时检测个纠则要求个随机错误纠则要求个随机错误检测有如下结论可以证明能力越强越大距离有关检错与纠错能力与汉明检错与纠错能力如离最小距离定义为汉明距则码字之间的的情况设一个集中有多个码字9.,,,01,10.,,10)1,1(),(,,)1(:.5/)(.4无任何纠检错能力没有监督码时因此码组出错后的码组仍为许用或原因是无法纠正故出错时由于没有禁用码组雨晴没有监督码时只有信息码雨和晴用二进码表示例题编码效率有效性的一种指标编码效率knnkR10可检出一个随机错误错误可检出这个故在接收端组范围由于它们不属于许用码或收到的码组变为产生了错误在传输过程中许用码组的汉明距离雨晴禁用码组许用码组种位编码共有后监督码加上一位重复码,,,),0,1()1,0(,,2:1011010011,10,01,00:42)1,2(),(,)()2(001daakn11)6(110,101,100,011,010,001:3111000:)2(111,110,101,100,011,010,001,000:)1,3(),(,)3(0012012个共禁用码组许用码组的汉明距离为雨晴个共许用码组全部码字为加上两位监督码元daaaaaakn1230d000111001010100011101110由(000)错一位的结果由(111)错一位的结果由上图可知,若传输过程中错一位,能够将其纠正139.2常用的几种简单的分组码9.2.1奇偶监督码一、二进制运算规则对于二进制的按位运算来说,加法,减法,异或三种运算的结果相同,这三个符号可视为相同即,,0111111000000110011001100101111110000000AAAAAAAAAAAAAAAAAAAA141210121001210121,,,0,1.1],,,,[)1,(),(.aaaaaaaaaaaaaaaaAnnnnnnnnnn之间的关系为与信息码得监督码元有的个数为偶数满足偶监督码设码字码奇偶监督码奇偶校验二监督码信息码15a7a6a5a4a3a2a1a7a6a5a4a3a2a1a0信道a7a6a5a4a3a2a1a0输出S应答信号校正子电路发送端接收端16只能用于检错重发方式不能纠错只能检错但无法检测偶数个错个错奇偶监督码可检测奇数小结需要重发有错若不要重发无错若端作为应答信号通知发送利用有错无错满足又称为校正子应答信号在纠错码中)3(;,)2(;,)1(:.,,1,,,0:10:,,01234567SSSaaaaaaaaSS179.2.2行列监督码对水平方向的码元和垂直方向的码元同时实施奇偶监督，在一般情况下有：L×M个信息码元加L+M+1个监督元，组成[L×M+(L+M+1),L×M]行列监督码的一个码字（L+1行,M+1列）。现以(n,k)=(66,50)为例加以说明。18110010100000100001101001111000011100111000001010101010111000111100水平方向偶校验垂直方向偶校验19有关差错的分类:1、随机差错：由加性高斯噪声等引起，特点：一般只错一位的可能最大，但哪位出错则是随机的，经计算得：（1）错一位的概率为：Pe(1)=7×10-3（2）错二位的概率为：Pe(2)=2.1×10-5（3）错三位的概率为：Pe(3)=3.5×10-8由上述结果可见，出一位错的可能性最大。2、突发差错：连续的一串码元出现错误，出错的长度称为突发长度。如磁盘上磁粉失落或划伤后，对其读写会出突发错。209.3线性分组码.,)3(.,,,)2(,)1(:100:,,,,012101210121似之处译码电路与偶校验有类线性分组码的编码既可检错又可纠错较多码元而线性分组码由于监督不能纠错偶校验只能检错督码元线性分组码则有多个监元偶校验只有一个监督码别与偶校验码的联系及区本节讨论的线性分组码分组码中来上述方法可推广到线性表示有错表示无错校正子系之间满足如下的编码关与监督码信息码在偶校验码中aaaaSaaaaaaaannnnnn219.3.1基本概念个禁用码字为个许用码字为许用码组与禁用码组设码字为点来说明线性分组码的特分组码为例现以监督码元信息码元11222162:)1(][:)4,7(4743460356145620123456aaaaaaaaaaaaaaaaaaaAa6a5a4a3a2a1a0000000000010110010101001111001001100101101011001101110001000111100110010100101011001110000111010101110100111111122)(112:)3(3,3,0,:)4,7()2(00能纠一位错纠错能力故得最小码重为码外除全由于该码具有封闭性码的汉明距离的求法ttdd239.3.2监督矩阵H和生成矩阵G（1）监督矩阵H及其物理意义)(]|[001101101011011001110,,:00000010110011101010111010000001234560123456034613562456346035614562标准监督矩阵可表为为监督矩阵为码字式中IPHHaaaaaaaAAHHAHAaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaTTTTT单位矩阵线性分组码的编码规则！24监督矩阵H的物理意义：1）在发送端，可利用监督H来进行编码，因此H实际上是一种编码规则。利用这种编码规则，使得H和码字A满足AHT=0或HAT=02）在接收端，可利用H，对经信道传送过来的码字A进行监督或检测，判断其正确性，若正确，必满足AHT=0或HAT=0，若不正确，则AHT不为0或HAT不为0。3）下文中将要讲述的校正子正是根据这一原理来判断接收码字A的正确性并进行纠错的。25GaaaaAaaaaGAaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaTT34563456345601234563460356145623344556634603561456233445566:1011110111100001001001001000:转置即如下形式前面的式子还可表示为物理意义：由生成矩阵G和信息码产生一个码字（2）生成矩阵G及其物理意义增加的原来的26.,,)(]|[001101101011011001110)(]|[0110001101001011001001111000HGGHPQQPGHIPHQIGTT求或由求可由由此可见或的关系为和生成矩阵监督矩阵显然标准监督矩阵矩阵为由前面得到的标准监督标准生成矩阵（3）生成矩阵G和监督矩阵H的关系279.3.3一种编码电路介绍：根据得编码电路：6a5a4a3a2a1a0a346035614562aaaaaaaaaaaa28例题：设（7,3）线性分组码的监督矩阵为10001100100011001011100110100123456Haaaaaaa监督码元信息码元试求：（1）监督码元与信息码元之间的关系表达式；（2）列出所有的许用码组（必须自己完成）；（3）求汉明距离；能纠几位错？（自己完成）；（4）画出编码器电路。需要用初等变换将其化成标准单位矩阵29解：由于H矩阵不是标准矩阵,需经初等变换后变换成标准矩阵。得变换后的标准矩阵为：1000110010001100101110001101H从而得监督码元与信息码元之间的关系表达式为4505614562463aaaaaaaaaaaaa30进一步可画出编码器电路如下：6a5a4a3a2a1a0a319.3.4S校正子（伴随式）时当时当并且有其中或即也称为误差矢量误图样定义收发码字之差为错接收码字变为可能会发生错误由于传输过程中设发送码字为工作原理来讨论其校正子的基本为例我们仍然以线性分组码iiiiiiinnnnnnabababeeeeeEEABABEEbbbbBaaaaAaaaaaaaaaaaa10],,,,,[,:,,],,,,[,],,,,,[.,01210121012134603561456232.,,,,0,0,0,0:0:][:0:.对接收的码进行纠错利用这一关系对应关系之间有确定的样正子与错误图样由上式知表明有错若不为表明无错若等于故有由发送端的编码规则知校正子为则令接收端的若发送端的编码规则为发送端编码规则应相同注意接收端解码规则与ESEEEHSAHEHAHHEABHSSAHSTTTTTTT33:710317,000000.,)4,7(03460135612456203461356245603461356