信息理论基础第六章课件

1、第六章第六章 有噪信道编码有噪信道编码 前言：前言：1. 在无损无噪信道中，总可以以最大信息传输在无损无噪信道中，总可以以最大信息传输率无错误的传输信息率无错误的传输信息。 2. 由于噪声的存在，信息传输会造成损失。由于噪声的存在，信息传输会造成损失。 3. 主要问题有：主要问题有： 在有噪信道中怎么能使消息通过传输以后，在有噪信道中怎么能使消息通过传输以后，发生的错误最少？发生的错误最少？ 在有噪信道中，无错误传输能达的最大信息在有噪信道中，无错误传输能达的最大信息传输率是多少？传输率是多少？ 怎样在不可靠的信道中实现可靠的信息传输？怎样在不可靠的信道中实现可靠的信息传输？ 6.1 信道编码

2、相关概念信道编码相关概念 信道编码又称为信道编码又称为数据传输码数据传输码或或差错控制码差错控制码。 信道编码的作用是提高信息传输的抗干扰能力。信道编码的作用是提高信息传输的抗干扰能力。 为了得到信道编码器的模型，先看看通信系统模型。为了得到信道编码器的模型，先看看通信系统模型。信源信源信源编码器信源编码器信道信道信源译码器信源译码器信宿信宿等效信源等效信源等效信宿等效信宿因此：因此： 信道的输入就是信源编码器输出的码字。信道的输入就是信源编码器输出的码字。 信道编码是在码符号通过信道传输之前应该做的事情。信道编码是在码符号通过信道传输之前应该做的事情。 总结以上亮点。可得到信道编码器的模型。

3、总结以上亮点。可得到信道编码器的模型。信道编码器信道编码器码符号序列码符号序列或或码符号码符号xi码字码字i 信道编码就是按一定的规则，将信源编码器的码字信道编码就是按一定的规则，将信源编码器的码字(信息序信息序列列)增加一些多于的码元增加一些多于的码元(冗余序列冗余序列),是的不具规律的信息序列变是的不具规律的信息序列变成具有某种规律的信道码字序列成具有某种规律的信道码字序列x。 在接收端，信道译码器利用这种规律在接收端，信道译码器利用这种规律(序列符号间的相关性序列符号间的相关性)来译码，检验收到的码字序列来译码，检验收到的码字序列y中是否有错，并纠正其中的错中是否有错，并纠正其中的错误。

4、误。 根据相关性来检测和纠正信息传输过程中的差错就是信道根据相关性来检测和纠正信息传输过程中的差错就是信道编码的基本思想。编码的基本思想。 结合以上思想，可得到通信系统模型如下结合以上思想，可得到通信系统模型如下:信源信源信源编码器信源编码器信道信道信源译码器信源译码器信宿信宿信道编码器信道编码器信道译码器信道译码器 在有噪信道中，传输信息发生错误的概率与信道的统计特在有噪信道中，传输信息发生错误的概率与信道的统计特性、编码方法和译码规则有关。性、编码方法和译码规则有关。 下面将讨论这些因素。下面将讨论这些因素。 错误概率与信道的统计特征错误概率与信道的统计特征 信道的统计特征由信道矩阵给出，

5、信道矩阵是由转移概率信道的统计特征由信道矩阵给出，信道矩阵是由转移概率构成，由信道矩阵可以求出错误概率。例子构成，由信道矩阵可以求出错误概率。例子 1-p 1-p p p 0 1 1 0 以上信道，单符号传递时错误概率为以上信道，单符号传递时错误概率为p.若若p=0.9,则错误传递则错误传递概率为概率为0.9.但信道传递与译码规则有关，若收到但信道传递与译码规则有关，若收到0译成译成1，收到，收到1译成译成0，则，则错误概率为错误概率为0.1.6.1.1 错误概率与译码规则错误概率与译码规则 译码规则的概念译码规则的概念定义定义设信道的输入符号集为设信道的输入符号集为x=xi，i=1,2,r,

6、输出符号输出符号集为集为y=yj,j=1,2,s,若对每一个输出符号若对每一个输出符号yj,都有一都有一个确定的函数个确定的函数f(yj)，使，使yj对应于唯一的一个输入符号对应于唯一的一个输入符号xi,则称这样的函数为则称这样的函数为译码规则译码规则。记为。记为1 21 2(), ,., ;, ,.,jif yx ir js例子例子6.2 以上例子可以看出，译码规则有很多种，到底应该如何选以上例子可以看出，译码规则有很多种，到底应该如何选择？择？ 使得平均错误概率最小。使得平均错误概率最小。 错误概率错误概率(平均错误概率平均错误概率)正确译码正确译码：在确定译码规则：在确定译码规则f(yj

7、)=xi以后，若发送端确实是以后，若发送端确实是xi,则则是正确译码。是正确译码。错误译码错误译码：在确定译码规则在确定译码规则f(yj)=xi以后，若发送端不是以后，若发送端不是xi,则是则是错误译码。错误译码。于是正确译码概率为：于是正确译码概率为：()|)(|)jjijp f yyp xy 于是条件错误概率为：于是条件错误概率为：11( |)(|)()|)jijjjp e yp xyp f yy 平均错误概率就是错误概率对平均错误概率就是错误概率对y的均值。的均值。 1( |)() ( |)sejjjjpe p e yp yp e y 译码规则译码规则 现在的目标就是选择适当的译码规则，

8、使得平均错误概现在的目标就是选择适当的译码规则，使得平均错误概率最小。率最小。 由于平均错误概率中的由于平均错误概率中的p(yj)与译码规则无关，所以选择与译码规则无关，所以选择译码规则使得错误概率最小即可。这就是译码规则使得错误概率最小即可。这就是最大后验概率准最大后验概率准则则。定义定义选择译码函数选择译码函数f(yj)=x*,使之满足：使之满足：*(|)(|),jijp xyp xyi xx则称这样的译码规则为则称这样的译码规则为最大后验概率准则，最大后验概率准则，又称为又称为最小错最小错误概率准则、最优译码、最佳译码、理想观测者规则。误概率准则、最优译码、最佳译码、理想观测者规则。 它

9、对于每一个输出符号，均译成最大后验概率的那个它对于每一个输出符号，均译成最大后验概率的那个符号，则信道的译码平均错误概率最小。符号，则信道的译码平均错误概率最小。根据贝叶斯公式，可以将最大后验概率改为：根据贝叶斯公式，可以将最大后验概率改为：*() (|)() (|),()()jijijjp xp yxp xp yxip yp y即：即：*() (|)() (|),jijip xp yxp xp yxi当输入是等概分布的时，为：当输入是等概分布的时，为：*(|)(|),jjip yxp yxi如果按上式定义译码规则，则称为极大似然译码规则。如果按上式定义译码规则，则称为极大似然译码规则。定义定

10、义选择译码函数选择译码函数f(yj)=x*,使之满足：使之满足：*(|)(|),jjip yxp yxi xx则称这样的译码规则为则称这样的译码规则为极大似然译码规则。极大似然译码规则。译码规则定义好以后，就可以计算平均错误概率。译码规则定义好以后，就可以计算平均错误概率。 平均错误概率平均错误概率 1111*,*( |)() ( |)( ,)( , )() (|)ssejjjjjjsrijiyjiixxpep e yp yp e yp e yp x yp xp yx 而正确译码概率为而正确译码概率为111*(),)(,)sseejjjjjppp f yyp xy 如果输入为等概分布，则如果输

11、入为等概分布，则 111*,( |)() ( |)( ,)( , )( ) ( | )( | )ssejjjjjjyyx xx xy x xpe p e yp y p e yp e yp x yp x p y xp y xr 例子例子6.3 译码时发生错误是由于信道的噪声引起的，因此平均错译码时发生错误是由于信道的噪声引起的，因此平均错误概率与信道疑义度有一定的关系。误概率与信道疑义度有一定的关系。定理定理(费诺不等式费诺不等式)平均错误概率与信道疑义度有如下的平均错误概率与信道疑义度有如下的关系：关系：1(|)()log()eeh x yh ppr 证明：思考讨论证明：思考讨论注注：1.物理

12、意义是物理意义是.？ 2.费诺不等式曲线图见教材。费诺不等式曲线图见教材。6.1.1 错误概率与编码方法错误概率与编码方法前面所讲的译码规则与错误概率的关系：前面所讲的译码规则与错误概率的关系： 1.选择最佳译码规则，只能使错误概率减小，不能使错误概选择最佳译码规则，只能使错误概率减小，不能使错误概率任意的小。率任意的小。 2. 要使错误概率任意的小，应该怎么做？要使错误概率任意的小，应该怎么做？选择恰当的编码方法。选择恰当的编码方法。例子见教材。例子见教材。 简单重复码简单重复码见教材。见教材。 (5.2)线性码线性码 设输入序列设输入序列 ，若，若 中各分量中各分量满足方程：满足方程： 1

13、2345(,)iiiiiixx xx xxix31241512iiiiiiiixxxxxxxx123451000001000110001000011000 iiiiiixxxxxx即：即： 现选取此序列现选取此序列 作为码字，可得（作为码字，可得（5. 2）线性码，）线性码，将下图：将下图：ix121001111011iiixxx或：或： 用 作 消 息 输 出 端 译 码 规 则 的 码 字 接 收 序 列 00000 000001000100011100000100000100000100000100000 01101 01101011101110011101001010100101111

14、0110001101 10111 101111010000110001111111110011101011011010111 11010 110101100101011010101001011110110001101111010 扩 展 信 道 优点优点：能纠一位或二位码元的错误。：能纠一位或二位码元的错误。正确译码概率正确译码概率:543252eppp pp p错误译码概率错误译码概率:324187.8 10 (0.01) eeppp pp注注：增大：增大n和和m的同时，既能降低错误译码概率，又能使传的同时，既能降低错误译码概率，又能使传输率不减少太多。输率不减少太多。类似可得类似可得(6.

15、3)/(7.4)线性码线性码。 (n.k)线性码线性码思考讨论。思考讨论。123110111101001100011iiiixxxx12341000010000100001110010100101iiiiixxxxx 汉明距离汉明距离定义定义(汉明距离汉明距离)长度为长度为n的两个码字的两个码字xi和和yj之间的距离是指之间的距离是指xi和和yj对应位置上码元不同的位置个数，称为汉对应位置上码元不同的位置个数，称为汉明距明距离离。1(,)kknijijkd xyxy 这样的码字距离满足距离公理，即：这样的码字距离满足距离公理，即：非负性非负性对称性对称性三角不等式三角不等式定义定义(最小汉明距

16、离最小汉明距离)码码c中，任意两个码字的汉明距离的中，任意两个码字的汉明距离的最小值称为码最小值称为码c的的最小距离最小距离(最小汉明距离最小汉明距离)。minmin(,),ijijijddc 例例6.4表5.15.1 五种码组的特性分析 mindep码的最小距离码a a码b b码c c码d d码e e码字00011100001110111000011110001000000011011011111010000001010011100101110111消息数m2444832131信息传输率r(比特/码符号)1/32/32/32/51(最大似然译码规则)310-4210-22.2810-27.8

17、10-4310-2错误概率注注：dmin越大，错误概率越小。越大，错误概率越小。?下面讨论汉明距离与极大似然译码之间的关系。下面讨论汉明距离与极大似然译码之间的关系。定义定义（极大似然译码极大似然译码）选择译码函数）选择译码函数f(yj)=x*,使之满足：使之满足：*(|)(|),jjip yxp yxi xx 则称这样的译码规则为则称这样的译码规则为极大似然译码规则。极大似然译码规则。 设码字在传输的过程中有设码字在传输的过程中有dij个位置发生错误，码字的长个位置发生错误，码字的长度为度为n，当二元对称信道是无记忆信道时：，当二元对称信道是无记忆信道时：11(|)(|)()ijijkknd

18、n djijikp yxp yxpp 只要只要p1/2,则则dij越大，越大，p(yj|xi)越小，因此，二元对称无越小，因此，二元对称无记忆信道的极大似然译码规则可以用汉明距离表示为：记忆信道的极大似然译码规则可以用汉明距离表示为：定义定义（最小距离译码最小距离译码）选择译码函数）选择译码函数f(yj)=x*,使之满足：使之满足：*(,)min(,)jijid xyd xy 错误译码概率错误译码概率:,*,*11(|)(1)ijijdn dejij ij ipp yxppmm或或:*111(|)(1) jjdn dejjjpp yxppmm注注：1.在非二元对称信道中也可以采取最小汉明距离准

19、则在非二元对称信道中也可以采取最小汉明距离准则译码，但不一定等于极大似然译码，也不一定使得错误概译码，但不一定等于极大似然译码，也不一定使得错误概率最小。率最小。 2.上面的讨论是基于相同的上面的讨论是基于相同的n和和m的，而且是在保持一的，而且是在保持一定的信息传输率的情况下，选择不同的编码方法，可以得定的信息传输率的情况下，选择不同的编码方法，可以得到不同距离的码，我们选择最小距离最大的一个码。这样到不同距离的码，我们选择最小距离最大的一个码。这样在译码时，可以得到错误概率最小。在译码时，可以得到错误概率最小。6.2.1 有噪信道编码定理有噪信道编码定理定理定理(有噪信道编码定理、香农第二

20、定理有噪信道编码定理、香农第二定理)设有一个离散无设有一个离散无记忆平稳信道，其信道容量为记忆平稳信道，其信道容量为c，当信息传输率，当信息传输率rc，只要码长只要码长n足够长，则总存在一种编码，使得平均译足够长，则总存在一种编码，使得平均译码错误概率任意小。码错误概率任意小。传统的证明思路是传统的证明思路是.?香农的证明思路是：用随机编码的方法得到所有可能生成香农的证明思路是：用随机编码的方法得到所有可能生成的码的集合，然后在码集合中随机选择一个码作为输入码的码的集合，然后在码集合中随机选择一个码作为输入码序列，最后计算这样随机选择的一个码在码集合上的平均序列，最后计算这样随机选择的一个码在

21、码集合上的平均性能。由于计算出平均错误概率可以达到任意小，可以证性能。由于计算出平均错误概率可以达到任意小，可以证明一定存在一种码，他的性能明一定存在一种码，他的性能pe达到或者超过随机编码的达到或者超过随机编码的平均性能。由于考虑的是平均性能，因此，不必考虑码的平均性能。由于考虑的是平均性能，因此，不必考虑码的结构，可以用大数定律。在译码时，将接收序列译成联合结构，可以用大数定律。在译码时，将接收序列译成联合典型序列中的码字。典型序列中的码字。定义定义(联合典型序列联合典型序列)设设(xi,yj)为长度为为长度为n的随机序列对，并的随机序列对，并且有下式成立：且有下式成立：1()()kkni

22、jijkp x yp x y 则在这些随机序列对中同时满足一下条件的序列称为则在这些随机序列对中同时满足一下条件的序列称为联合联合典型序列典型序列。111log( ()()log( ()( )log( ()()ijijp xh xnp yh ynp x yh xyn 联合联合典型序列的集合称为典型序列的集合称为联合联合典型序列集，典型序列集，记为记为g(xy)。x和和y的典型序列集分别记为的典型序列集分别记为g(x), g(y)包含的典型序列的数目分别记为包含的典型序列的数目分别记为:mg(xy),mg(x),mg(y)按照上面的定义按照上面的定义,对于任意小的正数对于任意小的正数0,0,当当

23、n足够大时，足够大时，有：有： 1.典型序列典型序列集集和联合典型序列和联合典型序列集的概率集的概率满足：满足： 111()( )()rrrpgxpg ypgxy 2.典型序列和联合典型序列典型序列和联合典型序列出现的概率出现的概率满足：满足：222222()()()()()()()()()n h xn h xin h yn h yjn h xyn h xyijp xp yp x y 3.典型序列集和联合典型序列集中元素的个数满足：典型序列集和联合典型序列集中元素的个数满足：122122122()()()()()()()()()( )()()n h xn h xgn h yn h ygn h

24、xyn h xygmxmymxy 注：联合典型序列集中出现相互独立的随即序列对的概注：联合典型序列集中出现相互独立的随即序列对的概率是非常小的。率是非常小的。(见教材说明见教材说明143)利用以上关系可以证明香农第二定理。利用以上关系可以证明香农第二定理。证明证明：假设通过随机编码，得到一个码集合：假设通过随机编码，得到一个码集合ck,k=1,2,2nm. 令输入为等概分布，则该码的平均错误概率为：令输入为等概分布，则该码的平均错误概率为：11()( |)mekiipcp e xm由于是随机编码，每个码的平均错误都相等。而且对于由于是随机编码，每个码的平均错误都相等。而且对于ck中的任何一个码

25、字的中的任何一个码字的p(e|xi)都相等，即都相等，即111111()( |)( |)( |)mmekiiipcp e xp e xp e xmm于是，于是，()()ekekpcpc设设yj是发送码字序列是发送码字序列x1时信道输出得到的接收序列，定义时信道输出得到的接收序列，定义yj与与xi构成联合典型序列构成联合典型序列ai,即即(,)(),1,2,.,iijaxygxyim 按照典型序列译码方法，把接收序列按照典型序列译码方法，把接收序列yj译成联合典型序译成联合典型序列的码字，译码错误的发生有两种可能：列的码字，译码错误的发生有两种可能： (1)yj不与不与x1构成联合典型序列构成联

26、合典型序列 (2)yj与与x1以外的其它码字构成联合典型序列。以外的其它码字构成联合典型序列。所以：所以：112( |).ermpp e xpaaa根据和事件的概率关系，得：根据和事件的概率关系，得： 12merriippapa 11()rrpapgxy 由于：由于：所以：所以： 1rpa由因为由因为yj和其它的输入是相互独立的序列，根据和其它的输入是相互独立的序列，根据(6.42), 有：有： 312 (; )()n i x yripa 3331 1221212 (; ) (; ) (; )()()()()n i x yenrn i x yn i x ypm 因此，选择任意小的因此，选择任意

27、小的0,0，当当r0.若选用码字总数若选用码字总数m=2nc+，则无论，则无论n取多大，也找不大一种编码，使取多大，也找不大一种编码，使得平均译码错误概率任意小。得平均译码错误概率任意小。证明证明：见教材：见教材6.2.3 错误概率的上界错误概率的上界(见教材见教材)6.3 纠错编码纠错编码 香农第二定理只是说明了码的存在，并没有给出这种香农第二定理只是说明了码的存在，并没有给出这种码的编码方法。码的编码方法。 信道编码的目的是提高信号传输的可靠性，广义的信信道编码的目的是提高信号传输的可靠性，广义的信道编码还包括为特定信道设计传输信号，如道编码还包括为特定信道设计传输信号，如mrz码、码、h

28、db码、伪随机序列码。码、伪随机序列码。 纠错编码作为提高传输可靠性的最主要的措施之一，纠错编码作为提高传输可靠性的最主要的措施之一，本节就讨论纠错编码。本节就讨论纠错编码。6.3.1 纠错编码的分类纠错编码的分类 信道中的干扰一般分两种形式信道中的干扰一般分两种形式:一是一是随机噪声随机噪声(主要主要)，二是二是脉冲干扰脉冲干扰和和信道衰落信道衰落。 根据信道中干扰的形式，可将信道分成三类：根据信道中干扰的形式，可将信道分成三类：随机信随机信道、突发信道和混合信道道、突发信道和混合信道。 随机信道产生的错误是随机独立出现的，称为随机信道产生的错误是随机独立出现的，称为随机错随机错误误。他的特

29、点是码元是否发生错误是随机且相互独立的，。他的特点是码元是否发生错误是随机且相互独立的，产生这种错误的信道称为产生这种错误的信道称为随机信道随机信道。（如卫星信道、同轴。（如卫星信道、同轴电缆、光缆以及微波）电缆、光缆以及微波） 脉冲干扰和信道衰落产生的错误是成串出现的，错误脉冲干扰和信道衰落产生的错误是成串出现的，错误之间具有相关性，这类错误称为之间具有相关性，这类错误称为突发错误突发错误， 产生突发错误产生突发错误的信道称为的信道称为突发信道突发信道。(如短波信道、移动通信、由于物理如短波信道、移动通信、由于物理原因引起差错的光盘和磁盘原因引起差错的光盘和磁盘) 包含以上两类错误的信道称为

30、包含以上两类错误的信道称为混合信道混合信道。 根据不同的信道设计不同的信道编码方法，因此，可根据不同的信道设计不同的信道编码方法，因此，可将信道编码分为将信道编码分为随机纠错码、纠突发错误码和纠混合错误随机纠错码、纠突发错误码和纠混合错误码。码。 在通信系统中，纠检错的工作方式有：在通信系统中，纠检错的工作方式有：反馈重传纠错反馈重传纠错、前向纠错前向纠错和和混合纠错等混合纠错等。 1.反馈重传纠错反馈重传纠错检错编码检错编码信道信道检错译码检错译码mccm反馈反馈注：注： 发送端发的是可以检错的码，若有错，怎重传，我国发送端发的是可以检错的码，若有错，怎重传，我国的电报系统就是反馈重传编码。

31、的电报系统就是反馈重传编码。 2.前向纠错前向纠错纠错编码纠错编码信道信道纠错译码纠错译码mccm注：注： 前向纠错可以自动纠错，因此也称前向纠错可以自动纠错，因此也称自动纠错自动纠错。 3. 混合纠错混合纠错 对发送端进行适当的编码，当错误不严重是，在码的对发送端进行适当的编码，当错误不严重是，在码的纠错能力范围内，采取自动纠错，当发生的差错查处码的纠错能力范围内，采取自动纠错，当发生的差错查处码的纠错能力时，则通过反馈系统向发送端要求重发。纠错能力时，则通过反馈系统向发送端要求重发。 检错码和纠错码在不加区别时统称为纠错码，纠错码检错码和纠错码在不加区别时统称为纠错码，纠错码就是引入一定的

32、剩余度，在传输的信息码元后增加一些码就是引入一定的剩余度，在传输的信息码元后增加一些码元元(校验元校验元)，使得信息损失或发生错误时，可以在接收端，使得信息损失或发生错误时，可以在接收端恢复。恢复。 编码实际上是信息序列到纠错码序列的映射。编码实际上是信息序列到纠错码序列的映射。纠错码的分类如下：纠错码的分类如下：根据信息码元和校验码元之间的关系分为根据信息码元和校验码元之间的关系分为线性码线性码和和非线性非线性码。码。根据不用的分组及映射，纠错码分为根据不用的分组及映射，纠错码分为分组码分组码和和树码。树码。 分组码分组码 把信息序列以把信息序列以k个码元分组，然后把个码元分组，然后把k个信

33、息元按一定个信息元按一定的规律产生的规律产生r个多于的校验元，输出码序列的长度为个多于的校验元，输出码序列的长度为n=k+r，每一个码字的每一个码字的r个校验元只与本分组的个校验元只与本分组的k个信息元有关，与个信息元有关，与别的分组的信息位无关，记为别的分组的信息位无关，记为分组码分组码(n,k). 如果码字与信息位的函数关系是线性的，则称为如果码字与信息位的函数关系是线性的，则称为线性线性分组码分组码。 树码树码 信息序列通常以信息序列通常以k0个码元分段，编码器输出的校验元个码元分段，编码器输出的校验元r=n-k0不仅与本段不仅与本段k0个信息元有关，而且还与前面若干段个信息元有关，而且

34、还与前面若干段的信息元有关，称此码为的信息元有关，称此码为树码树码。纠错码按结构分类纠错码按结构分类 见教材见教材6.3.2 纠错码的基本概念纠错码的基本概念 信源编码把信源符号编码成码字序列信源编码把信源符号编码成码字序列(一般是二元序一般是二元序列列)，它主要解决有效性，它主要解决有效性(可行性可行性)问题，而信道编码主要解问题，而信道编码主要解决可靠性问题，通过增加码元达到纠检错的目的。决可靠性问题，通过增加码元达到纠检错的目的。信道编码的一般要求是：信道编码的一般要求是： 纠检错能力强，可发现和纠正多个错误；纠检错能力强，可发现和纠正多个错误； 信息传输率高，所以码长尽可能短；信息传输

35、率高，所以码长尽可能短； 编码规律简单，实现设备简单合理；编码规律简单，实现设备简单合理； 与信道的差错统计特性相匹配。与信道的差错统计特性相匹配。定义定义(二元分组码二元分组码) 将信源编码器的输出序列进行分组，将信源编码器的输出序列进行分组，分组长度为分组长度为k,则可以有则可以有m=2k个不同的分组信息序列，个不同的分组信息序列，每个信息序列用一个每个信息序列用一个n长的码字来表示长的码字来表示(nk),这样的这样的码字集合称为码字集合称为二元分组码二元分组码。定义定义每个码字的前每个码字的前k为称为为称为信息位信息位，其余，其余n-k为称为为称为校验校验位位或者或者监督位监督位，长为，

36、长为n的码字共有的码字共有2n个，选出其中的个，选出其中的m个作为码字，称为个作为码字，称为许用序列许用序列，其他序列称为，其他序列称为禁用禁用序列序列。例例 6.5 (见教材见教材)定义定义若若(n,k)分组码中分组码中k个信息位与原始信息序列的个信息位与原始信息序列的k个信个信息位相同，且位于息位相同，且位于n长的码字的前长的码字的前(后后)k位，则该分组位，则该分组码为码为系统码系统码，否则为，否则为非系统码非系统码。 码的汉明距离是衡量码的纠检错能力的重要参数，码的码的汉明距离是衡量码的纠检错能力的重要参数，码的最小距离越大，其纠检错能力越强。最小距离越大，其纠检错能力越强。定义定义对

37、于某一码字，起非零元素的个数称为该码字的对于某一码字，起非零元素的个数称为该码字的汉汉明重量。明重量。例子见教材例子见教材6.4 几种重要的纠错码几种重要的纠错码 线性分组码是一类有价值的码，如汉明码、线性分组码是一类有价值的码，如汉明码、golay码、码、rs码、码、bch码都属于线性分组码。码都属于线性分组码。6.4.1 线性分组码线性分组码 校验矩阵和生成矩阵校验矩阵和生成矩阵 线性分组码一般由一组信息元的模线性分组码一般由一组信息元的模2线性方程生成。线性方程生成。 一个一个(7.3)线性分组码线性分组码c=c1c2c3c4c5c6c7,其中其中c1c2c3为信息元，为信息元，c4c5

38、c6c7为校验元，假设校验元用下面的方为校验元，假设校验元用下面的方程组得到：程组得到：4135123612723ccccccccccccc 称此方程为称此方程为校验方程校验方程或者或者监督方程监督方程。将方程组改写一下，使得等号的右边为将方程组改写一下，使得等号的右边为0，得：，得：13412351262370000ccccccccccccc然后写成矩阵形式如下：然后写成矩阵形式如下：123456710110000111010001100010001100010ccccccc 令：令：1011000111010011000100110001h则方程组可写成则方程组可写成hct=0或者或者ch

39、t=0,式中式中h称为称为一致校验矩一致校验矩阵阵，一旦建立了校验矩阵，校验元与信息元之间的关系，一旦建立了校验矩阵，校验元与信息元之间的关系就确定了，码字就确定了。就确定了，码字就确定了。校验方程组还可以写为：校验方程组还可以写为：1122334135123612723ccccccccccccccccccc令：令：123()mc c c100111001001110011101g则则cmg.定义定义对于对于k位信息位位信息位n长码元序列的方程组，有长码元序列的方程组，有cmg成成立，其中立，其中c为为n维行向量，维行向量，m为为k维行向量，维行向量，g为为kn矩阵，称矩阵，称g为线性分组码为

40、线性分组码c的的生成矩阵生成矩阵。 利用生成矩阵可以将信息序列利用生成矩阵可以将信息序列m变成码字序列变成码字序列c。例。例子见教材子见教材152页。页。可以将生成矩阵写成：可以将生成矩阵写成：12kgggggi为为n维行向量：维行向量：2(,)iniiiigggg信息序列写成：信息序列写成：12(,)kmm mm则：则：1kiiicmgm g观察生成矩阵：观察生成矩阵：100111001001110011101g生成矩阵的每一行可以是一个码字，共生成矩阵的每一行可以是一个码字，共k个，对比个，对比*式可式可得出以下结论。得出以下结论。k个码字的不同线性组合就得到了整个码组。个码字的不同线性组

41、合就得到了整个码组。构成生成矩阵的构成生成矩阵的k个码字必须线性无关，其秩为个码字必须线性无关，其秩为k。(只有只有线性无关时，才能得到整个码组，码字的个数为线性无关时，才能得到整个码组，码字的个数为2k)对于生成矩阵：对于生成矩阵：100111001001110011101g还可以写成：还可以写成：()gip其中其中p为为k(n-k)的矩阵，的矩阵，i为单位阵。具有这样形式的生为单位阵。具有这样形式的生成矩阵所产生的码是系统码。成矩阵所产生的码是系统码。因此，构造一个因此，构造一个(n.k)分组码，只需找出一个秩为分组码，只需找出一个秩为n-k的的(n-k)n的矩阵的矩阵h，然后由线性方程组

42、，然后由线性方程组hct=0t解出码字，得解出码字，得到到(n.k)分组码，或者构造一个秩为分组码，或者构造一个秩为r的的rn的生成矩阵的生成矩阵g，有有cmg得到得到(n.k)分组码。分组码。由于生成矩阵的每一行都是一个码字，因此由于生成矩阵的每一行都是一个码字，因此hgt=0t或者或者ght0.于是线性分组码的生成矩阵和校验矩阵的行向量彼此正交。于是线性分组码的生成矩阵和校验矩阵的行向量彼此正交。根据此关系，根据此关系，h也可以看成也可以看成(n-k,k)分组码的生成矩阵，而分组码的生成矩阵，而g为为(n-k,n)分组码的校验矩阵。称满足正交关系的两个矩分组码的校验矩阵。称满足正交关系的两个矩阵作为生成矩阵的两个码互为阵作为生成矩阵的两个码互为对偶码对偶码。标准形式的校验矩阵标准形