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

《第九章-差错控制编码-(1)要点.ppt》由会员分享，可在线阅读，更多相关《第九章-差错控制编码-(1)要点.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)。发端发送能够纠正错误。发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错的码，收端收到信码后自动地纠正传输中的错误。误。q优点：优点：不需要反馈信道；

5、能进行一个用户对多个用不需要反馈信道；能进行一个用户对多个用户的同时通信，特别适合于移动通信；译码实时性户的同时通信，特别适合于移动通信；译码实时性较好，控制电路也比较简单。较好，控制电路也比较简单。q缺点：缺点：译码设备较复杂；编码效率较低。译码设备较复杂；编码效率较低。6检错重发方式检错重发方式nARQ(AutomaticRepeatRequest)方式是：发端发方式是：发端发出能够发现错误的码（检错码），收端译码器收到后，出能够发现错误的码（检错码），收端译码器收到后，判断在传输中有无错误产生，并通过反馈信道把捡测判断在传输中有无错误产生，并通过反馈信道把捡测结果告诉发端。发端把收端认为

6、有错的消息再次传送，结果告诉发端。发端把收端认为有错的消息再次传送，直到收端认为正确接收为止。直到收端认为正确接收为止。q优点：优点：译码设备简单，在多余度一定的情况下，码的检错能译码设备简单，在多余度一定的情况下，码的检错能力比纠错能力要高得多，因而整个系统能获得极低的误码率。力比纠错能力要高得多，因而整个系统能获得极低的误码率。q缺点：缺点：应用应用ARQ方式必须有一条从收端至发端的反馈信道。方式必须有一条从收端至发端的反馈信道。并要求信源产生信息的速率可以进行控制，收、发两端必须并要求信源产生信息的速率可以进行控制，收、发两端必须互相配合，其控制电路比较复杂，传输信息的连贯性和实时互相配

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

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

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

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

11、2 线性分组码线性分组码13设传输一比特字符设传输一比特字符x=0或或1若传输过程中出现差错若传输过程中出现差错,不能被发现不能被发现引例引例14引例引例n0后附加字符后附加字符0，1后附加后附加1；即只有；即只有00和和11被接受，且被接受，且00视为视为0，11视为视为1；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 线性分组码线性分组码19线性

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

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

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;线性分组码的基本概念线性分组码的基本概念M=2k k=

19、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例题例题3：下面是一个

21、（下面是一个（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汉明距离汉明距离：指（指（n,k）分组码中

24、两个码字）分组码中两个码字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，xi，ri，eiG

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

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

28、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矩阵第一列与第矩阵第一列与第二列之和！二

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

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

31、若收到的字若收到的字符串是码字本身，则直接按码字译码；否则，按符串是码字本身，则直接按码字译码；否则，按与接收到的字的与接收到的字的Hamming距离最接近的码字译码距离最接近的码字译码.59线性分组码的线性分组码的译码译码（2）当码字用于检测错误时，如果要检测）当码字用于检测错误时，如果要检测e个错误，则个错误，则d e+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汉明码汉明码(Hamming Code)n汉明码是汉明码是1950年由汉明首先构造，年

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

34、的最小距离d=3；所以，；所以，纠错能力纠错能力t=1；66n汉明码汉明码(Hamming Code)的译码的译码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)=(001111)，但接收序列为，但接收序列为R=(000010),=(000010),其其伴随式伴随式S是什么？这个伴随式指出已发生的错误在什是什么？这个伴随式指出已发生的错误在什么地方，为什么与实际错误不符？么地方，为什么与实际错误不符？习题课（补充）习题课（补充）69解：解：设码字设码字C=(c5c4c3c2c1c0)，有，有习题课习题课故得故得所以所以n=6，k=3，为，为(6,3)

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

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

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

39、5习题课习题课接收序列接收序列R的伴随式的伴随式是校验矩阵的第五列据此可以判定码字中的是校验矩阵的第五列据此可以判定码字中的第五个分量发生错误，则第五个分量发生错误，则E=(000010)76但实际的错误图样但实际的错误图样E为为E=(000010)+(001111)=(001101)是码字传输中发生了三位码元错误是码字传输中发生了三位码元错误因为该（因为该（6，3）码）码dmin=3，所以根据伴随式只能，所以根据伴随式只能纠正一位码元发生错误的错误图样；从而。当传纠正一位码元发生错误的错误图样；从而。当传输过程中码字发生的多于一位错误就无法纠正输过程中码字发生的多于一位错误就无法纠正习题课习

40、题课779.3 常用的几种简单分组码常用的几种简单分组码9.3.1 奇偶监督码奇偶监督码(Parity)奇奇偶偶监监督督码码是是在在原原信信息息码码后后面面附附加加一一个个监监督督元元，使使得得码码组组中中“1”的的个个数数是是奇奇数数或或偶偶数数。或或者者说说，它它是是含含一一个个监监督督元元，码码重重为为奇奇数数或偶数的或偶数的(n,n-1)系统分组码。系统分组码。奇偶监督码又分奇偶监督码又分为奇监督码和偶监督码。为奇监督码和偶监督码。78Parity Error Checking79Simple Parity PerformancenCan detect all single-bit e

41、rrorsnMay detect all burst errors as long as total number of 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 P

42、aritynExample:five 7-bit character packet,even parity 01101001011010001011011101011001011101101000110183How Many Errors Can you Detect?nAll 1-bit errorsnExample:011010010110100000110111010110010111011010001101error bitodd number of 1s84How Many Errors Can you Detect?nAll 2-bit errorsnExample:0110100

43、10110100000111111010110010111011010001101error bitsodd number 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

44、 is not detected:011010010110100000111110010010010111011010001101error bits能纠正一些仅在一行中的单个错误。能纠正一些仅在一行中的单个错误。879.4循环码循环码一、循环码的特点 循环码最大的特点就是码字的循环特性，所谓循环特性是指：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。若若（）为一循环码组，则为一循环码组，则还是许用码组。还是许用码组。88【例例】（7，3）线性分组码）线性分组码由两组码字循环构成的循环码由两组码字循环构成的循环码。89n循环码举例循环码举例(7,3)循环码循环码90二、码多项

45、式为了利用代数理论研究循环码，可以将码组用代数多项式来表为了利用代数理论研究循环码，可以将码组用代数多项式来表示，这个多项式被称为码多项式，对于许用循环码示，这个多项式被称为码多项式，对于许用循环码可以将它的码多项式表示为：可以将它的码多项式表示为：对于二进制码组，多项式的每个系数不是对于二进制码组，多项式的每个系数不是0就是就是1，x 仅是码元位仅是码元位置的标志。因此，这里并不关心置的标志。因此，这里并不关心x 的取值。的取值。例：表中的第例：表中的第7码字可以表示为码字可以表示为91循环特性的表示循环特性的表示以（以（7，3）循环码为例：（任取一码字）循环码为例：（任取一码字）移一位移一

46、位移两位移两位移三位移三位?此时：此时：7 n-1=6，超出了，超出了n=7的矢量空间。的矢量空间。要求：要求：则：则：，即，即92下面用下面用 去除去除 ，得余，得余对于上面第三次移位结果，可重新表示如下：对于上面第三次移位结果，可重新表示如下：结论：结论：如果将一个循环码的某一非零码字用码多项式表示出来，那么其他如果将一个循环码的某一非零码字用码多项式表示出来，那么其他的非零码字多项式就可以用这个码字多项式（或码字多项式的和）的非零码字多项式就可以用这个码字多项式（或码字多项式的和）乘上乘上x的一个幂，再求（的一个幂，再求（xn+1）的余得到）的余得到。说明：说明：一个码字的移位最多能得到

47、一个码字的移位最多能得到n个码字，因此个码字，因此“循环码字的循环仍是循环码字的循环仍是码字码字”并不意味着循环码集可以从一个码字循环而得，还应包含码并不意味着循环码集可以从一个码字循环而得，还应包含码字的一些线性组合。字的一些线性组合。93在整数运算中，有模在整数运算中，有模n运算。例运算。例如，在模如，在模2运算中，有运算中，有1+120（模（模2），），1+231（模（模2），），2360（模（模2）等。因此，若一个整数）等。因此，若一个整数m可以表示为可以表示为:则在模则在模n运算下，有运算下，有mp（模（模n），也就是说，），也就是说，在模在模n运算下，一整数运算下，一整数m等于其被

48、等于其被n除所得的余除所得的余数。数。94在码多项式运算中也有类似的按模运算在码多项式运算中也有类似的按模运算法则。若一任意多项式法则。若一任意多项式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的值可得：的值可得：这样式也可以表示为：这样式也可以表示为：注意，在上述运算中，由于是模注意，在上述运

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

50、：一个长度为n的循环码，它必为按的循环码，它必为按模模(xn+1)运算的一个余式。运算的一个余式。981定义：定义：若若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)（首一：多项式最高幂次项系数首一：多项