第九章 纠错编码1

1、第九章第九章 纠错编码纠错编码1 1 纠错码的分类纠错码的分类2 2 纠错码的基本概念纠错码的基本概念 3 3 线性分组码线性分组码 4 4 汉明码汉明码 5 5 循环码循环码l 香农第二定理证明，当香农第二定理证明，当 时时 的码存在。的码存在。l 证明过程采用的是随机编码的方法：证明过程采用的是随机编码的方法：随机编码所得的码集很大，通过搜索得到好码的方法在实随机编码所得的码集很大，通过搜索得到好码的方法在实际上很难实现；际上很难实现；即时找到了好码，这种码的码字也没有规律，不便于译码。即时找到了好码，这种码的码字也没有规律，不便于译码。l 真正实用的信道编码方法还需要通过各种数学工具真正

2、实用的信道编码方法还需要通过各种数学工具来构造，使码具有好的结构性以便于译码。来构造，使码具有好的结构性以便于译码。RC0EP l 纠错编码的纠错编码的基本思路基本思路： 根据一定的规律在待发送的信息码元中人为的加根据一定的规律在待发送的信息码元中人为的加入一些冗余码元，这些冗余码元与信息码元之间以某入一些冗余码元，这些冗余码元与信息码元之间以某种确定的规则相互关联（约束）。种确定的规则相互关联（约束）。 在接收端按照既定的规则检验信息码元与监督码在接收端按照既定的规则检验信息码元与监督码元之间的关系。如果传输过程出错，则信息码元与监元之间的关系。如果传输过程出错，则信息码元与监督码元之间的关

3、系将受到破坏，从而可以发现错误乃督码元之间的关系将受到破坏，从而可以发现错误乃至纠正错误。至纠正错误。概述概述干扰一般分为两种形式：干扰一般分为两种形式：一是随机噪声，它主要来源于设备的热噪声和散弹一是随机噪声，它主要来源于设备的热噪声和散弹噪声以及传播媒介的热噪声，它是通信系统中的主噪声以及传播媒介的热噪声，它是通信系统中的主要噪声；要噪声；二是脉冲干扰和信道衰落，它的特点是突发出现，二是脉冲干扰和信道衰落，它的特点是突发出现，主要来源于雷电、通电开关、负荷突变或设备故障主要来源于雷电、通电开关、负荷突变或设备故障等。等。 概述概述信道可分为三类：信道可分为三类：1. 只产生随机错误的信道称

4、为随机信道。比如卫星信道、只产生随机错误的信道称为随机信道。比如卫星信道、同轴电缆、光缆信道以及大多数微波中继信道。同轴电缆、光缆信道以及大多数微波中继信道。2. 产生突发错误的信道称为突发信道。实际的短波信道、产生突发错误的信道称为突发信道。实际的短波信道、移动通信信道、由于差伤造成成串差错的光盘和磁盘，均移动通信信道、由于差伤造成成串差错的光盘和磁盘，均为这一类信道。为这一类信道。3. 有些实际信道既有随机错误又有突发错误，称为混合有些实际信道既有随机错误又有突发错误，称为混合信道。信道。 根据不同的信道类型设计的信道编码分为纠随机错误根据不同的信道类型设计的信道编码分为纠随机错误码、纠突

5、发错误码和纠混合错误码。码、纠突发错误码和纠混合错误码。 概述概述在通信系统中，纠检错的工作方式有：在通信系统中，纠检错的工作方式有：(1) 反馈重传反馈重传(ARQ)(2) 前向纠错前向纠错(FEC)(3) 混合纠错混合纠错概述概述 发送端经编码后发出能够发现错误的码，接收端收到后经发送端经编码后发出能够发现错误的码，接收端收到后经检验，如果发现传输中有错误，则通过反馈系统把这一判断结检验，如果发现传输中有错误，则通过反馈系统把这一判断结果反馈回发端，然后发送端把前面发出的信息重新传送一次，果反馈回发端，然后发送端把前面发出的信息重新传送一次，直到接收端认为正确地收到信息为止。直到接收端认为

6、正确地收到信息为止。 (1) 反馈重传反馈重传(ARQ)mCRm检错检错编码编码信道信道检错检错译码译码反馈反馈(2) 前向纠错前向纠错(FEC)mCRm纠错纠错编码编码信道信道纠错纠错译码译码 发送端发出的是具有纠错能力的纠错码，接收端根据译发送端发出的是具有纠错能力的纠错码，接收端根据译码规则进行译码。当误码个数在码的纠错能力范围内时，译码规则进行译码。当误码个数在码的纠错能力范围内时，译码器可以自动纠正错误。码器可以自动纠正错误。特点：特点： 1 1）前向纠错方式不需要反馈信道，特别适合于只能）前向纠错方式不需要反馈信道，特别适合于只能 提供单向信道的场合。提供单向信道的场合。2 2）由

7、于能自动纠错，不要求检错重发，因而延时小，）由于能自动纠错，不要求检错重发，因而延时小， 实时性好。实时性好。3 3）随着纠错能力的增强，译码设备也变得复杂。）随着纠错能力的增强，译码设备也变得复杂。 (3) 混合纠错混合纠错 对发送端进行适当的编码。当对发送端进行适当的编码。当错误不严重错误不严重，在码的，在码的纠错能力范围之内时，采用自动纠错；当产生的纠错能力范围之内时，采用自动纠错；当产生的差错超差错超出码的纠错能力范围出码的纠错能力范围时，通过反馈系统要求发端重发。时，通过反馈系统要求发端重发。(1) 按按功能功能分：分： 检错码：仅能检测误码检错码：仅能检测误码 纠错码：可纠正误码纠

8、错码：可纠正误码 纠删码：兼纠错和检错能力纠删码：兼纠错和检错能力纠错码纠错码1 1 纠错码的分类纠错码的分类(2) 按信息码元与监督码元之间的检验关系分： - 线性码线性码：满足线性关系- 非线性码非线性码：不存在线性关系 (3) 按信息码元与监督码元之间的按信息码元与监督码元之间的约束方式约束方式不同分：不同分： 分组码：本码组的监督码元仅和本码组的信息元相关。分组码：本码组的监督码元仅和本码组的信息元相关。 卷积码：本码组的监督码元不仅和本码组的信息元相卷积码：本码组的监督码元不仅和本码组的信息元相关，而且与前面码组的信息码元有关。关，而且与前面码组的信息码元有关。码与码相互影响不能码与

9、码相互影响不能分开，又称数码或链码分开，又称数码或链码重点讨论线性分组码重点讨论线性分组码(4) 按信息码元在编码后是否保持原形式不变：按信息码元在编码后是否保持原形式不变： 即：根据信息元在分组码中的位置分为系统码，非系统码系统码：信息码元与监督码元在分组内有确定位置，系统码：信息码元与监督码元在分组内有确定位置，编码后的信息码元保持不变；编码后的信息码元保持不变；非系统码：信息位打乱，与编码前不同。非系统码：信息位打乱，与编码前不同。(5)(5)按纠正差错的类型可分为：按纠正差错的类型可分为： 纠纠随机错误随机错误码码 纠纠突发错误突发错误码码 纠纠随机和突发错误随机和突发错误码码非线性卷

10、积码线性树码非线性非循环码循环码线性分组码纠错码纠错码按结构分类如下：纠错码按结构分类如下： 1 1 纠错码的分类纠错码的分类(续续)l 分组码的表示方法：分组码的表示方法： （二元分组码）（二元分组码） 信息码组由信息码组由 k 个信息码元组成，共有个信息码元组成，共有 2k 个不同的个不同的信息码组；信息码组；信息位信息位 附加附加 个校验码元，每个校验码元是该信息个校验码元，每个校验码元是该信息码组的某些信息码元模码组的某些信息码元模2和；和；校验位或监督位校验位或监督位 编码器输出长度为编码器输出长度为n的码字；的码字；码字的数目共有码字的数目共有 2k ；这这2k 个码字的集合称为个

11、码字的集合称为 (n,k) 分组码；分组码；rnk2 2 纠错码的基本概念纠错码的基本概念信息传输率（码率），编码效率信息传输率（码率），编码效率o 对 二进制(n, k)线性分组码，合法码字数为2k，可用编码空间的序列数为2n个。许用序列 ，禁用序列 o 任一种2k信息集合到二进制序列集合(2n)的映射都是一种(n, k)码。因此总共可能的编码方案有 种。22knC2 2 纠错码的基本概念（续）纠错码的基本概念（续）o 发现或构造好码是信道编码研究的主要问题：编码方案太多，以至全局搜索是不可能的。现实的做法是对编码方案加以一定的约束，在一个子集中寻找局部最优。这种约束即要能包含尽可能好的码，

12、又要便于分析，便于译码。o 线性分组码是最具实用价值的一类码，比如汉明码、循环码、BCH码、RS码等。2 2 纠错码的基本概念纠错码的基本概念（续）（续）2 2 纠错码的基本概念纠错码的基本概念（续）（续）对信道编码的一般要求是：对信道编码的一般要求是：纠错检错能力强；纠错检错能力强；信息传输率高；信息传输率高；编码规律简单，实现设备简单且费用合理；编码规律简单，实现设备简单且费用合理；与信道的差错统计特性相匹配。与信道的差错统计特性相匹配。 汉明距离汉明距离niiiiccc21cnjjjjccc21cnkjijikkccd1),(cc汉明距离满足距离公理汉明距离满足距离公理(1) 非负性非负

13、性(2) 对称性对称性(3) 三角不等式三角不等式 0),(jidcc),(),(ijjiddcccc),(),(),(jllijidddcccccc2 2 纠错码的基本概念纠错码的基本概念汉明重量汉明重量 nkiikcW1)(cniiiiccc21c码码C 的最小汉明距离的最小汉明距离 jiddjiji,: ),(minminCcccc),()()(),(10cccccclljijnkijidWWccdkk线性分组码的最小汉明距离等于非零码字的最小重量。线性分组码的最小汉明距离等于非零码字的最小重量。2 2 纠错码的基本概念纠错码的基本概念3 3 线性分组码线性分组码327216321531

14、4CCCCCCCCCCCCC00007326215321431CCCCCCCCCCCCC3.1 3.1 校验矩阵与生成矩阵校验矩阵与生成矩阵 7654321CCCCCCCC(1) 校验矩阵校验矩阵000010001100100011001011100011017654321CCCCCCCTT0HC0CHTIQH 1011000111010011000100110001H1234567 ,c c c c c c cC C0,0,0,00 0则则TTHC0HC0TCH0CH0令令l 被称为被称为校验矩阵校验矩阵。l 对对 线性分组码，校验矩阵为线性分组码，校验矩阵为 维矩阵。维矩阵。l对于系统码，

15、校验矩阵可以表示为对于系统码，校验矩阵可以表示为H, )n k（()nkn=HQI其中 为 维矩阵， 为 维单位矩阵。Q()nkk()()nknkI3272163215314332211CCCCCCCCCCCCCCCCCCC3272163215314CCCCCCCCCCCCCl由校验方程，得到由校验方程，得到(2) (2) 生成矩阵生成矩阵101110011100100111001321CCCCPIG l令令123 ,c c cm100111001001110011101GIPCmG其中其中 为为 维矩阵，维矩阵， 为为 维单位矩阵。维单位矩阵。l 被称为被称为生成矩阵生成矩阵。l 对对 线性

16、分组码，生成矩阵为线性分组码，生成矩阵为 维矩阵。维矩阵。l对于系统码，生成矩阵可以表示为对于系统码，生成矩阵可以表示为G, )n k（knP()knkkkGIPIl把生成矩阵的每一行用一个行向量把生成矩阵的每一行用一个行向量 来来表示，则生成矩阵可以表示为表示，则生成矩阵可以表示为12kmmmm12kGGGG1kiiimCmGG,1,2,iikG Gl令令 ，则，则l由于生成矩阵由于生成矩阵GG的每一行都是一个码字，所以的每一行都是一个码字，所以G G 的每的每行都满足行都满足 ，则有，则有l对于标准形式的校验矩阵和监督矩阵，有对于标准形式的校验矩阵和监督矩阵，有TTi iH HG G0 0

17、TH HG G0 0TTT+Q QI II IP PQ QP P0 0HGTQ QP P(3) (3) 校验矩阵和生成矩阵的关系校验矩阵和生成矩阵的关系l线性分组码的封闭性线性分组码的封闭性：线性分组码中任意两个码字之：线性分组码中任意两个码字之后仍然是该码的码字。后仍然是该码的码字。证明：设证明：设 和和 分别是码分别是码 中的两个码字，因此有中的两个码字，因此有即即 满足监督方程，所以是码满足监督方程，所以是码 中的一个码字。中的一个码字。TT1TTTT1212TT2(+)H HC C0 0H H C CC CH HC CH HC C0 0H HC C0 01C CC CC C2C C12

18、+C CC C例：重复码是一个（例：重复码是一个（3,1）线性分组码。其生成矩阵为）线性分组码。其生成矩阵为111G1111111321mmmmCCCC例：（例：（4,3）偶校验码是一个（）偶校验码是一个（4,3）线性分组码，其生成）线性分组码，其生成矩阵为矩阵为 110010101001G1100101010013213213214321mmmmmmmmmCCCCC例例 已知生成矩阵为已知生成矩阵为 求生成的线性分组码及由求生成的线性分组码及由H 生成的线性生成的线性分组码。分组码。 101110011100100111001G11101001111101001110101001110110

19、011101000111010011010011101000111010010000000000CmmGC 1000110010001100101110001101IQHQPT101111100111PPIG 101110011100100111001G1000110010001100101110001101IQH1101000011010011100101010001111111111111110100111011010011101110001011001011000101110100111010100111010011000101100001110100111011000101100101

20、10001010100111010000111010011001011000100001011000100000000000Cm关于码的最小距离与纠、检错能力的关系有以下结论：关于码的最小距离与纠、检错能力的关系有以下结论：对于（对于（n，k）线性分组码，设）线性分组码，设 为最小汉明距离。为最小汉明距离。（）（）这组码有纠正这组码有纠正 u 个错误的充要条件是个错误的充要条件是mind12min uduu2u+1对于一个二进制对称信道，当输入为对于一个二进制对称信道，当输入为2k个等可能的个等可能的n长长码字，则最大后验概率准则等效于最小汉明距离译码准则。码字，则最大后验概率准则等效于最小汉

21、明距离译码准则。 3.2 3.2 线性分组码的纠、检错能力线性分组码的纠、检错能力 lll+1（）具有检测（）具有检测l个错误的充要条件是个错误的充要条件是1min lduutlt+l+1（）具有纠正（）具有纠正 t 个错误，同时可以发现个错误，同时可以发现l个错误的充分必个错误的充分必要条件为要条件为1minltd码的纠错能力码的纠错能力u与码字的长度与码字的长度n和消息数和消息数M满足以下关系：满足以下关系：02uinniMC3.3 校验矩阵与最小距离的关系校验矩阵与最小距离的关系 对于（对于（n，k）线性分组码：校验矩阵）线性分组码：校验矩阵H中的任意中的任意t列线列线性无关而性无关而t

22、 +1列线性相关，则码的最小距离列线性相关，则码的最小距离(码字的最小码字的最小重量重量)为为t+1。反过来说，若码的最小距离。反过来说，若码的最小距离(码字的最小码字的最小重量重量)为为t+1则则H 的任意的任意t列线性无关而列线性无关而t+1列线性相关。列线性相关。3.4 线性分组码的伴随式线性分组码的伴随式 0CHTR=C+E E=e1 e2 en TTTTTEHCHEHHCERHS)(1) ，说明，说明R 是一个码字是一个码字;2) 2) ，说明，说明R 不是码字，传输过程产生了误码。不是码字，传输过程产生了误码。0S S0S STTS = HRTTS = HEl 令令12121nTT

23、niiinee=eeSHEHHHHSHEHHHH12n= eeeE E12n=HHHHHHHHiH HH H 则则（其中（其中 表示表示 的列向量）的列向量） 结论：结论：1) 当传输过程没有错误时当传输过程没有错误时 ，即，即 ， 2)2)当发生一位错误时，当发生一位错误时， 是校验矩阵的某一列。是校验矩阵的某一列。3)3)当发生多个错误时，当发生多个错误时， 为校验矩阵对应列的模为校验矩阵对应列的模2 2和。和。0 00=E ET0S STS STS S例例： 设设(7,3)线性分组码的校验矩阵为线性分组码的校验矩阵为1011000111010011000100110001H（1）接收码字

24、）接收码字R R=(1010011)，TT101011000011110100001100010000110001011 S = HR传输过程中没有误码，传输过程中没有误码，=CRCR（2）接收码字）接收码字R R=(1110011)，TT111011000011110100101100010100110001111 S = HR ，第，第2位出错，位出错，= (1010011)=+C CR RE ET2SH(0100000)=E E（3）接收码字）接收码字R R=(0011011)，TT001011000011110100111100010100110001011 S = HR与与 中的任一

25、列都不相同，中的任一列都不相同，TSHT142756SHHHHHH不能确定到底是哪两位出错，不能正确译码。不能确定到底是哪两位出错，不能正确译码。niiinnnnTTeeeeeee122112121HHHHHHHHES线性分组码的伴随式译码线性分组码的伴随式译码 ERCEEHST编码C=mG计算Em输出CER0RHTCRECnoyes输出R02uinniMC若（若（n，k）线性分组码能够纠正）线性分组码能够纠正 u 个错误，则其校验位个错误，则其校验位的数目必须满足的数目必须满足 uiinknC02完备码完备码l汉明码是一种能够纠正单个错误的完备码。汉明码是一种能够纠正单个错误的完备码。汉明码

26、最小码距汉明码最小码距设监督码共有设监督码共有m位，对于汉明码必然有位，对于汉明码必然有 。通常汉明码可以表示成通常汉明码可以表示成 。mn = 21mm(21,21)mmin3d4 汉明码汉明码 在同样的纠错能力下，汉明码的码率是最高的在同样的纠错能力下，汉明码的码率是最高的 12111212mmmmRl汉明码监督矩阵构成的两种方式：汉明码监督矩阵构成的两种方式：构成构成 H H 阵的标准形式，阵的标准形式， 。按按m位的二进制数的位的二进制数的自然自然顺序从左到右排列（不包顺序从左到右排列（不包括全括全0列）。当发生可纠的单个错误时，伴随式为列）。当发生可纠的单个错误时，伴随式为 H H

27、阵中对应的列，译码比较方便。阵中对应的列，译码比较方便。非标准形式的监督矩阵可以通过列置换变成标准形非标准形式的监督矩阵可以通过列置换变成标准形式的监督矩阵，纠错能力保持不变。式的监督矩阵，纠错能力保持不变。mHQIl如果给汉明码添加一位奇偶校验位，可得到扩展汉明码：如果给汉明码添加一位奇偶校验位，可得到扩展汉明码： 信息位保持不变，监督位增加一位。信息位保持不变，监督位增加一位。 最小码距最小码距 ， 可纠正一位错误，可纠正一位错误，同时发现两位错误。同时发现两位错误。min4d111000HH1214mindl扩展汉明码的监督方程：扩展汉明码的监督方程： l循环码是线性分组码的一个重要子集

28、。循环码是线性分组码的一个重要子集。l循环码除了具有线性分组码的一般性质外，还具有循环码除了具有线性分组码的一般性质外，还具有循循环性环性：循环码中任一许用码组经过循环移位后，所得：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。到的码组仍然是许用码组。 l循环码有严密的代数学理论基础，检错和纠错能力较循环码有严密的代数学理论基础，检错和纠错能力较强，而且编码和解码设备都不太复杂。强，而且编码和解码设备都不太复杂。5 循环码循环码5 循环码循环码 1)对于二进制码，码多项式的每个系数不是对于二进制码，码多项式的每个系数不是0就是就是1。 2) 仅是码元仅是码元位置的标记。我们并

29、不关心位置的标记。我们并不关心 的取值。的取值。 l设循环码的码字为设循环码的码字为 ，用码多项式表，用码多项式表示为示为120nnCccc121210( ).nnnnC xcxcxc xcl码字（码字（1100101）可以表示为：）可以表示为：xx 654321652( )11001011C xxxxxxxxxx l循环码的循环特性可以用码多项式来证明。循环码的循环特性可以用码多项式来证明。,mpQpnnn()mpn模l在整数运算中，有在整数运算中，有模模n运算运算。若一个整数。若一个整数m可以表示为可以表示为: 则则在模在模n运算下，一整数运算下，一整数m等于其被等于其被n除所得的余数。除

30、所得的余数。5 循环码循环码l在码多项式运算中也有类似的按模运算法则。在码多项式运算中也有类似的按模运算法则。l若一任意多项式若一任意多项式F(x)被一个被一个n次多项式次多项式N(x)除，得到商除，得到商式式Q(x)和一个次数小于和一个次数小于n的余式的余式R(x)，也就是：，也就是： 则可以写为：则可以写为： ( )()( )( )( )F xR XQ xN xN x( )( )( )F xR xN x模l在循环码中，若在循环码中，若 是一个长为是一个长为n的许用码字，则的许用码字，则 在模在模 运算下，也是一个许用码字。运算下，也是一个许用码字。( )C x( )ix C x1nx 例例

31、 某循环码的一个码字为某循环码的一个码字为1100101，则，则 若将此码左移一位，得：若将此码左移一位，得： 对应的码字为对应的码字为1001011，与将码字，与将码字1100101循环左移循环左移一位相同。一位相同。 652( )1C xxxx763( )xC xxxxx763763mod11xxxxxxxx5 循环码循环码012211)(cxcxcxcxCnn102112) 1 ()()(nnncxcxcxcxxCxC2120132)2()()(nnnncxcxcxcxCxxC1223101) 1()()(cxcxcxcxCxxCnnn5 循环码循环码l从码中取出一个前面从码中取出一个前

32、面k-1位都是位都是0的码字，定义这个码的码字，定义这个码字的码多项式为生成多项式字的码多项式为生成多项式 。l 在在 循环码中，除了全循环码中，除了全0码字以外，其他码字的连码字以外，其他码字的连0个数最多只有个数最多只有k-1个。个。( , )n k( )g xnkl 码多项式的次数为码多项式的次数为 ，且常数项不为，且常数项不为0。5 循环码循环码信息比特码字（循环1）信息比特码字(循环2）信息比特码字000100100101011010001011110000010110010110010110001100011000101101100011000100011 010001111001101011011110001110101001110111010100111