信息基础与编码理论 第九章

1、信息论与编码信息论与编码Information Theory & Coding 第九章第九章 差错控制差错控制 9.1 9.1 差错控制系统及其理论基础差错控制系统及其理论基础（1）差错产生的原因和差错类型）差错产生的原因和差错类型 差错产生的原因差错产生的原因 ：由于通信线路上总有噪声存在，有用：由于通信线路上总有噪声存在，有用信息在噪声的作用下就会出现信息在噪声的作用下就会出现传输差错传输差错 通过通信信通过通信信道后接收的数据与发送数据不一致。道后接收的数据与发送数据不一致。 差错类型差错类型 ：两类不同的噪声引发不同的差错：两类不同的噪声引发不同的差错 a）随机差错随机差错：由

2、：由热噪声热噪声引起，某个码元的出错具有独立引起，某个码元的出错具有独立性，与前后码元无关。性，与前后码元无关。 b）突发差错突发差错：由由冲击噪声冲击噪声引起，而引起，而 冲击噪声是由短暂冲击噪声是由短暂原因造成的，如电机的启动、停止，电器设备的放弧等。原因造成的，如电机的启动、停止，电器设备的放弧等。突发差错是成群的，其差错持续时间称为突发差错是成群的，其差错持续时间称为突发差错的长突发差错的长度度。（2 2）传输差错产生的过程）传输差错产生的过程 图图9-1 传输差错产生过程传输差错产生过程（3 3）差错控制机制）差错控制机制 差错控制机制分类：反馈纠错，前向纠错，及所派生出的差错控制机

3、制分类：反馈纠错，前向纠错，及所派生出的混合纠错。混合纠错。 a a）反馈纠错）反馈纠错 发信端采用某种能发现一定程度传输差错的简单编码发信端采用某种能发现一定程度传输差错的简单编码方法对所传信息加入少量监督码元进行编码，在接收端则方法对所传信息加入少量监督码元进行编码，在接收端则根据编码规则对收到的编码信号进行检查，根据编码规则对收到的编码信号进行检查，当检测出错码当检测出错码时，即向发信端发出询问的信号，要求重发时，即向发信端发出询问的信号，要求重发。发信端收到。发信端收到询问信号时，立即重发已发生传输差错的那部分信息，直询问信号时，立即重发已发生传输差错的那部分信息，直到正确收到为止。到

4、正确收到为止。 发现差错发现差错：在若干接收码元中，知道有一个或一些是：在若干接收码元中，知道有一个或一些是错的，但不一定知道错误的准确位置。错的，但不一定知道错误的准确位置。 优点：优点：纠错能力强，检错能力与信道干扰变化无关，编纠错能力强，检错能力与信道干扰变化无关，编 译码器简单。译码器简单。 缺点：缺点：必须有反向信道；收发双方必须互相配合，实必须有反向信道；收发双方必须互相配合，实时性较差。时性较差。b)b)前向纠错前向纠错 发信端采用某种在解码时能纠正一定程度传输差错的发信端采用某种在解码时能纠正一定程度传输差错的较复杂的编码方法，使接收端在收到信码时不仅能发现较复杂的编码方法，使

5、接收端在收到信码时不仅能发现错码，还能纠正错码。错码，还能纠正错码。优点：优点：不需要反馈信道，也无需反复重发而延误传输时不需要反馈信道，也无需反复重发而延误传输时 间，对实时传输有利。间，对实时传输有利。缺点：缺点：纠错设备比较复杂。纠错设备比较复杂。 c)c)混合纠错混合纠错 混合纠错是前向纠错和反馈纠错两种方式的混合。混合纠错是前向纠错和反馈纠错两种方式的混合。 少量纠错在接收端自动纠正，差错较严重，超出自少量纠错在接收端自动纠正，差错较严重，超出自行纠正能力时，就向发信端发出询问信号，要求重发。行纠正能力时，就向发信端发出询问信号，要求重发。 对于不同类型的信道，应采用不同的差错控制技

6、术，否对于不同类型的信道，应采用不同的差错控制技术，否则将事倍功半。则将事倍功半。 反馈纠错可用于双向数据通信，前向纠错则用于单向数反馈纠错可用于双向数据通信，前向纠错则用于单向数字信号的传输，例如广播数字电视系统，因为这种系统没字信号的传输，例如广播数字电视系统，因为这种系统没有反馈通道。有反馈通道。图图9-2 反馈重发纠错机制反馈重发纠错机制通常采用通常采用反馈重发纠错反馈重发纠错实现机制，如下图所示：实现机制，如下图所示：反馈重发机制的分类：反馈重发机制的分类：停止等待方式和连续工作方式；其中停止等待方式和连续工作方式；其中连续工作方式又可分为拉回方式和选择重发方式。具体如下连续工作方式

7、又可分为拉回方式和选择重发方式。具体如下图所示：图所示： 图图9-3 等待停止方式的工作过程等待停止方式的工作过程ACKACK：确认信号；：确认信号；NAKNAK：非确认信号：非确认信号图图 9-4 拉回方式的工作过程拉回方式的工作过程图图 9-5 选择重发方式的工作过程选择重发方式的工作过程（4 4）误码控制基本原理）误码控制基本原理 为了使信源代码具有检错和纠错能力，应当按一定的为了使信源代码具有检错和纠错能力，应当按一定的规则在信源编码的基础上增加一些冗余码元规则在信源编码的基础上增加一些冗余码元( (监督码监督码) )，使，使这些冗余码元与被传送信息码元之间建立一定的关系，发这些冗余码

8、元与被传送信息码元之间建立一定的关系，发信端完成这个任务的过程称为信端完成这个任务的过程称为误码控制编码误码控制编码。 在收信端，根据信息码元与监督码元的特定关系，实在收信端，根据信息码元与监督码元的特定关系，实现检错或纠错，输出原信息码元，完成这个任务的过程称现检错或纠错，输出原信息码元，完成这个任务的过程称误码控制译码误码控制译码( (或解码或解码) )。 注：无论检错和纠错，都有一定的误差范围。注：无论检错和纠错，都有一定的误差范围。 9.2 9.2 纠错编码的基本概念及其本质纠错编码的基本概念及其本质（1 1）差错控制码的分类）差错控制码的分类 a a）按照误码控制的不同功能）按照误码

9、控制的不同功能 检错码：检错码：仅具备识别错码功能仅具备识别错码功能 而无纠正错码功能。而无纠正错码功能。 纠错码：纠错码：不仅具备识别错码功能，同时具备纠正错码不仅具备识别错码功能，同时具备纠正错码功能。功能。 纠删码：纠删码：不仅具备识别错码和纠正错码的功能，而且不仅具备识别错码和纠正错码的功能，而且当错码超过纠正范围时可把无法纠错的信息删除。当错码超过纠正范围时可把无法纠错的信息删除。 b b）按照误码产生的原因不同）按照误码产生的原因不同 纠正随机错误的码：纠正随机错误的码：主要用于产生独立的局部误码的信主要用于产生独立的局部误码的信道。道。 纠正突发性错误的码：纠正突发性错误的码：主

10、要用于产生大面积的连续误码主要用于产生大面积的连续误码的情况，如磁带数码记录中磁粉脱落而发生的信息丢失。的情况，如磁带数码记录中磁粉脱落而发生的信息丢失。 c c）按照信息码元与附加的监督码元之间的检验关系）按照信息码元与附加的监督码元之间的检验关系 线性码线性码：若两者呈线性关系，即满足一组线性方程：若两者呈线性关系，即满足一组线性方程 式，称为线性码。式，称为线性码。 非线性码：非线性码：两者关系不能用线性方程式来描述，称为两者关系不能用线性方程式来描述，称为非线性码。非线性码。 d d）按照信息码元与监督附加码元之间的约束方式之不同）按照信息码元与监督附加码元之间的约束方式之不同 分组码

11、：分组码：编码后的码元序列每编码后的码元序列每n n位分为一组，其中包括位分为一组，其中包括k k位信息码元和位信息码元和r r位附加监督码元，即位附加监督码元，即n=k+r n=k+r ，每组的，每组的监督码元仅与本组的信息码元有关，而与其他组的信监督码元仅与本组的信息码元有关，而与其他组的信息码元无关。息码元无关。 卷积码：卷积码：编码后码元序列也划分为码组，但每组的监编码后码元序列也划分为码组，但每组的监督码元不但与本组的信息码元有关，而且与前面码组督码元不但与本组的信息码元有关，而且与前面码组的信息码元也有约束关系。的信息码元也有约束关系。e e）按照信息码元在编码之后是否保持原来的形

12、式不变按照信息码元在编码之后是否保持原来的形式不变 系统码：系统码：编码后的信息码元序列保持原样不变。编码后的信息码元序列保持原样不变。 非系统码：非系统码：信息码元会改变其原有的信号序列。由于信息码元会改变其原有的信号序列。由于原有码位发生了变化，使译码电路更为复杂，故较少选原有码位发生了变化，使译码电路更为复杂，故较少选用。用。 根据编码过程中所选用的数字函数式或信息码元特根据编码过程中所选用的数字函数式或信息码元特性的不同，又包括多种编码方式。对于某种具体的数字性的不同，又包括多种编码方式。对于某种具体的数字设备，为了提高检错、纠错能力，通常同时选用几种误设备，为了提高检错、纠错能力，通

13、常同时选用几种误码控制编码方式。码控制编码方式。 （2 2）有关差错控制编码的几个基本概念）有关差错控制编码的几个基本概念a)a)信息码元与监督码元信息码元与监督码元 信息码元信息码元（信息序列或信息位）：发端由信源编码（信息序列或信息位）：发端由信源编码后得到的被传送的信息数据比特，用后得到的被传送的信息数据比特，用k k表示信息码元的表示信息码元的个数。个数。 在二元码情况下，每个信息码元的取值只有在二元码情况下，每个信息码元的取值只有0 0或或1 1，故故k k位长的信息码组数共有位长的信息码组数共有 个。个。 监督码元监督码元（监督位或附加数据比特）：为了检纠错（监督位或附加数据比特）

14、：为了检纠错而在信道编码时加入的判断数据位而在信道编码时加入的判断数据位 。用。用r r表示监督码元表示监督码元的个数，对于长度为的个数，对于长度为n n的码字，有：的码字，有：n=k+rn=k+r或或r=nr=nk k K个信息码元序列个信息码元序列 | r个监督码元个监督码元2kr个监督码元个监督码元 | K个信息码元序列个信息码元序列 经过分组编码后的码又称为经过分组编码后的码又称为(n,k)(n,k)码码，即表示总码长，即表示总码长为为n n位，其中信息码长位，其中信息码长( (码元数码元数) )为为k k位，位， 监督码长监督码长( (码元码元数数) )为为r=nr=nk k。通常称

15、其为长为。通常称其为长为n n的码字的码字( (码组、码矢码组、码矢) )。b)b)许用码字和禁用码字许用码字和禁用码字 n n个的码元能组成的码字为：个的码元能组成的码字为：N=N=q q n n 个，源数据按个，源数据按k k个个信息位组成的不同信息组有信息位组成的不同信息组有: M=: M=q q k k 个。个。 组码字中与信源符号组对应的组码字中与信源符号组对应的 q q k k 个码字称为个码字称为许用许用码字码字 。这。这 q q k k 个码字集合记为个码字集合记为C C ，表示为：，表示为： C Ci i=( =( c ci i 1 1 , , c ci i 2 2 , ,

16、, , c ci n i n ) ) i i=1 , 2 , , M=1 , 2 , , M（其（其中中c ci i 1 1 , , c ci i 2 2 , , , , c ci n i n 为码元为码元 , , n n为码字的长度为码字的长度 ） 而其余而其余q q n n - - q q k k 个码字称为个码字称为禁用码字禁用码字。发端误码控制编码的任务发端误码控制编码的任务：寻求某种规则从总码组：寻求某种规则从总码组( ( 2 2n n ) )中选出许用码组；中选出许用码组；收端译码的收端译码的 任务：任务：利用相应的规则来判断及校正收到的利用相应的规则来判断及校正收到的码字符合许用

17、码组。码字符合许用码组。 c)c) 汉明重量汉明重量：码码 C 的一个码字的一个码字C i中非零码元的个数称为中非零码元的个数称为码字码字C i 的的Hamming重量（码重）重量（码重）, 记为记为W(C i) . 码字的最小重量：码字的最小重量：( (n n , ,k k) )码码 C C中所有非零码字的中所有非零码字的HammingHamming重量的最小值称为码重量的最小值称为码 C C 的最小的最小HammingHamming重量重量 , , 或码或码C C最小最小重量记为重量记为W Wmin min 。minmin()iWW C推论推论 设设C Ci i , ,C Cj j 为二元

18、分组码为二元分组码C C的任意两个码字的任意两个码字 , , 则则 W(CW(Ci i + C + Cj j ) ) = = d (d (C Ci i , , C Cj j ) )。 证明：证明：C Ci i , ,C Cj j 的对应码元相同时的对应码元相同时, ,则则C Ci i + + C Cj j 对应的码元为对应的码元为0 0； C Ci i , ,C Cj j 的对应码元不同时的对应码元不同时, ,则则 C Ci i + + C Cj j 对应的码元为对应的码元为1 1 ；则；则 W W( (C Ci i + + C Cj j ) ) 为为C Ci i 和和 C Cj j 的对应码

19、元不同的个数的对应码元不同的个数 , ,而而d d ( (C Ci i , , C Cj j ) ) 为为C Ci i , , C Cj j 的对应码元不同的个数的对应码元不同的个数 , , 故推论成立。故推论成立。定理定理 二元二元( n , k )线性分组码线性分组码C的最小距离等于其最小重量的最小距离等于其最小重量。 证明证明 ： 设设C 中的任意两个码字中的任意两个码字 Ci , Cj , 且且Ci Cj 则则 Cs= Ci + Cj 是非零码字是非零码字 , 同时是码同时是码 C 的码字的码字 又因为又因为W(Ci + Cj ) = W (Cs ) =d (Ci , Cj ) , 因

20、此因此 Wmin =d min 结论结论: 二元线性分组码二元线性分组码 C 的最小重量的最小重量 , 即非零码字即非零码字“1”的个的个数数 最少的码字决定了码最少的码字决定了码 C 的检错或纠错能力。的检错或纠错能力。d d）编码效率（码字效率）：）编码效率（码字效率）： 信息位在码字中所占的比例，信息位在码字中所占的比例，用用R R表示，是衡量分组码有效性的一个基本参数。表示，是衡量分组码有效性的一个基本参数。 对于分组码：对于分组码： R= k/nR= k/ne e）纠错码的基本任务：）纠错码的基本任务：构造出当构造出当R R 一定一定 , , 使得使得d d minmin 尽可尽可能

21、大的码能大的码 ；或；或 d d min min 一定一定, , R R 尽可能高的码尽可能高的码 。 9.3 9.3 纠错编码方法的性能评价纠错编码方法的性能评价将二进制源数据码流经过如下几种处理将二进制源数据码流经过如下几种处理( (编码编码) )后后, , 在在BSCBSC信道信道中传输中传输 。（1 1）不编码：）不编码：若其中有码元若其中有码元“0”0”错成错成“1”1”或或“1”1”错成错成“0”,0”, 接收端都无法检查出其错误接收端都无法检查出其错误 。（2 2） 将码流中的码元将码流中的码元“0” (00) , “1” (11)0” (00) , “1” (11) 无论若无论

22、若(00)(00)或或(11)(11)错成错成(01)(01)或或(10) , (10) , 则接收端能检查出其则接收端能检查出其错误错误 ; ; 但不能确定是但不能确定是(00)(00)还是还是(11)(11)，若若(00)错成错成(11) 或或 (11)错错成成(00) , 则接收端无法检出其错误则接收端无法检出其错误 . 结论结论:最小最小 码距为码距为1，无法检纠其错误；最小码距为，无法检纠其错误；最小码距为2时，时， 能检测能检测1个随机错误，不能纠正随机错误。个随机错误，不能纠正随机错误。 （3 3） 将码流中的码元将码流中的码元“0” (000) , “1” (111)0” (0

23、00) , “1” (111) 无论无论(000)(000)或或(111)(111)传输后有一个错误或有两个错误传输后有一个错误或有两个错误 , , 接收端能检测其错误接收端能检测其错误 ; ; 若若 (000) (000) 、(111) (111) 传输后只有一个错误传输后只有一个错误 , , 则接收端可则接收端可将将(001) (001) 、(010) (010) 、(100)(100)译码为译码为(000) ;(000) ;将将(011) (011) 、(101) (101) 、(110)(110)译码为译码为(111) (111) ； 若若 (000) (000) 、(111) (11

24、1) 传输后有两个以上错误传输后有两个以上错误 , , 则接收端则接收端无法将无法将 (011) (011) 、(101) (101) 、(110)(110)正确地译码正确地译码 ； 若传输后若传输后(000)(000)错成错成(111)(111)或或(111)(111)错成错成(000) ,(000) ,则接收端则接收端无法检测其错误无法检测其错误 。 结论结论: : 最小码距为最小码距为3 3时，能检测时，能检测2 2个随机错误个随机错误 , , 能纠正能纠正1 1个随机错误。个随机错误。 推荐给你看，http:/ 小结：小结：以上使用的编码方式为以上使用的编码方式为重复码重复码 。 （1

25、 1）最小码距）最小码距d=n d=n ，随着，随着n n的增大，抗干扰能力越来越的增大，抗干扰能力越来越强，但强，但 R=1/n R=1/n 随之下降，编码效率越来越低。随之下降，编码效率越来越低。（2 2）检错能力大于或等于纠错能力；距离）检错能力大于或等于纠错能力；距离d d越大，纠错越大，纠错能力越强。能力越强。（3 3）分组编码最小码距与检纠错能力的关系：）分组编码最小码距与检纠错能力的关系： 在一个码组内为了检测在一个码组内为了检测e e个误码，要求最小码距应个误码，要求最小码距应满足：满足：dede1 1 在一个码组内为了纠正在一个码组内为了纠正t t个误码，要求最小码距应个误码

26、，要求最小码距应满足：满足： d2td2t1 1 在一个码组内为了纠正在一个码组内为了纠正t t个误码，同时能检测个误码，同时能检测e e个误个误码码(e(et)t)，要求最小码距应满足：，要求最小码距应满足：dedet t1 1 9.4 9.4 纠错编码方式简介纠错编码方式简介 （1 1）奇偶监督码）奇偶监督码奇奇- -偶校验码（奇偶监督码），一种最简单的线性分组偶校验码（奇偶监督码），一种最简单的线性分组检错编码方式。检错编码方式。 编码方法：编码方法： 把信源编码后的信息数据流分成等长码组。把信源编码后的信息数据流分成等长码组。 在每一信息码组之后加入一位在每一信息码组之后加入一位(1(

27、1比特比特) )监督码元作监督码元作为奇偶检验位。为奇偶检验位。 使得总码长使得总码长n(n(包括信息位包括信息位k k和监督位和监督位1)1)中的码重为中的码重为偶数偶数( (称为称为偶校验码偶校验码) )或为奇数或为奇数 ( (称为称为奇校验码奇校验码) )。 校验：如果在传输过程中任何一个码组发生一位校验：如果在传输过程中任何一个码组发生一位( (或奇数位或奇数位) )错误，则收到的码组必然不再符合奇偶校验错误，则收到的码组必然不再符合奇偶校验的规律，因此可以发现误码。的规律，因此可以发现误码。 奇校验和偶校验两者具有完全相同的工作原理和检奇校验和偶校验两者具有完全相同的工作原理和检错能

28、力，原则上采用任一种都是可以的。错能力，原则上采用任一种都是可以的。 由于每两个由于每两个1 1的模的模2 2相加为相加为0 0，故利用模，故利用模2 2加法可以判断一个加法可以判断一个码组中码重是奇数或是偶数。模码组中码重是奇数或是偶数。模2 2加法等同于加法等同于“异或异或”运算。运算。现以偶监督为例。现以偶监督为例。 对于偶校验，应满足对于偶校验，应满足故监督位码元故监督位码元 C C0 0 可由下式求出：可由下式求出： 奇偶校验编码只能检出单个或奇数个误码，而无法检知偶奇偶校验编码只能检出单个或奇数个误码，而无法检知偶数个误码，对于连续多位的突发性误码也不能检知，故检错数个误码，对于连续多位的突发性误码也不能检知，故检错能力有限，另外，该编码后码组的最小码距为能力有限，另外，该编码后码组的最小码距为 d =2d =2，故