第九章-差错控制编码-(1)要点.ppt

1,第9章差错控制编码,2,通信系统,信源编码（减少）冗余，提高编码效率；信道编码提高信息传递的可靠性.,3,9.1纠错编码的基本概念,一信道纠错编码,近年来，随着计算机、卫星通信及高速数据网的飞速发展，数据的交换、处理和存储技术得到了广泛的应用，人们对数据传输和存储系统的可靠性提出了越来越高的要求。因此，如何控制差错、提高数据传输和存储的可靠性，成为现代数字通信系统设计工作者面临的重要课题。香农第二定理指出，当信息传输速率低于信道容量时，通过某种编译码方法，就能使错误概率为任意小。目前已有了许多有效的编译码方法，并形成了一门新的技术纠错编码技术。这里所讲的纠错编码即信道编码，与信源编码一样都是一种编码，但两者的作用是完全不同的。,信源编码的目的是压缩冗余度，提高信息的传输速率。信道编码的目的是提高信息传输时的抗干扰能力以增加信息传输的可靠性。,4,二差错控制系统模型及分类,1差错控制系统模型,模型突出了以控制差错为目的的纠错码编、译码器，因此也称为差错控制系统。,2差错控制系统的分类,按其纠错能力的不同可分为两种：检错码和纠错码。,检错码：能发现错误但不能纠正错误的码；纠错码：不仅能发现错误而且还能纠正错误的码。,5,差错控制方式,图差错控制方式,6,前向纠错方式,前向纠错方式记作FEC(ForwordErrorCorrection)。发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。优点：不需要反馈信道；能进行一个用户对多个用户的同时通信，特别适合于移动通信；译码实时性较好，控制电路也比较简单。缺点：译码设备较复杂；编码效率较低。,7,检错重发方式,ARQ(AutomaticRepeatRequest)方式是：发端发出能够发现错误的码（检错码），收端译码器收到后，判断在传输中有无错误产生，并通过反馈信道把捡测结果告诉发端。发端把收端认为有错的消息再次传送，直到收端认为正确接收为止。优点：译码设备简单，在多余度一定的情况下，码的检错能力比纠错能力要高得多，因而整个系统能获得极低的误码率。缺点：应用ARQ方式必须有一条从收端至发端的反馈信道。并要求信源产生信息的速率可以进行控制，收、发两端必须互相配合，其控制电路比较复杂，传输信息的连贯性和实时性也较差。,8,混合纠错方式,HEC(HybridErrorControl)方式是上述两种方式的结合。发端发送的码既能检错、又有一定的纠错能力。收端译码时若发现错误个数在码的纠错能力以内，则自动进行纠错；若错误个数超过了码的纠错能力，但能检测出来，则通过反馈信道告知发方重发。这种方式在一定程度上避免了FEC方式译码设备复杂和ARQ方式信息连贯性差的缺点。,9,在设计差错控制系统时，选择何种实现方式，应综合考虑各方面的因素。主要有：满足用户对误码率的要求；有尽可能高的信息传输速率；有尽可能简单的编译码算法且易于实现；可接受的成本。,10,三纠错码的分类,常用的纠错码按其码字结构形式和对信息序列处理方式的不同可分成两大类：分组码卷积码,11,分组码：把信息序列以每k个码元分组，编码器将每个信息组按一定规律产生r个多余的码元（称为校验元），形成一个长为n=k+r的码字。,对于k个码元分组，共有2k个不同的信息组，编码器输出长n的2k个码字，这2k个长为n的码字构成的集合称为一个（n，k）分组码。,n：码长；k：信息位的数目；R=k/n：分组码码率。,卷积码：把信息序列以每k个分组，通过编码器输出长为n（nk）的一个子码。但是该子码的nk个校验元不仅与本子码的信息元有关，而且也与其前m个子码的信息元有关。,12,引例线性分组码的基本概念线性分组码的译码汉明码的编码与译码,9.2线性分组码,13,引例线性分组码的基本概念线性分组码的译码汉明码的编码与译码,9.2线性分组码,14,设传输一比特字符x=0或1若传输过程中出现差错,不能被发现,引例,15,引例,0后附加字符0，1后附加1；即只有00和11被接受，且00视为0，11视为1；故：如果有一位错误发生，可以被检出！,16,如果通信过程中发现差错，可以通过要求对方重新发送来获得正确的信息，即所谓的“数量换质量”.但是这在实时信息采集系统中可能是有困难的，因为信息源已经发生变化；即使是在发方保留原信息样本的情况下，也只有在差错率很低的条件下是比较可行的.因为如果通信条件比较恶劣，差错出现频繁，以至多次重发仍然得不到一份正确的信息.这时，仅有“检错”手段，已无能为力！,引例,17,引例,0后附加字符00，1后附加11；即传输000相当于传送单字符0，111相当于传送单字符1；这时：发生不超过两位的错误均可被检出；发生一位错误可以被纠正.,18,引例,0后附加字符00，1后附加11；即传输000相当于传送单字符0，111相当于传送单字符1；这时：发生不超过两位的错误均可被检出；发生一位错误可以被纠正.,纠错码,信息位,校验位,19,引例线性分组码的基本概念线性分组码的编码汉明码的编码与译码,9.2线性分组码,20,线性分组码的基本概念,分组码分组码是把信源输出的信息序列，以k个信息位分为一段，通过编码器把这段信息位按一定规则f产生r个校验位，输出长为n=k+r的一个码字，所得码字的全体.称之为（n，k）分组码！n表示码长，k信息位个数.,21,引例,0后附加字符00，1后附加11；即传输000相当于传送单字符0，111相当于传送单字符1；这时：发生不超过两位的错误均可被检出；发生一位错误可以被纠正.,(3,1)分组码,信息位,校验位,22,线性分组码的基本概念,（n，k）分组码,若校验位与信息位之间的关系是线性的，即上述编码规则是线性的，称之为（n，k）线性分组码！,23,线性编码从到的一个线性映射称为一个线性编码；,线性分组码的基本概念,即,均有；,若是一一映射，则称其为唯一可译线性编码；,24,线性分组码的基本概念,线性分组码线性分组码是把信源输出的信息序列，以k个信息位分为一段，通过编码器把这段信息位按线性编码规则f产生r个校验位，输出长为n=k+r的一个码字，所得码字的全体.称之为（n，k）线性分组码！n表示码长，k信息位个数.码字个数M=2k.,25,编码效率用差错控制编码提高通信系统的可靠性，是以降低有效性为代价换来的。我们定义编码效率R来衡量有效性:R=k/n其中,k是信息元的个数，n为码长。对纠错码的基本要求是:检错和纠错能力尽量强；编码效率尽量高；编码规律尽量简单。实际中要根据具体指标要求，保证有一定纠、检错能力和编码效率，并且易于实现。,26,若设码字，则,即校验位是由信息位线性组合得到.,线性分组码的基本概念,27,可见，码字的三个校验元都由其前两位线性组合得到，即可由的线性方程组求得；,线性分组码的基本概念,信息位k=2码字数M=4,28,线性编码,线性分组码的基本概念,29,例题1：下面是某个（n，k）线性二元码的全部码字x16=000000 x26=100011x36=010101x46=001111x56=110110 x66=101100 x76=011010 x86=111001求n、k的值；,n=6;,线性分组码的基本概念,M=2kk=3.,解：,30,例2、现以(7,4)分组码为例来说明线性分组码的特点。设其码字为A=a6a5a4a3a2a1a0，其中前4位是信息元，后3位是监督元，可用下列线性方程组来描述该分组码，产生监督元。,线性分组码的基本概念,31,表(7,4)码的码字表,32,监督矩阵H和生成矩阵G,33,其中,P为rk阶矩阵，Ir为rr阶单位矩阵。可以写成H=PIr形式的矩阵称为典型监督矩阵。HAT=0T，说明H矩阵与码字的转置乘积必为零，可以用来作为判断接收码字A是否出错的依据。,并简记为,H被称为校验矩阵或者监督矩阵。,34,若把监督方程补充为下列方程,35,可改写为矩阵形式,36,称为生成矩阵,37,例题3：下面是一个（6，3）线性二元码的全部码字,构造它的一个生成矩阵.,线性分组码的基本概念,解：由k=3个线性独立的码字组成：,38,例题3：下面是一个（6，3）线性二元码的全部码字,验证：,线性分组码的基本概念,39,系统码若（n,k）线性分组码的生成矩阵形如G=(IkA)其中Ik是k阶单位阵，A为阶子阵，则称这类码为系统码.,线性分组码的基本概念,特点：校验矩阵为H=(-ATI(n-k).,40,例题3：下面是一个（6，3）线性二元码的全部码字,它的一个生成矩阵,线性分组码的基本概念,请写出它的校验矩阵H.,信息组原封不动地搬到码字前位的码,41,线性分组码的基本概念,42,线性分组码的基本概念,汉明距离：指（n,k）分组码中两个码字xn、yn对应位取值不同的个数；记为d（xn，yn）.例：,43,线性分组码的基本概念,理查德卫斯里汉明（RichardWesleyHamming，1915.2.111998.1.7.），美国数学家，主要贡献在计算机科学和电讯。1937年芝加哥大学学士学位毕业，1939年内布拉斯加大学硕士学位毕业，1942年伊利诺伊大学香槟分校博士学位毕业，博士论文为一些线性微分方程边界值理论上的问题（SomeProblemsintheBoundaryValueTheoryofLinearDifferentialEquations）。二战期间在路易斯维尔大学当教授，1945年参加曼哈顿计划，负责编写电脑程式，计算物理学家所提供方程的解。该程式是判断引爆核弹会否燃烧大气层，结果是不会，于是核弹便开始试验。1946至76年在贝尔实验室工作。他曾和约翰怀尔德杜奇、克劳德艾尔伍德香农合作。1956年他参与了IBM650的程式语言发展工作。,44,线性分组码的基本概念,汉明距离：指（n,k）分组码中两个码字xn、yn对应位取值不同的个数；记为d（xn，yn）.例：,45,线性分组码的基本概念,线性分组码的最小距离：称（n,k）分组码中任两个码字汉明距离的最小值，为该分组码的最小距离d.（5,2）线性分组码全部码字：最小距离d=3.,汉明重量,46,引例线性分组码的基本概念线性分组码的译码汉明码的编码与译码,9.2线性分组码,生成矩阵校验矩阵码的最小距离,47,引例线性分组码的基本概念线性分组码的译码汉明码的编码与译码,9.2线性分组码,48,线性分组码的译码,基本概念错误图样设发送的码字xn=(x1,x2,xn)，通过有扰信道传输，到达接收端译码器的序列为rn=(r1,r2,rn)信道中的干扰表示为二进序列：错误图样en=(e1,e2,en).相应有错的ei取值为1.rn=xn+en，其中ri=xi+ei，xi，ri，eiGF(2)称en为信道中的错误图样.,译码器任务从rn中得到xn或en.,49,线性分组码的译码,例4设发送序列xn=(1111100000)，收到的序列rn=(1001010000).第二、三、五、六位产生了错误，因此信道的错误图样en的二、三、五、六位取值为1，其它各位取值为0，即en=(0110110000).用式子可表示成：,rn=xn+en,50,线性分组码的译码,基本概念伴随式由于分组码中的任一码字满足：xnHT=0，所以，可对收到的序列rn进行检验：rnHT=(xn+en)HT=xnHT+enHT=enHT若en=0，则rnHT=0；若en0，则rnHT0.记S=enHT，称之为接收序列rn的伴随式.,rnHT仅与错误图样有关，与发送什么码字无关！,51,（n，k）线性分组码的校验矩阵，用列向量表出：,线性分组码的译码,其中，hn-i为H矩阵的第i列.,52,设en=(e1，e2，en)=(0，ei1，0，ei2，0，ei3，0，eit，0，0)其中eij=1,即第i1，i2，it位有错，则,线性分组码的译码,S是H中相应于eij那几列的线性组合！,53,线性分组码的译码,例5已知（7，3）码的校验矩阵为若发送码字xn=（1110100），收到rn=（0010100）.则错误图样为en=（1100000）.,54,线性分组码的译码,由定义可以求得，rn的伴随式：,是H矩阵第一列与第二列之和！,55,线性分组码的译码,若错误图样en=（0010000），则,是H矩阵第三列！,若错误图样中只有一个分量非零，则ST是H矩阵相应的列，因而能够纠正单个错误！,56,表(7,4)码S与E的对应关系,57,线性分组码的译码,若错误图样en=（0010100），则,是H矩阵第三列与第五列之和！,若发生两个错误，译码器只能判决传输有错（en0）,不能判定由哪几位错误引起！,58,纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越大，抗干扰能力就越强。分组码的最小汉明距离d与检错和纠错能力之间满足下列关系：,59,线性分组码的译码,（1）当码字用于纠正错误时，线性分组码能自动纠正t个错误的充要条件是d2t+1,最大似然译码准则是纠错的策略依据.若收到的字符串是码字本身，则直接按码字译码；否则，按与接收到的字的Hamming距离最接近的码字译码.,60,线性分组码的译码,（2）当码字用于检测错误时，如果要检测e个错误，则de+1,61,（3）若码字用于纠t个错误，同时检e个错误时（et），则dt+e+1,线性分组码的译码,62,线性分组码的译码,例5已知（7，3）码的校验矩阵为,最小距离d=3,d=2t+1,63,线性分组码的译码,（n,k）码的译码步骤（1）由接收到的rn，计算伴随式S=rnHT；（2）若S=0，则认为接收无误；若S0，则由S找出错误图样en；（3）由en和rn找出xn=rn-en.,64,引例线性分组码的基本概念线性分组码的译码汉明码的编码与译码,9.2线性分组码,65,线性分组码,汉明码(HammingCode)汉明码是1950年由汉明首先构造，用以纠正单个错误的线性分组码.由于它的编译码非常简单，很容易实现，因此用得很普遍，特别是在计算机的存贮和运算系统中更常用到，是一类特别引人注意的码.,66,线性分组码,汉明码(HammingCode)汉明码不是指一个码，而是代表一类码；汉明码码长n和信息位k服从以下规律：(n,k)=(2m-1,2m-1-m)，其中m=n-k；汉明码的最小距离d=3；所以，纠错能力t=1；,67,汉明码(HammingCode)的译码例6已知GF(2)上的（6，3）汉明码的一致校验矩阵H为：,线性分组码,68,线性分组码,若发送码字xn=(101011),接收序列为rn=(101011).若发送码字xn=(101011),接收序列为rn=(100011).,判定传输中没有发生错误！,判定接收序列rn的第3位是有错的！,69,设一分组码具有一致校验矩阵：求这个分组码n=？k=？，共有多少个码字？此分组码的生成矩阵；向量101010是否是码字？设发送码字C=(001111)，但接收序列为R=(000010),其伴随式S是什么？这个伴随式指出已发生的错误在什么地方，为什么与实际错误不符？,习题课（补充）,70,解：设码字C=(c5c4c3c2c1c0)，有,习题课,故得,所以n=6，k=3，为(6,3)分组码共有码字2k=8个,71,设一分组码具有一致校验矩阵：求这个分组码n=？k=？，共有多少个码字？此分组码的生成矩阵；向量101010是否是码字？设发送码字C=(001111)，但接收序列为R=(000010),其伴随式S是什么？这个伴随式指出已发生的错误在什么地方，为什么与实际错误不符？,习题课（补充）,72,习题课,由上式可得,取一组线性无关的基础解系，得到生成矩阵,73,设一分组码具有一致校验矩阵：求这个分组码n=？k=？，共有多少个码字？此分组码的生成矩阵；向量101010是否是码字？设发送码字C=(001111)，但接收序列为R=(000010),其伴随式S是什么？这个伴随式指出已发生的错误在什么地方，为什么与实际错误不符？,习题课（补充）,74,习题课,由,可知，向量101010不是码字,75,设一分组码具有一致校验矩阵：求这个分组码n=？k=？，共有多少个码字？此分组码的生成矩阵；向量101010是否是码字？设发送码字C=(001111)，但接收序列为R=(000010),其伴随式S是什么？这个伴随式指出已发生的错误在什么地方，为什么与实际错误不符？,习题课（补充）,76,习题课,接收序列R的伴随式,是校验矩阵的第五列据此可以判定码字中的第五个分量发生错误，则E=(000010),77,但实际的错误图样E为E=(000010)+(001111)=(001101)是码字传输中发生了三位码元错误因为该（6，3）码dmin=3，所以根据伴随式只能纠正一位码元发生错误的错误图样；从而。当传输过程中码字发生的多于一位错误就无法纠正,习题课,78,9.3常用的几种简单分组码,9.3.1奇偶监督码(Parity),奇偶监督码是在原信息码后面附加一个监督元，使得码组中“1”的个数是奇数或偶数。或者说，它是含一个监督元，码重为奇数或偶数的(n,n-1)系统分组码。奇偶监督码又分为奇监督码和偶监督码。,79,ParityErrorChecking,80,SimpleParityPerformance,Candetectallsingle-biterrorsMaydetectallbursterrorsaslongastotalnumberofbitschangedisoddCannotdetecterrorswhentotalnumberofbitschangedisevensinceparitycheckwillpasseventhougherrorshadoccurred,奇偶监督码的编码效率R为,81,9.3.2行列监督码,图(66,50)行列监督码,82,Two-DimensionalParity,83,Two-dimensionalParity,Example:five7-bitcharacterpacket,evenparity,84,HowManyErrorsCanyouDetect?,All1-biterrorsExample:,85,HowManyErrorsCanyouDetect?,All2-biterrorsExample:,86,HowManyErrorsCanyouDetect?,All3-biterrorsExample:,87,HowManyErrorsCanyouDetect?,Most4-biterrorsExampleof4-biterrorthatisnotdetected:,能纠正一些仅在一行中的单个错误。,88,9.4循环码,一、循环码的特点,循环码最大的特点就是码字的循环特性，所谓循环特性是指：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。,若（）为一循环码组，则还是许用码组。,89,【例】（7，3）线性分组码,由两组码字循环构成的循环码。,90,循环码举例(7,3)循环码,91,二、码多项式,为了利用代数理论研究循环码，可以将码组用代数多项式来表示，这个多项式被称为码多项式，对于许用循环码,可以将它的码多项式表示为：,对于二进制码组，多项式的每个系数不是0就是1，x仅是码元位置的标志。因此，这里并不关心x的取值。,例：表中的第7码字可以表示为,92,循环特性的表示,以（7，3）循环码为例：（任取一码字）,93,下面用去除，得余,对于上面第三次移位结果，可重新表示如下：,结论：如果将一个循环码的某一非零码字用码多项式表示出来，那么其他的非零码字多项式就可以用这个码字多项式（或码字多项式的和）乘上x的一个幂，再求（xn+1）的余得到。,说明：一个码字的移位最多能得到n个码字，因此“循环码字的循环仍是码字”并不意味着循环码集可以从一个码字循环而得，还应包含码字的一些线性组合。,94,在整数运算中，有模n运算。例如，在模2运算中，有1+120（模2），1+231（模2），2360（模2）等。因此，若一个整数m可以表示为:,则在模n运算下，有mp（模n），也就是说，在模n运算下，一整数m等于其被n除所得的余数。,95,在码多项式运算中也有类似的按模运算法则。若一任意多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，也就是：,则可以写为：F(x)R(x)mod（N(x)）,这时，码多项式系数仍按模2运算，即只取值0和1。,96,假设：计算x4+x2+1除以x3+1的值可得：,这样式也可以表示为：,注意，在上述运算中，由于是模2运算，因此，加法和减法是等价的，在式子中通常用加法运算符，具体模2运算的规则定义如下：,97,在循环码中，若A(x)是一个长为n的许用码组，则xiA(x)在按模(xn+1)运算下，亦是一个许用码组，也就是假如：可以证明Al(x)亦是一个许用码组，并且，Al(x)正是A(x)代表的码组向左循环移位i次的结果。,98,例：上式的循环码，其码长n7，现给定i3，则：,其对应的码组为0101110，它正是表中第3码字。,结论：一个长度为n的循环码，它必为按模(xn+1)运算的一个余式。,99,1定义：若g(x)是一个(n-k)次多项式，且是(xn+1)的因式，则由g(x)可以生成一个（n，k）循环码，g(x)称为该循环码的生成多项式。,两个结论：,使得所有码多项式都是g(x)的倍式，即：,且所有小于n次的g(x)的倍式都是码多项式。,故循环码完全由它的生成多项式确定。,三、循环码的生成多项式及其特征,100,（2）（n，k）循环码的生成多项式g(x)一定是(xn+1)的因子，即,或写成,相反，如果g(x)是xn+1的n-k次因子，则g(x)一定是（n，k）循环码的生成多项式。生成多项式不唯一。,2（n，k）循环码的构造,（1）对(xn+1)做因式分解，找出(nk)次因式；（2）以该(nk)次因式为生成多项式g(x)与不高于k1次信息多项式u(x)相乘，即得到对应消息序列的码多项式。,101,【例】一个长度n=7的循环码的构造方法。,（1）对x7+1作因式分解,故x7+1有如下因式：,102,nk=1，k=6，生成一种（7，6）循环码；nk=3，k=4，生成两种（7，4）循环码；nk=4，k=3，生成两种（7，3）循环码；nk=6，k=1，生成一种（7，1）循环码；,例：要得到一（7，4）循环码，可选nk=3次多项式1+x2+x3或1+x+x3为生成多项式：,以g（x）=1+x2+x3为例，（信息位长度为4）,设信息多项式为：,则：循环码编码后的码多项式为：,（2）若以n-k次因式作