第九章-差错控制编码-要点优秀PPT.ppt

《第九章-差错控制编码-要点优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第九章-差错控制编码-要点优秀PPT.ppt（113页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第 9 章章 差错限制编码差错限制编码1通信系统通信系统n信源编码（削减）冗余，提高编码效率；n信道编码提高信息传递的牢靠性.29.1 9.1 9.1 9.1 纠错编码的基本概念纠错编码的基本概念纠错编码的基本概念纠错编码的基本概念一信道纠错编码一信道纠错编码一信道纠错编码一信道纠错编码 近年来，随着计算机、卫星通信及高速数据网的飞速发展，数据的交近年来，随着计算机、卫星通信及高速数据网的飞速发展，数据的交换、处理和存储技术得到了广泛的应用，人们对数据传输和存储系统的牢靠换、处理和存储技术得到了广泛的应用，人们对数据传输和存储系统的牢靠性提出了越来越高的要求。因此，如何限制差错、提高数据传输

2、和存储的牢性提出了越来越高的要求。因此，如何限制差错、提高数据传输和存储的牢靠性，成为现代数字通信系统设计工作者面临的重要课题。靠性，成为现代数字通信系统设计工作者面临的重要课题。香农其次定理指出，当信息传输速率低于信道容量时，通过某种编译香农其次定理指出，当信息传输速率低于信道容量时，通过某种编译码方法，就能使错误概率为随意小。目前已有了很多有效的编译码方法，并码方法，就能使错误概率为随意小。目前已有了很多有效的编译码方法，并形成了一门新的技术形成了一门新的技术纠错编码技术。纠错编码技术。这里所讲的纠错编码即信道编码，与信源编码一样都是一种编码，但这里所讲的纠错编码即信道编码，与信源编码一样

3、都是一种编码，但两者的作用是完全不同的。两者的作用是完全不同的。u 信源编码的目的是压缩冗余度，提高信息的传输速率。信源编码的目的是压缩冗余度，提高信息的传输速率。u 信道编码的目的是提高信息传输时的抗干扰实力以增加信息传输的牢信道编码的目的是提高信息传输时的抗干扰实力以增加信息传输的牢靠性。靠性。3二差错限制系统模型及分类二差错限制系统模型及分类二差错限制系统模型及分类二差错限制系统模型及分类 1差错限制系统模型差错限制系统模型模型突出了以限制差错为目的的纠错码编、译码器，因此也称为模型突出了以限制差错为目的的纠错码编、译码器，因此也称为差错限制系统。差错限制系统。2差错限制系统的分类差错限

4、制系统的分类按其纠错实力的不同可分为两种：检错码和纠错码。按其纠错实力的不同可分为两种：检错码和纠错码。检错码：能发觉错误但不能订正错误的码；检错码：能发觉错误但不能订正错误的码；纠错码：不仅能发觉错误而且还能订正错误的码。纠错码：不仅能发觉错误而且还能订正错误的码。4差错限制方式差错限制方式 图图 差错限制方式差错限制方式 5前向纠错方式前向纠错方式n前向纠错方式记作前向纠错方式记作FEC(ForwordErrorCorrection)。发端发送能够订正错误。发端发送能够订正错误的码，收端收到信码后自动地订正传输中的错的码，收端收到信码后自动地订正传输中的错误。误。n优点：不须要反馈信道；能

5、进行一个用户对多优点：不须要反馈信道；能进行一个用户对多个用户的同时通信，特殊适合于移动通信；译个用户的同时通信，特殊适合于移动通信；译码实时性较好，限制电路也比较简洁。码实时性较好，限制电路也比较简洁。n缺点：译码设备较困难；编码效率较低。缺点：译码设备较困难；编码效率较低。6检错重发方式检错重发方式nARQ(AutomaticRepeatRequest)方式是：发端发方式是：发端发出能够发觉错误的码（检错码），收端译码器收到后，出能够发觉错误的码（检错码），收端译码器收到后，推断在传输中有无错误产生，并通过反馈信道把捡测推断在传输中有无错误产生，并通过反馈信道把捡测结果告知发端。发端把收端

6、认为有错的消息再次传送，结果告知发端。发端把收端认为有错的消息再次传送，直到收端认为正确接收为止。直到收端认为正确接收为止。n优点：译码设备简洁，在多余度确定的状况下，码的优点：译码设备简洁，在多余度确定的状况下，码的检错实力比纠错实力要高得多，因而整个系统能获得检错实力比纠错实力要高得多，因而整个系统能获得极低的误码率。极低的误码率。n缺点：应用缺点：应用ARQ方式必需有一条从收端至发端的反馈方式必需有一条从收端至发端的反馈信道。并要求信源产生信息的速率可以进行限制，收、信道。并要求信源产生信息的速率可以进行限制，收、发两端必需相互协作，其限制电路比较困难，传输信发两端必需相互协作，其限制电

7、路比较困难，传输信息的连贯性和实时性也较差。息的连贯性和实时性也较差。7混合纠错方式混合纠错方式nHEC(HybridErrorControl)方式是上述两种方式是上述两种方式的结合。方式的结合。n发端发送的码既能检错、又有确定的纠错实力。发端发送的码既能检错、又有确定的纠错实力。收端译码时若发觉错误个数在码的纠错实力以收端译码时若发觉错误个数在码的纠错实力以内，则自动进行纠错；若错误个数超过了码的内，则自动进行纠错；若错误个数超过了码的纠错实力，但能检测出来，则通过反馈信道告纠错实力，但能检测出来，则通过反馈信道告知发方重发。知发方重发。n这种方式在确定程度上避开了这种方式在确定程度上避开了

8、FEC方式译码方式译码设备困难和设备困难和ARQ方式信息连贯性差的缺点。方式信息连贯性差的缺点。8n在设计差错限制系统时，选择何种实现方式，在设计差错限制系统时，选择何种实现方式，应综合考虑各方面的因素。主要有：应综合考虑各方面的因素。主要有：n满足用户对误码率的要求；满足用户对误码率的要求；n有尽可能高的信息传输速率；有尽可能高的信息传输速率；n有尽可能简洁的编译码算法且易于实现；有尽可能简洁的编译码算法且易于实现；n可接受的成本。可接受的成本。9三纠错码的分类三纠错码的分类三纠错码的分类三纠错码的分类n常用的纠错码按其码字结构形式和对信常用的纠错码按其码字结构形式和对信息序列处理方式的不同

9、可分成两大类：息序列处理方式的不同可分成两大类：q分组码分组码q卷积码卷积码10分组码：把信息序列以每分组码：把信息序列以每k个码元分组，编码器将每个信息组按确定规律产个码元分组，编码器将每个信息组按确定规律产 生生r个多余的码元（称为校验元），形成一个长为个多余的码元（称为校验元），形成一个长为n=k+r 的码字。的码字。对于对于k个码元分组，共有个码元分组，共有2k个不同的信息组，编码器输出长个不同的信息组，编码器输出长n的的2k个码个码字，这字，这2k个长为个长为n的码字构成的集合称为一个（的码字构成的集合称为一个（n，k）分组码。）分组码。n：码长码长；k：信息位的数目信息位的数目；R

10、=k/n：分组码码率。分组码码率。卷积码卷积码：把信息序列以每：把信息序列以每k个分组，通过编码器输出长为个分组，通过编码器输出长为n（n k）的一个）的一个子码。但是该子码的子码。但是该子码的nk个校验元不仅与本子码的信息元有关，而个校验元不仅与本子码的信息元有关，而且也与其前且也与其前m个子码的信息元有关。个子码的信息元有关。11引例引例线性分组码的基本概念线性分组码的基本概念线性分组码的译码线性分组码的译码汉明码的编码与译码汉明码的编码与译码9.2 线性分组码线性分组码12引例引例线性分组码的基本概念线性分组码的基本概念线性分组码的译码线性分组码的译码汉明码的编码与译码汉明码的编码与译码

11、9.2 线性分组码线性分组码13设传输一比特字符设传输一比特字符x=0或或1若传输过程中出现差错若传输过程中出现差错,不能被发觉不能被发觉引例引例14引例引例n0后附加字符后附加字符0，1后附加后附加1；即只有；即只有00和和11被接受，且被接受，且00视为视为0，11视为视为1；n故：故：n假如有一位错误发生，可以被检出！假如有一位错误发生，可以被检出！15n假如通信过程中发觉差错，可以通过要求对方假如通信过程中发觉差错，可以通过要求对方重新发送来获得正确的信息，即所谓的重新发送来获得正确的信息，即所谓的“数量数量换质量换质量”.但是这在实时信息采集系统中可能但是这在实时信息采集系统中可能是

12、有困难的，因为信息源已经发生变更；即使是有困难的，因为信息源已经发生变更；即使是在发方保留原信息样本的状况下，也只有在是在发方保留原信息样本的状况下，也只有在差错率很低的条件下是比较可行的差错率很低的条件下是比较可行的.n因为假如通信条件比较恶劣，差错出现频繁，因为假如通信条件比较恶劣，差错出现频繁，以至多次重发仍旧得不到一份正确的信息以至多次重发仍旧得不到一份正确的信息.n这时，仅有这时，仅有“检错检错”手段，已无能为力！手段，已无能为力！引例引例16引例引例0后附加字符后附加字符00，1后附加后附加11；即传输；即传输000相当于传送单字符相当于传送单字符0，111相当于传送单字相当于传送

13、单字符符1；这时：；这时：发生不超过两位的错误均可被检出；发生不超过两位的错误均可被检出；发生一位错误可以被订正发生一位错误可以被订正.17引例引例0后附加字符后附加字符00，1后附加后附加11；即传输；即传输000相当于传送单字符相当于传送单字符0，111相当于传送单字相当于传送单字符符1；这时：；这时：发生不超过两位的错误均可被检出；发生不超过两位的错误均可被检出；发生一位错误可以被订正发生一位错误可以被订正.纠错码纠错码信息位信息位校验位校验位18引例引例线性分组码的基本概念线性分组码的基本概念线性分组码的编码线性分组码的编码汉明码的编码与译码汉明码的编码与译码9.2 线性分组码线性分组

14、码19线性分组码的基本概念线性分组码的基本概念n分组码分组码n分组码是把信源输出的信息序列，以分组码是把信源输出的信息序列，以k个信息个信息位位n分为一段，通过编码器把这段信息位按确定规分为一段，通过编码器把这段信息位按确定规则则nf产生产生r个校验位，输出长为个校验位，输出长为n=k+r的一个码字，的一个码字，n所得码字的全体所得码字的全体.n称之为（称之为（n，k）分组码）分组码！nn表示码长，表示码长，k信息位个数信息位个数.20引例引例0后附加字符后附加字符00，1后附加后附加11；即传输；即传输000相当于传送单字符相当于传送单字符0，111相当于传送单字相当于传送单字符符1；这时：

15、；这时：发生不超过两位的错误均可被检出；发生不超过两位的错误均可被检出；发生一位错误可以被订正发生一位错误可以被订正.(3,1)分组分组码码信息位信息位校验位校验位21线性分组码的基本概念线性分组码的基本概念（n，k）分组码分组码若校验位与信息位之间的关系是线性的，即若校验位与信息位之间的关系是线性的，即上述编码规则是线性的，称之为上述编码规则是线性的，称之为（n，k）线性分组码！线性分组码！22线性编码线性编码从从到到的一个线性映射的一个线性映射称为称为一个一个线性编码线性编码；线性分组码的基本概念线性分组码的基本概念即即均有均有；若若是一一映射，则称其为是一一映射，则称其为唯一唯一可译线性

16、编可译线性编码；码；23线性分组码的基本概念线性分组码的基本概念n线性分组码线性分组码线性分组码线性分组码是把信源输出的信息序列，以是把信源输出的信息序列，以k个信个信息位分为一段，通过编码器把这段信息位按息位分为一段，通过编码器把这段信息位按线性线性编码规则编码规则f 产生产生r个校验位，输出长为个校验位，输出长为n=k+r的一的一个码字，所得码字的全体个码字，所得码字的全体.称之为称之为（n，k）线性分组码）线性分组码！n表示码长，表示码长，k信息位个数信息位个数.码字个数码字个数M=2k.24编码效率编码效率 用用差差错错限限制制编编码码提提高高通通信信系系统统的的牢牢靠靠性性，是是以以

17、降降低低有有效效性性为为代代价价换换来来的的。我我们们定定义义编编码码效效率率R来来衡衡量量有有效效性性:R=k/n其中其中,k是信息元的个数，是信息元的个数，n为码长。为码长。对对纠纠错错码码的的基基本本要要求求是是:检检错错和和纠纠错错实实力力尽尽量量强强；编编码码效效率率尽尽量量高高；编编码码规规律律尽尽量量简简洁洁。实实际际中中要要依依据据具具体体指指标标要要求求，保保证证有有确确定定纠纠、检检错错实实力力和和编编码码效效率率，并并且易于实现。且易于实现。25若设码字若设码字 ，则即校验位是由信息位线性组合得到即校验位是由信息位线性组合得到.线性分组码的基本概念线性分组码的基本概念26

18、可见，可见，码字的三个校验元都由其前两位线码字的三个校验元都由其前两位线性组合得到，即可由的线性方程组求得性组合得到，即可由的线性方程组求得；线性分组码的基本概念线性分组码的基本概念信息位信息位k=2码字数码字数M=427线性编码线性编码线性分组码的基本概念线性分组码的基本概念28例题例题1：下面是某个下面是某个（n，k）线性二元码的全部码字线性二元码的全部码字x16=000000 x26=100011 x36=010101 x46=001111x56=110110 x66=101100 x76=011010 x86=111001求求n、k的值；的值；n=6;线性分组码的基本概念线性分组码的基

19、本概念M=2k k=3.解：29例例2、现现以以(7,4)分分组组码码为为例例来来说说明明线线性性分分组组码码的的特特点点。设设其其码码字字为为A=a6 a5 a4 a3 a2 a1 a0，其其中中前前 4 位位是是信信息息元元，后后 3 位位是是监监督督元元，可可用用下下列列线线性性方方程程组组来来描描述述该该分分组组码，产生监督元。码，产生监督元。线性分组码的基本概念线性分组码的基本概念30表表(7,4)码的码字表码的码字表 31监督矩阵监督矩阵H和生成矩阵和生成矩阵G 32 其其中中,P为为rk阶阶矩矩阵阵，Ir为为rr阶阶单单位位矩矩阵阵。可可以以写写成成H=P Ir形式的矩阵称为典型

20、监督矩阵。形式的矩阵称为典型监督矩阵。HAT=0T，说说明明H矩矩阵阵与与码码字字的的转转置置乘乘积积必必为为零零，可可以以用用来作为推断接收码字来作为推断接收码字A是否出错的依据。是否出错的依据。并简记为并简记为 H被称为校验矩阵或者监督矩阵。被称为校验矩阵或者监督矩阵。33若把监督方程补充为下列方程若把监督方程补充为下列方程 34可改写为矩阵形式可改写为矩阵形式 35称为生成矩阵36例题例题3：下面是一个（下面是一个（6，3）线性二元码的全部码字）线性二元码的全部码字构造它的一个生成矩阵构造它的一个生成矩阵.线性分组码的基本概念线性分组码的基本概念解：由k=3 个线性独立的码字组成：37例

21、题例题3：下面是一个（下面是一个（6，3）线性二元码的全部码字）线性二元码的全部码字验证：验证：线性分组码的基本概念线性分组码的基本概念38n系统码系统码若若（n,k）线性分组码的生成矩阵形如线性分组码的生成矩阵形如 G=(Ik A)其中其中Ik是是k阶单位阵，阶单位阵，A为为 阶子阵，阶子阵，则称这类码为系统码则称这类码为系统码.线性分组码的基本概念线性分组码的基本概念特点：校验矩阵为特点：校验矩阵为H=(-AT I(n-k).39例题例题3：下面是一个（下面是一个（6，3）线性二元码的全部码字）线性二元码的全部码字它的一个生成矩阵它的一个生成矩阵线性分组码的基本概念线性分组码的基本概念请写

22、出它的校验矩阵请写出它的校验矩阵H.信息组原封不动地搬到码字前位的码 40线性分组码的基本概念线性分组码的基本概念41线性分组码的基本概念线性分组码的基本概念n汉明汉明距离距离：指（指（n,k）分组码中两个码字）分组码中两个码字xn、yn对应位取对应位取值不同的个数；记为值不同的个数；记为d（xn，yn）.例：例：42线性分组码的基本概念线性分组码的基本概念n理查德卫斯里汉明（Richard Wesley Hamming，1915.2.111998.1.7.），美国数学家，主要贡献在计算机科学和电讯。n1937年芝加哥高校学士学位毕业，1939年内布拉斯加高校硕士学位毕业，1942年伊利诺伊高

23、校香槟分校博士学位毕业，博士论文为一些线性微分方程边界值理论上的问题（Some Problems in the Boundary Value Theory of Linear Differential Equations）。n二战期间在路易斯维尔高校当教授，1945年参与曼哈顿支配，负责编写电脑程式，计算物理学家所供应方程的解。该程式是推断引爆核弹会否燃烧大气层，结果是不会，于是核弹便起先试验。n1946至76年在贝尔试验室工作。他曾和约翰怀尔德杜奇、克劳德艾尔伍德香农合作。1956年他参与了IBM 650的程式语言发展工作。43线性分组码的基本概念线性分组码的基本概念n汉明距离汉明距离：指（

24、指（n,k）分组码中两个码字）分组码中两个码字xn、yn对应位取对应位取值不同的个数；记为值不同的个数；记为d（xn，yn）.例：例：44线性分组码的基本概念线性分组码的基本概念n线性分组码的最小距离线性分组码的最小距离：称（称（n,k）分组码中任两个码字汉明距离的最）分组码中任两个码字汉明距离的最小值，为该分组码的最小距离小值，为该分组码的最小距离d.n（5,2）线性分组码全部码字：）线性分组码全部码字：n最小距离最小距离d=3.汉明重量汉明重量45引例引例线性分组码的基本概念线性分组码的基本概念线性分组码的译码线性分组码的译码汉明码的编码与译码汉明码的编码与译码9.2 线性分组码线性分组码

25、生成矩阵校验矩阵码的最小距离46引例引例线性分组码的基本概念线性分组码的基本概念线性分组码的译码线性分组码的译码汉明码的编码与译码汉明码的编码与译码9.2 线性分组码线性分组码47线性分组码的译码线性分组码的译码n基本概念基本概念错误图样错误图样n设发送的码字设发送的码字xn=(x1,x2,xn)，通过有扰，通过有扰信道传输，信道传输，到达接收端译码器的序列为到达接收端译码器的序列为 rn=(r1,r2,rn)n信道中的干扰表示为二进序列：信道中的干扰表示为二进序列：错误图样错误图样en=(e1,e2,en).相应有错的相应有错的ei取值为取值为1.nrn=xn+en，其中其中ri=xi+ei

26、，xi，ri，eiGF(2)称称en为信道中的错误图样为信道中的错误图样.译码器任务译码器任务从从rn中得中得到到xn或或en.48线性分组码的译码线性分组码的译码n例例4设发送序列设发送序列xn=(1111100000)，收到的收到的序列序列rn=(1001010000).n其次、三、五、六位产生了错误，其次、三、五、六位产生了错误，因此信道因此信道的错误图样的错误图样en的二、的二、三、三、五、五、六位取值为六位取值为1，其它各位取值为，其它各位取值为0，即即nen=(0110110000).用式子可表示成：用式子可表示成：rn=xn+en49线性分组码的译码线性分组码的译码n基本概念基本

27、概念伴随式伴随式n由于分组码中的任一码字满足：由于分组码中的任一码字满足：xnHT=0，n所以，可对收到的序列所以，可对收到的序列rn进行检验：进行检验：nrnHT=(xn+en)HT=xnHT+enHT=enHTn若若en=0，则，则rnHT=0；n若若en0，则，则rnHT0.n记记S=enHT，称之为接收序列，称之为接收序列rn的伴随式的伴随式.rnHT仅与错误图仅与错误图样有关，与发送什样有关，与发送什么码字无关！么码字无关！50n（n，k）线线性性分分组组码码的的校校验验矩矩阵阵，用用列列向向量表出：量表出：线性分组码的译码线性分组码的译码其中其中，hn-i为为H矩阵的第矩阵的第i列

28、列.51n设设en=(e1，e2，en)=(0，ei1，0，ei2，0，ei3，0，eit，0，0)其中其中eij=1,即即第第i1，i2，it位有错，位有错，则则线性分组码的译码线性分组码的译码S是是H中相应于中相应于eij那几那几列的线性组合！列的线性组合！52线性分组码的译码线性分组码的译码n例例5已知（已知（7，3）码的校验矩阵为）码的校验矩阵为若发送码字若发送码字xn=（1110100），收到），收到rn=（0010100）.则则错误图样为错误图样为en=（1100000）.53线性分组码的译码线性分组码的译码由定义可以求得，由定义可以求得，rn的伴随式：的伴随式：是是H H矩阵第一

29、列与其矩阵第一列与其次列之和！次列之和！54线性分组码的译码线性分组码的译码n若错误图样若错误图样en=（0010000），则），则是是H矩阵第三列！矩阵第三列！若错误图样中只有一个重量非零，则若错误图样中只有一个重量非零，则ST是是H矩阵相应的列，因而能够订正矩阵相应的列，因而能够订正单个错误！单个错误！55表表(7,4)码码S与与E的对应关系的对应关系 56线性分组码的译码线性分组码的译码n若错误图样若错误图样en=（0010100），则），则是是H矩阵第三列与第矩阵第三列与第五列之和！五列之和！若发生两个错误，译码器只能判决若发生两个错误，译码器只能判决传输有错（传输有错（en 0）,不

30、能判定由哪不能判定由哪几位错误引起！几位错误引起！57 纠错码的抗干扰实力完全取决于许用纠错码的抗干扰实力完全取决于许用码字之间的距离，码的最小距离越大，说码字之间的距离，码的最小距离越大，说明码字间的最小差别越大，抗干扰实力就明码字间的最小差别越大，抗干扰实力就越强。越强。分组码的最小汉明距离分组码的最小汉明距离d d与检错和纠错与检错和纠错实力之间满足下列关系：实力之间满足下列关系：58线性分组码的译码线性分组码的译码（1）当码字用于订正错误时，线性分组码能自）当码字用于订正错误时，线性分组码能自动订正动订正t个错误的充要条件是个错误的充要条件是d2t+1最大似然译码准则是纠错的策略依据最

31、大似然译码准则是纠错的策略依据.若收到的字若收到的字符串是码字本身，则干脆按码字译码；否则，按符串是码字本身，则干脆按码字译码；否则，按与接收到的字的与接收到的字的Hamming距离最接近的码字译码距离最接近的码字译码.59线性分组码的译码线性分组码的译码（2）当码字用于检测错误时，假如要检测）当码字用于检测错误时，假如要检测e个错误，则个错误，则de+1eBAd60（3）若码字用于纠若码字用于纠t个错误，同时检个错误，同时检e个错误个错误时（时（et），则），则 d t+e+1 tAeB1d线性分组码的译码线性分组码的译码61线性分组码的译码线性分组码的译码n例例5已知（已知（7，3）码的校

32、验矩阵为）码的校验矩阵为最小距离最小距离d=3d=2t+1d=2t+162线性分组码的译码线性分组码的译码n（n,k）码的译码步骤）码的译码步骤（1）由接收到的）由接收到的rn，计算伴随式，计算伴随式S=rnHT；（2）若）若S=0，则认为接收无误；，则认为接收无误；若若S0，则由，则由S找出错误图样找出错误图样en；（3）由）由en和和rn找出找出xn=rn-en.63引例引例线性分组码的基本概念线性分组码的基本概念线性分组码的译码线性分组码的译码汉明码的编码与译码汉明码的编码与译码9.2 线性分组码线性分组码64线性分组码线性分组码n汉明码汉明码(HammingCode)n汉明码是汉明码是

33、1950年由汉明首先构造，年由汉明首先构造，用以订用以订正单个错误的线性分组码正单个错误的线性分组码.n由于它的编译码特别简洁，由于它的编译码特别简洁，很简洁实现，很简洁实现，因此用得很普遍，因此用得很普遍，特殊是在计算机的存贮特殊是在计算机的存贮和运算系统中更常用到，是一类特殊引人和运算系统中更常用到，是一类特殊引人留意的码留意的码.65线性分组码线性分组码n汉明码汉明码(HammingCode)n汉明码不是指一个码，而是代表一类码；汉明码不是指一个码，而是代表一类码；n汉明码码长汉明码码长n和信息位和信息位k听从以下规律：听从以下规律：(n,k)=(2m-1,2m-1-m)，其中，其中m=

34、n-k；n汉明码的最小距离汉明码的最小距离d=3；所以，纠错实力；所以，纠错实力t=1；66n汉明码汉明码(HammingCode)的译码的译码n例例6已知已知GF(2)上的（上的（6，3）汉明码的一）汉明码的一样校验矩阵样校验矩阵H为：为：线性分组码线性分组码67线性分组码线性分组码n若发送码字若发送码字xn=(101011),接收序列为接收序列为rn=(101011).n若发送码字若发送码字xn=(101011),接收序列为接收序列为rn=(100011).判定传输中没有发判定传输中没有发生错误！生错误！判定接收序列判定接收序列rn的第的第3 3位是有错的！位是有错的！68设一分组码具有一

35、样校验矩阵：设一分组码具有一样校验矩阵：求这个分组码求这个分组码n=？k=？，共有多少个码字？，共有多少个码字？此分组码的生成矩阵；此分组码的生成矩阵；向量向量101010是否是码字？是否是码字？设发送码字设发送码字C=(001111)，但接收序列为，但接收序列为R=(000010),其伴随式其伴随式S是什么？这个伴随式指出已发生的错误在是什么？这个伴随式指出已发生的错误在什么地方，为什么与实际错误不符？什么地方，为什么与实际错误不符？习题课（补充）习题课（补充）69解：解：设码字设码字C=(c5c4c3c2c1c0)，有，有习题课习题课故得故得所以所以n=6，k=3，为，为(6,3)分组码分

36、组码共有码字共有码字2k=8个个70设一分组码具有一样校验矩阵：设一分组码具有一样校验矩阵：求这个分组码求这个分组码n=？k=？，共有多少个码字？，共有多少个码字？此分组码的生成矩阵；此分组码的生成矩阵；向量向量101010是否是码字？是否是码字？设发送码字设发送码字C=(001111)，但接收序列为，但接收序列为R=(000010),其伴随式其伴随式S是什么？这个伴随式指出已发生的错误在是什么？这个伴随式指出已发生的错误在什么地方，为什么与实际错误不符？什么地方，为什么与实际错误不符？习题课（补充）习题课（补充）71习题课习题课由上式可得由上式可得取一组线性无关的基础解系，得到生成矩阵取一组

37、线性无关的基础解系，得到生成矩阵72设一分组码具有一样校验矩阵：设一分组码具有一样校验矩阵：求这个分组码求这个分组码n=？k=？，共有多少个码字？，共有多少个码字？此分组码的生成矩阵；此分组码的生成矩阵；向量向量101010是否是码字？是否是码字？设发送码字设发送码字C=(001111)，但接收序列为，但接收序列为R=(000010),其伴随式其伴随式S是什么？这个伴随式指出已发生的错误在是什么？这个伴随式指出已发生的错误在什么地方，为什么与实际错误不符？什么地方，为什么与实际错误不符？习题课（补充）习题课（补充）73习题课习题课由由可知，向量可知，向量101010不是码字不是码字74设一分组

38、码具有一样校验矩阵：设一分组码具有一样校验矩阵：求这个分组码求这个分组码n=？k=？，共有多少个码字？，共有多少个码字？此分组码的生成矩阵；此分组码的生成矩阵；向量向量101010是否是码字？是否是码字？设发送码字设发送码字C=(001111)，但接收序列为，但接收序列为R=(000010),其伴随式其伴随式S是什么？这个伴随式指出已发生的错误在是什么？这个伴随式指出已发生的错误在什么地方，为什么与实际错误不符？什么地方，为什么与实际错误不符？习题课（补充）习题课（补充）75习题课习题课接收序列接收序列R的伴随式的伴随式是校验矩阵的第五列据此可以判定码字中的是校验矩阵的第五列据此可以判定码字中

39、的第五个重量发生错误，则第五个重量发生错误，则E=(000010)76但实际的错误图样但实际的错误图样E为为E=(000010)+(001111)=(001101)是码字传输中发生了三位码元错误是码字传输中发生了三位码元错误因为该（因为该（6，3）码）码dmin=3，所以依据伴随式只，所以依据伴随式只能能订正一位码元发生错误的错误图样；从而。当传订正一位码元发生错误的错误图样；从而。当传输过程中码字发生的多于一位错误就无法订正输过程中码字发生的多于一位错误就无法订正习题课习题课779.3 常用的几种简洁分组码常用的几种简洁分组码9.3.1 奇偶监督码奇偶监督码(Parity)奇奇偶偶监监督督码

40、码是是在在原原信信息息码码后后面面附附加加一一个个监监督督元元，使使得得码码组组中中“1”的的个个数数是是奇奇数数或或偶偶数数。或或者者说说，它它是是含含一一个个监监督督元元，码码重重为为奇奇数数或偶数的或偶数的(n,n-1)系统分组码。系统分组码。奇偶监督码又分为奇监督码和偶监督码。奇偶监督码又分为奇监督码和偶监督码。78Parity Error Checking79Simple Parity PerformancenCan detect all single-bit errorsnMay detect all burst errors as long as total number of

41、bits changed is oddnCannot detect errors when total number of bits changed is even since parity check will pass even though errors had occurred 奇偶监督码的编码效率R为 809.3.2 行列监督码行列监督码 图图(66,50)行列监督码行列监督码 81Two-Dimensional Parity82Two-dimensional ParitynExample:five 7-bit character packet,even parity 0110100

42、1011010001011011101011001011101101000110183How Many Errors Can you Detect?nAll 1-bit errorsnExample:011010010110100000110111010110010111011010001101error bitodd number of 1s84How Many Errors Can you Detect?nAll 2-bit errorsnExample:011010010110100000111111010110010111011010001101error bitsodd number

43、 of 1s on columns85How Many Errors Can you Detect?nAll 3-bit errorsnExample:011010010110100000111110010110010111011010001101error bitsodd number of 1s on column86How Many Errors Can you Detect?nMost 4-bit errorsnExample of 4-bit error that is not detected:01101001011010000011111001001001011101101000

44、1101error bits能订正一些仅在一行中的单个错误。能订正一些仅在一行中的单个错误。879.4循环码循环码一、循环码的特点 循环码最大的特点就是码字的循环特性，所谓循环特性是指：循环码中任一许用码组经过循环移位后，所得到的码组仍旧是许用码组。若若（）为一循环码组，则为一循环码组，则还是许用码组。还是许用码组。88【例】（【例】（7，3）线性分组码）线性分组码由两组码字循环构成的循环码由两组码字循环构成的循环码。89n循环码举例循环码举例(7,3)循环码循环码90二、码多项式为了利用代数理论探讨循环码，可以将码组用代数多项式来表为了利用代数理论探讨循环码，可以将码组用代数多项式来表示，这

45、个多项式被称为码多项式，对于许用循环码示，这个多项式被称为码多项式，对于许用循环码可以将它的码多项式表示为：可以将它的码多项式表示为：对于二进制码组，多项式的每个系数不是对于二进制码组，多项式的每个系数不是0就是就是1，x仅是码元位仅是码元位置的标记。因此，这里并不关切置的标记。因此，这里并不关切x的取值。的取值。例：表中的第例：表中的第7码字可以表示为码字可以表示为91循环特性的表示循环特性的表示以（以（7，3）循环码为例：（任取一码字）循环码为例：（任取一码字）移一位移一位移两位移两位移三位移三位?此时：此时：7 n-1=6，超出了，超出了n=7的矢量空间。的矢量空间。要求：要求：则：则：

46、，即，即92下面用下面用 去除去除 ，得余，得余对于上面第三次移位结果，可重新表示如下：对于上面第三次移位结果，可重新表示如下：结论：假如将一个循环码的某一非零码字用码多项式表示出来，那么其他结论：假如将一个循环码的某一非零码字用码多项式表示出来，那么其他的非零码字多项式就可以用这个码字多项式（或码字多项式的和）的非零码字多项式就可以用这个码字多项式（或码字多项式的和）乘上乘上x的一个幂，再求（的一个幂，再求（xn+1）的余得到）的余得到。说明：说明：一个码字的移位最多能得到一个码字的移位最多能得到n个码字，因此个码字，因此“循环码字的循环仍是循环码字的循环仍是码字码字”并不意味着循环码集可以

47、从一个码字循环而得，还应包含码并不意味着循环码集可以从一个码字循环而得，还应包含码字的一些线性组合。字的一些线性组合。93在整数运算中，有模在整数运算中，有模n运算。例运算。例如，在模如，在模2运算中，有运算中，有1+120（模（模2），），1+231（模（模2），），2360（模（模2）等。因此，若一个整数）等。因此，若一个整数m可以表示为可以表示为:则在模则在模n运算下，有运算下，有mp（模（模n），也就是说，），也就是说，在模在模n运算下，一整数运算下，一整数m等于其被等于其被n除所得的余除所得的余数。数。94在码多项式运算中也有类似的按模运算在码多项式运算中也有类似的按模运算法则。若一

48、随意多项式法则。若一随意多项式F(x)被一个被一个n次多项式次多项式N(x)除，得到商式除，得到商式Q(x)和一个次数小于和一个次数小于n的余的余式式R(x)，也就是：，也就是：则可以写为：则可以写为：F(x)R(x)mod（N(x)）这时，码多项式系数仍按模这时，码多项式系数仍按模2运算，即只取值运算，即只取值0和和1。95假设：计算假设：计算x4+x2+1除以除以x3+1的值可得：的值可得：这样式也可以表示为：这样式也可以表示为：留意，在上述运算中，由于是模留意，在上述运算中，由于是模2运算，因此，加法和运算，因此，加法和减法是等价的，在式子中通常用加法运算符，具体模减法是等价的，在式子中

49、通常用加法运算符，具体模2运算的规则定义如下：运算的规则定义如下：96在循环码中，若A(x)是一个长为n的许用码组，则xiA(x)在按模(xn+1)运算下，亦是一个许用码组，也就是假如：可以证明Al(x)亦是一个许用码组，并且，Al(x)正是A(x)代表的码组向左循环移位 i 次的结果。97例：上式的循环码，其码长例：上式的循环码，其码长n7，现给定，现给定i3，则：，则：其对应的码组为其对应的码组为0101110，它正是表中第，它正是表中第3码字。码字。结论：一个长度为结论：一个长度为n的循环码，它必为按的循环码，它必为按模模(xn+1)运算的一个余式。运算的一个余式。981定义：定义：若若

50、g(x)是一个是一个(n-k)次多项式，且是次多项式，且是(x(xn n+1)+1)的因式，则由的因式，则由g(x)g(x)可以可以生成一个（生成一个（n n，k k）循环码，）循环码，g(x)称称为该循环码的为该循环码的生成多项式生成多项式。两个结论：两个结论：两个结论：两个结论：（1）GF(2)上的（上的（n，k）循环码中，存在着一个常数项为）循环码中，存在着一个常数项为1，次数为，次数为(n-k)的的首一码多项式首一码多项式g(x)（首一：多项式最高幂次项系数首一：多项式最高幂次项系数 gn-k=1）（gn-k=1）使得全部码多项式都是使得全部码多项式都是g(x)的倍式，即：的倍式，即：