1、信息论与编码信息论与编码第七章第七章 线性分组码线性分组码信息论与编码信息论与编码内容提要内容提要 目前，几乎所有得到实际应用的纠错码都是线性的。本目前，几乎所有得到实际应用的纠错码都是线性的。本章首先介绍有关纠错码的基本概念，然后重点论述线性分组章首先介绍有关纠错码的基本概念，然后重点论述线性分组码的定义及其编译码理论。在此基础上，介绍了一种典型的码的定义及其编译码理论。在此基础上，介绍了一种典型的线性分组码：汉明码。线性分组码：汉明码。掌握内容：线性分组码的概念，生成矩阵，校验矩阵，掌握内容：线性分组码的概念，生成矩阵，校验矩阵，最小距离，伴随式，标准阵列等。最小距离，伴随式，标准阵列等。
2、信息论与编码信息论与编码近年来，随着计算机、卫星通信及高速数据网的飞速发展，数据的交近年来，随着计算机、卫星通信及高速数据网的飞速发展，数据的交换、处理和存储技术得到了广泛的应用，人们对数据传输和存储系统的可换、处理和存储技术得到了广泛的应用，人们对数据传输和存储系统的可靠性提出了越来越高的要求。因此，如何控制差错、提高数据传输和存储靠性提出了越来越高的要求。因此，如何控制差错、提高数据传输和存储的可靠性，成为现代数字通信系统设计工作者面临的重要课题。的可靠性，成为现代数字通信系统设计工作者面临的重要课题。香农第二定理指出，当信息传输速率低于信道容量时，通过某种编译香农第二定理指出，当信息传输
3、速率低于信道容量时，通过某种编译码方法，就能使错误概率为任意小。目前已有了许多有效的编译码方法，码方法，就能使错误概率为任意小。目前已有了许多有效的编译码方法，并形成了一门新的技术并形成了一门新的技术纠错编码技术。纠错编码技术。这里所讲的纠错编码即信道编码，与信源编码一样都是一种编码，但这里所讲的纠错编码即信道编码，与信源编码一样都是一种编码，但两者的作用是完全不同的。两者的作用是完全不同的。u 信源编码的目的是压缩冗余度，提高信息的传输速率。信源编码的目的是压缩冗余度，提高信息的传输速率。u 信道编码的目的是提高信息传输时的抗干扰能力以增加信息传输的可信道编码的目的是提高信息传输时的抗干扰能
4、力以增加信息传输的可靠性。靠性。信息论与编码信息论与编码1差错控制系统模型差错控制系统模型模型突出了以控制差错为目的的纠错码编、译码器，因此也称为模型突出了以控制差错为目的的纠错码编、译码器，因此也称为差错控制系统差错控制系统。2差错控制系统的分类差错控制系统的分类按其纠错能力的不同可分为两种：按其纠错能力的不同可分为两种：检错码检错码和和纠错码纠错码。检错码检错码：能发现错误但不能纠正错误的码；：能发现错误但不能纠正错误的码；纠错码纠错码：不仅能发现错误而且还能纠正错误的码。：不仅能发现错误而且还能纠正错误的码。信息论与编码信息论与编码按差错控制系统类型，可分为按差错控制系统类型，可分为前向
5、纠错前向纠错、重传反馈重传反馈和和混合纠错混合纠错等三种方式。等三种方式。前向纠错前向纠错(FEC)方式方式：FEC(Forward Error Control)方式是发端发送有纠错能力的码（纠错方式是发端发送有纠错能力的码（纠错码），接收端收到这些码后，通过纠错译码器自动地纠正传输中的错误。码），接收端收到这些码后，通过纠错译码器自动地纠正传输中的错误。优点优点：是不需要反馈信道；能进行一个用户对多个用户的同时通信，特：是不需要反馈信道；能进行一个用户对多个用户的同时通信，特别适合于移动通信；译码实时性较好，控制电路也比较简单。别适合于移动通信；译码实时性较好，控制电路也比较简单。缺点缺点：
6、是译码设备较复杂；编码效率较低。：是译码设备较复杂；编码效率较低。重传反馈重传反馈(ARQ)方式方式:ARQ(Automatic Repeat Request)方式是：发端发出能够发现错误的方式是：发端发出能够发现错误的码（检错码），收端译码器收到后，判断在传输中有无错误产生，并通过码（检错码），收端译码器收到后，判断在传输中有无错误产生，并通过反馈信道把捡测结果告诉发端。发端把收端认为有错的消息再次传送，直反馈信道把捡测结果告诉发端。发端把收端认为有错的消息再次传送，直到收端认为正确接收为止。到收端认为正确接收为止。信息论与编码信息论与编码优点优点：译码设备简单，在多余度一定的情况下，码的检
7、错能力比纠错能力：译码设备简单，在多余度一定的情况下，码的检错能力比纠错能力要高得多，因而整个系统能获得极低的误码率。要高得多，因而整个系统能获得极低的误码率。缺点缺点：应用：应用ARQ方式必须有一条从收端至发端的反馈信道。并要求信源产方式必须有一条从收端至发端的反馈信道。并要求信源产生信息的速率可以进行控制，收、发两端必须互相配合，其控制电生信息的速率可以进行控制，收、发两端必须互相配合，其控制电路比较复杂，传输信息的连贯性和实时性也较差。路比较复杂，传输信息的连贯性和实时性也较差。混合纠错混合纠错(HEC)方式：方式：HEC(Hybrid Error Control)方式是上述两种方式的结
8、合。发端发送方式是上述两种方式的结合。发端发送的码既能检错、又有一定的纠错能力。收端译码时若发现错误个数在码的的码既能检错、又有一定的纠错能力。收端译码时若发现错误个数在码的纠错能力以内，则自动进行纠错；若错误个数超过了码的纠错能力，但能纠错能力以内，则自动进行纠错；若错误个数超过了码的纠错能力，但能检测出来，则通过反馈信道告知发方重发。这种方式在一定程度上避免了检测出来，则通过反馈信道告知发方重发。这种方式在一定程度上避免了 FEC方式译码设备复杂和方式译码设备复杂和 ARQ方式信息连贯性差的缺点。方式信息连贯性差的缺点。信息论与编码信息论与编码 在设计差错控制系统时，选择何种实现方式，应综
9、合考虑各方面的因在设计差错控制系统时，选择何种实现方式，应综合考虑各方面的因素。主要有：素。主要有：满足用户对误码率的要求；满足用户对误码率的要求；有尽可能高的信息传输速率；有尽可能高的信息传输速率；有尽可能简单的编译码算法且易于实现；有尽可能简单的编译码算法且易于实现；(4)可接受的成本。可接受的成本。常用的纠错码按其码字结构形式和对信息序列处理方式的不同可分常用的纠错码按其码字结构形式和对信息序列处理方式的不同可分成两大类：成两大类：分组码分组码和和卷积码卷积码。信息论与编码信息论与编码分组码分组码：把信息序列以每：把信息序列以每k个码元分组，编码器将每个信息组按一定规律产个码元分组，编码
10、器将每个信息组按一定规律产 生生r个多余的码元（称为校验元），形成一个长为个多余的码元（称为校验元），形成一个长为n=k+r 的码字。的码字。对于对于k个码元分组，共有个码元分组，共有2k个不同的信息组，编码器输出长个不同的信息组，编码器输出长n的的2k个码个码字，这字，这2k个长为个长为n的码字构成的集合称为一个（的码字构成的集合称为一个（n，k）分组码。）分组码。n：码长码长；k：信息位的数目信息位的数目；R=k/n：分组码码率分组码码率。卷积码卷积码：把信息序列以每：把信息序列以每k个分组，通过编码器输出长为个分组，通过编码器输出长为n（n k）的一个）的一个子码。但是该子码的子码。但是
11、该子码的nk个校验元不仅与本子码的信息元有关，个校验元不仅与本子码的信息元有关，而且也与其前而且也与其前m个子码的信息元有关。个子码的信息元有关。信息论与编码信息论与编码讨论码字序列通过离散信道时发生的情况，信道分为讨论码字序列通过离散信道时发生的情况，信道分为无记忆信道无记忆信道和和有有记忆信道记忆信道。在无记忆信道中，噪声对传输码元的影响是相互独立的，即每一在无记忆信道中，噪声对传输码元的影响是相互独立的，即每一个差错的出现与其前后是否有错无关，如图所示。在无记忆信道中，个差错的出现与其前后是否有错无关，如图所示。在无记忆信道中，错误是随机产生的，因此被称作错误是随机产生的，因此被称作随机
12、错误随机错误，无记忆信道也被称为，无记忆信道也被称为随机随机信道（信道（random channel）。信息论与编码信息论与编码有记忆信道中，各种干扰所造成的错误往往不是单个地，而是成群、有记忆信道中，各种干扰所造成的错误往往不是单个地，而是成群、成串地出现，表现出错误之间有相关性，称为成串地出现，表现出错误之间有相关性，称为突发错误突发错误。下图就是这种信道。下图就是这种信道的一个模型。的一个模型。就实际信道而言，由于其干扰的复杂性，往往是两种错误并存。随就实际信道而言，由于其干扰的复杂性，往往是两种错误并存。随机错误与突发错误并存的信道，称为机错误与突发错误并存的信道，称为组合信道组合信道
13、或或复合信道复合信道。信息论与编码信息论与编码设消息或数据以二进制形式表示，并以设消息或数据以二进制形式表示，并以F2=0,1 表示这个二元集。表示这个二元集。消息集：消息集：01k-1i2uuuuF，序列个数：序列个数：2k设长为设长为n的二元码元序列集为：的二元码元序列集为：01n-1cccnk，序列个数：序列个数：2n 2k设消息集是长为设消息集是长为k的二元消息序列集，表示如下：的二元消息序列集，表示如下：信息论与编码信息论与编码1分组编码：分组编码：在长为在长为n的二元序列集中的二元序列集中 选出与消息序列数选出与消息序列数2k相同相同数目的码元序列，并使两者一一对应。数目的码元序列
14、，并使两者一一对应。01n-1ccc，几个概念：几个概念：码字码字：对应于消息的长：对应于消息的长n的的2k个码元序列，用个码元序列，用 表示。表示。c选出的选出的2k个码元序列称为个码元序列称为许用码组许用码组，另外的，另外的2n-2k个为个为禁用码组禁用码组。码码：所有码字的集合，用：所有码字的集合，用C表示。表示。字字：所有长为：所有长为n的二元序列。的二元序列。消息消息：长为：长为k的二元码元序列，用的二元码元序列，用 表示。表示。u信息论与编码信息论与编码2消息消息 与码字与码字 cu0001k-11101k-11101k-1nncfuuucfuuucfuuu，线性分组码线性分组码：
15、与与 呈线性关系（呈线性关系（fi为为线性函数）线性函数）01n-1ccc，01k-1uuu，非线性分组码非线性分组码：与与 不呈线性关系不呈线性关系（fi为非线性函数）为非线性函数）01n-1ccc，01k-1uuu，对于消息为对于消息为k位，码长为位，码长为n的线性分组码称（的线性分组码称（n，k）线性分组码。）线性分组码。信息论与编码信息论与编码【例例】一个原始数字消息一个原始数字消息u0编码规则：编码规则：001010ncucucu000,0001,111nucuc k=1，故为（，故为（n，1）码，称（）码，称（n，1）重复码。码率：）重复码。码率：R=1/n【例例】编码规则编码规则
16、001122102n-2nnncucucucuuu构成一个（构成一个（n，n-1）线性分组码：）线性分组码：R=(n-1)/n（加法为模（加法为模2加）加）信息论与编码信息论与编码由最后一个方程：由最后一个方程：2211100000nnnniniiiiicucuc（奇）偶校验码（奇）偶校验码：码字中：码字中1的个数为偶数。的个数为偶数。在接收到一个字中在接收到一个字中1的个数不是偶数时，就可以确定接收的不是码的个数不是偶数时，就可以确定接收的不是码字。这种码能检出奇数个错误，但不能发现偶数个错误。字。这种码能检出奇数个错误，但不能发现偶数个错误。比较上面两例编码方案：比较上面两例编码方案：重复
17、码：重复码：R=1/n，编码效率最低，检纠错能力最高。，编码效率最低，检纠错能力最高。奇偶校验码：奇偶校验码：R=(n-1)/n，编码效率最高，检纠错能力最低。（两个极端），编码效率最高，检纠错能力最低。（两个极端）3纠错编码理论的中心任务纠错编码理论的中心任务：在重复码和奇偶校验码之间寻找一些性能良好：在重复码和奇偶校验码之间寻找一些性能良好的码，使编码效率和检、纠错能力得到统一。的码，使编码效率和检、纠错能力得到统一。信息论与编码信息论与编码【例例】（2，1）重复码）重复码（2，1）重复码可以检出一个错误，但错误不能纠正。）重复码可以检出一个错误，但错误不能纠正。信息论与编码信息论与编码（
18、3，1）重复码）重复码（3，1）重复码可以检出最多不超过两个错误（作为检错码使用），）重复码可以检出最多不超过两个错误（作为检错码使用），能纠正一个错误（作为纠错码使用），但不能检出能纠正一个错误（作为纠错码使用），但不能检出3个错误。个错误。信息论与编码信息论与编码对应着对应着n为码字，长为为码字，长为n的二元序列的二元序列0112(,)nieeeeeF，u 当当ei=1时，表明码字中第时，表明码字中第i位位ci发生错误；发生错误；u 当当ei=0时，表明码字中第时，表明码字中第i位位ci没有错误。没有错误。称称 011(,)neeee，中中“1”的个数表示产生错误的个数，称错误图样的的个数
19、表示产生错误的个数，称错误图样的错误重数错误重数（t）。）。e设设 为码字在传输过程中发生错误而得到的接收字，则为码字在传输过程中发生错误而得到的接收字，则rrce信息论与编码信息论与编码【例例】（2，1）重复码）重复码（3，1）重复码）重复码信息论与编码信息论与编码 作为按照极大似然准则译码的纠错码，可以作为按照极大似然准则译码的纠错码，可以纠正该重错误图样的条件为：纠正该重错误图样的条件为：每个码字对应于该重错误图样的接收字集合中，每个码字对应于该重错误图样的接收字集合中，不可包含发送的码字。不可包含发送的码字。每个码字对应于该重错误图样的接收字集合中，每个码字对应于该重错误图样的接收字集
20、合中，不包含公共元素。不包含公共元素。每个码字对应于该重错误图样的接收字集合，与每个码字对应于该重错误图样的接收字集合，与其它码字的错误重数低的接收字集合中，不包含其它码字的错误重数低的接收字集合中，不包含公共元素。公共元素。信息论与编码信息论与编码1定义：定义：设设 是集合是集合Vn（F2）（）（n维向量空间维向量空间）中的任意两个字，令）中的任意两个字，令ab，011naaaa，011nbbbb，ai，bi取自取自G(F2)(0，1)规定规定 表示字表示字 的各对应码元之间不相同的个数，则的各对应码元之间不相同的个数，则 ()d ab，ab，1100()()nniiiiiid ababab
21、，称称 为为 之间的之间的汉明距离汉明距离，简称，简称距离距离。()d ab，ab，信息论与编码信息论与编码例如：例如：(01100)()2(11101)ad abb，说明：说明：收到接收字收到接收字 后，通过计算后，通过计算 与各码字与各码字 之间的汉明距离，如之间的汉明距离，如 与某一与某一码字码字 的汉明距离最小，则的汉明距离最小，则 与码字与码字 最像，译码器将最像，译码器将 译成译成 。rricrjcjcrrjcr 极大似然译码基础：收到的字是从一个码字经错传尽可能少的位而来的极大似然译码基础：收到的字是从一个码字经错传尽可能少的位而来的可能性较从一个码字经错传较多的位而来的可能性要
22、大。故通过判断汉可能性较从一个码字经错传较多的位而来的可能性要大。故通过判断汉明距离来译码，符合极大似然译码规则。明距离来译码，符合极大似然译码规则。如：如：pe10-5，则错一位的概率：，则错一位的概率：pe10-5，错两位的概率：，错两位的概率：pe10-10信息论与编码信息论与编码【例例】有码字有码字0123(10010)(01001)(10101)(01110)cccc，如接收字：如接收字：判断该接收字最有可能的码字。判断该接收字最有可能的码字。(10110)r 0()1d cr，1()5d cr，2()2d cr，3()2d cr，0rc2汉明距离的性质汉明距离的性质 自反性：自反性
23、：n2()d()0aV Faa，对称性：对称性：n2()()()abVFd abd ba，三角不等式：三角不等式：n2()abcVF，()()()d abd bcd ac，信息论与编码信息论与编码1码的最小距离码的最小距离码码C中不同码字之间距离的最小值称码中不同码字之间距离的最小值称码C的最小距离。的最小距离。minijijmin(),dd ccc cC ij，dmin是衡量码的检、纠错能力的一个重要的参数。是衡量码的检、纠错能力的一个重要的参数。2码的检、纠错能力与码的检、纠错能力与dmin的关系的关系 若若dmin t+1，则码，则码C可以检出所有不多于可以检出所有不多于t重的错误；重的
24、错误；信息论与编码信息论与编码 若若dmin 2t+1，则码，则码C可以纠正所有不多于可以纠正所有不多于t重的错误；重的错误；若若dmin 2t1+t2+1，则码，则码C可以纠正所有不多于可以纠正所有不多于t1重的错误，并能检重的错误，并能检出所有的从出所有的从t1+1到到（t1+t2）重的错误。）重的错误。信息论与编码信息论与编码1线性空间线性空间定义定义：如果域：如果域F上的上的n重元素集合重元素集合V满足下述条件时，满足下述条件时，V关于加法构成阿贝尔群；关于加法构成阿贝尔群；对对V中任何元素中任何元素 和和F中的任何元素中的任何元素a，称，称V中元素中元素 为矢为矢量（向量），量（向量
25、），F中元素中元素a称纯量（标量），称乘称纯量（标量），称乘a运算为数乘。运算为数乘。cacVc 分配律成立：分配律成立：,uvVa bF，()()a uvauavab uaubu()()11ab va bvvvF，若若,a bFvV，有有则称则称V是域是域F上的一个上的一个n维线性空间维线性空间（矢量空间），表示为：（矢量空间），表示为：Vn（F）信息论与编码信息论与编码2子空间子空间 线性空间线性空间Vn(F)中矢量中矢量 的所有线性组合所构成的集合的所有线性组合所构成的集合S是是Vn(F)的子空间。的子空间。12kvvv，1 122kkiubvb vb vbF3线性相关和线性无关线性相关
26、和线性无关设设 是线性空间是线性空间Vn(F)中的一组非全零矢量，当且仅当中的一组非全零矢量，当且仅当存在有一组不全为零的纯量存在有一组不全为零的纯量 12kvvv，12i()kaaa aF，使，使1 1220kka va va v成立时，称这组矢量线性相关，否则，称这组矢量成立时，称这组矢量线性相关，否则，称这组矢量线性无关线性无关（线性独立）。（线性独立）。即：若即：若12kvvv，线性无关，若等式成立，必有线性无关，若等式成立，必有120kaaa信息论与编码信息论与编码如：如：（1）123(010)(100)(001)000aaa则则1230aaa(010)(100)(001)故 线性无
27、关。（2）123(010)(100)(110)000aaa故 线性相关。则则1231aaa(010)(100)(110)线性相关的充要条件线性相关的充要条件：在线性空间中，对于矢量：在线性空间中，对于矢量 存在存在着一个矢量着一个矢量 ，它可以表示为其余矢量的线性，它可以表示为其余矢量的线性组合。组合。12kvvv，iv信息论与编码信息论与编码4矢量空间（线性空间）的基底矢量空间（线性空间）的基底如果存在一组线性无关的矢量如果存在一组线性无关的矢量 ，这些矢量的线性组合的，这些矢量的线性组合的集合可以构成一个矢量空间，则称这组矢量为这个矢量空间的集合可以构成一个矢量空间，则称这组矢量为这个矢量
28、空间的基底基底。12nvvv，n维矢量空间包含维矢量空间包含n个基底，也可以说，个基底，也可以说，n个基底个基底“张成张成”n维矢量空间。维矢量空间。如果如果 是是n维矢量空间维矢量空间Vn(F)中中k个线性无关的矢量，则这些个线性无关的矢量，则这些矢量线性组合的集合可构成矢量线性组合的集合可构成Vn(F)的一个的一个k维子空间，这维子空间，这k个矢量为子空间的个矢量为子空间的基底。基底。12kvvv，结论：（结论：（n，k）线性分组码可由）线性分组码可由k个线性独立的码字组成的基底张成。个线性独立的码字组成的基底张成。码矢量码矢量：由（：由（n，k）线性分组码的每个码字构成的矢量（码字）线性
29、分组码的每个码字构成的矢量（码字）字矢量字矢量：n维线性空间任一个字构成的矢量。维线性空间任一个字构成的矢量。信息论与编码信息论与编码1定义：（线性分组码的模型）定义：（线性分组码的模型）设设Vn(F2)是定义在是定义在F2上的一个上的一个n维的矢量空间，而维的矢量空间，而C是它的一个是它的一个k维的子维的子空间，则称空间，则称C是码长为是码长为n，消息位为，消息位为k的的线性分组码线性分组码或或（n，k）线性分组码）线性分组码。【例例】（6，3）分组码）分组码C0120 1 2 3 4 5()u u uc c c c c c编码规则：编码规则：001122301402512cucucucuu
30、cuucuu用矩阵表示：用矩阵表示：110100101010011001)()(210543210uuucccccc组成矩阵的三个组成矩阵的三个6维的行矢量是线性无关的，它构成了维的行矢量是线性无关的，它构成了V6(F2)上的一个上的一个3维子空间，故维子空间，故C是（是（6，3）线性分组码。）线性分组码。信息论与编码信息论与编码2线性分组码的矩阵描述：线性分组码的矩阵描述：设设011kggg，是（是（n，k）线性分组码中）线性分组码中k个线性无关的非零码字，个线性无关的非零码字，011(2)kuuuGF，则（则（n，k）线性分组码）线性分组码2k个码字中的任一码字个码字中的任一码字 可表示为
31、可表示为c001111kkcu gu gug用矩阵表示：用矩阵表示：010111()kkggcu Gu uug：长为：长为k的序列，构成的序列，构成2k个不同的消息。个不同的消息。011()kuu uu1,11,10,11,11,10,11,01,00,0110nkkknnkggggggggggggG生成矩阵生成矩阵信息论与编码信息论与编码【例例】（7，3）线性分组码，）线性分组码，k=3，2k=8（消息）（消息）012100111001001110011101ggg0012101221001110()()01001110011101gcu Gu u ugu u ug则：则：如：如：41001
32、110(110)0100111(1101001)0011101c信息论与编码信息论与编码3生成矩阵的性质生成矩阵的性质（1）如果）如果G是一个生成矩阵，那么与是一个生成矩阵，那么与G行等价的任一矩阵也是生成矩阵。行等价的任一矩阵也是生成矩阵。初等行变换初等行变换：任意两行交换；：任意两行交换；将任一行加到另一行；将任一行加到另一行；将任一行同乘一个数。将任一行同乘一个数。【例例】（6，3）线性分组码）线性分组码012345012100110()()101101011110c c c c c cu u u对对G作初等行变换：作初等行变换：01100110101011010011001110101
33、0110100110011011110110100110011101101110100231232rrrrrrG信息论与编码信息论与编码（2）每个线性分组码都有唯一的梯形生成矩阵）每个线性分组码都有唯一的梯形生成矩阵knkkPIG,（3）一个矢量空间的基底不止一个，）一个矢量空间的基底不止一个，G不唯一不唯一.（4）等价的各个）等价的各个G编出的码相同，但各消息对应的码字不同。编出的码相同，但各消息对应的码字不同。（5）生成矩阵）生成矩阵G中的每一个行矢量，不仅仅是张成中的每一个行矢量，不仅仅是张成k维线性空间的维线性空间的 基底矢量，本身也是一个码字。基底矢量，本身也是一个码字。（6）各个）
34、各个G编出的码相同，因此码集合的最小汉明距离编出的码相同，因此码集合的最小汉明距离dmin信息论与编码信息论与编码4系统码系统码：信息位以不变的形式在码组中出现的码称为系统码（出现的位置：信息位以不变的形式在码组中出现的码称为系统码（出现的位置一般在前面或后面）。一般在前面或后面）。如：前例（如：前例（7，3）线性分组码）线性分组码一般性结论：一般性结论：（1）每一个线性分组码都有一个与之等价的系统码存在；）每一个线性分组码都有一个与之等价的系统码存在；（2）（）（n，k）线性分组码系统码的生成矩阵是一个）线性分组码系统码的生成矩阵是一个kk的单位阵的单位阵 Ik 和和一个一个k(n-k)矩阵
35、矩阵Pkn-k组合而成的。组合而成的。（3）与非系统码相比，系统码编码过程及所需设备可以简化。）与非系统码相比，系统码编码过程及所需设备可以简化。信息论与编码信息论与编码1校验矩阵校验矩阵【例例】（6，3）线性分组码）线性分组码),(110100101010011001)()(212010210210543210uuuuuuuuuuuucccccc在码字中在码字中c0、c1、c2是信息位，是信息位，c3、c4、c5是冗余位（校验位）是冗余位（校验位）信息论与编码信息论与编码),()(212010210543210uuuuuuuuucccccc由校验位方程得：由校验位方程得：2121520204
36、10103ccuucccuucccuuc000521420310ccccccccc用矩阵表示用矩阵表示0100110010101001011543210cccccc0TH c即即（H为为nk行行n列的矩阵）列的矩阵）信息论与编码信息论与编码【例例】（1）（）（n，1）重复码，）重复码，k1校验位010100ucucucn000102010ncccccc01001010100111101nnnccc（2）（）（n，n-1）奇偶校验码）奇偶校验码)(2101221100校验位nnnnuuucucucuc0110nccc0111110nccc信息论与编码信息论与编码结论结论：一般的（：一般的（n，k
37、）线性分组码）线性分组码C总可以从该码的编码规则中选出（总可以从该码的编码规则中选出（n-k）个独立校验位方程，如将它们写成齐次线性方程的形式，则它们可以用个独立校验位方程，如将它们写成齐次线性方程的形式，则它们可以用矩阵表示为：矩阵表示为：0,00,10,101,01,11,111,01,11,110nnn kn kn knnhhhchhhchhhc 简记为：简记为：0TH c（H(nk)n为线性分组码的为线性分组码的校验矩阵校验矩阵）。）。说明：（说明：（1）矩阵）矩阵H的的n-k个行矢量是线性独立的，它们的不同组合张成了个行矢量是线性独立的，它们的不同组合张成了 Vn（F2）上的一个）上
38、的一个n-k维的子空间。维的子空间。（2）0()000TTTTTH cHu GH G uH Gcu GH的行空间与的行空间与G的行空间是相互正交的（对偶的）。的行空间是相互正交的（对偶的）。信息论与编码信息论与编码2对偶码对偶码生成矩阵生成矩阵G的的k行矢量组成行矢量组成Vn(F2)的的k维子空间（码字空间维子空间（码字空间C）；）；校验矩阵校验矩阵H的的n-k个行矢量组成个行矢量组成Vn(F2)的的n-k维的子空间维的子空间(C的对偶子空间的对偶子空间C)。对偶码定义对偶码定义：C是是Vn（F2）的一个子空间，它的维数为）的一个子空间，它的维数为n-k，因此可以，因此可以把把C看作是一个二元
39、（看作是一个二元（n，n-k）线性分组码，并把它称为）线性分组码，并把它称为C的对偶码。的对偶码。结论：设结论：设C是（是（n，k）线性分组码，其生成矩阵为）线性分组码，其生成矩阵为G，那么码，那么码C的对偶码的对偶码C的生成矩阵的生成矩阵H就是码就是码C的校验矩阵。的校验矩阵。3线性分组码的译码问题线性分组码的译码问题由于生成矩阵和校验矩阵的行空间是对偶的，因此我们可以利用这种对由于生成矩阵和校验矩阵的行空间是对偶的，因此我们可以利用这种对偶特性来判断接收到的任一矢量是否为码矢量，这在原则上提供了一种解决偶特性来判断接收到的任一矢量是否为码矢量，这在原则上提供了一种解决线性分组码的译码问题的
40、途径。线性分组码的译码问题的途径。2()rVn FrC，的充要条件是：的充要条件是：即：即：0TH r 信息论与编码信息论与编码4生成矩阵生成矩阵G与校验矩阵与校验矩阵H的梯形矩阵的关系的梯形矩阵的关系（1）每个线性分组码的生成矩阵存在唯一的）每个线性分组码的生成矩阵存在唯一的kn的梯形矩阵；的梯形矩阵；（2）每个线性分组码的校验矩阵存在唯一的）每个线性分组码的校验矩阵存在唯一的(n-k)n的梯形矩阵；的梯形矩阵；（3）如）如G有有 Ik P 的形式，则的形式，则H有有 PT In-k 的形式（条件：在的形式（条件：在F2中）。中）。【例例】110100101010011001G1001100
41、10101001011H信息论与编码信息论与编码1定义定义设设 ，令，令 为码字为码字 中不为零码元的个数，即中不为零码元的个数，即 011(,)ncc ccC()w cc100()1iniicw cc称称 为码字为码字 的的汉明重量汉明重量，简称，简称重量重量。()w cc2最小重量：码最小重量：码C中非零码字重量的最小值中非零码字重量的最小值min()min()0wCw c cCc，信息论与编码信息论与编码3任一码字的重量都可以看作是该码字与任一码字的重量都可以看作是该码字与0码字之间的汉明距离码字之间的汉明距离10(0)()niid ccw c，4定理：任一线性分组码的最小距离等于它的最
42、小重量。定理：任一线性分组码的最小距离等于它的最小重量。证明：证明：12ccC，1121212120()(0)()niiid ccccd ccw cc，由于由于C是线性码，故是线性码，故 ，即线性分组码中任意两个码，即线性分组码中任意两个码矢量间的距离等于另一个码矢的重量，即矢量间的距离等于另一个码矢的重量，即12()ccC12123()()()d ccw ccw c，312()cccC故故121212333min()min()0d ccccC ccw ccC c，信息论与编码信息论与编码定理：设定理：设C是线性分组码，是线性分组码，H是它的校验矩阵，那么码是它的校验矩阵，那么码C的最小重量就
43、等于的最小重量就等于H中线性相关的最小列数。因此，如果中线性相关的最小列数。因此，如果H中的中的2t个和小于个和小于2t个列的任一个列的任一子集都线性无关，而子集都线性无关，而H中有中有2t+1个列线性相关，那么码个列线性相关，那么码C就是纠正就是纠正t个个错误的纠错码，或能检出错误的纠错码，或能检出2t个错误的检错码。个错误的检错码。【例例】（7，4）线性分组码）线性分组码011110010110101101001H线性相关的最小列数为线性相关的最小列数为3故：故：wmin(C)=3推论：如果推论：如果H的任意小于等于的任意小于等于t个列的线性组合都不相同，那么个列的线性组合都不相同，那么w
44、min(C)2t+1，即，即C是能纠正重数小于等于是能纠正重数小于等于t的纠错码。的纠错码。信息论与编码信息论与编码定义定义：设：设G是非空集合，在是非空集合，在G中规定一种运算中规定一种运算“*”，,*a bGa bG，即运算，即运算*在在G中是封闭的。中是封闭的。同时要求：同时要求：（2）eG，对一切的，对一切的aG，使，使 a*e=a，e为恒元；为恒元；（1）,a b cG(*)*(*)a bcab c，有，有结合律；结合律；（3）aG1aG，有，有a*a-1=e，存在逆元，存在逆元a-1。，若以上条件均满足，称若以上条件均满足，称G对于对于“*”运算是一个群。运算是一个群。交换群交换群
45、（阿贝尔群）：（阿贝尔群）：a*b=b*a(满足交换律满足交换律)加法群加法群：运算：运算“*”为加法运算。为加法运算。e：零元素：零元素乘法群乘法群：运算：运算“*”为乘法运算。为乘法运算。e：单位元：单位元有限群有限群：G中只含有有限个元，元的个数称群的阶。中只含有有限个元，元的个数称群的阶。信息论与编码信息论与编码1子群子群：设：设G是一个群，而是一个群，而G0是是G的一个非空子集，若的一个非空子集，若G0在在G规定的运算下规定的运算下 满足群的条件，则满足群的条件，则G0是是G的子群。的子群。2群按子群展开（陪集展开）群按子群展开（陪集展开）设加群设加群G的子群的子群123rHhehh
46、h，展开步骤：展开步骤：（1）把）把H的元依次排在第一行；的元依次排在第一行；（2）取不属于）取不属于H的的G中的任一元，记为中的任一元，记为g1，将它与，将它与H中的元依次相加，结中的元依次相加，结果记为果记为 ，并依次，并依次排在第二行；排在第二行；111112131rgHghgghghgh，（3）再取不属于）再取不属于H又不属于又不属于g1+H的的G中的任一元中的任一元g2，将它与，将它与H中的元依次中的元依次相加，结果记为相加，结果记为 ，并依次排在第三行；并依次排在第三行；221222232rgHghgghghgh，（4）按步骤继续下去，直到排完）按步骤继续下去，直到排完G中所有的元
47、。中所有的元。信息论与编码信息论与编码Hh1=e h2.hrg1+Hg1g1+h2.g1+hrg2+Hg2g2+h2.g2+hr.gn+Hgngn+h2.gn+hr 把把 叫做叫做H的一的一个个陪集陪集。而。而g称为该陪集的一个代表元或称为该陪集的一个代表元或陪集首陪集首（e，g1，g2，.，gn）。）。123iiiiiirgHghgghghgh，信息论与编码信息论与编码【例例】V4（F2）的模）的模2加群：子群加群：子群H=0000，0101，1110，1011，陪集展开。，陪集展开。H00000101111010110110H01100011100011011111H11111010000
48、101000010H0010011111001001结论：（结论：（1）G的每一个元素仅在且至少在子群的每一个元素仅在且至少在子群H的一个陪集中的一个陪集中 （2）设）设G是个交换群，是个交换群，H是它的一个子群，那么是它的一个子群，那么G可以唯一地表示可以唯一地表示为为H的一些两两没有公共元的陪集的并。的一些两两没有公共元的陪集的并。()iIGgH信息论与编码信息论与编码1定义：所有构成群的码称为群码。定义：所有构成群的码称为群码。2定理：二元分组码对于码字的模定理：二元分组码对于码字的模2加法成群的充要条件：码是线性的。加法成群的充要条件：码是线性的。1伴随式（校验子）伴随式（校验子）对任
49、一错误图样对任一错误图样 ，接受字可表示为：，接受字可表示为：erce()TTTTTH rH ceH cH e由于由于c是码字，是码字，0TH c，故，故TTTH rH es称称 为接收字为接收字 的的伴随式伴随式或或校验子校验子，它是一个，它是一个n-k维的行矢量。维的行矢量。sr信息论与编码信息论与编码2定理：任意两个长定理：任意两个长n的二元矢量的二元矢量 ，如果对群码，如果对群码C的校验矩阵有相的校验矩阵有相同的伴随式，即同的伴随式，即 ，那么，那么 属于群码属于群码C的同一个的同一个陪集（有相同的陪集首）陪集（有相同的陪集首）。12rr，12TTH rH r12rr，在全部长为在全部
50、长为n的二元序列按线性码的二元序列按线性码C的陪集展开中，陪集首可以用该陪的陪集展开中，陪集首可以用该陪集中的任意序列担任，而不会改变此陪集的元，只是他们的排列次序有所变集中的任意序列担任，而不会改变此陪集的元，只是他们的排列次序有所变动。动。标准阵列：标准阵列：全体长全体长n的二元序列按线性码的二元序列按线性码C的以陪集中最小重量的字作为陪的以陪集中最小重量的字作为陪集首的陪集展开就称为集首的陪集展开就称为C的标准阵列。的标准阵列。信息论与编码信息论与编码【例例】（4，2）系统线性码）系统线性码C=0000，0101，1110，1011，其标准阵列为，其标准阵列为 码字码字伴随式伴随式000
