信息论第7章抗干扰信道编码

1、1信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题： 如何正确接收载有信息的信号线路编码 如何避免少量差错信号对信息内容的影响纠错编码第第7 7章章 抗干扰信道编码抗干扰信道编码2 从功能角度：检错码 、纠错码 对信息序列的处理方法：分组码、卷积码 码元与原始信息位的关系：线性码、非线性码 差错类型：纠随机差错码、纠突发差错码、介于中间的纠随机/突发差错码。 构码理论：代数码、几何码、算术码、组合码等 纠错码分类 3差错控制系统分类 前向纠错（FEC）：发端信息经纠错编码后传送，收端通过纠错译码自动纠正传递过程中的差错 反馈重发（ARQ）：收端通过检测接收码是否符合编码规

2、律来判断，如判定码组有错，则通过反向信道通知发端重发该码 混合纠错（HEC）：前向纠错和反馈重发的结合，发端发送的码兼有检错和纠错两种能力 4第第7 7章章 抗干扰信道编码抗干扰信道编码 通信的有效性问题：通信的有效性问题：即如何通过对即如何通过对信源信源进行进行编码编码，压缩信源的多余度，提高传输的效率。压缩信源的多余度，提高传输的效率。 通信的可靠性问题：通信的可靠性问题：即消息通过即消息通过信道信道传输时如何传输时如何选择选择编码编码方案以减少差错。方案以减少差错。 通信的可靠性显然与通信的可靠性显然与信道的统计特性信道的统计特性有关，因为有关，因为杂噪干扰是造成错误的主要因素。其次，杂

3、噪干扰是造成错误的主要因素。其次，编码方编码方法和译码方法法和译码方法也将影响信息传输的可靠性。也将影响信息传输的可靠性。5信道是通信系统中的重要组成部分，信道的任务是以信信道是通信系统中的重要组成部分，信道的任务是以信号方式传输信息。号方式传输信息。信道的输入端和输出端连接着编码器和译码器，形成了信道的输入端和输出端连接着编码器和译码器，形成了一个新的信道，即一个新的信道，即编码信道。编码信道。信道的特征是由信道传递概率信道的特征是由信道传递概率p(y|x)来描述的。由此可来描述的。由此可以算出它的信道容量以算出它的信道容量C，只要在信道中实际传送的信息，只要在信道中实际传送的信息率率RC，

4、在接收端就应当能够无差错地译出发端所输，在接收端就应当能够无差错地译出发端所输送的信息。送的信息。第第7 7章章 抗干扰信道编码抗干扰信道编码6 通过信道编码实现信源与信道相匹配。通过信道编码实现信源与信道相匹配。 信道编码的编码对象是信源编码器输出的数字序信道编码的编码对象是信源编码器输出的数字序列列M，又称为信息序列。通常是由二元符号，又称为信息序列。通常是由二元符号0,1构构成的序列，而且成的序列，而且0和和1是独立等概的。是独立等概的。 信道编码是按一定的规则给数字序列信道编码是按一定的规则给数字序列M增加一些增加一些多余的码元，使不具有规律性的信息序列多余的码元，使不具有规律性的信息

5、序列M变换变换为为具有某种规律性具有某种规律性的数字序列的数字序列C，又称为码序列。，又称为码序列。 码序列中信息序列的诸码元与码序列中信息序列的诸码元与多余码元多余码元之间是相之间是相关的。关的。第第7 7章章 抗干扰信道编码抗干扰信道编码7 在接收端，信道译码器利用这种在接收端，信道译码器利用这种预知的编码规预知的编码规则则来译码，或者说检验接收到的数字序列来译码，或者说检验接收到的数字序列R中中 是否有错，或者纠正其中的差错。是否有错，或者纠正其中的差错。 信道编码的基本思想是根据相关性来检测和纠信道编码的基本思想是根据相关性来检测和纠正传输过程中产生的差错。正传输过程中产生的差错。 在

6、有噪信道中传输消息是会发生错误的，在有噪信道中传输消息是会发生错误的，错误错误概率和信道的统计特性、译码过程及译码规则概率和信道的统计特性、译码过程及译码规则有关。有关。第第7 7章章 抗干扰信道编码抗干扰信道编码8第第7 7章章 抗干扰信道编码抗干扰信道编码9第第7 7章章 抗干扰信道编码抗干扰信道编码 内容提要内容提要 7.1 .1 译码规则译码规则 7.2 7.2 译码规则的选择准则译码规则的选择准则 7.3 7.3 信道编码的编码原则信道编码的编码原则 7.4 7.4 抗干扰信道编码定理抗干扰信道编码定理 7.5 7.5 分组码及其检纠能力分组码及其检纠能力 7.7 7.7 线性分组码

7、及其生成矩阵线性分组码及其生成矩阵 7.8 7.8 一致检验矩阵与伴随式一致检验矩阵与伴随式 7.9 7.9 标准阵列与译码表标准阵列与译码表 7.10 7.10 检纠能力与一致检验矩阵的关系检纠能力与一致检验矩阵的关系 7.11 7.11 完备码完备码 7.12 7.12 汉明码与扩展汉明码汉明码与扩展汉明码 107.1 译码规则译码规则 错误概率与信道统计特征有关。例如在二错误概率与信道统计特征有关。例如在二元对称信道中元对称信道中 单个符号的单个符号的错误传递概率是错误传递概率是p 单个符号的单个符号的正确传递概率是正确传递概率是1-p 错误概率与译码过程和译码规则的关系也错误概率与译码

8、过程和译码规则的关系也很大。很大。117.1 译码规则译码规则 例例7.1 设有一个二元对称信道，如下图所示，其输入符号为设有一个二元对称信道，如下图所示，其输入符号为等概分布。等概分布。 1-p=0.1 1-p p=0.9 p X a1=0 0 a2=1 1=b2 Y 0=b1 结论：错误概率既与信道的统计特性有关，也与译码规则有关。结论：错误概率既与信道的统计特性有关，也与译码规则有关。在信道输出端，如果规定：在信道输出端，如果规定：接收到符号接收到符号0时，译码器把它译成时，译码器把它译成0；接收到符号接收到符号1时，译码器把它译成时，译码器把它译成1；译码错误概率译码错误概率PE=0.

9、9。反之，如果：反之，如果：接收到符号接收到符号0时，译码器把它译成时，译码器把它译成1；接收到符号接收到符号1时，译码器把它译成时，译码器把它译成0；译码错误概率译码错误概率PE=0.1。12 定义定义7.1 设信道输入符号集为设信道输入符号集为X=(xi，i=1,2 ,r)，输出符号集为输出符号集为Y=(yj，j=l,2,s)，若对每一个输出，若对每一个输出符号符号yj都有一个确定的函数都有一个确定的函数F(yj)，使，使yj对应于唯一的对应于唯一的一个输入符号一个输入符号xi，则称这样的函数为译码规则，即，则称这样的函数为译码规则，即 F(yj)=xi i=1,2 ,r和和 jl,2,s

10、 显然，对于有显然，对于有r个输入、个输入、s个输出的信道而言，按个输出的信道而言，按上述定义得到的译码规则共有上述定义得到的译码规则共有rs 种。种。7.1 译码规则译码规则13 7.1 译码规则译码规则例例 7.2 设有一信道，其信道矩阵为设有一信道，其信道矩阵为 由于由于r3，s3，s个输出符号中的每一个个输出符号中的每一个都可以译成都可以译成 r 个输入符号中的任何一个，个输入符号中的任何一个，故按此倍道矩阵总共可设计出故按此倍道矩阵总共可设计出3 3=27种译码种译码规则。规则。 在所有的译码规则中，不是每一种译码规在所有的译码规则中，不是每一种译码规则部是合理的，因此我们要讨论则部

11、是合理的，因此我们要讨论选择选择译码译码规则的准则规则的准则。141、错误概率错误概率在确定译码规则在确定译码规则 F(yj)xi， i=1,2 ,r , j=l,2,s 之后，之后，若信道输出端接收到的符号为若信道输出端接收到的符号为yj，则一定译成则一定译成xi。如果发送端发送的就是如果发送端发送的就是xi，即为正确译码；，即为正确译码；反之，若发送端发送的反之，若发送端发送的xk，且，且k i，即为，即为错误译码。错误译码。经过译码后经过译码后条件正确概率为条件正确概率为条件错误概率为条件错误概率为 平均错误概率平均错误概率pE为为平均错误概率平均错误概率pE的含义是经过译码后，平均接收

12、到一个符号的含义是经过译码后，平均接收到一个符号所产生错误概率的大小。所产生错误概率的大小。)|(| )(jijjyxpyyFp | )(1)|(1)|(jjjijyyFpyxpyep sjjjjEyepypyepEp1)|()()|(7.2 译码规则的选择准则译码规则的选择准则152、译码规则译码规则 使平均错误概率使平均错误概率pE最小为最小为选择译码规则的选择译码规则的准则准则(1) 定义定义7. 2.1 最大后验概率译码规则最大后验概率译码规则理想观测者规则理想观测者规则 选择译码函数选择译码函数F(yj)x*，使之满足条件，使之满足条件iyxpyxpjij 对对 )|()|(* 它是

13、选择这样一种译码函数，对于每一个输出符号它是选择这样一种译码函数，对于每一个输出符号yj，j1、2，s 均译成具有最大后验概率的那个输均译成具有最大后验概率的那个输入符号入符号x*，则信道译码错误概率会最小。但一般说来，则信道译码错误概率会最小。但一般说来，后验概率应用起来并不方便，这时我们引入极大似然译后验概率应用起来并不方便，这时我们引入极大似然译码规则。码规则。7.2 译码规则的选择准则译码规则的选择准则16(2) 定义定义7.2.2 极大似然译码规则极大似然译码规则 选择译码函数选择译码函数F(yj)x*，使之满足条件，使之满足条件 7.2 译码规则的选择准则译码规则的选择准则ixpx

14、ypxpxypiijj 对对 )()|()()|(*ixypxypijj 对对 )|()|(* 当信道输入符号为等概分布时，应用极大似然译码规则当信道输入符号为等概分布时，应用极大似然译码规则是最方便的。所用的条件概率为信道矩阵中的元素。是最方便的。所用的条件概率为信道矩阵中的元素。当信道输入符号为等概分布时，可以写成当信道输入符号为等概分布时，可以写成17(3) 最大后验概率译码规则和极大似然译码规则是等价的最大后验概率译码规则和极大似然译码规则是等价的 最大后验概率译码规则可以很容易推出极大似然译码最大后验概率译码规则可以很容易推出极大似然译码规则。由贝叶斯公式，最大后验概率公式可写为规则

15、。由贝叶斯公式，最大后验概率公式可写为iypxpxypypxpxypjiijjj 对对 )( )()|()()()|(*当输入为等概分布，当输入为等概分布， 则有则有)()(*ixpxp ixypxypijj 对对 )|()|(*7.2 译码规则的选择准则译码规则的选择准则183、平均错误概率、平均错误概率 *xY,XxY,XYXYYXYYjjYjjjYjYjjjsjjjEp(y|x)p(x)p(xy)x*ypxypF(y),ypxypyyFpyp|yyFpypyp|yyFpe|ypypp)()()(),(1)()()()()(1)()(17.2 译码规则的选择准则译码规则的选择准则193、平

16、均错误概率、平均错误概率若输入为等慨分布，则若输入为等慨分布，则 *,)|(1xXYExyprp(*)式式( (* *) )意味着，在输入为等概分布的条件下，意味着，在输入为等概分布的条件下，译码错误概率译码错误概率P PE可用信道矩阵中的元素来表示。可用信道矩阵中的元素来表示。这种求和是除去信道矩阵中每列中对应于这种求和是除去信道矩阵中每列中对应于F(yj)x*的那一项后，求矩阵中其余元素之和。的那一项后，求矩阵中其余元素之和。7.2 译码规则的选择准则译码规则的选择准则注：注：改变信道的传递特性，降低平均错误概率。改变信道的传递特性，降低平均错误概率。20 4、费诺不等式费诺不等式 译码时

17、发生错误是由信道中噪声引起的，因此平均译码时发生错误是由信道中噪声引起的，因此平均错误概率错误概率pE与信道疑义度与信道疑义度H(X|Y)有关。表述这种关系有有关。表述这种关系有下述引理：费诺不等式下述引理：费诺不等式引理引理7.2.1 错误概率错误概率pE与信道疑义度与信道疑义度H(X|Y)之间的关系之间的关系 H(X|Y)H(pE)十十pElog(r1)这个不等式称为费诺不等式。这个不等式称为费诺不等式。 虽然虽然PE与译码规则有关，但不管采用什么译码规则与译码规则有关，但不管采用什么译码规则该不等式均成立。对于给定的信源、信道及编码、译码规该不等式均成立。对于给定的信源、信道及编码、译码

18、规则，信道疑义度则，信道疑义度H(X|Y)=H(X)I(X;Y)就可以被确定，它就可以被确定，它是信源熵超过是信源熵超过I(X;Y)的部分。这个值给定了译码错误的下的部分。这个值给定了译码错误的下限。限。7.2 译码规则的选择准则译码规则的选择准则214、费诺不等式、费诺不等式 以以H(X|Y)为纵坐标，为纵坐标， pE为横坐标，函数为横坐标，函数H(pE)十十pElog(r1)随随pE变化的曲线如下图所示。变化的曲线如下图所示。7.2 译码规则的选择准则译码规则的选择准则22 4、费诺不等式费诺不等式 费诺不等式费诺不等式 H(X|Y)H(pE)十十pElog(r1) 从费诺不等式可以看出，

19、当作了一次译码判决后所保留的从费诺不等式可以看出，当作了一次译码判决后所保留的关于信源的不确定性可以分成两部分：关于信源的不确定性可以分成两部分： 第一部分是接收到第一部分是接收到Y后，判决是否发生错误的不确定性后，判决是否发生错误的不确定性H(PE, 1-PE)， 第二部分是当判决是错误的，其错误概率为第二部分是当判决是错误的，其错误概率为PE确定由确定由r-1个个输人符号中哪一个引起错误的不确定性，它是输人符号中哪一个引起错误的不确定性，它是(r-1 )个符号个符号不确定性的最大值不确定性的最大值log(r-1 )与与PE的乘积。的乘积。7.2 译码规则的选择准则译码规则的选择准则237.

20、3 信道编码的编码原则信道编码的编码原则 选择最佳译码规则只能使错误概率选择最佳译码规则只能使错误概率pE有限地减小，有限地减小，无法使无法使pE任意地小任意地小 必须优选信道编码方法来进一步减小错误概率必须优选信道编码方法来进一步减小错误概率 编码方法介绍编码方法介绍 简单重复编码简单重复编码 247.3.1 简单重复编码简单重复编码 99. 001. 001. 099. 0P其信道矩阵为其信道矩阵为2,1001. 001. 021)|(1,* xXYExyprp平均错误概率平均错误概率件下件下输入分布为等概分布条输入分布为等概分布条 2211)()(:xyFxyFA最最佳佳译译码码规规则则

21、 设有二元对称信道如图所示。设有二元对称信道如图所示。257.3.1 简单重复编码简单重复编码简单重复编码：简单重复编码：规定信源符号为规定信源符号为“0 0( (或或“1 1”) )时，则重复发时，则重复发送三个送三个“0 0”( (或或“1 1”) )，此时构成的新信道可，此时构成的新信道可以看成是二元对称信道的三次扩展信道。以看成是二元对称信道的三次扩展信道。 87654321110101100011010001 aaaaaaaa的码字的码字没有使用没有使用111 000 消消息息的的码码字字发发送送端端用用作作11111010110001101000100087654321 接收序列接

22、收序列接收端接收端267.3.1 简单重复编码简单重复编码设输入符号为等概分布，采用极大似然译码规则设输入符号为等概分布，采用极大似然译码规则（即大数逻辑译码）（即大数逻辑译码）3222222332222223 pp pp pppp pppppppppppp pppp pp ppP15131211)()()()( FFFF88878684)()()()( FFFF42332222223,1033)(21)|(1)()|(* ppppppppppppppppppMpppxXYijixXYijE 输入为等概条件下，相应的平均错误概率为输入为等概条件下，相应的平均错误概率为277.3.1 简单重复编

23、码简单重复编码 采用简单重复编码方法，如果进一步增大重复次数采用简单重复编码方法，如果进一步增大重复次数n，则，则会继续降低平均错误概率会继续降低平均错误概率pE ，不难算出，不难算出 n=5 pE = 10-5 n=7 pE410-5 n=9 pE10-8 n=11 pE510-10 在这种情况下，采用在这种情况下，采用“择多译码择多译码”的译码规则，即根据的译码规则，即根据信道输出端接收序列中信道输出端接收序列中“0”多还是多还是“1”多。多。 如果是如果是“0”多译码器就判决为多译码器就判决为“0”， 如果是如果是“1”多译码器就判决为多译码器就判决为“1”。得到的平均错误概率与极大译码

24、规则是一致的。得到的平均错误概率与极大译码规则是一致的。287.3.2 汉明距离汉明距离 1、汉明距离汉明距离 设设X(x1 , x2 , xn)，Y(y1 , y2 , yn)为两个为两个n长的二长的二元码字，则码字元码字，则码字X和和Y之间的汉明距离定义为之间的汉明距离定义为 2、物理含义：两个码字之间的汉明距离是它们在相同位、物理含义：两个码字之间的汉明距离是它们在相同位上不同码符号的数目的总和。上不同码符号的数目的总和。3、性质、性质 汉明距离满足距离公理汉明距离满足距离公理 (1)非负性非负性 (2)对称性对称性 (3)三角不等式三角不等式 nikkyxYXD1,表示模二和运算表示模

25、二和运算其中其中 29 4、 码码C的最小距离的最小距离 在二元码在二元码C中，任意两个码字的汉明距离的最中，任意两个码字的汉明距离的最小值，称为码小值，称为码C的最小距离，即的最小距离，即 5、举例、举例 7.3.2 汉明距离汉明距离CCCCCCCDDjijiji, ,minmin且1 2 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 3minminmin432121 DDDaaaaCCn的的两两组组码码设设有有307.3.2 汉明距离汉明距离 很明显，最小码间距离很明显，最小码间距离Dmin越大，则平均错误概越大，则平均错误概率率pE越小。

26、在输入消息符号个数越小。在输入消息符号个数M相同的情况相同的情况下，同样地下，同样地Dmin越大，越大， pE越小。越小。 码组中最小距离越大，受干扰后，越不容易把码组中最小距离越大，受干扰后，越不容易把一个码字错译成另一个码字，因而平均错误概一个码字错译成另一个码字，因而平均错误概率率pE小。如果最小码间距离小。如果最小码间距离Dmin小，受干扰后小，受干扰后 很容易把一个码字译成另一个码，因而平均错很容易把一个码字译成另一个码，因而平均错误概率大。这意味着，在选择编码规则时，应误概率大。这意味着，在选择编码规则时，应使码字之间的距离越大越好。使码字之间的距离越大越好。316 6、基于汉明距

27、离的最小近邻译码规则、基于汉明距离的最小近邻译码规则消息数固定为消息数固定为M M，码字长度固定为，码字长度固定为N N，离散无记忆，离散无记忆信道的信道的N N次扩展信道次扩展信道7.3.2 汉明距离汉明距离),(),(22112121)()()()()(jijiyxDNyxDiNjNijijiNiijNjjijppppppppxypxypxypxxxyyypxyp 32M个消息先验等概条件下，采用最大似然准则个消息先验等概条件下，采用最大似然准则若有若有则选择译码函数则选择译码函数7.3.2 汉明距离汉明距离), 2 , 1)()(*Mixypxypijj ),(),(),(),(*jij

28、ijjyxDNyxDyxDNyxDpppp ppp 且当21),(),(*jijyxDyxD ), 2 , 1(Mi )2 , 2 , 1(,)(21*NMjjxxxxyF 337.3.2 汉明距离汉明距离6 6、基于汉明距离的最小近邻译码规则、基于汉明距离的最小近邻译码规则将与将与yj汉明距离最近的汉明距离最近的xi译作译作yj原码，即选择译原码，即选择译码函数码函数),(),()(min*jijjyxDyxDxyF 对于等概输入，当误码率较低时（小于对于等概输入，当误码率较低时（小于1/21/2），），基于汉明距离的最小近邻译码规则基于汉明距离的最小近邻译码规则等价于等价于极大似然译码规则

29、。极大似然译码规则。347.3.2 汉明距离汉明距离 在有噪信道中，传输的平均错误概率在有噪信道中，传输的平均错误概率pE和和各种编、译码方法有关。各种编、译码方法有关。 可采用使码的最小距离尽可能增大的编码可采用使码的最小距离尽可能增大的编码方法，又采用将接收序列方法，又采用将接收序列yj译成与之距离译成与之距离最短的码字最短的码字x*的译码方法，则只要的译码方法，则只要n足够足够长时，适当选择输入符号个数长时，适当选择输入符号个数M，就可以，就可以使平均错误概率很小，而信息传输率又能使平均错误概率很小，而信息传输率又能保持一定。保持一定。357.4 抗干扰信道编码定理抗干扰信道编码定理定理

30、定理7.4.1 香农第二定理香农第二定理 设有一离散无记忆平稳信道，信道容量为设有一离散无记忆平稳信道，信道容量为C，只要，只要待传送的信息传输率待传送的信息传输率 RC，则存在一种编码，当输，则存在一种编码，当输入序列长度入序列长度n足够大时，使译码错误概率任意小足够大时，使译码错误概率任意小。物理意义：物理意义：(1) 只要只要RC，就可以在有噪信道中以任意小的错误概率，就可以在有噪信道中以任意小的错误概率(pE )传传 输信息输信息(2) 当输入序列长度当输入序列长度n足够大时，可以以任意接近信道容量足够大时，可以以任意接近信道容量C的信息的信息传输率传递信息。传输率传递信息。367.4

31、 抗干扰信道编码定理抗干扰信道编码定理定理定理 7.5.2 香农第二定理的逆定理香农第二定理的逆定理 设有一离散无记忆平稳信道，其信道容量为设有一离散无记忆平稳信道，其信道容量为C，对于任，对于任意意 0，若选用码字总数，若选用码字总数M2n(C+ )，则无论，则无论n取多大也找不取多大也找不到一种编码，使译码错误概率到一种编码，使译码错误概率pE任意小。任意小。CnCnnMLSHR2log)(log)(香农第二定理及其逆定理香农第二定理及其逆定理表明表明：耍想使信息传输率耍想使信息传输率R R大于信道容量大于信道容量C C而又无错误的传输消息是不而又无错误的传输消息是不可能的。可能的。在任何

32、信道中，信道容量是进行可靠传输的最大信息传输率。在任何信道中，信道容量是进行可靠传输的最大信息传输率。当选择码字个数当选择码字个数M2n(C+ )时，信息传输率为时，信息传输率为37一、分组码的基本概念一、分组码的基本概念差错控制思想：差错控制思想：在在2k个长度为个长度为k的的0,1消息消息序列中，设法按一定规则加入若干序列中，设法按一定规则加入若干0,1符号，符号，把长度为把长度为k的的0,1信息序列变为长度为信息序列变为长度为n(nk)的具有一定抗干扰能力的符号序列的具有一定抗干扰能力的符号序列其中其中k+r=n.由由2k个长度为个长度为n的的0,1符号序符号序组成的集合，构成一个组成的

33、集合，构成一个(n,k)分组码，代表分组码，代表2k个长度为个长度为k的消息序列。的消息序列。7.5 分组码及其检纠能力分组码及其检纠能力)(2121rkkkkaaaaaa 38 与与 (n,k)分组码分组码 对应关系对应关系(n,k)分组码实质：分组码实质：如何从如何从2n个长为个长为n的的0,1序列中选序列中选2k个长为个长为n的的0,1序列序列7.5 分组码及其检纠能力分组码及其检纠能力)(21kaaa)(21nccc )()()(2121222111knnkkaaafcaaafcaaafc39奇偶校验码奇偶校验码特点：特点：长度为长度为N；信息位；信息位k=(N-1)，且有，且有表明：

34、表明：码字中码字中1的个数是偶数，只能发现奇的个数是偶数，只能发现奇数个错误。数个错误。7.5 分组码及其检纠能力分组码及其检纠能力) 1, 2 , 1( Niacii 11NiiNac40二、分组码的检错、纠错能力二、分组码的检错、纠错能力(n,k)分组码是一种纠错码分组码是一种纠错码.(3,1)分组码分组码(N=3次重复码次重复码)可纠正一位错，可纠正一位错，发现两位错发现两位错.7.5 分组码及其检纠能力分组码及其检纠能力41(n,k)分组码的检纠能力与汉明距离的关系分组码的检纠能力与汉明距离的关系7.5 分组码及其检纠能力分组码及其检纠能力),(,(1),(),(knwwewwDekn

35、jiji 个错误分组码能发现),(,(12),(),(jiknwwewwDeknjiji 个错误分组码能纠正),(,(1),()(),(jiknwwfewwDeffeknjiji 个错误个错误，同时发现分组码能纠正注：注：上述结论可换为最小汉明距离上述结论可换为最小汉明距离.42重复码重复码很强检纠能力，码率最低很强检纠能力，码率最低奇偶校验码奇偶校验码检纠能力极低，码率最高检纠能力极低，码率最高7.5 分组码及其检纠能力分组码及其检纠能力码符比特NNNMR12loglog11 码符比特NNNNNMRN1112loglog12 43线性分组码线性分组码7.7 线性分组码及其生成矩阵线性分组码及

36、其生成矩阵 消息消息m (n , k) 码字码字c m=(mk-1,m1,m0) 分组编码器分组编码器 c=(cn-1,c1,c0) qk qn 由码符号集由码符号集0,1组成的组成的(n,k)线性分组码，是线性分组码，是k维子空间维子空间 (n,k)线性分组码可由线性分组码可由k个线性独立的码字张成个线性独立的码字张成 qk个信息元组以什么算法一一对应映射到码空间。个信息元组以什么算法一一对应映射到码空间。 码率编码效率：码率编码效率：Rc =k/n 447.7 线性分组码及其生成矩阵线性分组码及其生成矩阵生成矩阵 c m G 1n 1k kn 码字 消息 生成矩阵 Ggk-1g1g0T，有

37、k个(1n)行矢量，如何选择呢？457.7 线性分组码及其生成矩阵线性分组码及其生成矩阵线性分组码的形成线性分组码的形成 c = mk-1 gk-1+ m1 g1+m0 g0 码空间的所有元素（即码字）都可以写成k个基底的线性组合 由于k个基底即G的k个行矢量线性无关，矩阵G的秩一定等于k。 当信息元确定后，码字仅由G矩阵决定，因此我们称这kn 矩阵G为该(n,k)线性分组码的生成矩阵。 467.7 线性分组码及其生成矩阵线性分组码及其生成矩阵生成矩阵生成矩阵G(kn)的特点的特点 想要保证 (n,k)线性分组码能够构成k维n重子空间，G 的k个行矢量gk-1, g1, g0必须是线性无关的，

38、只有这样才符合作为基底的条件。 由于基底不是唯一的，所以G也就不是唯一的。 不同的基底有可能生成同一码集，但因编码涉及码集和映射两个因素，码集一样而映射方法不同也不能说是同样的码。 477.7 线性分组码及其生成矩阵线性分组码及其生成矩阵 (n,k)码的任何生成矩阵都可以通过行运算（以及列置换）简化成“系统形式” 。G = Ik P =Ik是kk单位矩阵，P是kr矩阵(k+r = n)。 (1)(1)(1)1(1)01(1)11100(1)01001000100001kn kkkn kn kppppppppp 系统形式的生成矩阵(1)(1)(1)1(1)01(1)11100(1)0100100

39、0100001kn kkkn kn kppppppppp (1)(1)(1)1(1)01(1)11100(1)01001000100001kn kkkn kn kppppppppp (1)(1)(1)1(1)01(1)11100(1)01001000100001kn kkkn kn kppppppppp (1)(1)(1)1(1)01(1)11100(1)01001000100001kn kkkn kn kppppppppp krkkrrppppppppp21222211121110001000148系统码构造7.7 线性分组码及其生成矩阵线性分组码及其生成矩阵 krkkrrkpppppppp

40、pmmmPMw21222211121121)()()()2()1(21rknknknkCCCmmmw ),12(1)(rjpmCkiijijkn 其中其中49码字码字码字汉明重量码字汉明重量(n,k)线性分组码最小重量线性分组码最小重量7.7 线性分组码及其生成矩阵线性分组码及其生成矩阵), 2 , 1(1 , 0)(21niCCCCwin 01)(iCwW0,),(min)(min iiiiwWwwWWW结论结论)(),(minminWWwwDji 其中其中),(,),(min),(minknwwwwDwwDjijijiji 507.7 线性分组码及其生成矩阵线性分组码及其生成矩阵 前k位由

41、单位矩阵Ik决定，等于把信息组m原封不动搬到码字的前k位； 其余的n-k位叫冗余位或一致校验位一致校验位，是前k个信息位的线性组合。 这样生成的（n,k）码叫做系统码系统码。 若生成矩阵G不具备系统形式，则生成的码叫做非系统码非系统码。 系统化不改变码集，只是改变了映射规则。 生成的码字生成的码字C517.7 线性分组码及其生成矩阵线性分组码及其生成矩阵 若通过行运算和列置换能将两个生成矩阵G互等，则称这两个G等效。 非系统码的G可通过运算转变为系统码的G，且不改变原码的检纠能力。 等效的两个G生成的两个(n,k)线性码也是等效的。 因此，每个(n,k)线性码都可以和一个系统的(n,k)线性码

42、等效。 系统码52一致校验矩阵的构成一致校验矩阵的构成(n,k)码生成矩阵G=Ik,P ，则H PT In-k ， 且GHT=0 H的校验作用的校验作用7.8 一致检验矩阵与伴随式一致检验矩阵与伴随式TTWHknW0),( 537.8 一致检验矩阵与伴随式一致检验矩阵与伴随式 n维n重空间有相互正交的n个基底 选择k个基底构成码空间C 选择另外的(n-k)个基底构成空间H C和H是对偶的 CHT0, GHT=0 n维维n重空间重空间V k维维k重重 k维维n重重 n-k维维 信息组信息组 码空间码空间 n重重H 空间空间m C空间构成空间构成547.8 一致检验矩阵与伴随式一致检验矩阵与伴随式

43、 将H空间的n-k个基底排列起来可构成一个(n-k)n矩阵，称为校验矩阵H。用来校验接收到的码字是否是正确的； G是(n,k)码的生成矩阵，H是它的校验矩阵； H是(n,n-k)对偶码的生成矩阵，它的每一行是一个基底。 G则是它的校验矩阵。55 例7.8.1 (6,3)线性分组码，其生成矩阵是 G= 求：(1)计算码集，列出信息组与码字的映射关系。(2)将该码系统化处理后，计算系统码码集并列出映射关系。(3)计算系统码的校验矩阵H。若收码r = 100110, 检验它是否码字？ (4)根据系统码生成矩阵画出编码器电原理图。 1 1 1 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1

44、 56例7.8.1 码集与映射关系信息 码字 系统码字000 000000 00000000101110100101101011000101011001110110001110110011101010011110110011110110011000101111000111101011011101057例7.8.1 二元(6,3)线性分组码编码器 m0m1m2 输入 输出 c0c1c258伴随式伴随式 m C=(cn-1,c1,c0) R=(rn-1,r1,r0) (n,k) 信道定义差错图案E E(en1,e1,e0) RC (rn-1cn-1,r1c1,r0c0) 二进制码中模2加与模2减是

45、等同的，因此有E = R C 及R = C E 59伴随式S的定义因为CHT = 0 所以RHT(CE)HTCHTEHT= EHT如果收码无误：必有RC即E0， 则EHT= 0 RHT = 0。如果收码有误：即E 0， 则RHT = EHT 0。 在HT固定的前提下，RHT仅仅与差错图案E有关，而与发送码C无关。定义伴随式S S = (sn-k-1,s1,s0) = RHT = EHT 60 从物理意义上看，伴随式S并不反映发送的码字是什么，而只是反映信道对码字造成怎样的干扰。 差错图案E是n重矢量，共有2n个可能的组合，而伴随式S是(n-k)重矢量，只有2n-k个可能的组合，因此不同的差错图

46、案可能有相同的伴随式。 接收端收到R后，因为已知HT，可求出 SRHT；如果能知道对应的E，则通过C = RE而求得C。 RHT = S ? C = RE R S E C 只要E正确，译出的码也就是正确的。 伴随式S的意义61 上述方程组中有n个未知数en1, e1,e0 ，却只有n-k个方程，可知方程组有多解。 在有理数或实数域中，少一个方程就可能导致无限多个解，而在二元域中，少一个方程导致两个解，少两个方程四个解，以此类推，少n-( n-k) = k个方程导致每个未知数有2k个解。 因此，由上述方程组解出的E可以有2k个解。到底取哪一个作为附加在收码R上的差错图案E的估值呢？ 概率译码：把

47、所有2k个解的重量(差错图案E中1的个数)作比较，选择其中最轻者作为E的估值。该方法概念上很简单但计算效率不高。差错图案差错图案E的求解的求解(2) 62依据：依据：若若BSC信道的差错概率是信道的差错概率是p，则长度，则长度n的码中错误概率的码中错误概率 ： 0个错个错 1个错个错 2个错个错 n个错个错 (1-p)n p(1-p)n-1 p2(1-p)n-2 pn 由于由于p 出错越少的情况，发生概率越大，出错越少的情况，发生概率越大，E的重量越轻，的重量越轻，所以该译码方法实际上体现了最小距离译码准则，所以该译码方法实际上体现了最小距离译码准则，即最大似然译码。即最大似然译码。63(n,

48、k)码的一般译码方法：码的一般译码方法：把把n维线性空间维线性空间Vn中所有中所有2n种不同的种不同的n维矢维矢量，划分成量，划分成2k个不交的子集个不交的子集D1,D2, ,D2k，每个子集中只含每个子集中只含(n,k)码中的一个码字码中的一个码字wi,每每个个Di含有含有2(n-k)个矢量个矢量.Di中任一矢量与中任一矢量与Di中中的码字的码字wi之间距离，是与其他子集之间距离，是与其他子集Dj (ij)中所含码字中所含码字wj (ij)间距离最小的。每个间距离最小的。每个Di中矢量都译成中矢量都译成Di所包含的码字所包含的码字wi.注：注：2k个码字先验等概时平均错误译码概率最小个码字先

49、验等概时平均错误译码概率最小7.9 标准阵列与译码表标准阵列与译码表64 表中所列码字是接收到的码字表中所列码字是接收到的码字R； 将没有任何差错时的收码将没有任何差错时的收码R放在第一行，收码等于发码放在第一行，收码等于发码R=C(C Ci,i =0,1,2k-1), 差错图案为全零差错图案为全零E0=(0,00)，伴随，伴随式为全零式为全零S0=(0,00)。由于有。由于有2k个码字，码表有个码字，码表有2k列。列。 在第在第2到第到第n+1的的n行中差错图案的所有重量为行中差错图案的所有重量为1 (共共n个个)。 如果如果(1+ n)2n-k，再在下面行写出全部带有，再在下面行写出全部带

50、有2个差错的图案个差错的图案 (共共 个个)。 如果总行数如果总行数(1+n + )仍然小于仍然小于2n-k，再列出带有，再列出带有3个差错的图个差错的图案，以此类推，直到放满案，以此类推，直到放满2n-k行，每行一个行，每行一个Ej, 对应一个不同的对应一个不同的伴随式伴随式Sj。这样，表的行数。这样，表的行数2n-k正好等于伴随式的数目。正好等于伴随式的数目。标准阵列的构成 2n2nC2nC65S0 E0S1 E1 Sj Ej E0+C0= 0+0= 0E0+C1= C1E0+Ci= CiE1+C0= E1 E1+Ci Ej+C0= EjEj+C1Ej+Ci 标准阵列标准阵列 E1+C1

51、11022n kn k ECE1122n kn k SE112n k EC12n ki EC1221n kk EC21kjEC121kEC02121kkECC66陪集和子集陪集和子集 译码表中有译码表中有2n-k行，每行是一个行，每行是一个陪集陪集，每陪集的第一个，每陪集的第一个元素元素(位于第一列位于第一列)叫叫陪集首陪集首。同一陪集（同一行）中的。同一陪集（同一行）中的所有元素对应共同的一个伴随式。第一行陪集的陪集所有元素对应共同的一个伴随式。第一行陪集的陪集首是全零伴随式首是全零伴随式S0所对应的全零差错图案所对应的全零差错图案E0(无差错无差错)，而第而第j行陪集的陪集首是伴随式行陪集

52、的陪集首是伴随式Sj所对应的重量最小的所对应的重量最小的差错图案差错图案Ej (C0=0, Rj=Ej)。 译码表中有译码表中有2k列，每列是一个列，每列是一个子集子集，每子集的第一个，每子集的第一个元素元素(位于第一行位于第一行)叫叫子集头子集头。同一子集（同一列）中的。同一子集（同一列）中的所有元素对应同一个码字，第一列子集的子集头是全所有元素对应同一个码字，第一列子集的子集头是全零码字零码字C0，而第，而第i列子集的子集头是码字列子集的子集头是码字Ci (E0=0, Ri=Ci) 。67例例 7.9.1 一个一个(5,2)系统线性码的生成矩阵是系统线性码的生成矩阵是G = 设收码设收码R

53、 = (10101)，构造标准阵列译码表，译出发码的估值，构造标准阵列译码表，译出发码的估值解：解：(1)构造标准阵列译码表。分别以信息组构造标准阵列译码表。分别以信息组m= (00)、(01) 、(10)、(11)及已知的及已知的G求得求得4个许用码字为个许用码字为C1 =(00000)、C2 = (10111) 、C3 = (01101)、C4 = (11010)。求出校验矩阵：求出校验矩阵： H = PT I3 = 列出方程组：列出方程组：1011011101ic 000102030410111213142021222324100110100100111hhhhhhhhhhhhhhh00

54、0011022033044010011112213314412002112222332442hehehehehesheheheheheshehehehehes 68伴随式有伴随式有2n-k238种组合，差错图案中代表无差错的有种组合，差错图案中代表无差错的有一种，代表一个差错的图案有一种，代表一个差错的图案有 种，已有种，已有6种。种。代表两个差错的图案有代表两个差错的图案有 种。只需挑选其中的两个，种。只需挑选其中的两个，挑选方法可有若干种，不是唯一的。先将挑选方法可有若干种，不是唯一的。先将Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)

55、代入上面的代入上面的线性方程组，解得对应的线性方程组，解得对应的Sj分别是分别是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴随式中，。剩下的伴随式中，(011)所对应的差所对应的差错图案是错图案是2k个即个即(00011)、(10100)、(01110)、(11001),其中其中(00011)和和(10100)并列重量最轻，任选其中一个如并列重量最轻，任选其中一个如(00011)。同样可得伴随式同样可得伴随式(110)所对应的最轻差错图案之一是所对应的最轻差错图案之一是(00110)。 551 5102 例例 7.9.1 标准阵列的构成标准阵列的构成515

56、C1025 C69S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100例例 7.9.1 标准阵列标准阵列70例 7.9.1 将接收码R10101译码 可选以下三种方

57、法之一译码：可选以下三种方法之一译码： 直接搜索码表，查得直接搜索码表，查得(10101)所在列的子集头是所在列的子集头是(10111)，因此，因此译码输出取为译码输出取为(10111)。 先求伴随式先求伴随式RHT = (10101) HT = (010) = S4，确定，确定S4所在行，再所在行，再沿着行对码表作一维搜索找到沿着行对码表作一维搜索找到(10101), 最后顺着所在列向上找最后顺着所在列向上找出码字出码字(10111)。 先求出伴随式先求出伴随式RHT = (010) = S4并确定并确定S4所对应的陪集首（差错所对应的陪集首（差错图案）图案）E4=(00010)，再将陪集首

58、与收码相加得到码字，再将陪集首与收码相加得到码字C= R+ E4= (10101)+ (00010)= (10111)。 上述三种方法由上而下，查表的时间下降而所需计算量增大，上述三种方法由上而下，查表的时间下降而所需计算量增大，实际使用时可针对不同情况选用。实际使用时可针对不同情况选用。71 对上例作进一步分析，还可以看到，该对上例作进一步分析，还可以看到，该(5,2)码的码的dmin=3, 纠错能力是纠错能力是t = INT(3-1)/2 = 1。因此，译码阵列。因此，译码阵列中只有前中只有前6行具有唯一性、可靠性，真正体现了最大似然行具有唯一性、可靠性，真正体现了最大似然译码准则，而第译

59、码准则，而第7、8行的差错图案行的差错图案(00011)和和(00110)中包含中包含两个两个“1”，已超出了，已超出了t= 1的纠错能力，译码已不可靠。比的纠错能力，译码已不可靠。比如，当收码如，当收码R(10100)时，根据码表译出的码字是时，根据码表译出的码字是(10111)，与收码与收码R的汉明距离是的汉明距离是2，然而收码，然而收码R与全零码字与全零码字(00000)的的汉明距离也是汉明距离也是2，为什么不能译成，为什么不能译成(00000)呢？事实上，码呢？事实上，码表的第表的第7、8行本身就不是唯一的。注意在码表计算过程中，行本身就不是唯一的。注意在码表计算过程中，伴随式伴随式(

60、011)所对应的所对应的4个差错图案中有两个并列重量最轻，个差错图案中有两个并列重量最轻，如果当时选的不是如果当时选的不是(00011)而是而是(10100)，那么码表第，那么码表第7行就行就不是现在这样了。不是现在这样了。 对例对例 7.9.1的的分析分析72译码表的构成 由陪集首由陪集首ei和伴随式和伴随式Si两列构成两列构成 共有共有2n-k行，按发生错误递增的顺序，排行，按发生错误递增的顺序，排列陪集首，直到排满列陪集首，直到排满2n-k行行 计算每个陪集首对应的伴随式计算每个陪集首对应的伴随式Si= eiHT 译码过程译码过程 计算计算S=RHT S=0,则没有发生错误，译为则没有发