通信原理_第十一章 差错控制编码

1、通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网 11.1 概述概述 11.2 纠错编码的基本原理纠错编码的基本原理 11.4 简单的实用编码简单的实用编码 11.5 线性分组码线性分组码 11.6 循环码循环码 11.7 卷积码卷积码第十一章第十一章 差错控制编码差错控制编码本章内容简介本章内容简介通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.1 概述概述一一. 差错的产生差错的产生二二. 差错控制方法差错控制方法噪声与干扰噪声与干扰 检错重发法检错重发法 前向纠错法前

2、向纠错法 反馈校验法反馈校验法随机噪声与干扰随机噪声与干扰突发噪声与干扰突发噪声与干扰混合噪声与干扰混合噪声与干扰随机信道随机信道突发信道突发信道混合信道混合信道噪声与干扰是通信出噪声与干扰是通信出现差错的基本原因。现差错的基本原因。不同的不同的噪声与噪声与干扰信干扰信道，应道，应采用不采用不同的差同的差错控制错控制策略。策略。检错重发法检错重发法：双向信道工作。接收信息方：双向信道工作。接收信息方具有检错能力，收到信息无误，回发肯定具有检错能力，收到信息无误，回发肯定应答；有误则不发应答或发否定应答。应答；有误则不发应答或发否定应答。前向纠错法前向纠错法：单向信道工作。接收信息方：单向信道工

3、作。接收信息方具有纠错能力，发现收到信息有误时，确具有纠错能力，发现收到信息有误时，确定误码的位置并按规则予以纠正。定误码的位置并按规则予以纠正。反馈校验法反馈校验法：双向信道工作。接收信息方：双向信道工作。接收信息方简单地将收到信息回传给发送方，由发送简单地将收到信息回传给发送方，由发送方判断前次发送是否无误。方判断前次发送是否无误。第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.1 概述概述三三. 自动要求重发自动要求重发(ARQ)系统系统第十一章第十一章 差错控制编码差错控制编码接收

4、码组ACKACKNAKACKACKNAKACKt1233455发送码组12334556t有错码组有错码组 数据按分组发送。每发送一组数据后发送端等待接收端数据按分组发送。每发送一组数据后发送端等待接收端的确认的确认(ACK)答复，然后再发送下一组数据。答复，然后再发送下一组数据。 图中的第图中的第3组接收数据有误，接收端发回一个否认组接收数据有误，接收端发回一个否认(NAK)答复。这时，发送端将重发第答复。这时，发送端将重发第3组数据。组数据。 系统是工作在半双工状态，时间没有得到充分利用，传系统是工作在半双工状态，时间没有得到充分利用，传输效率较低。输效率较低。 停止等待停止等待ARQ系统系

5、统通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.1 概述概述三三. 自动要求重发自动要求重发(ARQ)系统系统第十一章第十一章 差错控制编码差错控制编码拉后拉后ARQ系统系统接收数据有错码组有错码组910 1110 1112214365798576ACK1NAK5NAK9ACK5发送数据576952143679810 1110 11 12重发码组重发码组 发送端连续发送数据组，接收端对于每个接收到的数据发送端连续发送数据组，接收端对于每个接收到的数据组都发回确认组都发回确认(ACK)或否认或否认(NAK)答复。答复。 例如，图中

6、第例如，图中第5组接收数据有误，则在发送端收到第组接收数据有误，则在发送端收到第5组组接收的否认答复后，从第接收的否认答复后，从第5组开始重发数据组。组开始重发数据组。 在这种系统中需要对发送的数据组和答复进行编号，以在这种系统中需要对发送的数据组和答复进行编号，以便识别。显然，这种系统需要双工信道。便识别。显然，这种系统需要双工信道。通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.1 概述概述三三. 自动要求重发自动要求重发(ARQ)系统系统第十一章第十一章 差错控制编码差错控制编码选择重发选择重发ARQ系统系统接收数据有错码组

7、有错码组9214365759810 11131412发送数据995852143671011131412重发码组重发码组NAK9ACK1NAK5ACK5ACK9它只重发出错的数据组，因此进一步提高了传输效率。它只重发出错的数据组，因此进一步提高了传输效率。通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.1 概述概述三三. 自动要求重发自动要求重发(ARQ)系统系统图图11-1 典型典型ARQ系统组成框图系统组成框图 发送信源终端接收信宿终端编码器、缓冲存储重发控制解码器指令产生输出缓存双 向 信 道正确输出错误删除 ARQ系统主要优

8、点系统主要优点: 1. 只需少量多余码元；只需少量多余码元； 2. 适应不同差错特性；适应不同差错特性； 3. 检错方法简单。检错方法简单。 ARQ系统主要缺点系统主要缺点: 1. 需要双向信道；需要双向信道； 2. 出错率高时，重发降低信道效率；出错率高时，重发降低信道效率； 3. 信息传输实时性差。信息传输实时性差。第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.1 概述概述四四. 差错控制编码差错控制编码 在信息码元序列中加入一定数目的监督码元就称为差错在信息码元序列中加入一定数目的

9、监督码元就称为差错控制编码。控制编码。 差错控制编码的检纠错能力差错控制编码的检纠错能力 差错控制编码的编码效率（码率）差错控制编码的编码效率（码率） 一般说来，差错控制编码的检纠错能力取决于：一般说来，差错控制编码的检纠错能力取决于： 在信息码元序列中加入的监督码元的多少在信息码元序列中加入的监督码元的多少。对于一定长度。对于一定长度的信息码元序列的信息码元序列,加入的监督码元越多，检纠错能力越强。加入的监督码元越多，检纠错能力越强。 不同的编码规则与方法不同的编码规则与方法（有不同的（有不同的检错或或纠错能力）能力）。 在一定长度信息码元序列中加入监督码元的数目越多在一定长度信息码元序列中

10、加入监督码元的数目越多, 差差错控制编码的编码效率越低。如信息码长为错控制编码的编码效率越低。如信息码长为k，监督码长为，监督码长为r,则编码效率为则编码效率为k/(k+r)=k/n。监督码元数监督码元数r 和信息码元数和信息码元数 k 之比之比称为称为冗余度冗余度。多余度多余度指增加的监督码元多少，指增加的监督码元多少，r/n。第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.2 纠错编码的基本原理纠错编码的基本原理第十一章第十一章 差错控制编码差错控制编码分组码基本原理：举例说明如下。分

11、组码基本原理：举例说明如下。设有一种由设有一种由3位二进制数字构成的码组，它共有位二进制数字构成的码组，它共有8种不同的可能组合。若将其全部用来表示天气，种不同的可能组合。若将其全部用来表示天气，则可以表示则可以表示8种不同天气，种不同天气， 例如：例如：“000”（晴），（晴），“001”（云），（云）， “010”（阴），（阴），“011”（雨），（雨）， “100”（雪），（雪），“101”（霜），（霜）， “110”（雾），（雾），“111”（雹）。（雹）。其中任一码组在传输中若发生一个或多个错码，其中任一码组在传输中若发生一个或多个错码，则将变成另一个信息码组。这时，接收端将无法则将

12、变成另一个信息码组。这时，接收端将无法发现错误。发现错误。通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.2 纠错编码的基本原理纠错编码的基本原理第十一章第十一章 差错控制编码差错控制编码若在上述若在上述8种码组中只准许使用种码组中只准许使用4种来传送天气，例如：种来传送天气，例如：“000”晴晴 “011”云云 “101”阴阴 “110”雨雨这时，虽然只能传送这时，虽然只能传送4种不同的天气，但是接收端却种不同的天气，但是接收端却有可能发现码组中的一个错码。有可能发现码组中的一个错码。例如，若例如，若“000”（晴）中错了一位，

13、则接收码组将变（晴）中错了一位，则接收码组将变成成“100”或或“010”或或“001”。这。这3种码组都是不准使种码组都是不准使用的，称为用的，称为禁用码组禁用码组。接收端在收到禁用码组时，就认为发现了错码。当发接收端在收到禁用码组时，就认为发现了错码。当发生生3个错码时，个错码时，“000”变成了变成了“111”，它也是禁用码，它也是禁用码组，故这种编码也能检测组，故这种编码也能检测3个错码。个错码。但是这种码不能发现一个码组中的两个错码，因为发但是这种码不能发现一个码组中的两个错码，因为发生两个错码后产生的是生两个错码后产生的是许用码组许用码组。通信原理通信原理内容简介 第一章 第二章

14、第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.2 纠错编码的基本原理纠错编码的基本原理第十一章第十一章 差错控制编码差错控制编码检错和纠错检错和纠错上面这种编码只能检测错码，不能纠正错码。例如，当接收上面这种编码只能检测错码，不能纠正错码。例如，当接收码组为禁用码组码组为禁用码组“100”时，接收端将无法判断是哪一位码发时，接收端将无法判断是哪一位码发生了错误，因为晴、阴、雨三者错了一位都可以变成生了错误，因为晴、阴、雨三者错了一位都可以变成“100”。要能够纠正错误，还要增加多余度。例如，若规定许用码组要能够纠正错误，还要增加多余度。例如，若规定许用码组只有两个：只有

15、两个：“000”（晴），（晴），“111”（雨），其他都是禁用码（雨），其他都是禁用码组，则能够检测两个以下错码，或能够纠正一个错码。组，则能够检测两个以下错码，或能够纠正一个错码。例如，当收到禁用码组例如，当收到禁用码组“100”时，若当作仅有一个错码，则时，若当作仅有一个错码，则可以判断此错码发生在可以判断此错码发生在“1”位，从而纠正为位，从而纠正为“000”（晴）。（晴）。因为因为“111”（雨）发生任何一位错码时都不会变成（雨）发生任何一位错码时都不会变成“100”这这种形式。种形式。 但是，这时若假定错码数不超过两个，则存在两种可能性：但是，这时若假定错码数不超过两个，则存在两种可

16、能性：“000”错一位和错一位和“111”错两位都可能变成错两位都可能变成“100”，因而只能，因而只能检测出存在错码而无法纠正错码。检测出存在错码而无法纠正错码。通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.2 纠错编码的基本原理纠错编码的基本原理表表11-1 差错控制编码举例差错控制编码举例 消息消息 信息位信息位 监督位监督位 晴晴 0 0 0 云云 0 1 1 阴阴 1 0 1 雨雨 1 1 0两位信息位后加入一个监督位两位信息位后加入一个监督位,使使每码组中每码组中“1”的个数为偶数的个数为偶数, 能够能够检测出码组中

17、所有单数个误码。检测出码组中所有单数个误码。为每组信息码后附加若干个监督为每组信息码后附加若干个监督位构成的码组集合位构成的码组集合, 称为称为分组码分组码。分组码用符号分组码用符号(n,k)表示表示, k是信息是信息位的数目位的数目, n是码组总长度是码组总长度, n-k=r是监督位数目。是监督位数目。an-1 an-2 ar ar-1 a1 a0k个信息位个信息位r个监督位个监督位码组总长度码组总长度 n = k+r图图11-2 (n,k)分组码的结构分组码的结构第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八

18、章 第九章东北大学网11.2 纠错编码的基本原理纠错编码的基本原理 码重与码距概念码重与码距概念 一条码组中一条码组中 “1” 的个的个数称为该码组的数称为该码组的码重码重。 两码组中不同位的数目两码组中不同位的数目称为该两码组的称为该两码组的码距码距。 最小码重与最小码距最小码重与最小码距 某码组集合中含某码组集合中含 “1” 个数最少的码组的码重个数最少的码组的码重, 称该码组集合的称该码组集合的最小码重最小码重。 某码组集合中不同位数某码组集合中不同位数最少的两码组的码距最少的两码组的码距, 称称该码组集合的该码组集合的最小码距最小码距。码组集合码组集合10010010011011101

19、1100011101101000111000100码重码重w=3w=4w=4w=5w=3w=2最小码重最小码重 w0=2码重与码距概念举例码重与码距概念举例码距码距d12=3d13=3d14=4d15=3d16=3d24=1最小码距最小码距 d0=1第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.2 纠错编码的基本原理纠错编码的基本原理 码距码距(汉明汉明Hamming距离距离)概念概念图图11-3 码距的几何意义码距的几何意义a0a1a2(0,0,0)(0,0,1)(1,0,1)(1,0

20、,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1) 如果使用全部如果使用全部8个三位的个三位的码组分别表示码组分别表示8种不同信息，种不同信息，由于由于最小码距最小码距d0 =1, 说明某说明某码组的任何一位错误，都可码组的任何一位错误，都可能变为其他合法码组能变为其他合法码组,无检错无检错或纠错能力。或纠错能力。 如果使用其中如果使用其中4个三位的个三位的码组分别表示码组分别表示4种不同信息，种不同信息，由于由于最小码距最小码距d0 =2, 说明某说明某码组的任何一位错误，都不码组的任何一位错误，都不可能变为其他合法码组可能变为其他合法码组,能够能够检测出单个误码。检测出单个误码

21、。 最小码距最小码距d0 是衡量差错控制编码系统是衡量差错控制编码系统检错及纠错能力检错及纠错能力的的决定性参数。决定性参数。第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.2 纠错编码的基本原理纠错编码的基本原理 最小码距最小码距d0与检错纠错能力关系与检错纠错能力关系（1）只检模式）只检模式 为检测为检测 e 个误码，要求最小码距个误码，要求最小码距 d0 e + 1 (11.2-2)AB0123ed0图图11-4 码距与检错纠错能力的关系码距与检错纠错能力的关系（a）只检模式）只检模

22、式第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.2 纠错编码的基本原理纠错编码的基本原理 最小码距最小码距d0与检错纠错能力关系与检错纠错能力关系（2）只纠模式）只纠模式 为纠正为纠正 t 个误码，要求最小码距个误码，要求最小码距 d0 2t + 1 (11.2-3) 图图11-4 码距与检错纠错能力的关系码距与检错纠错能力的关系（b）只纠模式）只纠模式AB0123td0t4567第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章

23、第六章 第七章 第八章 第九章东北大学网11.2 纠错编码的基本原理纠错编码的基本原理 最小码距最小码距d0与检错纠错能力关系与检错纠错能力关系（3）先纠后检，纠检结合模式）先纠后检，纠检结合模式 为纠正为纠正 t 个误码个误码, 同时能检出同时能检出 e 个误码个误码, 要求最小码距要求最小码距 d0 t + e + 1 ( e t ) (11.2-4) 图图11-4 码距与检错纠错能力的关系码距与检错纠错能力的关系（c）纠检结合模式）纠检结合模式ABtet1d0第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章

24、 第九章东北大学网11.2 纠错编码的基本原理纠错编码的基本原理 最小码距最小码距d0与检错纠错能力关系与检错纠错能力关系(1)只检模式只检模式 由由d0 e + 1 , 可知系统的检错能力：最多可检出可知系统的检错能力：最多可检出6位误码。位误码。(2) 只纠模式只纠模式 由由d0 2t + 1 , 可知系统的纠错能力：最多可检出可知系统的纠错能力：最多可检出3位误码。位误码。(3) 纠检结合模式纠检结合模式 由由d0 t + e + 1 ( e t ) , 可知可知: 若先纠正若先纠正1位误码，则还可以检出位误码，则还可以检出5位以下的误码位以下的误码。举例举例 某差错控制编码系统，码组集

25、合的最小码距某差错控制编码系统，码组集合的最小码距d0 = 7 , 试试求该编码系统的检纠错能力。求该编码系统的检纠错能力。ABe6t3t =1e5t =2e4 若先纠正若先纠正2位误码，则还可以检出位误码，则还可以检出4位以下的误码位以下的误码。第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.2 纠错编码的基本原理纠错编码的基本原理 差错控制差错控制(纠错纠错)编码的效用编码的效用AB错错2位位错错5位位错错3位位错错4位位错错1位位错错6位位假设在随机信道中发送假设在随机信道中发送“0

26、”和和“1”时的出错概率相同，都等于时的出错概率相同，都等于Pe（ Pe 1），则容易证明，在长度为），则容易证明，在长度为n 的码组中恰好发生的码组中恰好发生r个个误码的概率为误码的概率为rernerernnPrnrnPPCrP)!( !)1 ()(11.2-5)例如，当码长例如，当码长 n =7 ，Pe = 10-3 时时 P7 ( 1 ) 710-3 P7 ( 2 ) 2.110-5 P7 ( 3 ) 3.510-8采用差错控制编码采用差错控制编码,即使即使仅能够检出或纠正仅能够检出或纠正12个误码，也能使误码率个误码，也能使误码率降低几个数量级。降低几个数量级。第十一章第十一章 差错控

27、制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.4 常用的简单编码常用的简单编码1. 奇偶监督码奇偶监督码 偶监督码偶监督码 信息位附加监督位后，码组中信息位附加监督位后，码组中“1”的个数为偶数的个数为偶数, 即满足即满足 an-1 an-2 a1 a0 = 0 (11.4-1)由由k = n-1个信息位个信息位 an-1 an-2 a1 和和 r = 1个监督位个监督位 a0 构成的总长度为构成的总长度为n=k+1的的 ( k+1, k ) 分组码。分组码。 奇监督码奇监督码 信息位附加监督位后，码组中信息位

28、附加监督位后，码组中“1”的个数为奇数的个数为奇数, 即满足即满足 an-1 an-2 a1 a0 = 1 (11.4-2)监督关系式监督关系式偶监督码偶监督码由已知信息位获得监督位的表示式为由已知信息位获得监督位的表示式为 a0 = an-1 an-2 a1奇监督码奇监督码由已知信息位获得监督位的表示式为由已知信息位获得监督位的表示式为 a0 = an-1 an-2 a1 1奇偶监督码奇偶监督码的编码效率的编码效率=(n-1)/n第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.4 常用的

29、简单编码常用的简单编码2. 二维奇偶监督码二维奇偶监督码 二维奇偶监督码有可能检测出偶数个错误二维奇偶监督码有可能检测出偶数个错误, 甚至可能纠正一甚至可能纠正一些错误。些错误。 二维奇偶监督码特别适合于检测突发性错误。二维奇偶监督码特别适合于检测突发性错误。 二维奇偶监督码的编码效率低于一维奇偶监督码。二维奇偶监督码的编码效率低于一维奇偶监督码。上例中，上例中，= m(n-1)/n(m+1) 二维奇偶监督码又二维奇偶监督码又称为方阵码。它是将上称为方阵码。它是将上述的述的m条偶或奇监督码条偶或奇监督码排成一个方阵，然后沿排成一个方阵，然后沿垂直方向加上垂直监督垂直方向加上垂直监督位构成。位构

30、成。a1n-1 a1n-2 a11 a10a2n-1 a2n-2 a21 a20amn-1 amn-2 am1 am0cn-1 cn-2 c1 c0信息位信息位m(n-1) 水平监督位水平监督位m1垂直垂直监督位监督位 1n第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网信息位信息位1 0 0 1 1 0 10 0 1 0 1 1 01 0 1 1 1 0 11 1 0 0 0 1 00 1 0 0 0 0 10 0 0 1 1 1 00 1 0 1 0 1 100000111.4 常用的简单编

31、码常用的简单编码2. 二维奇偶监督码二维奇偶监督码 0 水平监督位水平监督位垂直监督位垂直监督位 0 1 1 1 0 1 1 0 举例举例 本例中，信息位本例中，信息位 k = 77 = 49位，监督位位，监督位 r = 7+8 = 15位，位，编码效率编码效率 = 49/(49+15) = 49/64第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.4 常用的简单编码常用的简单编码3. 恒比码恒比码 (等重码等重码) 在全部码组集合中，在全部码组集合中，每条码组中包含每条码组中包含 “1”

32、 的数目相同的数目相同 。表表11-2 我国电传机数字代码我国电传机数字代码字符字符 保护电码保护电码 字符字符 保护电码保护电码 0 01101 5 00111 1 01011 6 10101 2 11001 7 11100 3 10110 8 01110 4 11010 9 10011 恒比码中无法清晰地将信息位与监督位分开。因此一般只恒比码中无法清晰地将信息位与监督位分开。因此一般只适用与传输电传机或键盘设备输入信息编码。恒比码不适合信适用与传输电传机或键盘设备输入信息编码。恒比码不适合信源随机信息的编码。源随机信息的编码。4. 正反码正反码 正反码中信息位数目和监督位数目相同。当信息位

33、中正反码中信息位数目和监督位数目相同。当信息位中“1”为奇数时，监督位与信息位相同为奇数时，监督位与信息位相同; 当信息位中当信息位中“1”为偶数时，为偶数时，监督位与信息位相反。正反码的编码效率监督位与信息位相反。正反码的编码效率= 1/2, 是具有是具有纠错纠错能力能力的编码。的编码。详见讲义（略）详见讲义（略）第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.5 线性分组码线性分组码前述的偶监督码，前述的偶监督码，n-1个信息位附加个信息位附加1个监督位，构成整个码组个监督位，构成整个

34、码组中中“1”的个数为偶数的个数为偶数, 唯一的监督关系满足唯一的监督关系满足 an-1 an-2 a1 a0 = 0在接收端，由收到整个码组在接收端，由收到整个码组an-1 an-2 a1 a0 ，计算，计算校正子校正子S S = an-1 an-2 a1 a0 (11.5-1)单个单个校正子校正子S的取值只有两种可能，的取值只有两种可能，“0”或或“1”。若。若S = 0, 表表示示“无错无错”, S = 1, 表示表示“有错有错”。无法确定误码的位置进行。无法确定误码的位置进行纠正。纠正。 增加监督位的数量，可以建立监督位和信息位关系（监督增加监督位的数量，可以建立监督位和信息位关系（监

35、督关系）的多个监督关系式。在接收端，由收到整个码组关系）的多个监督关系式。在接收端，由收到整个码组an-1 an-2 a1 a0 ，计算多个，计算多个校正子校正子S1、S2 、 Sr 。组合取值有组合取值有2r 种可能，一种表示种可能，一种表示“无错无错”, 其他其他2r -1种可以用来确定误码种可以用来确定误码的位置以进行纠正。的位置以进行纠正。第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.5 线性分组码线性分组码 若由信息位和监督位构成的整个码组的总长度若由信息位和监督位构成的整个码

36、组的总长度n满足满足 n 2r 1 或或 2r n + 1 = k + r + 1 (11.5-2)则除一种状态表示则除一种状态表示“无错无错”外，外，校正子校正子S1、S2 、 Sr 组合组合的其他的其他2r -1种状态种状态,至少可以确定长度为至少可以确定长度为n的码组中，一个单个的码组中，一个单个误码的位置。误码的位置。 若码组的总长度若码组的总长度n满足满足 n = 2r 1 或或 2r = n + 1这时这时r个个校正子校正子组合的组合的2r 种状态种状态,恰好可以表示出恰好可以表示出“无错无错”和和n位码组当中的位码组当中的1位误码位置。作为能够纠正位误码位置。作为能够纠正1位误码

37、的一种编码，位误码的一种编码，其编码效率是最高的其编码效率是最高的, 称为称为汉明汉明(Hamming)码码。能够纠正能够纠正1位误码的位误码的 (7,4)、(15,11)、(31,26)、(63,57)、. ，其编码效率在同码长的编码中都是最高的其编码效率在同码长的编码中都是最高的, 都是都是汉明码汉明码。第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.5 线性分组码线性分组码现在通过（现在通过（7, 4）分组码例子说明汉明码的监督关系式构造。）分组码例子说明汉明码的监督关系式构造。 信

38、息位信息位(k=4): a6 a5 a4 a3 监督位监督位(r=3) : a2 a1 a0 表表11-4 校正子与误码位置的对应关系校正子与误码位置的对应关系S1S2S3 误码位置误码位置 S1S2S3 误码位置误码位置 0 0 0 无错无错 0 1 1 a3 0 0 1 a0 1 0 1 a4 0 1 0 a1 1 1 0 a5 1 0 0 a2 1 1 1 a6 可以看出，仅当可以看出，仅当1位误码位置在位误码位置在a2 、a4 、a5或或a6时，校正子时，校正子S1为为1；否则；否则S1为为0。这意味着。这意味着a2 、a4 、a5、a6 4个码元构成偶监个码元构成偶监督关系督关系 S

39、1 = a6 a5 a4 a2 (11.5-3)第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网同理可得到关于同理可得到关于S2、S3的偶监督关系，有的偶监督关系，有 S1 = a6 a5 a4 a2 (11.5-3) S2 = a6 a5 a3 a1 (11.5-4) S3 = a6 a4 a3 a0 (11.5-5)11.5 线性分组码线性分组码 表表11-4 校正子与误码位置的对应关系校正子与误码位置的对应关系S1S2S3 误码位置误码位置 S1S2S3 误码位置误码位置 0 0 0 无错

40、无错 0 1 1 a3 0 0 1 a0 1 0 1 a4 0 1 0 a1 1 1 0 a5 1 0 0 a2 1 1 1 a6编码时，给信息位加入监督位应使得编码时，给信息位加入监督位应使得S1 = S2 = S3 = 0，即满足，即满足 a6 a5 a4 a2 = 0 a6 a5 a3 a1 = 0 (11.5-6) a6 a4 a3 a0 = 0第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.5 线性分组码线性分组码由监督关系式（方程组）由监督关系式（方程组） a6 a5 a4 a

41、2 = 0 a6 a5 a3 a1 = 0 (11.5-6) a6 a4 a3 a0 = 0整理可得到已知信息位求监督位的关系式整理可得到已知信息位求监督位的关系式 a2 = a6 a5 a4 a1 = a6 a5 a3 (11.5-7) a0 = a6 a4 a3 对于信息位对于信息位 k=4 情况，共有情况，共有 24=16 种信息码组合，由式种信息码组合，由式(11.5-7)求出每种信息组合所附加的监督位，进而得到全部求出每种信息组合所附加的监督位，进而得到全部 24=16 条条完整码组，如表完整码组，如表11-5（书表（书表114）所示。）所示。表表11-5 前例前例 (7,4) 汉明

42、码的全部码组汉明码的全部码组 (略略)第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网例如：接收到码组例如：接收到码组“0000011”,该码组该码组确实确实是表是表11-5中某码组中某码组传输中产生了传输中产生了1位误码所致。由式位误码所致。由式(11.5-3) 、(11.5-4) 和和(11.5-5) 分别计算分别计算3个校正子，有个校正子，有 S1 = a6 a5 a4 a2 = 0 0 0 0 = 0 S2 = a6 a5 a3 a1 = 0 0 0 1 = 1 S3 = a6 a4 a

43、3 a0 = 0 0 0 1 = 1根据表根据表11-4 校正子与误码位置对应关系，可以确定校正子与误码位置对应关系，可以确定1位误码的位误码的位置在位置在a3 处，正确的码组应该为处，正确的码组应该为“0001011”，它就是表，它就是表11-5中中的第的第2条码组。条码组。11.5 线性分组码线性分组码 表表11-4 校正子与误码位置对应关系校正子与误码位置对应关系S1S2S3 误码位置误码位置 S1S2S3 误码位置误码位置 0 0 0 无错无错 0 1 1 a3 0 0 1 a0 1 0 1 a4 0 1 0 a1 1 1 0 a5 1 0 0 a2 1 1 1 a6如果如果 1 条码

44、组在传输过程中条码组在传输过程中确实产生了确实产生了 1 位错误，前述位错误，前述的的(7,4)汉明码就能无误地指汉明码就能无误地指出误码位置以进行纠正。出误码位置以进行纠正。第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.5 线性分组码线性分组码从表从表11-5 (7,4) 汉明码的全部码组可以看到，这种码的最小码汉明码的全部码组可以看到，这种码的最小码距距 (数值上和非全零码的最小码重相等数值上和非全零码的最小码重相等) d0=3，用于检错可检，用于检错可检测出测出 e=2 位以下的误

45、码，用于纠错只可纠正位以下的误码，用于纠错只可纠正 t=1 位误码位误码 。这。这种码的编码效率种码的编码效率= k/n = 4/7。汉明码汉明码是能够纠正是能够纠正1位误码，其编码效率在同码长的编码中是位误码，其编码效率在同码长的编码中是最高的。具有最高的。具有1位误码纠正能力的位误码纠正能力的 (7,4)、(15,11)、(31,26)、(63,57)、. 都是都是汉明码汉明码。汉明码的编码效率随着码组总长。汉明码的编码效率随着码组总长 n 的增加而增加。因为码组越长，信息位所占比例越大，监的增加而增加。因为码组越长，信息位所占比例越大，监督位所占比例越小。督位所占比例越小。 当码长当码长

46、n很大时，编码效率接近于很大时，编码效率接近于1。nnnrnnk) 1(log12汉明码汉明码 2r=n+1第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.5 线性分组码线性分组码改写监督关系式（方程组）改写监督关系式（方程组） a6 a5 a4 a2 = 0 a6 a5 a3 a1 = 0 (11.5-6) a6 a4 a3 a0 = 0为为 1a6 + 1a5 + 1a4 + 0a3 + 1a2 + 0a1 + 0a0 = 0 1a6 + 1a5 + 0a4 + 1a3 + 0a2 +

47、 1a1 + 0a0 = 0 (11.5-8) 1a6 + 0a5 + 1a4 + 1a3 + 0a2 + 0a1 + 1a0 = 0为简化将为简化将“ ”改写改写为为“+”, 均表示模均表示模2加。加。并可表示为矩阵形式并可表示为矩阵形式 111010011010101011001a6 a5a4a3 a2 a1a0000(11.5-9)简记为简记为H AT=OT 或或 A HT=O(11.5-10)rn监督矩阵监督矩阵a6 a5 a4 a3 a2 a1 a01n码组向量码组向量 0 0 0 1r零向量零向量第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第

48、三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.5 线性分组码线性分组码 式式(11.5-9)中的中的监督矩阵监督矩阵是一个是一个 r行行n列列的矩阵，内容可的矩阵，内容可以分为两部分以分为两部分其中其中P为为 rk 阶矩阵，阶矩阵，Ir为为 r r 阶单位矩阵。具有阶单位矩阵。具有PIr形式形式的监督矩阵称为的监督矩阵称为典型监督矩阵典型监督矩阵。(11.5-11)111010011010101011001PIr H1110 1001101 0101011 001 式式(11.5-7)改写可得到已知信息位改写可得到已知信息位a6 a5 a4 a3 求监督位求监督位a2 a

49、1 a0的矩阵关系式的矩阵关系式a2 a1a0111011011011a6 a5a4a3或或(11.5-12)(11.5-13)a2a1a0a6a5a4a3111110101011Prk Qkr其其Q为为 kr 阶阶, 它是它是 P 的转置矩阵的转置矩阵Q = PT (11.5-14)第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.5 线性分组码线性分组码对已知信息位对已知信息位a6 a5 a4 a3 求监督位求监督位a2 a1 a0的关系的关系(11.5-7)扩充，变扩充，变为已知信息位

50、为已知信息位a6 a5 a4 a3 求整个码组求整个码组a6 a5 a4 a3 a2 a1 a0的关系式的关系式a2 = a6 a5 a4 a1 = a6 a5 a3a0 = a6 a4 a3a6 = a6a5 = a5a4 = a4 a3 = a3矩阵形式矩阵形式a6 a5a4a3a6 a5a4a3a2 a1a01000010000100001111011011011简记为简记为 A=a6 a5 a4 a3 G (11.5-17)G10001110100110001010100010111000 1110100 1100010 1010001 011IkQ(11.5-15)GTkk 阶单位矩

51、阵阶单位矩阵Ikkr阶矩阵阶矩阵Q典型典型生成生成矩阵矩阵生成矩阵生成矩阵第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.5 线性分组码线性分组码 线性分组码具有封闭性。它是指一种线性分组码的任意两线性分组码具有封闭性。它是指一种线性分组码的任意两条合法码组相异或，得到的结果仍然是该线性分组码的一条合条合法码组相异或，得到的结果仍然是该线性分组码的一条合法码组。法码组。 线性分组码的两个重要性质线性分组码的两个重要性质 线性分组码的最小码重（全零码除外），就是该线性分组线性分组码的最小码重

52、（全零码除外），就是该线性分组码的最小码距。这是因为，任一码组中码的最小码距。这是因为，任一码组中“1”的个数（码重），的个数（码重），都是某两条码组不相同位的数目（码距）。都是某两条码组不相同位的数目（码距）。性质性质1（线性分组码的封闭性）（线性分组码的封闭性）给我们提供了利用某些已知码给我们提供了利用某些已知码组获得一些未知码组的一条可组获得一些未知码组的一条可能的途径。能的途径。性质性质2（最小码距（最小码距=最小码重）最小码重）给我们提供了从码组获得最小给我们提供了从码组获得最小码距，并判断检错纠错能力的码距，并判断检错纠错能力的便捷方法。便捷方法。第十一章第十一章 差错控制编码差错

53、控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.6 循环码循环码 循环码循环码是一种简单、重要、常用的线性分组码。除了具有是一种简单、重要、常用的线性分组码。除了具有线性分组码的一般性质外，还具有循环性，即码组集合中任一线性分组码的一般性质外，还具有循环性，即码组集合中任一码组循环左移或右移若干位，得到的结果仍然为该码组集合中码组循环左移或右移若干位，得到的结果仍然为该码组集合中的一条合法码组。的一条合法码组。11.6.1 循环码原理循环码原理 表表11-6 (7, 3)循环码举例循环码举例 码组码组 信息位信息位 监督位

54、监督位 编号编号 a6 a5 a4 a3 a2 a1 a0 1 0 0 0 0 0 0 0 2 0 0 1 0 1 1 1 3 0 1 0 1 1 1 0 4 0 1 1 1 0 0 1 5 1 0 0 1 0 1 1 6 1 0 1 1 1 0 0 7 1 1 0 0 1 0 1 8 1 1 1 0 0 1 0循环循环m位位循环左移循环左移3位位循环左移循环左移2位位本例中，只要知道本例中，只要知道一条非全零码组一条非全零码组,通通过移位就可求出全过移位就可求出全部码组。部码组。循环右移循环右移3位位第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章

55、第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.6 循环码循环码 码的多项式表示码的多项式表示 对于码组对于码组an-1 an-2 a1 a0 ，若将各码元作为多项式系数，若将各码元作为多项式系数，则可得到码组的多项式表示则可得到码组的多项式表示 T(x) = an-1 xn-1 + an-2 xn-2 + + a1 x + a0 (11.6-1)对于前例的对于前例的 (7, 3)码码, 任一码组都可表示为任一码组都可表示为 T(x) = a6 x6 + a5 x5 + a4 x4 + a3 x3 + a2 x2 + a1 x + a0 (11.6-2)而其中的第而其中的第7条码

56、组条码组“1 1 0 0 1 0 1”可表示为多项式可表示为多项式 T7 (x) = x6 + x5 + x2 + 1 (11.6-3)11.6.1 循环码原理循环码原理对于码长为对于码长为n的码组，码多的码组，码多项式的最高次数为项式的最高次数为xn-1 。多项式系数取值是模多项式系数取值是模2的，的，即只能是即只能是“1”或或“0”。第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.6 循环码循环码11.6.1 循环码原理循环码原理1. 码多项式的按模运算码多项式的按模运算 如整数的按模

57、运算如整数的按模运算 对整数对整数m按模按模n运算运算, 将整数将整数m除以整数除以整数n, 商为整数商为整数Q, 余数余数为为p ( p n ), 即即我们说整数我们说整数m按模按模n运算之结果为运算之结果为 m p (模模n)npnpQnm,(11.6-4)(11.6-5) 多项式的按模运算多项式的按模运算 对任意多项式对任意多项式F(x)被另一个被另一个n次多项式次多项式N(x) 除，得到一商式除，得到一商式Q(x)和一个次数小于和一个次数小于n的余式的余式R(x) , 即即 F(x) = N(x) Q(x) + R(x) 我们说多项式我们说多项式F(x) 按模按模N(x) 运算之结果为

58、运算之结果为 F(x) R(x) (模模N(x)(11.6-6)(11.6-7)第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章东北大学网11.6 循环码循环码11.6.1 循环码原理循环码原理1. 码多项式的按模运算码多项式的按模运算 多项式的按模运算多项式的按模运算例例 x3 按模按模 (x3+1)运算，结果为运算，结果为 x3 1 (模模 x3+1) x4 + x2 +1 按模按模 (x3+1)运算，结果为运算，结果为 x4 + x2 +1 x2 + x +1 (模模 x3+1)(11.6-6)(1

59、1.6-7)x3+1x4 + x2 +1xx4 + xx2 + x +1注意注意: 多项式系数是模多项式系数是模2的的,取取值只能是值只能是“1”或或“0” , 这也是这也是余式为余式为x2 + x +1 ,而不为而不为 x2 - x +1 的原因。的原因。重要结论重要结论: 在循环码中，若在循环码中，若 T(x) 是一个长度为是一个长度为 n 的码组，则的码组，则xi T(x) 在按模在按模 xn+1 运算下，也是该循环码的一个许用码组。运算下，也是该循环码的一个许用码组。第十一章第十一章 差错控制编码差错控制编码通信原理通信原理内容简介 第一章 第二章 第三章 第四章 第五章 第六章 第七

60、章 第八章 第九章东北大学网11.6 循环码循环码11.6.1 循环码原理循环码原理1. 码多项式的按模运算码多项式的按模运算重要结论重要结论: 在循环码中，若在循环码中，若 T(x) 是一个长度为是一个长度为 n 的码组，则的码组，则xi T(x) 在按模在按模 xn+1 运算下，也是该循环码的一个许用码组。运算下，也是该循环码的一个许用码组。证明详见讲义。证明详见讲义。举例举例 T(x)= x 4 + x2 + x + 1 是一个长度为是一个长度为 7 的合法码组的合法码组, 可可以证明以证明 T (x) = x 3 T(x) = x7 + x5 + x4 + x3 按模按模 x7 +1运