第九章差错控制编码sxq.ppt

第9章差错控制编码,南京航空航天大学信息科学与技术学院通信原理教研组,copyright信息科学与技术学院通信原理教研组,2,引言,1,纠错编码的基本原理,2,常用的简单编码,3,线性分组码,4,循环码,5,第9章差错控制编码,6,7,卷积码,网格编码调制,copyright信息科学与技术学院通信原理教研组,3,9.1引言,信道,解调,信源,编码,加密,调制,解密,译码,信宿,噪声,同步系统,信源编码信道编码差错控制,ASKFSKPSKDPSK,数字通信的组成,copyright信息科学与技术学院通信原理教研组,4,采用信道编码,在通信过程中，会受到各种外来干扰，如脉冲干扰，随机噪声干扰，人为干扰及通信线路传输性能的限制都将使信号失真。由于以上原因，引起数据信息序列产生错误，称之为差错。,随机性错误：前后出错位之间无一定关系，随机、离散出现。突发性错误：差错成串出现，且有一定相关性。,差错的两大类型：,copyright信息科学与技术学院通信原理教研组,5,数字通信中的编码,信道编码：,信源编码：,为提高信号传输的有效性而采取的措施。,为提高信号传输的可靠性而采取的措施,亦称差错控制编码。,在发送端利用信道编码器在数据信息中增加一些监督信息，使不带规律性或规律性不强的原始数字信号变为带规律性或加强了规律性的数字信号，信道译码器则利用这些规律性来鉴别是否发生错误，或进行错误纠正。,差错控制,copyright信息科学与技术学院通信原理教研组,6,1、差错控制方法,copyright信息科学与技术学院通信原理教研组,7,（2）信息反馈法IF,信息信号,信息信号,发端,收端,方法和设备简单，无需纠检错编译系统。但需要双向信道，传输效率、实时性差。,copyright信息科学与技术学院通信原理教研组,8,(3)检错重发法ARQ,所发码具有检错能力，收端接收后判决是否出错，通过反向信道发送判决结果，发端据此决定是否重发。,译码设备简单，对突发错误有效，要求有反馈信道。,工作过程：发送检测回复重发或发送新的数据,copyright信息科学与技术学院通信原理教研组,9,停止等待方式,3,2,2,1,2,2,1,ACK,ACK,NACK,发送端,接收端,ARQ的三种实现方式：,特点：半双工工作，简单，要求的缓存量小，但等待时间较长，,传输效率,copyright信息科学与技术学院通信原理教研组,10,连续重发方式,退N步方式：从出错帧开始重发,优缺点：传输效率，但重发的N帧中，大部分为正确，所以仍有浪费。发端缓存必须可存N帧。,copyright信息科学与技术学院通信原理教研组,11,只对出错信息重发，因此传输效率大大提高。但收发两端都要有足够的存储空间。,选择重发方式,copyright信息科学与技术学院通信原理教研组,12,反馈信道,ARQ,FEC编码器,正向信道,FEC译码器,ARQ,编码既有纠错能力也有检错能力，收端收到信息码组后在收端进行检测。在纠错范围内：纠正；超出范围：通过ARQ方式进行重发。,(4)混合方式,copyright信息科学与技术学院通信原理教研组,13,（1）,根据各码组信息码和监督码的关系分：线性码，非线性码,根据监督码元是否仅与本组信息元有关分组码，卷积码,（2）,根据纠错码组中信息元是否隐蔽分：系统码，非系统码,（3）,纠错码的分类,copyright信息科学与技术学院通信原理教研组,14,根据码的用途分：检错码，纠错码,（4）,根据码元的取值：二进制码，多进制码,（5）,根据构造编码的数学方法：代数码，几何码，算术码,（6）,本课程主要讨论纠随机错误的二进制线性分组码。,copyright信息科学与技术学院通信原理教研组,15,纠错码的发展概况,通信的数学理论，Shannon(1948)汉明码，Hamming(1950)级连码，Forney(1966)卷积码及有效译码，(60年代)RS码及有效译码，(60年代)TCM，Ungerboeck(1982),Forney(1984)Turbo码，Berrou(1993)LDPC码，Gallager(1963),Macky(1996)空时编码,Tarokh(2000),copyright信息科学与技术学院通信原理教研组,16,9.2纠错编码的基本原理,1、几个术语,码长：码组中码元的数目，常用n表示；,码距：两等长码字C1、C2对应位上取值不同的数目，又称为汉明(Hamming)距离，记为d(c1,c2)。,码重：码组中非零码元的数目，记为W；,copyright信息科学与技术学院通信原理教研组,17,n=3时，码距的几何说明：,（a2a1a0）,a2,a1,a0,（110）（011）,d=2,110,011,（111）（000）,d=3,000,111,最小码距：在分组码(n,k)中，任意两个码字之间汉明距离的最小值，记为dmin。,最小码距的大小关系到编码的检纠错能力。,010,101,100,001,copyright信息科学与技术学院通信原理教研组,18,发送序列C:(1111011000),接收序列R:(0110010110),比较C和R，可写出另一个序列E：1001001110,R=C+E,序列E定义为错误图样(ErrorPattern),错误图样：,copyright信息科学与技术学院通信原理教研组,19,A、B两消息，可用一位二进制数表示，A=1、B=0出错时无法判定,增加一个监督位，取11A、00B,再增加一个监督位，取111A、000B,许用码组：00，11,禁用码组：01，10,若收到01或10时，可知发生了错误，但不能纠正错误。,许用码组：000，111,禁用码组：001,010,100,011,101,110,如一位错能够纠正错误；若两位错，则只能发现不能纠错,2、纠错或检错的原理,copyright信息科学与技术学院通信原理教研组,20,可以看出：差错控制是以牺牲传输效率为代价而换取了传输质量的提高的。纠检错能力与加入的监督元方式和数目有关。,copyright信息科学与技术学院通信原理教研组,21,分组码的三个参数码长n，信息位k，最小距离d0，用符号(n,k,d0)表示,R=k/n为编码效率，d0一定(纠错能力一定)时，k/n大，效率高。,对被传输的信息序列分组，每组为k个信息元，对每组按某种关系附加(n-k)个监督码元(校验)，形成为n位的码字。这种方法构成的码组称为分组码。,3、分组码,copyright信息科学与技术学院通信原理教研组,22,4、分组码的纠(检)错能力与最小码距d0的关系,任一（n，k）分组码，若要在码字内能：1/检测e个随机错误，则要求：d0e+12/纠正t个随机错误，则要求：d02t+13/纠正t个同时检测e(et)个随机错误，则要求：d0e+t+1,copyright信息科学与技术学院通信原理教研组,23,1,纠（检）错能力的几何解释,A1,d0,e,A2,（a）,A1,d0,t,A2,（b）,A2,t,1,1,copyright信息科学与技术学院通信原理教研组,24,例9-1,一个码集，只有两个许用码：0000、1111，试求其纠、检错能力和编码效率。,copyright信息科学与技术学院通信原理教研组,25,解：,根据码距的定义，则该码集d0=4，,1/用于检错，ed01=3，即可检3个错误；,2/用于纠错，t(d01)/2=3/2，取整，即可纠1个错误；,3/同时用于纠、检错，d0e+t+1（et）取：e=2，t=1，则可满足上式，即可检2个错误同时纠一个错；,R=k/n=1/4,编码效率：,copyright信息科学与技术学院通信原理教研组,26,4、对纠错编码的要求,纠、检错能力强，编码效率高，码长短，编码规律简单。,copyright信息科学与技术学院通信原理教研组,27,5.差错控制编码的效用,假设在随机信道中，发送“0”和“1”的错误概率相等，都等于p，且p1，在码长为n的码组中，发生r个错误的概率为：,copyright信息科学与技术学院通信原理教研组,28,例如：当n=7，p=10-时，则有：,由此可见，即使仅能纠正1-2个错误，也可使误码率下降几个数量级。所以差错控制编码具有较大的实际应用价值。,copyright信息科学与技术学院通信原理教研组,29,6.有扰信道编码定理（Shannon第二定理）,对于给定的有扰信道，若信道容量为C，只要发送端以低于C的信息速率Rb发送信息，则一定存在一种编码方法，使得译码错误概率P随着码长n的增加，按指数下降至任意小的值，表示为Pe-nE(Rb)E(Rb)为误差指数，Rb0。Rbmax=C=Blog2(1+S/N)（bit/s）,copyright信息科学与技术学院通信原理教研组,30,1.码长n和信息速率Rb一定时，随C误差指数E(Rb)P随指数下降。其中C=Blog2(1+S/N)（bit/s）,2.在C和Rb一定时(RbC)，随码长nP随指数下降(P0)。,数字传输系统中，无误码传输的最高信息速率Rbmax=C=Blog2(1+S/N)（bit/s）,两个结论：,copyright信息科学与技术学院通信原理教研组,31,编码性能举例未采用纠错编码时，若接收信噪比等于7dB，编码前误码率约为810-4，图中A点，在采用纠错编码后，误码率降至约410-5，图中B点。这样，增大发送功率,就能降低误码率约一个半数量级。,编码后,Pe,B,信噪比(dB),copyright信息科学与技术学院通信原理教研组,32,由图还可以看出，若保持误码率在10-5，图中C点，未采用编码时，约需要信噪比Eb/n0=9.5dB。在采用这种编码时，约需要信噪比7.5dB，图中D点。可以节省功率2dB。通常称这2dB为编码增益。上面两种情况付出的代价是带宽增大。,Pe,C,D,信噪比(dB),编码后,copyright信息科学与技术学院通信原理教研组,33,传输速率和Eb/n0的关系对于给定的传输系统式中，RB为码元速率。若希望提高传输速率，由上式看出势必使信噪比下降，误码率增大。假设系统原来工作在图中C点，提高速率后由C点升到E点。但加用纠错编码后，仍可将误码率降到D点。这时付出的代价仍是带宽增大。,编码后,Pe,信噪比(dB),copyright信息科学与技术学院通信原理教研组,34,9-3常用的简单编码,1、奇偶监督码：k=n-1,r=1的线性码。特点：码组中的1个数是奇数（奇监督码）或偶数（偶监督码）。,偶监督时，要满足：,奇监督时，要满足：,两者的校验能力相同，均只能检测出奇数个错误。,R=k/n=n-1/n=1-1/n,编码效率：,copyright信息科学与技术学院通信原理教研组,35,码长5的偶监督码,序码字序码字号信息码元监督元号信息码元监督元a4a3a2a1a0a4a3a2a1a0000000810001100011910010200101101010030011011101114010011211000501010131101160110014111017011111511110,copyright信息科学与技术学院通信原理教研组,36,偶监督码编码器,copyright信息科学与技术学院通信原理教研组,37,偶监督码的检错电路,copyright信息科学与技术学院通信原理教研组,38,例9-2：一数据序列：1110010111011011000110101,试对其进行（6，5）偶校验编码，写出码序列并分析其抗干扰能力,copyright信息科学与技术学院通信原理教研组,39,一数据序列：1110010111011011000110101,试对其进行（6，5）偶校验编码，写出码序列并分析其抗干扰能力,解：,（6，5）,将数据序列每5码元分组，,并作：,的运算,可得出编码数据序列：,111001101110011011100010101011,只能检测出奇数个错误，不能发现偶数个错误，也不能纠错。,copyright信息科学与技术学院通信原理教研组,40,2、水平垂直奇偶校验码：又称行列监督码或二维奇偶监督码。特点：对水平方向和垂直方向的码元同时实施奇偶监督。,110010100000100001101001111000011100111000001010101010111000111100,行列监督码,copyright信息科学与技术学院通信原理教研组,41,适于监测突发错误：逐行传输时，能检测长度bM+1的突发错误;逐列传输时,能检测长度bL+1的突发错误；还能纠正一些仅在一行中的单个错误。,110010100000100001101001111000011100111000001010101010111000111100,L5，M10的行列监督码,其中M为列数，L为行数,copyright信息科学与技术学院通信原理教研组,42,3、恒比码：又称等重码或定1码。特点：码组中0，1的个数保持不变。若码长为n，码重为w，则此码的码字个数为：Cnw，禁用码字个数为：2n-Cnw,码字的个数C53=10,检错能力较强，可检出所有奇数和部分偶数错误。,检错能力较强，可检出所有奇数和部分偶数错误。,适用于传输电报或其他键盘设备产生的字母或符号，但不适合信源发出的是二进制随机数字序列的场合。,copyright信息科学与技术学院通信原理教研组,43,3:2恒比码,如：我国的电报，每个汉字用四个10进制数表示，每位10进制数就采用3：2恒比码构成的5位码组来表示。,码字的个数C53=10,copyright信息科学与技术学院通信原理教研组,44,作业：,4、正反码：简单的可纠错编码，信元数等于监督元数特点：信息位中，有奇数个1时，监督位重复信息位；信息位中，有偶数个1时，监督位取信息位的反码；,可纠一位、检测所有两位错和部分两位以上的错误。,例：,110011100111001,100011000101110,(n,k)其中k=n/2编码效率：R=k/n=1/2,copyright信息科学与技术学院通信原理教研组,45,9.4线性分组码,9.4.1基本概念,可用线性方程组表述码的规律性的分组码称为线性分组码。线性码建立在代数学群论基础上，线性码各许用码的集合构成代数学中的群，因此，又称为群码。,copyright信息科学与技术学院通信原理教研组,46,1.含有全零码字。2.任意两个许用码字之和仍是一个许用码字。（封闭性）3.最小码距d0等于非零码字的最小重量即d0=Wmin（由此性质可以方便的确定出线性分组码的最小码距，进而明确其纠错能力。）,在群中只有一种运算，就是模2和。,线性分组码的性质：,copyright信息科学与技术学院通信原理教研组,47,奇偶监督码是一种最简单的线性码，我们曾经作了偶校验的例子。,称为监督方程。,接收时，为了检测传输时是否有错，还要做同样的计算：,这里S称为校正子，上式也称伴随式。,奇偶监督码中只有一位监督码，因此只能表示有否错误。,copyright信息科学与技术学院通信原理教研组,48,当监督位增加，则监督方程增加，校正子增加。,r位监督码除了用全“0”表示无错外，可表示,种错误图样。(n,k)码可纠错的错误图样数为：,我们把接收码组R与发射码组C的差称为错误图样，用E表示：,E=C-R，或者C=R+E,(n,k)中，信息码为k位，可传输M=2k种信息，当增加r位的监督位后，有2n种状态，但只取2k种为许用状态，其他为禁用，,(n,k)码可检测的错误图样数为2n-2k,2n-k-1=2r-1,不可检测的错误图样数为2k-1,copyright信息科学与技术学院通信原理教研组,49,2n-k-1+=,对于能纠正t个错误的线性分组码(n,k)应满足：,是错i位的个数。,如果满足，则有可能构造出纠正一位或一位以上的线性码。,i=1时，,即对于码组长度为n，信息码元k位，监督元r，,copyright信息科学与技术学院通信原理教研组,50,思考：例9-3设(n，k)中，k=4，要求能纠一位错，取r=？,copyright信息科学与技术学院通信原理教研组,51,解：(n，k)线性分组码，k=4，要求能纠一位错，现取r=3，可指示23-1=7种错误，码长n=4+3=7，,表示为：C=C6C5C4C3C2C1C0,其中C6C5C4C3为信息码元，C2C1C0为监督元,由r=3，可有三个监督方程和校正子，设为s1s2s3,恰好满足,故可纠一位错。,copyright信息科学与技术学院通信原理教研组,52,设s1s2s3三位校正子与误码位置的对应关系为：,000001010100011101110111,误码位置,无错C0C1C2C3C4C5C6,S1S2S3,于是监督码元C2C1C0应由以下监督方程决定。,C2=C6+C5+C4,C1=C6+C5+C3,C0=C6+C4+C3,监督元与信息元之间的线性方程组,s1=C2+C6+C5+C4=0,s2=C1+C6+C5+C3=0,s3=C0+C6+C4+C3=0,copyright信息科学与技术学院通信原理教研组,53,于是得到(7，4)线性分组码如下：,copyright信息科学与技术学院通信原理教研组,54,9.4.2监督矩阵,将前面的监督方程改写成矩阵的形式，C=C6C5C4C3C2C1C0可看成为编码矢量，于是有：,记做：,监督方程,copyright信息科学与技术学院通信原理教研组,55,H-监督矩阵,不满足以上关系的为非典型矩阵，典型矩阵和非典型矩阵之间可以转换。,2/H矩阵各行是线性无关的。,行数-监督元的个数r,列数-码组长度n,Ir为r阶单位阵,1/当有H=PIr时称为典型矩阵，,copyright信息科学与技术学院通信原理教研组,56,利用监督方程，我们可以对线性码的封闭性加以证明,即H阵与编码码字的转置乘积为0，可用来作为判断接收码组是否错的依据。,copyright信息科学与技术学院通信原理教研组,57,设监督方程A1、A2均为线性码集合中的许用码组，因此有令两许用码组相加,A1+A2带入监督方程，有：,因此，A1+A2亦为许用码组。,copyright信息科学与技术学院通信原理教研组,58,9.4.3生成矩阵,当给出信息组后，如何方便迅速地求出整个编码码组，即如何生成编码矢量？,由监督元与信息元之间的关系：,或者可以写成：,copyright信息科学与技术学院通信原理教研组,59,令,则有：,给Q的左边，加一个kk阶的单位矩阵，则构成：,G=IkQ称为生成矩阵，且为典型形式。典型,G矩阵,行数-信息元的个数k,列数-码组长度n,每行本身就是一个许用码组,于是有：,矩阵和非典型矩阵之间可以转换。,copyright信息科学与技术学院通信原理教研组,60,码字的前面k位为信息位，后面位为监督位,一般情况，定义线性分组码的码字有如下形式：,信息码元,监督位,信息位,编码,码字,系统形式的线性分组码,编码,copyright信息科学与技术学院通信原理教研组,61,设信息组,生成矩阵,编码码组,copyright信息科学与技术学院通信原理教研组,62,1）由G和信息组即可产生全部码字.,通过典型生成矩阵产生的一定是系统码。,copyright信息科学与技术学院通信原理教研组,63,（1）试确定(n,k)，并求H；(2)写出监督元与信息元的关系式及该（n,k）码的全部码字；(3)确定最小码距及检错能力。,例9-4设已知,copyright信息科学与技术学院通信原理教研组,64,解：求H，需确定P，,应将已知的那个G转换成典型形式，求出Q，再利用求出G。,H=PIr=,copyright信息科学与技术学院通信原理教研组,65,(2),设C=,于是有：,监督元与信息元的关系式,copyright信息科学与技术学院通信原理教研组,66,用三位二进制数的所有8种状态带入，可得到所有码字如右表。,序号码字00000001001011201011030111014100101510111061100117111000,(3)确定最小码距及检错能力,所以有：d0=3,可用于检两位错或纠一位错。,利用性质知：最小码距d0等于非零码字的最小重量即d0=wmin,copyright信息科学与技术学院通信原理教研组,67,9.4.4校正子S,发送端经过编码后给出：,接收端收到的码组为：,两者的差记为：,表示第i位无错,表示第i位有错,E称为错误图样。共有2n个错误图样。,当E为全零错误图样时，R=C没有传输错误;,copyright信息科学与技术学院通信原理教研组,68,可能有两种情况：,(n,k)可检测的错误图样数为2n-2k(n,k)可纠错的错误图样数为2n-k-1,这时的错误图样称为不可检测的错误图样,一般来讲，E=0，则R=C，可满足监督方程,E0，则RC，不满足监督方程,检错：当S=0时，认为E=0，当S0时，认为E0,校正子S的计算,即校正子只与错误图样E有关。,copyright信息科学与技术学院通信原理教研组,69,标准阵列表,排列方法,陪集,陪集首,copyright信息科学与技术学院通信原理教研组,70,陪集,陪集首,copyright信息科学与技术学院通信原理教研组,71,构造标准阵列的一般方法如下：1）用概率译码确定各伴随式S对应的差错图案E，共对；2）表格为列，行，先确定第一行和第一列，第一行为个码字，第一列为；3）各列对应的元素为第一列的和该列的之和；,陪集首,译码时，计算伴随式S，查表获得错误图样E，最后恢复出发送码字CER。,copyright信息科学与技术学院通信原理教研组,72,例9-5已知监督矩阵：,若接收为：R=0000011，试确定是否错误，若接收错误，试进行纠错。,copyright信息科学与技术学院通信原理教研组,73,R=0000011，,解：计算校正子,copyright信息科学与技术学院通信原理教研组,74,错误图样：,E=0001000,对照校正子与误码位置，确定错误图样：,copyright信息科学与技术学院通信原理教研组,75,于是：R=R+E,=0000011+0001000,由于，当只发生一位错码时，矩阵E中只有一个非零元素，与H的转置相乘的结果是选出其中的一列，即校正子与H矩阵的哪一列相同，则该列即为码元发生错误的位置。,=0001011,copyright信息科学与技术学院通信原理教研组,76,(n，k)线性分组码编、译码过程小结：,编码过程：,设线性分组码为(n，k)，,信息码为：,1)根据生成矩阵或监督矩阵，,2)由C=MG0求出所有码字，且为系统码。,H0=PIr,G0=IkQ,求出典型生成矩阵；,copyright信息科学与技术学院通信原理教研组,77,译码过程：,1）由收到的码组R计算校正子S；,2）由S判决是否有错并通过找出错误图样；,3）按照R+E=C计算并还原C；,4）将码组C还原成原信息组M。,copyright信息科学与技术学院通信原理教研组,78,9.4.5汉明码,汉明码是用于纠一位错误的线性分组码。,特点：,最小码距：,纠错能力：,编码效率：,copyright信息科学与技术学院通信原理教研组,79,例9-6,n=15的汉明码，其监督位为多少？编码,效率为多少？,copyright信息科学与技术学院通信原理教研组,80,解：,于是其信息位有15-4=11位,此汉明码为（15，11）码,编码效率：,其监督位有15-11=4位,copyright信息科学与技术学院通信原理教研组,81,汉明码是线性分组码，因此其监督矩阵同样有n列、r行，当监督位数给定后，即可构造出汉明码。,例，r=3,构造,copyright信息科学与技术学院通信原理教研组,82,得到的汉明码如下所示：,copyright信息科学与技术学院通信原理教研组,83,（7，4）汉明码编码器,copyright信息科学与技术学院通信原理教研组,84,完备码,纠正单个错误的汉明码中，r位校正子码组与误码图样一一对应，最充分地利用了监督位所能提供的信息。,在一般情况下，对于能纠正t个错误的线性分组码(n，k)，应满足以下不等式：,因此，汉明码也是纠一位错的线性分组码中，编码效率最高的。,copyright信息科学与技术学院通信原理教研组,85,上式取等号时，校正子与误码不超过t个的所有图样一一对应，监督码元得到最充分的利用，这种线性分组码即完备码。,除汉明码外，迄今为止，找到的唯一能纠正多个错误的完备码为(23，12)戈雷码。t=3,汉明码就是一种完备码。,该式亦称为汉明界，它给出已知k和t时，所需要的监督位数。,copyright信息科学与技术学院通信原理教研组,86,但此时构成的则非汉明码。,通常选择码重最小的矢量优先。,例9-6,试构造一个k=5的可纠一个错的线性分组码,1/计算最短的码长；2/构造H；3/求生成矩阵G；4/求信息组为(10101)的编码码字C。,copyright信息科学与技术学院通信原理教研组,87,解：,1/因为t等于1,且要求k=5,可用试探法确定n,设：n-k=3，则不满足纠错要求；,设：n-k=4，则满足纠错要求；,于是取n=9，此时r=n-k=4，(9,5)线性分组码,copyright信息科学与技术学院通信原理教研组,88,2/r=4，四位码共有种状态，除全零外都可用于构造H矩阵。,为了构造典型矩阵，选1000，0100，0010，0001四码组，然后从其余的11个码组中，再选出5个，通常按照码重从小到大选择。,P,Ir,实际只需9个,copyright信息科学与技术学院通信原理教研组,89,4/M=10101,C=MG=101010110,Q,3/求生成矩阵已知,Ik,于是有：,copyright信息科学与技术学院通信原理教研组,90,9.5循环码,9.5.1循环码原理,循环码是线性分组码的一个重要子类，也是目前研究最成熟的一类码。它不仅有封闭性，且还有循环性。,(n，k)码组,则将所有码元向左循环一位，得到的：,也是许用码组,是许用码组。,即,copyright信息科学与技术学院通信原理教研组,91,若线性分组码的任一码组循环移位所得码组仍在该码组集中，则此码为循环码。,（7，3）循环码,序号码字0000000010011101201001113011101041001110510100116110100171110100,循环码的循环圈数2,同一循环圈内，码字的重量相同,copyright信息科学与技术学院通信原理教研组,92,序号码字00000001001001201001030110114100100510110161101107111111,（6，3）循环码,copyright信息科学与技术学院通信原理教研组,93,由于具有循环性，编译码设备较简单；,可以用代数的方法分析和设计编码。,10-5-2循环码的多项式表示,已知码组：,设x为一个任意的实变量，其幂次代表移位的次数，,以Ci作为多项式的系数，则可以得到码多项式：,循环码的特点,copyright信息科学与技术学院通信原理教研组,94,每循环一位，相当于码多项式乘以x，仍为许用码组,0111010,1、生成多项式与生成矩阵,循环码中次数最低的多项式（全0码字除外）称为生成多项式g(x)。,0011101,例：,即：,copyright信息科学与技术学院通信原理教研组,95,那么，,都是许用码组，,而这k个码组是线性无关的。,于是用它们组成的矩阵则为生成矩阵,设信息码组为：,其对应多项式为：,copyright信息科学与技术学院通信原理教研组,96,则编码码组为：,由上式可看出：用G(x)生成的码字，都是g(x)的倍式，都可以被g(x)整除。,copyright信息科学与技术学院通信原理教研组,97,如何寻找生成多项式？,已知编码码组为：,生成多项式是一个n-k次的多项式，且本身也是,一个许用码组：,为一个n次多项式，它是在模,运算下的一个许用码组，即：,分子分母均为n次，故Q(x)=1,于是上式成为：,copyright信息科学与技术学院通信原理教研组,98,有,就是说：,也就是说，寻找g(x)的过程，就是对进行因式分解的过程。,copyright信息科学与技术学院通信原理教研组,99,例9-8,为了寻找(7，3)循环码的生成多项式，只需找出(n-k)=(7-3)=4次的因式即可。,两者均可，但将产生出不同的编码码组。,(7，6)码：,(7，1)码：,(7，4)码：,copyright信息科学与技术学院通信原理教研组,100,9.5.2循环码的编、译码方法,1、循环码的编码方法,首先根据给定的(n,k)选定生成多项式g(x)并求出G(x)；,由C(x)=MG(x)可以生成所有码字，但不是系统码；,生成系统码的步骤如下：,1/做,，即在信息码后附加n-k个零；,如：m=110，n-k=7-3=4时，,相当于：1100000,copyright信息科学与技术学院通信原理教研组,101,2/用g(x)除得到商Q(x)和余式r(x),余式r(x)的次数必小于g(x)的次数n-k，将此余式加于信息位之后，成为编码多项式。,3/编出码组,它必能被g(x)整除。,copyright信息科学与技术学院通信原理教研组,102,例9-9（7，3）码，选定,解：,m=110，试编码。,编出码组为：1100101,copyright信息科学与技术学院通信原理教研组,103,2、循环码的译码方法,设接收码组为：,对应多项式为R(x),1/用生成多项式g(x)除R(x)，当传输无错时，必能整除。,因此，当r(x)=0，则R(x)无错。,如果仅是检错，可给出结论。,copyright信息科学与技术学院通信原理教研组,104,2/,如果用于纠错，需进一步按余式r(x)用查表法或运算求出错误图样E(x)；,3/根据错误图样做：C(x)=R(x)-E(x)完成纠错。,例：（7，3）码，选定,接收码组为：0010101，是判断是否有错？,解：,r(x)=111，传输有错误。,copyright信息科学与技术学院通信原理教研组,105,9.5.3截短循环码,截短目的：在设计纠错编码方案时，常常信息位数k、码长n和纠错能力都是预先给定的。但是，并不一定有恰好满足这些条件的循环码存在。这时，可以采用将码长截短的方法，得出满足要求的编码。截短方法：设给定一个(n,k)循环码，它共有2k种码组，现使其前i(0ik)个信息位全为“0”，于是它变成仅有2k-i种码组。然后从中删去这i位全“0”的信息位，最终得到一个(ni,ki)的线性码。将这种码称为截短循环码。截短循环码性能：循环码截短前后至少具有相同的纠错能力，并且编解码方法仍和截短前的方法一样。例：要求构造一个能够纠正1位错码的(13,9)码。这时可以由(15,11)循环码的11种码组中选出前两信息位均为“0”的码组，构成一个新的码组集合。然后在发送时不发送这两位“0”。于是发送码组成为(13,9)截短循环码。,copyright信息科学与技术学院通信原理教研组,106,什么是BCH码？它是一种获得广泛应用的能够纠正多个错码的循环码，是以3位发明这种码的人名(Bose-Chaudhuri-Hocguengh