信息论与编码纠错第7章.ppt

《信息论与编码纠错第7章.ppt》由会员分享，可在线阅读，更多相关《信息论与编码纠错第7章.ppt（60页珍藏版）》请在三一文库上搜索。

1、第七章 线性分组码,内容提要,目前，几乎所有得到实际应用的纠错码都是线性的。本章首先介绍有关纠错码的基本概念，然后重点论述线性分组码的定义及其编译码理论。在此基础上，介绍了一种典型的线性分组码：汉明码。 掌握内容：线性分组码的概念，生成矩阵，校验矩阵，最小距离，伴随式，标准阵列等。,7.1 纠错编码的基本概念,一信道纠错编码,近年来，随着计算机、卫星通信及高速数据网的飞速发展，数据的交换、处理和存储技术得到了广泛的应用，人们对数据传输和存储系统的可靠性提出了越来越高的要求。因此，如何控制差错、提高数据传输和存储的可靠性，成为现代数字通信系统设计工作者面临的重要课题。 香农第二定理指出，当信息传

2、输速率低于信道容量时，通过某种编译码方法，就能使错误概率为任意小。目前已有了许多有效的编译码方法，并形成了一门新的技术纠错编码技术。 这里所讲的纠错编码即信道编码，与信源编码一样都是一种编码，但两者的作用是完全不同的。,信源编码的目的是压缩冗余度，提高信息的传输速率。 信道编码的目的是提高信息传输时的抗干扰能力以增加信息传输的可靠性。,二差错控制系统模型及分类,1差错控制系统模型,模型突出了以控制差错为目的的纠错码编、译码器，因此也称为差错控制系统。,2差错控制系统的分类,按其纠错能力的不同可分为两种：检错码和纠错码。, 检错码：能发现错误但不能纠正错误的码； 纠错码：不仅能发现错误而且还能纠

3、正错误的码。,按差错控制系统类型，可分为前向纠错、重传反馈和混合纠错等三种方式。, 前向纠错(FEC)方式 ：,FEC (Forward Error Control) 方式是发端发送有纠错能力的码（纠错码），接收端收到这些码后，通过纠错译码器自动地纠正传输中的错误。,优点：是不需要反馈信道；能进行一个用户对多个用户的同时通信，特别适合于移动通信；译码实时性较好，控制电路也比较简单。 缺点：是译码设备较复杂；编码效率较低。, 重传反馈(ARQ)方式:,ARQ (Automatic Repeat Request) 方式是：发端发出能够发现错误的码（检错码），收端译码器收到后，判断在传输中有无错误产

4、生，并通过反馈信道把捡测结果告诉发端。发端把收端认为有错的消息再次传送，直到收端认为正确接收为止。,优点：译码设备简单，在多余度一定的情况下，码的检错能力比纠错能力要高得多，因而整个系统能获得极低的误码率。 缺点：应用ARQ方式必须有一条从收端至发端的反馈信道。并要求信源产生信息的速率可以进行控制，收、发两端必须互相配合，其控制电路比较复杂，传输信息的连贯性和实时性也较差。, 混合纠错(HEC)方式：,HEC (Hybrid Error Control) 方式是上述两种方式的结合。发端发送的码既能检错、又有一定的纠错能力。收端译码时若发现错误个数在码的纠错能力以内，则自动进行纠错；若错误个数超

5、过了码的纠错能力，但能检测出来，则通过反馈信道告知发方重发。这种方式在一定程度上避免了 FEC方式译码设备复杂和 ARQ方式信息连贯性差的缺点。,在设计差错控制系统时，选择何种实现方式，应综合考虑各方面的因素。主要有： 满足用户对误码率的要求； 有尽可能高的信息传输速率； 有尽可能简单的编译码算法且易于实现； (4) 可接受的成本。,三纠错码的分类,常用的纠错码按其码字结构形式和对信息序列处理方式的不同可分成两大类：分组码和卷积码。,分组码：把信息序列以每k个码元分组，编码器将每个信息组按一定规律产 生r个多余的码元（称为校验元），形成一个长为n = k + r 的码字。,对于k个码元分组，共

6、有2k个不同的信息组，编码器输出长n的2k个码字，这2k个长为n的码字构成的集合称为一个（n，k）分组码。,n：码长；k：信息位的数目；R = k / n：分组码码率。,卷积码：把信息序列以每k个分组，通过编码器输出长为n（n k）的一个子码。但是该子码的nk个校验元不仅与本子码的信息元有关，而且也与其前m个子码的信息元有关。,四差错类型,讨论码字序列通过离散信道时发生的情况，信道分为无记忆信道和有记忆信道。,在无记忆信道中，噪声对传输码元的影响是相互独立的，即每一个差错的出现与其前后是否有错无关，如图所示。在无记忆信道中，错误是随机产生的，因此被称作随机错误，无记忆信道也被称为随机信道（ra

7、ndom channel）。,有记忆信道中，各种干扰所造成的错误往往不是单个地，而是成群、成串地出现，表现出错误之间有相关性，称为突发错误。下图就是这种信道的一个模型。,就实际信道而言，由于其干扰的复杂性，往往是两种错误并存。随机错误与突发错误并存的信道，称为组合信道或复合信道。,7.2 分组码及检、纠错能力的获得,一分组码定义,设消息或数据以二进制形式表示，并以F2 = 0 , 1 表示这个二元集。,设消息集是长为k的二元消息序列集，表示如下：,1分组编码：,在长为n的二元序列集中 选出与消息序列数2k相同数目的码元序列，并使两者一一对应。,几个概念：,2消息 与码字 的映射关系（函数关系）

8、,线性分组码： 与 呈线性关系（fi为线性函数）,非线性分组码： 与 不呈线性关系（fi为非线性函数）,对于消息为k位，码长为n的线性分组码称（n，k）线性分组码。,由最后一个方程：,（奇）偶校验码：码字中1的个数为偶数。,在接收到一个字中1的个数不是偶数时，就可以确定接收的不是码字。这种码能检出奇数个错误，但不能发现偶数个错误。,比较上面两例编码方案：, 重复码：R = 1/n，编码效率最低，检纠错能力最高。 奇偶校验码：R = (n-1)/n，编码效率最高，检纠错能力最低。（两个极端）,3纠错编码理论的中心任务：在重复码和奇偶校验码之间寻找一些性能良好的码，使编码效率和检、纠错能力得到统一

9、。,二分组码检、纠错能力的获得,【例】（2，1）重复码,（2，1）重复码可以检出一个错误，但错误不能纠正。,（3，1）重复码,（3，1）重复码可以检出最多不超过两个错误（作为检错码使用），能纠正一个错误（作为纠错码使用），但不能检出3个错误。,三错误图样,中“1”的个数表示产生错误的个数，称错误图样的错误重数（t）。,设 为码字在传输过程中发生错误而得到的接收字，则,【例】（2，1）重复码,（3，1）重复码,作为按照极大似然准则译码的纠错码，可以纠正该重错误图样的条件为： 每个码字对应于该重错误图样的接收字集合中，不可包含发送的码字。 每个码字对应于该重错误图样的接收字集合中，不包含公共元素。

10、 每个码字对应于该重错误图样的接收字集合，与其它码字的错误重数低的接收字集合中，不包含公共元素。,7.3 汉明距离和分组码的检、纠错能力,一汉明距离,1定义：,设 是集合Vn（F2）（ n维向量空间）中的任意两个字，令,ai，bi取自G(F2) (0，1),规定 表示字 的各对应码元之间不相同的个数，则,称 为 之间的汉明距离，简称距离。,例如：,说明：, 收到接收字 后，通过计算 与各码字 之间的汉明距离，如 与某一码字 的汉明距离最小，则 与码字 最像，译码器将 译成 。, 极大似然译码基础：收到的字是从一个码字经错传尽可能少的位而来的可能性较从一个码字经错传较多的位而来的可能性要大。故通

11、过判断汉明距离来译码，符合极大似然译码规则。,如：pe10-5，则错一位的概率：pe10-5，错两位的概率：pe10-10,2汉明距离的性质, 自反性：, 对称性：, 三角不等式：,二分组码的检、纠错能力与最小汉明距离之间的关系,1码的最小距离,码C中不同码字之间距离的最小值称码C的最小距离。,dmin是衡量码的检、纠错能力的一个重要的参数。,2码的检、纠错能力与dmin的关系, 若dmin t + 1，则码C可以检出所有不多于t重的错误；, 若dmin 2t + 1，则码C可以纠正所有不多于t重的错误；, 若dmin 2t1 + t2 + 1，则码C可以纠正所有不多于t1重的错误，并能检出所

12、有的从t1+1到（t1+t2）重的错误。,7.4 线性分组码及其矩阵描述,一基本概念,1线性空间,定义：如果域F上的n重元素集合V满足下述条件时，, V关于加法构成阿贝尔群；, 对V中任何元素 和F中的任何元素a， ，称V中元素 为矢量（向量），F中元素a称纯量（标量），称乘a运算为数乘。, 分配律成立：,则称V是域F上的一个n维线性空间（矢量空间），表示为：Vn（F）,2子空间,线性空间Vn(F)中矢量 的所有线性组合所构成的集合S是Vn(F)的子空间。,3线性相关和线性无关,如：,（1）,（2）,线性相关的充要条件：在线性空间中，对于矢量 存在着一个矢量 ，它可以表示为其余矢量的线性组合。

13、,4矢量空间（线性空间）的基底,如果存在一组线性无关的矢量 ，这些矢量的线性组合的集合可以构成一个矢量空间，则称这组矢量为这个矢量空间的基底。,n维矢量空间包含n个基底，也可以说，n个基底“张成”n维矢量空间。,如果 是n维矢量空间Vn(F)中k个线性无关的矢量，则这些矢量线性组合的集合可构成Vn(F)的一个k维子空间，这k个矢量为子空间的基底。,结论：（n，k）线性分组码可由k个线性独立的码字组成的基底张成。,码矢量：由（n，k）线性分组码的每个码字构成的矢量（码字） 字矢量：n维线性空间任一个字构成的矢量。,二线性分组码的矩阵描述,1定义：（线性分组码的模型）,设Vn(F2)是定义在F2上

14、的一个n维的矢量空间，而C是它的一个k维的子空间，则称C是码长为n，消息位为k的线性分组码或（n，k）线性分组码。,【例】（6，3）分组码C,编码规则：,用矩阵表示：,组成矩阵的三个6维的行矢量是线性无关的，它构成了V6(F2)上的一个3维子空间，故C是（6，3）线性分组码。,2线性分组码的矩阵描述：,则（n，k）线性分组码2k个码字中的任一码字 可表示为,用矩阵表示：,：长为k的序列，构成2k个不同的消息。,生成矩阵,【例】（7，3）线性分组码，k = 3，2k = 8（消息）,则：,如：,3生成矩阵的性质,（1）如果G是一个生成矩阵，那么与G行等价的任一矩阵也是生成矩阵。,初等行变换：任意

15、两行交换； 将任一行加到另一行； 将任一行同乘一个数。,【例】（6，3）线性分组码,对G作初等行变换：,（2）每个线性分组码都有唯一的梯形生成矩阵,（3）一个矢量空间的基底不止一个，G不唯一.,（4）等价的各个G编出的码相同，但各消息对应的码字不同。,（5）生成矩阵G中的每一个行矢量，不仅仅是张成k维线性空间的 基底矢量，本身也是一个码字。,（6）各个G编出的码相同，因此码集合的最小汉明距离dmin 不变， 因此码的检纠错能力不变，因此可以寻找最容易实现的编码 方案。,4系统码：信息位以不变的形式在码组中出现的码称为系统码（出现的位置一般在前面或后面）。,如：前例（7，3）线性分组码,一般性结

16、论：,（1）每一个线性分组码都有一个与之等价的系统码存在； （2）（n，k）线性分组码系统码的生成矩阵是一个kk的单位阵 Ik 和一个k(n-k)矩阵Pkn-k组合而成的。 （3）与非系统码相比，系统码编码过程及所需设备可以简化。,三线性分组码的校验矩阵,1校验矩阵,【例】（6，3）线性分组码,在码字中c0、c1、c2是信息位，c3、c4、c5是冗余位（校验位）,由校验位方程得：,用矩阵表示,【例】（1）（n，1）重复码，k1,（2）（n，n-1）奇偶校验码,结论：一般的（n，k）线性分组码C总可以从该码的编码规则中选出（n-k）个独立校验位方程，如将它们写成齐次线性方程的形式，则它们可以用矩

17、阵表示为：,说明：（1）矩阵H的n-k个行矢量是线性独立的，它们的不同组合张成了 Vn（F2）上的一个n-k维的子空间。,2对偶码,对偶码定义：C是Vn（F2）的一个子空间，它的维数为n-k，因此可以把C看作是一个二元（n，n-k）线性分组码，并把它称为C的对偶码。,结论：设C是（n，k）线性分组码，其生成矩阵为G，那么码C的对偶码C的生成矩阵H就是码C的校验矩阵。,3线性分组码的译码问题,由于生成矩阵和校验矩阵的行空间是对偶的，因此我们可以利用这种对偶特性来判断接收到的任一矢量是否为码矢量，这在原则上提供了一种解决线性分组码的译码问题的途径。,4生成矩阵G与校验矩阵H的梯形矩阵的关系,（1）

18、每个线性分组码的生成矩阵存在唯一的kn的梯形矩阵； （2）每个线性分组码的校验矩阵存在唯一的(n-k)n的梯形矩阵； （3）如G有 Ik P 的形式，则H有 PT In-k 的形式（条件：在F2中）。,【例】,7.5 线性分组码的检、纠错能力,一码字重量,1定义,设 ，令 为码字 中不为零码元的个数，即,称 为码字 的汉明重量，简称重量。,2最小重量：码C中非零码字重量的最小值,3任一码字的重量都可以看作是该码字与0码字之间的汉明距离,4定理：任一线性分组码的最小距离等于它的最小重量。,证明：,由于C是线性码，故 ，即线性分组码中任意两个码矢量间的距离等于另一个码矢的重量，即,故,二线性分组码

19、的检、纠错能力与H矩阵的关系,定理：设C是线性分组码，H是它的校验矩阵，那么码C的最小重量就等于H中线性相关的最小列数。因此，如果H中的2t个和小于2t个列的任一子集都线性无关，而H中有2t+1个列线性相关，那么码C就是纠正t个错误的纠错码，或能检出2t个错误的检错码。,【例】（7，4）线性分组码,线性相关的最小列数为3,故：wmin(C)=3,推论：如果H的任意小于等于t个列的线性组合都不相同，那么wmin(C) 2t+1，即C是能纠正重数小于等于t的纠错码。,7.6 群及其性质,一群的概念,定义：设G是非空集合，在G中规定一种运算“ * ”，,，即运算*在G中是封闭的。,同时要求：,若以上

20、条件均满足，称G对于“*”运算是一个群。,交换群（阿贝尔群）：a * b = b * a (满足交换律) 加法群：运算“*”为加法运算。e：零元素 乘法群：运算“*”为乘法运算。e：单位元 有限群：G中只含有有限个元，元的个数称群的阶。,二子群和陪集展开,1子群：设G是一个群，而G0是G的一个非空子集，若G0在G规定的运算下 满足群的条件，则G0是G的子群。,2群按子群展开（陪集展开）,设加群G的子群,展开步骤：,（1）把H的元依次排在第一行；,（2）取不属于H的G中的任一元，记为g1，将它与H中的元依次相加，结果记为 ，并依次排在第二行；,（3）再取不属于H又不属于g1+H的G中的任一元g2

21、，将它与H中的元依次相加，结果记为 ，并依次排在第三行；,（4）按步骤继续下去，直到排完G中所有的元。,把 叫做H的一个陪集。而g称为该陪集的一个代表元或陪集首（e，g1，g2，.，gn）。,【例】V4（F2）的模2加群：子群H = 0000，0101，1110，1011，陪集展开。,结论：（1）G的每一个元素仅在且至少在子群H的一个陪集中 （2）设G是个交换群，H是它的一个子群，那么G可以唯一地表示为H的一些两两没有公共元的陪集的并。,7.7 线性码的伴随式译码和标准阵列,一群码,1定义：所有构成群的码称为群码。,2定理：二元分组码对于码字的模2加法成群的充要条件：码是线性的。,二伴随式,1

22、伴随式（校验子）,对任一错误图样 ，接受字可表示为：,称 为接收字 的伴随式或校验子，它是一个n-k维的行矢量。,2定理：任意两个长n的二元矢量 ，如果对群码C的校验矩阵有相同的伴随式，即 ，那么 属于群码C的同一个陪集（有相同的陪集首） 。,三标准阵列：,在全部长为n的二元序列按线性码C的陪集展开中，陪集首可以用该陪集中的任意序列担任，而不会改变此陪集的元，只是他们的排列次序有所变动。,标准阵列：全体长n的二元序列按线性码C的以陪集中最小重量的字作为陪集首的陪集展开就称为C的标准阵列。,【例】（4，2）系统线性码C = 0000，0101，1110，1011，其标准阵列为,说明：对于（4，2

23、）线性码，码字的最小重量为2，可以检出一个错误，实际上按标准阵列展开的陪集就是码字错误图样为陪集首的接收字。,四伴随式译码,1标准阵列法：,按标准阵列的陪集展开实际上就构成了线性码的译码表，因此完全可以通过标准阵列来译码。其中，陪集首就是线性码可以纠错的错误图样。,2伴随式译码,（1）原理：对于码C的同一陪集，有相同的伴随式和陪集首(错误图样 ），因此，只要知道伴随式与陪集首的对应关系，通过计算接收字的伴随式，就可以知道错误图样，从而进行译码。,（3）优点：不用记住整张译码表（标准阵列），只需记住伴随式与陪集首相对应的表。,【例】（7，3）线性分组码,能纠正1重错误，同时检出2重错误 。,如：

24、 （一个错）,7.8 汉明码,一基本概念,汉明码：一类能纠单个错误的纠错码。,二纠单个错误的线性分组码,【例】（7，4）线性码,（1）H中列为非全零元素；,（2）H中任意两列都不相同，但存 在相加等于0的三个列的子集。,H中线性相关的最小列数为3，故 ，该码是纠单个错误的码。,定理：C是一个线性分组码，H是校验矩阵，C是可以纠单个错误的纠错码的充要条件：,（1）H中没有元素全为0的列矢量； （2）H中任意两个列矢量都不相同。,（3）若 ，但不等于H中的任一列，则错误不能纠正。,几个结论：对于具有纠单个错误能力的线性分组码。,（1）若接收矢量的伴随式 ，则译码器认为接收矢量没有错误；,（2）如果

25、 ，且 等于H矩阵中的某一列，则译码器纠认为接收矢量在该列对应校验矩阵中的位置出错，此时只需将接收字该位置的码元取反就能纠错；,【例】,（1）,伴随式对应于H中的第五列，故：,（2）,H中无对应列与之对应，不能正确译码。,结论：为了得到具有纠一个错误的二元（n，n-m）线性码，（其中n-m=k，m为校验位的个数），只需从定义在F2上的m维非零列矢量中选取彼此不同的n个列矢量H0、H1、.、Hn-1并依任意次序把它们排成一个mn的矩阵：,那么以H为校验矩阵的二元（n，n-m）线性码C就是一个可以纠正所有单个错误的的码。,三汉明码：,1定义：令H是二元 m（2m-1）矩阵，这个矩阵的列是Vm（F2）中按某种次序排列的2m-1个非零矢量，那么定义在F2上的n=2m-1，k = 2m-1-m的线性分组码（校验矩阵为H）就称为长2m-1的汉明码。,如：,的（7，4）线性分组码就是汉明码,m=3，n=23-1=7，k=7-3=4,2定理：二元（2m-1，2m-1-m）汉明码是能够纠单个错误的线性码，而且是校验位数为m的所有二元线性码中编码效率最高的码，其最小重量：wmin（C）=3。,3完备码：设C是（n，k）线性分组码，其纠错能力为t，如果用且只用小于等于t个错误的全部错误图样作为陪集首就能做成标准阵列，那么称这个码为完备码。,