信息论理论基础课件.ppt

2022/12/3,1,信息论基础第4章 抗干扰二元编码,韩宇辉,2,2022/12/3,第4章 抗干扰二元编码,4.1 抗干扰二元编码的基本概念4.2 检错码4.3 用于单向信道的简单纠错码4.4 纠一位错误的汉明码4.5 循环码4.6 纠正独立错误的卷积码4.7 纠正突发错误的编码4.8 有限域的基本知识,2022/12/3,3,4.1 抗干扰二元编码的基本概念,4,2022/12/3,4.1.1 抗干扰编码的基本思想,00 01 10 11,0,0,1,1,奇校验,抗干扰编码的基本思想：利用剩余的增加来换取可靠性的提高,信息元,监督元,许用码字：系统实际使用的码字。001,010,100,111禁用码字：系统中不使用的码字。000,011,101,110,5,2022/12/3,4.1.2 几个定义, 码距（汉明距离）W =x1 x2 xn xi 0,1W=x1x2xn xi 0,1 最小码距（最小汉明距离）一个码组（码字）集合中，两码字间的最小距离dmin称为该码字集合的最小距离，简称最小码距。 码重（汉明重量）码组中所含码元“1”的数量，称为该码组的重量，简称码重。,6,2022/12/3,4.1.3 最小码距与纠检错能力的关系,1.译码准则,X:x1, x2, , xn Y:y1, y2, , ymP(Y/X):p(yj/xi); i=1,2,n; j=1,2,m这时定义一个收到yj后判定为xi的单值函数，即： F(yj)=xi (i=1,2,n; j=1,2,m)；这个函数称为译码函数。它构成一个译码函数组，这些函数的值组成了译码准则。,对于有n个输入，m个输出的信道来说，可以有nm个不同的译码准则。,7,2022/12/3,2.最小码距译码准则若 d(x*j,yj) d(xi,yj) (对一切的i)，则F(yj)=x*j (j=1,2,m， x*j X )3.最小码距与纠检错能力的关系,【例】 X：0000000,1111111， dmin=7检错能力：发送码字：接收码字：判断结果：纠错能力：发送码字：接收码字：译码结果：,0000000,0000000 ,0000000,0000000 ,1000000,0000000 ,1100000,0000000 ,1110000,1111111 ,1111000,1111111 ,1111100,1111111 ,1111110,1111111 ,1111111,0000000,最多可以发现6位错误,0000000,传输正确 ,最多可以纠正3位错误,1000000,传输错误 ,1100000,传输错误 ,1110000,传输错误 ,1111000,传输错误 ,1111100,传输错误 ,1111110,传输错误 ,1111111,传输正确 ,8,2022/12/3,纠错同时检错的能力纠正1位错误：发送码字：接收码字：判断结果：译码结果：纠正2位错误：发送码字：接收码字：判断结果：译码结果：,0000000,0000000,1000000,1100000,1110000,1111000,1111100,1111110,1111111,0000000,最多可以同时发现5位错误,0000000,传输正确 ,1000000,传输错误 ,1100000,传输错误 ,1110000,传输错误 ,1111000,传输错误 ,1111100,传输错误 ,1111110,传输错误 ,1111111,传输正确 ,最多可以同时发现4位错误,0000000 ,0000000 ,不进行译码,不进行译码,不进行译码,不进行译码,1111111 ,1111111 ,传输正确 ,传输错误 ,传输错误 ,传输错误 ,传输错误 ,传输错误 ,传输错误 ,传输正确 ,0000000 ,0000000 ,0000000 ,不进行译码 ,不进行译码,1111111 ,1111111 ,1111111 ,9,2022/12/3,若发现e个错误，则要求 dmine+1;若纠正t个错误，则要求 dmin2t+1;若纠正t个错误，同时发现e个错误，则要求dmint+e+1 （ te ）,10,2022/12/3,4.1.4 抗干扰编码的基本原理,1.原理： dmin与纠检错能力的关系2.实现方法：信息元+监督元3.代数编码：信息元与监督元是按一定的代数关系互相制约的。(1)分组码（块码） k信息位长度 n码长 r=n-k监督位长度特点：无记忆性(n,k)分组码的码率（编码效率）：=R/C=H(A)/Hmax(A)=k/n,11,2022/12/3,分组码按其结构可以分为系统码和非系统码。如果在一个分组码码字中，信息元安排在前k位，而监督元安排在后n-k=r位，则称其为系统码，否则就称为非系统码。(2)卷积码（连环码） m=m+1编码器的约束长度 或编码约束长度 n=n0m卷积码的约束长度 特点：有记忆性，输出不仅与当时的输入有关，还与前m个单位时间的输入有关。(n0,k0,m)卷积码的码率（编码效率）：=k0/n0,12,2022/12/3,4.抗干扰编码的分类(1)用途：检错码和纠错码(2)干扰的性质： 纠正独立错误的编码和纠正突发错误的编码 独立错误也称为随机错误，是由随机噪声引起的，其特点是各码元发生错误与否是互相独立的，因而一般不会成片地出现错误。 突发错误是由突发噪声（脉冲噪声、深衰落、接触不良引起噪声等）引起的，其特点是各码元是否发生错误存在某种相关性。通常称突发错误持续时间内的码元数目为突发长度。(3)对信息的处理方式：分组码和卷积码(4)约束关系：线性码和非线性码(5)信息元的位置：系统码和非系统码,13,2022/12/3,5.差错控制系统的分类(1)ARQ(Automatic Repeat reQuest)自动反馈重传 采用检错码，接收端收到码字后判断在传输中有无错误产生，并通过反馈信道把检测结果告诉发送端。发端把收端认为有错的消息再次传送，直到收端认为正确为止。优点：译码设备简单，由于同一种码的检错能力比纠错能力要高得多，因而整个系统能获得极低的误码率。缺点：应用ARQ方式必须有一条从收端至发端的反馈信道，只适用于点对点的方式，并要求收、发两端必须互相配合，其控制电路比较复杂，实时性也较差。,14,2022/12/3,(2)FEC(Forward Error Correction)前向纠错 采用纠错码，接收端收到码字后，自动地纠正传输中的错误。优点：不需要反馈信道，既适用于点对点的方式，也适用于点对多点的方式，实时性较好，控制电路也比较简单。缺点：译码设备较复杂，编码效率较低。,(3)HFC(Hybrid Error Correction)混合纠错 是前两种方式的结合。发端发送的码既能检错、又有一定的纠错能力。收端译码时若发现错误个数在码的纠错能力以内，则自动进行纠错；若错误个数超过了码的纠错能力，但能检测出来，则通过反馈信道告知发方重发。,2022/12/3,15,4.2 检错码,16,2022/12/3,一致监督检错码也叫一致监督校验码或奇偶校验码。1.原理：信息元（k位）：x1，x2， ，xk监督元（1位）： xn = xk+1偶校验：奇校验：,4.2.1 一致监督检错码,17,2022/12/3,2.漏检概率 奇偶校验码只能发现码字中的奇数个错误，不能发现偶数个错误。n为偶数：n为奇数：若 ，则,18,2022/12/3,定比码也称恒比码、等重码或范德伦码，每个码字中“1”与“0”的比例是固定的，“1”的个数也是固定的。 1.五三定比码 五三定比码每个码字的码长为5，含有3个“1”和2个“0”的码字作为许用码字。 (1) 许用码字数目： 禁用码字数目：,4.2.2 定比码,19,2022/12/3,(2) 漏检概率 若“1”错成“0”的数目正好等于“0”错成“1”的数目，则五三定比码不能发现这类错误。 一个码字中有2位错误，且其中1位“1”错成“0”， 1位“0”错成“1”的概率为 一个码字中有4位错误，且其中2位“1”错成“0”， 2位“0”错成“1”的概率为 因此，漏检概率为 当 时，,20,2022/12/3,(3) 编码效率 =R/C=H/Hmax=log10/log3266%2.七三定比码 七三定比码每个码字的码长为7，含有3个“1”和4个“0”的码字作为许用码字。 (1) 许用码字数目： 禁用码字数目： (2) 编码效率 =R/C=H/Hmax=log35/log12872%,21,2022/12/3,(3) 漏检概率 一个码字中有2位错误，且其中1位“1”错成“0”， 1位“0”错成“1”的概率为 一个码字中有4位错误，且其中2位“1”错成“0”， 2位“0”错成“1”的概率为 一个码字中有6位错误，且其中3位“1”错成“0”， 3位“0”错成“1”的概率为因此，漏检概率为 当 时，,2022/12/3,22,4.3 用于单向信道的简单纠错码,23,2022/12/3,编码效率：=1/n(1) 逐位重复：用于纠正随机错误。(2) 逐段重复：还可用于纠正突发错误。例如，1 0 1 1 0 1 0 0逐位重复，三重码：111 000 111 111 000 111 000 000逐段重复，四位一段，三重码：1011 1011 1011 0100 0100 0100,4.3.1 简单重复码,将信息重复多次，只要正确传输的次数多于传错的次数，则可以将错误纠正过来。重复次数n通常为奇数。,2022/12/3,24,4.4 纠一位错误的汉明码,25,2022/12/3,1.线性分组码的定义若分组码的监督元与信息元之间是一种线性约束关系，则称其为线性分组码。(n,k) 线性分组码的码率：=k/n许用码字数目：2k禁用码字数目：2n -2k系统码：x1 x2 xk xk+1 xk+2 xn,信息元,监督元,26,2022/12/3,2.线性分组码的监督矩阵线性分组码监督元与信息元之间的线性关系可以用二元域上的线性方程组描述。整理得：,27,2022/12/3,将方程组用矩阵方程来表示，可得,监督矩阵H,H CT= 0,码字向量 C =x1 x2 xn ,28,2022/12/3,rk子阵P,rr单位阵Ir,r=n-k行：r个监督元，r个监督方程n列：n个码元之间的监督关系,(n,k)系统线性分组码监督矩阵形式:(典型监督矩阵或标准监督矩阵),H=P Ir,29,2022/12/3,3.线性分组码的生成矩阵,30,2022/12/3,码字C,信息码组m,生成矩阵G,由于对于矩阵A，B，C有因此,C =mG,31,2022/12/3,G=Ik PT,(n,k)系统线性分组码生成矩阵形式:(典型生成矩阵或标准生成矩阵),子阵PT,kk单位阵Ik,k行n列,32,2022/12/3,【例】已知线性分组码的生成矩阵G，写出信息码组m1=1 0 0 0， m2=0 1 0 0， m3=0 0 1 0， m4=0 0 0 1， m5=1 1 0 0， m6=1 1 1 0， m7=1 1 1 1 对应的各个码字。 C1=m1 G =1 0 0 0 G=1 0 0 0 0 1 1 C2=m2 G =0 1 0 0 G=0 1 0 0 1 0 1 C3=m3 G =0 0 1 0 G=0 0 1 0 1 1 0 C4=m4 G =0 0 0 1 G=0 0 0 1 1 1 1,解：,33,2022/12/3,C5=m5 G =1 1 0 0 G=1 1 0 0 1 1 0 C6=m6 G =1 1 1 0 G=1 1 1 0 0 0 0 C7=m7 G =1 1 1 1 G=1 1 1 1 1 1 1,(n,k)线性分组码的2k个码字构成二元n重矢量空间中的一个k维子空间。 (n,k)线性分组码的生成矩阵由k个线性无关的码字矢量组成，构成k维子空间的一个基底，其线性组合可以生成所有的码字。,34,2022/12/3,【例】已知线性分组码的监督矩阵为判断其码长和信息位长度，并写出其生成矩阵G。解： r=3，n=7 ， k=4 H=P I3 G=I4 PT,35,2022/12/3,4.线性分组码的译码(1)错误图样发送码字： 接收码字：错误图样：,ei=1表明相应位有错，ei=0表明相应位无错。,36,2022/12/3,(2)校验矩阵定义S=HRT为校验矩阵，也称为校验子或伴随式。若S=0，表明收到的码字为许用码字，译码器认为接收码字无错误。若S0，表明收到的码字为禁用码字，可以判定接收码字一定有错误。由于 因此,校验子与发送码字无关，而仅与错误图样有关。,37,2022/12/3,(3)校验子与译码【例】(7,4) 线性分组码的监督矩阵为(1) 无错 E=0 0 0 0 0 0 0(2) 错一位 E=1 0 0 0 0 0 0 E=0 1 0 0 0 0 0 E=0 0 1 0 0 0 0,S= HET=0 0 0T,S= HET=0 1 1T,S= HET=1 0 1T,S= HET=1 1 0T,38,2022/12/3,若校验子为0，认为收到的码字没有错误；若校验子恰好等于H的第i列，认为接收码字的第i位发生了错误。,线性分组码可以纠正1位错误需满足的条件： H的各个列不同且不含有全0列； 2r-1n。,39,2022/12/3,5.汉明码(1)汉明码的定义对于任意正整数r3，存在有下列参数的线性分组码：码长：n 2r-1信息位：k=n-r监督位：r=n-k最小码距：dmin=3 这种码称为汉明码。若n = 2r-1称为狭义汉明码或完备汉明码；若n 2r-1称为广义汉明码。(2)汉明码H矩阵的构造 将2r-1非全0的r维列向量作为H的各列。,40,2022/12/3,【例】构造(7,4) 汉明码的监督矩阵。解：n=7，k=4，r=n-k=3。由于n = 2r-1，故为狭义汉明码。将7个非全0的3维列向量作为H的各列即可。或,系统码,非系统码,41,2022/12/3,(3)汉明码的错误译码概率 狭义汉明码 狭义汉明码可以纠正一位错误，因此其错误译码概率为：由于当 时，有因此当 时，有所以,42,2022/12/3, 广义汉明码 广义汉明码可以纠正一位错误，还可以纠正部分2位及2位以上的错误，因此其错误译码概率：比如，(6,3)广义汉明码的监督矩阵为错2位时：若第1位和第6位错，或者第2位和第5位错，或者第3位和第4位错，校验子均为1 1 1T。因此，不妨规定当校验子为1 1 1T时，译作第1位和第6位错。此时，该广义汉明对于第1位和第6位错这种错两位的情况也可以纠正。,43,2022/12/3,(4)增余汉明码在汉明码的基础上，再增加一位监督元，使汉明码的最小码距dmin=4，可以在纠一位错的同时检两位错，这种线性分组码称为增余汉明码。增加的监督元通常取为原汉明码所有码元的模2和，也就是说增余汉明码的H矩阵是在原汉明码H矩阵的最右侧加上一个全0列，再在下面加上一个全为1的行。,44,2022/12/3,(7,4)汉明码(8,4)增余汉明码H矩阵的各个列不同，且任何两列之和不同于另一列，因此可以纠1位错的同时检出2位错。增余汉明码的构成方法不唯一。,1 1 1 1 1 1 1 1,1 1 1 0 0 0 0 1,2022/12/3,45,4.5 循环码,46,2022/12/3,1.循环码的定义具有循环移位自闭性的线性分组码称为循环码。所谓循环移位自闭性是指码字集合中的任何一个码字的循环移位也是该码字集合中的一个码字。若 C(0)=cn-1,cn-2,c1,c0C (C为许用码字集合) ， 则 C(1)=cn-2,cn-3,c0,cn-1C。,0000000,0011101,0100111,0111010,循环码,1001110,1010011,1101001,1110100,循环码,000,001,010,011,信息码,100,101,110,111,信息码,(7,3)系统循环码,47,2022/12/3,2.循环码的多项式描述一个(n,k)循环码的码字c=cn-1, cn-2, ,c1, c0可以用一个二元域上的n-1次多项式表示： c(x)= cn-1xn-1+cn-2xn-2+c1x+c0 ci 0,1 这个多项式称为码字多项式或码多项式。 码字矢量的向左循环移位一次可以用x乘上C(x)后取模xn-1(或xn+1)来表示。 模xn-1相当于xn-1=0，即xn=1 xc(x) = x(cn-1xn-1+cn-2xn-2+c1x+c0) = cn-1xn+cn-2xn-1+c1x2+c0 x = cn-2xn-1+c1x2+c0 x+ cn-1 (模xn-1),48,2022/12/3,3.循环码的生成多项式定义：(n,k)循环码中，次数最低的非0码多项式是唯一的，其次数为r=n-k次。该多项式称为循环码的生成多项式。 g(x)= grxr+gr-1xr-1+g1x+g0 （gr=g0=1）g(x), xg(x), x2g(x), , xk-1g(x)为k个线性无关的码字，可以作为该循环码生成矩阵的k行。,49,2022/12/3,信息码组m=mk-1,mk-2, ,m0 对应的码多项式为： c(x)=mk-1,mk-2, ,m0 G(x) =mk-1xk-1g(x)+ mk-2xk-2g(x)+ + m0g(x) =m(x)g(x),结论：所有循环码的码多项式都是其生成多项式g(x)的倍式；反之，任何次数不大于n-1次的多项式也一定是码多项式。,50,2022/12/3,4.循环码的编码(1)非系统循环码c(x)=m(x)g(x)【例】已知(7,4)循环码的生成多项式为g(x)= x3+x+1，求信息码组0 1 0 1对应的循环码码字。解： m(x)= x2+1 c(x)= m(x)g(x) =(x2+1)(x3+x+1) = x5+x3+x2+x3+x+1 = x5+x2+x+1 C=0 1 0 0 1 1 1,51,2022/12/3,(2)系统循环码信息多项式m(x)=mk-1xk-1+ mk-2xk-2+ + m0所对应的系统循环码的码多项式c(x)应满足如下条件： c(x)的次数不大于n-1次，即可以表示c(x)= cn-1xn-1+cn-2xn-2+c1x+c0； c(x)为g(x)的倍式； cn-1=mk-1，cn-2=mk-2， ，cn-k=m0。系统循环码编码步骤： ( r(x) 次数n-k-1 ) ,52,2022/12/3,由于因此可见，c(x)为g(x)的倍式，条件满足。,53,2022/12/3,【例】(7,4)循环码g(x)=x3+x+1，求m=1010的系统循环码码字。解：m(x)=x3+x xn-km(x)=x3(x3+x)=x6+x4 C(x)=xn-km(x)+r(x)=x6+x4+x+1；C=1010 011,x3x6 +x4+x3 x3,除式,x6 +x4,x3+x+1,+1,x3+x+1,x+1,被除式,商式,余式,54,2022/12/3,(3)如何确定g(x)?定理1：(n,k)循环码的生成多项式g(x)是xn-1的因式。定理2：若g(x)是一个n-k次多项式，且为xn-1的因式，则g(x)一定可以生成一个(n,k)循环码。例如，x7-1= (x+1)(x3+x2+1)(x3+x+1)(7,6)循环码： g(x) = (x+1)(7,4)循环码： g(x) = x3+x2+1 或 g(x)= x3+x+1(7,3)循环码： g(x) = (x+1)(x3+x2+1) 或 g(x)=(x+1)(x3+x+1)(7,1)循环码： g(x) = (x3+x2+1)(x3+x+1),结论： xn-1的诸因式决定了所有码长为n的循环码。,55,2022/12/3,5.循环码的译码,发送码字多项式：c(x)=cn-1xn-1+cn-2xn-2+c1x+c0错误图样多项式：e(x)=en-1xn-1+en-2xn-2+e1x+e0接收码字多项式：c(x)=cn-1xn-1+cn-2xn-2+c1x+c0 c(x)=c(x)+e(x)校验子多项式：s(x) c(x) e(x) 模g(x) s(x)=sr-1xr-1+sr-2xr-2+ +s0 r-1次多项式 若s(x) =0，表明收到的码字为许用码字，译码器认为接收码字无错误。 若s(x)0，表明收到的码字为禁用码字，可以判定接收码字一定有错误。,56,2022/12/3,【例】(7,4)循环码g(x)=x3+x+1，求接收码字不错或只错一位时的校验子多项式。,57,2022/12/3,这个表给出了接收码字不出错或只错一位时校验子多项式和校验子矢量的结果。根据这个表可以进行译码。例如，发送码字多项式为 c(x)=x4+x2+x 接收码字多项式为c(x)=x4+x3+x2+x g(x)=x3+x+1 校验子多项式为：s(x) c(x) 模g(x) = x+1 查表可知 e(x)=x3 因此 c(x)=c(x)+e(x)=x4+x2+x 发送码字为 0010110,58,2022/12/3,6.截短循环码通常xn-1只能分解出不多的几个因式，因此使得给定长度为n的循环码的数量往往很少。为了克服这个缺点，出现了截短循环码。对于一个(n,k)循环码，若取所有前i个信息元均为0的码字构成一个子集(0ik)，其监督位长度不变，信息位长度减少至k-i位，则得到一个(n- i,k- i)码，称为截短循环码或缩短循环码。截短循环码是原循环码的子集，因此它的最小码距保证了它的纠错能力不会低于原来的(n,k)循环码。,59,2022/12/3,截短循环码的H矩阵可以从原码的H矩阵中除去前i列而得到，G矩阵可以从原码的G矩阵中除去前i列和前i行而得到。例如，可以由(7,4)循环码构成(5,2)截短循环码。,(7,4)循环码,(5,2)截短循环码,60,2022/12/3,截短循环码的H矩阵可以从原码的H矩阵中除去前i列而得到，G矩阵可以从原码的G矩阵中除去前i列和前i行而得到。例如，可以由(7,4)循环码构成(5,2)截短循环码。,(7,4)循环码,(5,2)截短循环码,2022/12/3,61,4.6 纠正独立错误的卷积码,62,2022/12/3,卷积码的最大特点是有记忆性， (n0,k0,m)卷积码编码器在j时刻输出与 j，j-1，j-2， ， j-m+1共m个单位时间的输入有关。m 编码器的约束长度或编码约束长度n=n0m 卷积码的约束长度,4.6.1 卷积码的基本监督矩阵,63,2022/12/3,mj第j个子码的信息元；pj,1, pj,2 第j个子码的监督元；Cj=mj, pj,1, pj,2 第j个子码；Cj=cj-2, cj-1 ,cj 第j个约束度内的卷积码。Cj=mj-2, pj-2,1, pj-2,2 , mj-1, pj-1,1, pj-1,2 , mj, pj,1, pj,2,mj-1,mj-2,(3,1,3)卷积码,pj,1 = mj + mj-1; pj,2 = mj + mj-2,64,2022/12/3,第j个约束度内的卷积码共包括9个码元： mj-2, pj-2,1, pj-2,2 , mj-1, pj-1,1, pj-1,2 , mj, pj,1, pj,2 将两个约束方程改写： pj,1 = mj + mj-1; pj,2 = mj + mj-20mj-2+0pj-2,1+0pj-2,2+1mj-1+0pj-1,1+0pj-1,2+1mj+1pj,1+0pj,2=0 1mj-2+0pj-2,1+0pj-2,2+0mj-1+0pj-1,1+0pj-1,2+1mj+0pj,1+1pj,2=0表示为矩阵的形式,基本监督矩阵h,65,2022/12/3,mj-2, pj-2,1, pj-2,2 ; mj-1, pj-1,1, pj-1,2 ; mj, pj,1, pj,2,P2,P1,P0,02X2,02X2,I2,h2,h1,h0,(n0,k0,m)卷积码h的标准形式： h= hm-1 hm-2 h0 =Pm-1 0 Pm-2 0 P0 Ir0 ,hr0Xn； hm-1,hm-2, ,h0 r0Xn0；Pr0Xk0； 0r0Xr0。,66,2022/12/3,4.6.2 卷积码的一致监督矩阵,67,2022/12/3,4.6.3 卷积码的生成矩阵,68,2022/12/3,4.6.4 卷积码的编码方法,69,2022/12/3,4.6.7 维特比译码,2022/12/3,70,4.7 纠正突发错误的编码,71,2022/12/3,2022/12/3,72,4.8 有限域的基本知识,73,2022/12/3,