差错控制编码

第7章差错控制编码7.1差错控制编码的基本原理7.2简单控制编码7.3线性分组码和汉明码7.4循环码7.5卷积码7.6turbo码传输ASCII码010001110100110001011010ILY010001110100011001011010IHY7.1差错控制编码的基本原理加性噪声、码间串扰都会产生误码。为提高系统抗干扰性能，可以加大发射功率，降低接收设备本身的噪声，合理选择调制、解调方法等。差错控制编码即是减少加性干扰造成错误判决的措施之一。差错控制编码：是在信息序列上附加上一些监督码元，利用这些冗余的码元，使原来不规律的或规律性不强的原始数字信号变为有规律的数字信号；采用差错控制编码，即使仅能纠正（或检测）这种码组中1~2个错误，也可以使误码率下降几个数量级。一般说来，编码中增加的监督码元越多，检(纠)错的能力就越强。差错控制译码则利用这些规律性来鉴别传输过程是否发生错误，或进而纠正错误。1.差错控制的工作方式反馈校验法：接收端将收到的信码原封不动地转发回发送端，发送端将其与原发送信码比较，如果发现错误，则重发。混合纠错(HEC)：当收到少量的错码时，就在接收端直接纠正，当错码太多超过其纠错能力时，则采用差错重发方式。前向纠错法：接收端不仅能在收到的信码中发现有错码，还能够解定错码的位置，纠正错码。检错重发(ARQ)：接收端在收到的信码中检测出(发现)错码时，即设法通知发送端重发，直到正确收到为止。发端纠错码收端前向纠错FEC发端检错码收端检错重发ARQ判决信号发端检错和纠错码收端混合纠错HEC判决信号既存在随机错误又存在突发错误的信道称为混合信道。突发错误：错码成串出现，在短促的时间区间内错误密集成群，而在这些短促的时间区间之间却又存在较长的无错码区间。以突发错误为的信道称为突发信道。（脉冲干扰、信道中的衰落现象）。随机错误:错误的位置是随机,且统计独立高斯白噪声)。以随机错误为主的信道称为随机信道。2.差错控制编码的类别按照编码的用途不同，差错控制编码可分为检错码、纠错码、纠删码。按照监督码元和信息码元的不同关系，差错控制编码可分为线性码和非线性码。按照对信息码元的处理方式不同，差错控制编码可分为分组码和卷积码。按照码组中的信息码元在编码前后的位置是否发生变化，差错控制编码分为系统码、非系统码。按照编码针对的不同干扰类型，差错控制编码可分为纠(检)随机(独立)错误码、纠(检)突发错误码和既能纠(检)随机错误，有纠(检)突发错误码。纠错编码线性码分组码卷积码非线性码非循环码循环码纠随机错误码纠同步错误码纠随机突发错误码纠突发错误码纠错编码分类示意图3.差错控制编码的基本方法最小码距：在码字集合中全体码字之间距离的最小数值用d0表示。4码间距离d及检错纠错能力码长:码字中码元的数目；码重:码字中非0数字的数目；码距：两个等长码字之间对应位不同的数目，有时也称作这两个码字的汉明距离，用d表示。码组11010码长N=5，码重w=3码组11010和10100，码距d=310100⊕11010=01110两个码组的模二相加得到的新码组的重量就是这两个码组之间的距离。码组集合000011101110的最小码距d0为2码距纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，抗干扰能力就越强。(1)检测错误时，如果要检测e个错误，则dmin≥e+1；(2)纠正错误时，如果要纠正t个错误，则dmin≥2t+1；(3)纠t个错误，同时检e个错误时(et)，则dmin≥t+e+1。eBAd0tAtB1tAeB1(a)(b)(c)d0d05.编码效率η是指码字的信息码元个数k与总的码长n的比值，即：nrnnk7.2简单控制编码7.7.2奇偶监督码偶监督码规则:在信息位后加上一位监督位，要求整个码字中“1”的个数为偶数，例如1011001010100110不能确定如果是奇监督，则要求整个码字中“1”的个数为奇数，例如1011001110100010有错奇偶监督码的编码可以用软件实现，也可用硬件电路实现。如果码组B无错，B＝A，则M＝0；如果码组B有单个（或奇数个）错误，则M＝1。a4a3a2a1a0a4a3a2a1信息组编码输出b0b4b3b2b1接收码组检错信号SBAM二维奇偶监督码，它是将若干个信息码字按每个码字一行排列成矩阵形式，然后在每一行和每一列的码元后面附加一位奇（偶）监督码元。信息码元监督码元信息码元监督码元10110001101100011101001011010010001001110110011101101100011011001001100110011001监督码元10110001101100017.2.2二维奇偶监督码7.3线性分组码和汉明码7.3.1线性分组码的定义及性质线性码有一个重要性质，就是它具有封闭性。即线性码中的任意两个码组之各仍为该码中的一个码组。所谓线性分组码，是指信息位和监督位满足一组线性方程，编码规则用一组线性方程来描述的分组码。分组码是一组固定长度的码组，可表示为(n,k)，k个信息位被编为n位码组长度，而r=n-k个监督位的作用就是实现检错与纠错。信息位(n)监督位(r=n-k)a6a5a4a3a2a1a01011001(7,4)线性分组码编码效率η=k/n(7,4)线性分组码a0=a6a4a3监督关系：a2=a6a5a4a1=a6a5a3线性分组码的生成矩阵和监督矩阵输入：1011a6a5a4a3a2a1a000110110011111001误码不满足监督关系(纠错)a2a6a5a4=1a1a6a5a3=1a0a6a4a3=0=a5错a0=a6a4a3a2=a6a5a4a1=a6a5a3线性分组码的生成矩阵和监督矩阵Taaaaaaa0123456100110101010110010111000简记作H·AT=0T或A·HT=0监督矩阵H写成矩阵形式接收端H·AT≠0T说明有错a0=a6a4a3a2=a6a5a4a1=a6a5a3线性分组码的生成矩阵和监督矩阵a3=a3a4=a4a5=a5a6=a6[a6a5a4a3a2a1a0]=[a6a5a4a3]1000111010011000101010001011生成矩阵GGGMA3456aaaa可以根据生成矩阵写出编码1011001111010011010101011001H==[PIr]G=[IkQ]Q=PT汉明码是一种能够纠正单个错误的线性分组码。它有以下特点：(1)最小码距dmin＝3，可纠正一位错误；(2)码长n与监督元个数r之间满足关系式：12rn6.7.3汉明码如果信息长度为5位，要求纠正1位错，需要增加的校验位是()。对于(n,k)线性分组码，由于它的监督码元数为r=n-k，只发生一位错误时，监督码元的应能指出所有n个码元位置上出错及全对共(n+1)中情况。2n-k≧n+1汉明码校验和与错误码元位置对应关系为：S1=a6a5a4a2S2=a5a4a3a1S3=a6a4a3a0S1S2S3错码位置S1S2S3错码位置001101010110100111011000a0a1假设某汉明码的监督关系为a2a3a6a5a4无错rIPH100011101011100011101已知某汉明码监督矩阵：试求（1）n=?，k=?，（2）验证1111001和0101011是否有错，若有错，请纠正之。（3）若信息码元为1001，写出其相应的汉明码字。?rIPH100011101011100011101(1)n=7，k=4，7/40111001111100011101011100011101a3错误，正确的序列为1110001S=BHT=(A+E)HT=EHTS1=a6a4a3a2S2=a5a4a3a1S3=a6a5a4a0S=当0101011，a2错误，正确的序列为0100011(3)1111001(2)信息码元1001，由监督矩阵H：对应的生成矩阵为101110001110101110001H==[PIr]1000101010001100101110001110G=[IkQ]=[IkPT]=A=M·G=[1001]G=[1001011]一对码字之间的海明距离是()A.码字之间不同的位数B.两个码字之间相同的位数C.两个码字的校验和之和D.两个码字的校验和之差A一个码的最小码距是所有不同码字的码距的()A．平均值B．最大值C．最小值D．任意值如果要检查出d位错，那么码的最小码距是()A．d-1B．d+1C．2d-1D．2d+l如果信息长度为5位，要求纠正1位错，按照海明编码，需要增加的校验位是()A．3B．4C．5D．6以太网中使用的校验码标准是()A．CRC-12B．CRC-CCITTC．CRC-16D．CRC-32CBBD为了进行差错控制，必须对传送数据帧进行校验。在局域网中广泛使用的校验方法是(1)校验。CRC—16标准规定的生成多项式为G(x)=X16+X15+X2+l，它产生的校验码是(2)位，接收端发现错误后采取的措施是(3)。如果(9,5)CRC的生成多项式为G(X)=X4+X+1，信息码字为10110，则计算出的CRC校验码是(4)。(1)A．奇偶(Parity)B．海明(Hamming)C．格雷(Gray)D．循环冗余(CyclicRedundancy)(2)A．2B．4C．16D．32(3)A.自动纠错B．报告上层协议C．自动请求重发D．重新生成原始数据(4)A．0100B．1010C．0111D．1111DCCD7.4循环码7.4.1循环码的基本概念及码多项式所谓循环码，是指任何一个码字循环右移一位后所得到的仍是一个合法码字。属于线性分组码，应用：局域网数据传输。00000000010111→1001011→1100101→1110010—0101110←1011100←0111001←循环码特点：编码电路简单，可以很容易的用带有反馈的移位寄存器来实现。码字的多项式描述设码字A=(a0,a1,…,an-1)，10111A=an-1xn-1+an-2xn-2+…+a1x+a0例如：1011x3+x+1可以用码字多项式:表示。x4+x2+x+1xk-1g(x)xk-2g(x)…xg(x)g(x)G=g(x)生成多项式，循环码的生成矩阵G可以写成x2g(x)xg(x)g(x)100101101011100010111G=101110001011100010111=G=例如：g(x)=x4+x2+x+1，则7.4.2循环码的生成多项式及生成矩阵7.4.3循环码的编码原理步骤：1.写出码多项式m(x)2.写出xn-km(x)3.用(生成多项式)G(x)除(码多项式)m(x)4.得余式R(x)模2运算5.写出消息码组:信息码在前、监督码在后。信息码0111(7,4)循环码组，生成多项式G(x)=x3+x+1码多项式m(x)=x2+x+1x7-4m(x)=x5+x4+x3用G(x)除m(x)得余式R(x)=x-010消息码组0111010例计算信息码110的(7，3)循环码组，生成多项式G(x)=x4+x2+x+1。步骤：码多项式m(x)=x2+x+0xn-km(x)=x4(x2+x)=x6+x5用(生成多项式)G(x)除xn-km(x)x4+x2+x+1除x6+x5(模2运算)得余式R(x)=x2+1写出消息码组：信息码在前、监督码在后110010111110111∕1100000信息码补n-k个01011111110101111001010111101