第七讲纠错编码

第七讲差错控制编码现代通信理论信源信源编码信道编码调制发转换器媒质收转换器解调信道译码信源译码信宿目的：提高信息传输的的可靠性和有效性，始终是通信工作所追求的目标，纠错编码是提高信息传输可靠性的一种重要手段。第一部分差错控制编码的概念•差错控制编码属于信道编码提高通信系统的可靠性，降低误码率，减少发射功率，提高接收机的灵敏度等等。•信道容量：信息通过信道传输，单位时间内信道上所能传输的最大信息量（即信息速率速率）称为信道容量。对于加性高斯白噪声信道有：C=Blog2(1+S/N)；•香农信道编码理论：通过对信息进行适当的编码，一个含有噪声的信道所引起的差错可以减小到任一期望的水平，而又不会牺牲信息的发射速率；•对于有噪声的信道，存在可以实现可靠通信的信道编码。它能在发送速率RC时达到所期望的任意小的水平，若RC，则无差错传输是不可能的。随机性差错：由高斯噪声引起，差错是随机的且相互间是独立出现的。突发性差错：由脉冲性干扰引起，在短暂的时间内出现大量的差错，而这些短暂时间之后却又存在较长的无误码区间。混合性差错：即存在随机差错又有突发性差错。在信息序列之后附加一些监督码元，这些多余的码元与信息码元之间以某种确定的规则相互关联，接收端按照既定的规则检验出关联关系，如这种规则受到破坏，将会发现错误，乃至纠正错误。二、差错控制的基本方法一、差错类型随机性差错和突发性差错通常采用不同的纠错编码方法。检错与纠错能力与最小码距d0有密切关系：许用码组禁用码组00011110许用码组禁用码组000001010100111101110011可以用来检测出一位错误可纠正一位或检测两位错误AB0123d0AB012345d02.为了纠正t个错误：d0≥2t＋11.为了检测e个错误：d0≥e＋1；3.为了同时检测e个错误，纠正t个错误：d0≥e＋t＋1ABd0ettA0B1无检错与纠错能力三、差错控制方式2.前向纠错（FEC）可以纠正错误发收3.混和纠错（HEC）可以发现和纠正错误发收应答信号比较：译码复杂性、实时性和占用传输链路(单向还是双向)1.检错重发（ARQ）（包括停发等候重发、返回重发和选择重发）能够发现错误发收应答信号ARQ：自动重复请求发送1233123ACKNAKACK等待时间发送端接收端123456234567891011123456234567891011从码组2开始重发NAKACK发现错误停发等候重发返回重发1234562789101121234562789101112重发码组2NAKACK发现错误选择重发四、纠错码分类1.分组码与卷积码：分组码：将信息码分组，为每组信息码后面附加若干位监督码元，且监督码元仅监督本码组中的信息位。1na2nara1ra0aK个信息位r个监督位码长n＝k＋r卷积码：也是先将信息序列分组，后面附加监督位，但是监督位不但与本码组的信息位有关，还与前面码组的信息位有关，或者说监督位不仅监督本码组的信息位还监督其它码组的信息位。2.系统码与非系统码系统码：就是信息位在前，监督位在后的码字。非系统码:信息位与监督位之间无特定的位置关系。五、常用的简单纠错编码1.奇偶校验偶校验00121aaaann设信息位每组长度为n-1位，增加一位监督位，n位编码构成以下约束关系：错误正确100121aaaaSnn接收端计算：奇偶校验可以用来检测单个或奇数个错误2.纵向奇偶校验（LRC）－用于检测突发错误1110011111011101001110011010100111100111110111010011100110101001纵向排列原始数据1110011111011101001110011010100110101010突发错误接收方检验是否满足LRC。LRC10101010监督码元信息码元0101101100010101001000110000111100011100001111111100010011111110110000监督码元00111000010监督码元10010113.水平垂直奇偶校验它能发现某一行或某一列上所有奇数个错误以及长度不大于列数（或行数）的突发错误六、差错控制编码的效用假设在随机信道中发“0”和发“1”的概率相同，可以证明，在码长为n的码组中恰好发生r个错误的概率为：rrnrrnnprnrnppCrP)!(!!)()(15271012212.)(pP8371053353.)(pP可见采用差错控制编码，即使仅能纠正（或检测）1～2个错误，就能使误码率下降几个数量级。3710771pP)(当码长n＝7，误码率P＝10-3时:则有：第二部分线性分组码若监督位增加到2位，就可增加一个监督方程式，接收时就可计算2个校正子S1和S2，共有四种可能，除了00表示无错以外，其余3种就可以表示一位错码的的具体位置了。这里S称为校正子，若S＝0，表示无错，S＝1表示有错误，由于只用了一位监督位a0，因此只能表示有错与无错。0121aaaaSnn•奇偶校验码就是一种效率很高的线性分组码分组码中，信息位和监督位之间由线性方程组联系的编码称作线性分组码，或者说监督码元是由信息码元的线性组合而产生。•一般说来对于，对于r个监督位，可以计算r个校正子，它可以指出种错误图样，即个错误位置，因此对于(n，k)码。要想指出一位错码的所有可能位置，则要求：12r12rrknCnr1123r0123456aaaaaaa123SSS设分组码中（n，k）中k＝4，为了纠正一位错误，则，取r＝3，则n＝7，用表示，用表示由3个监督方程式计算得到的校正子，并假设这3个校正子与误码对应的关系如下表所示：tiinrC112若纠正t个错误一、线性分组码的构成：校正子表S1S2S3误码位置S1S2S3误码位置001a0101a4010a1110a5100a2111a6011a3000无错因此接收端计算下面3个校验关系，可确定误码的位置034631356224561aaaaSaaaaSaaaaS发送端构成偶校验关系000034613562456aaaaaaaaaaaa监督位由信息位的线性组合得到：346035614562aaaaaaaaaaaa许用码组信息位监督位信息位监督位00000001000111000101110011000010101101001000111101011001010011011000010101101110101001100111110100011100011111113456aaaa012aaa3456aaaa012aaa001102031415061000112031405161000102130415161aaaaaaaaaaaaaaaaaaaaa00010011010101011001011101234567Taaaaaaaa二、线性分组码的生成和监督矩阵1.监督矩阵TTHA0即：0123456Aaaaaaaa0000100110101010110010111H其中：][rIPH1001101010101100101110其中P为r×k阶矩阵，Ir为r×r阶单位阵，具有H0形式称为典型形式的监督矩阵；线性代数理论告诉我们，典型形式的监督矩阵各行一定是线性无关的，非典型形式的监督矩阵可以通过矩阵的初等变换转化为典型形式的监督矩阵。34634565634560123456aaaaaaaaaaaaaaaaaaaa2.生成矩阵对于所有的编码与信息位的关系：34563463564563456012345601234561111111111111aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaATTTGaaaaaaaa345634561101000101010001100101110001GaaaaA3456则QIGk1101000101010001100101110001其中Q为K×r阶矩阵，Ik为k阶单位阵具有典型化形式G0=[Ik，Q]的生成矩阵称为典型生成矩阵它与典型化形式H0=[P，Ir]的关系为：TTPQQP或,结论：线性分组码的特性：1)任意两个许用码组之和仍为许用码组－封闭性2)码的最小距离等于非零码的最小重量。1)由典型化的生成矩阵产生的是系统码组；2)典型化的生成矩阵的各行也必定是线性无关的，每一行都是一个许用码组，k行许用码组经过运算可以生成2k个不同的码组；3)非典型形式的生成矩阵经过运算也一定可化为典型形式。三、线性分组码的伴随式译码].......,,,[021rrrRnn].......,,,[021eeeEnn发送码组为A，接收码组为R设E为传输错误图样，则：R－A＝ETTTTTEHEHAHHEARHS)(计算校正子TTHES或者校正子S只与E有关，若接收码字R中第i位有错，那么导出的伴随式恰好是矩阵H的第i列相同的位置。利用伴随式不仅可以判决接收码字中是否有错，而且可以指出差错的位置。TTHES61110000001100110101010110010111HHET对于前面的例子，一位错误图样为（1000000)，（0100000)，(0010000),(0001000)，(0000100)，(0000001)，(0000001)50110000010101100111010101110100H01001000000100110101010110010111H……….第三部分循环码一、特点：循环码是一种具有循环移位特性的线性分组码，这类码除了具有线性分组码的一般性质外，还具有循环性质带来的其它性能和特征，并可以用不太长的码长来实现，循环码本身的特性使编译设备比较容易实现。1.码多项式：012211cxcxcxcxCnnnn)(即：若C＝[Cn-1Cn-2……..C1C0]是一个码字，则C的每次循环移位:[Cn-2Cn-3……..C0Cn-1][C0Cn-1Cn-2……C2C1]都是一个码字。………）模（17x,...,,29871xxxxx例：(7，3)循环码)1(2346236xxxxxxxx)1(23422456xxxxxxxx)1(1234525xxxxxxx)1(12343356xxxxxxx1234xxx)1(234345xxxxxxxx)1(1234446xxxxxxx序号信息码00000000000100100111010201101110101311111101002411011010013510110100114601001001115710010011106码多项式移位次数(7.3)循环码按模运算规则：模n运算下，一整数m等于其被n除得到的余数．模２运算中，１＋１＝２＝０２＊３＝６＝０r