第3章线性分组码.ppt

《第3章线性分组码.ppt》由会员分享，可在线阅读，更多相关《第3章线性分组码.ppt（39页珍藏版）》请在课桌文档上搜索。

1、1,第3章 线性分组码,3.1 线性分组码的基本概念 3.2 码的一致校验矩阵与生成矩阵 3.3 伴随式与标准阵列及其它译码 3.4 线性码的覆盖半径 3.5 由一个已知码构造新码的简单方法 3.6 用多个已知码构造新码的方法 3.7 线性码的重量分布与译码错误概率 3.8 线性码的纠错能力,2,3.1 线性分组码的基本概念,线性空间设V 是一个非空集合,P 是一个数域,在集合V 中定义了一种代数运算，叫做加法:即对在V 中都存在唯一的一个元素，称为与的和，记为：；在P与V的元素之间还定义了一种运算，叫做数量乘法：即在V中都存在唯一的一个元素与它们对应，称为 的数量乘积，记为 如果加法和数量乘

2、法还满足下述规则，则称V 为数域P上的线性空间：,3,3.1 线性分组码的基本概念,加法满足下列四条规则：,在V中有一个元素0，对,（具有这个性质的元素0称为V的零元素）,;（称为 的负元素）,4,3.1 线性分组码的基本概念,数量乘法与加法满足下列两条规则：,数量乘法满足下列两条规则:,5,3.1 线性分组码的基本概念,线性空间的性质零元素是唯一的负元素是唯一的，-唯一关于0元素有如果,6,3.1 线性分组码的基本概念,线性分组码定义n,k线性分组码是GF(q)上的n维线性空间中的一个k维子空间。线性分组码的基本特性：线性结构。即如果 c1、c2 分别是信息序列 m1、m2的码字，则 c1+

3、c2 必定是信息序列 m1+m2 的码字。两码字C1和C2之间的距离d(C1,C2)必等于第三个码字C1+C2的汉明重量。n,k,d线性分组码的最小距离等于非零码字的最小重量,7,3.1 线性分组码的基本概念,GF(2)上n，k，d线性分组码中，任何两个码字C1，C2之间有如下关系：w(C1+C2)=w(C1)+w(C2)-2w(C1C2)或 d(C1，C2)w(C1)+w(C2)式中，C1C2是两个码字的内积。GF(2)上线性分组码任3个码字C1，C2，C3之间的汉明距离，满足以下三角不等式d(C1，C2)+d(C2，C3)d(C1，C3)任何n，k，d线性分组码，码字的重量或全部为偶数，或

4、者奇数重量的码字数等于偶数重量的码字数。,8,3.2 码的一致校验矩阵与生成矩阵,n，k，d分组码在n 维线性空间Vn 中，如何找出满足一定要求的，有2k 个矢量组成的k 维线性子空间Vn,k。在满足给定条件(码的最小距离d或码率R)下，如何从已知的k 个信息元求得r=n-k 个校验元。,9,3.2 码的一致校验矩阵与生成矩阵,码的生成矩阵（k 维线性子空间）由于n,k,d线性分组码是一个k维线性空间。因此必可找到k个线性无关的矢量，能张成该线性空间。设 是k个线性无关的矢量，则对任意,，可有：,G称为该分组码的生成矩阵,10,3.2 码的一致校验矩阵与生成矩阵,例：一个7,3 码，m2 m1

5、 m0 c6 c5 c4 c3 c2 c1 c0，如果码字的生成规则为：,若用矩阵形式表示这些线性方程组，则：,11,3.2 码的一致校验矩阵与生成矩阵,则矩阵 就是该7,3 码的生成矩阵。注：生成矩阵G中的每一行都是一个码字任意k个线性独立的码字都可以作为生成矩阵给定一个n,k,d线性分组码，其生成矩阵可有多个,12,3.2 码的一致校验矩阵与生成矩阵,码的校验矩阵(求r=n-k 个校验元),n-k个校验位可用k个已知的信息位表示出来,13,3.2 码的一致校验矩阵与生成矩阵,校验矩阵H与任意一个码字之积为零，因此有,14,3.2 码的一致校验矩阵与生成矩阵,例,c6+c4+c3=0 c6+

6、c5+c4+c2=0 c6+c5+c1=0 c5+c4+c0=0,15,3.2 码的一致校验矩阵与生成矩阵,c6+c4+c3=0 c6+c5+c4+c2=0 c6+c5+c1=0 c5+c4+c0=0,16,3.2 码的一致校验矩阵与生成矩阵,系统码、对偶码和缩短码系统码若信息组以不变的形式在码组的任意k 位(通常在最前面：cn-1，cn-2，cn-k)中出现的码称为系统码，生成矩阵和校验矩阵应该具有性质,17,3.2 码的一致校验矩阵与生成矩阵,7，3，4码,18,3.2 码的一致校验矩阵与生成矩阵,对偶码设C是n,k,d码，则它的对偶码C是 CxV n,(n-k)；对所有yC使xy=0 式

7、中，xy为x与y的内积。由G生成的n,k,d码C与由H生成的n,n-k,d码C互为对偶码。,19,3.2 码的一致校验矩阵与生成矩阵,缩短码 缩短码是k 维子空间Vn,k 中取前i位均为0的码字组成的一个子集,该子集组成了一个n i,k-i分组码。n i,k-i缩短码的纠错能力至少与原n,k 码相同。n i,k-i缩短码是n,k 码缩短i位得到的，因而码率R 比原码要小，但纠错能力不一定比原码强。,20,3.3 伴随式与标准阵列及译码,伴随式(校正子)设发送的码字C=(cn-1，cn-2，c1，c0)，通过有扰信道传输，信道产生的错误图样 E=(en-1，en-2，e1，e0)。接收端译码器收

8、到的n 重为R=(rn-1，rn-2，r1，r0)，R=C+E，ri=ci+ei，ci，ri，eiGF(q)或GF(2)中。RHT=(C+E)HT=CHT+EHT=EHT 令 S=RHT=EHT 称为接收向量R的伴随式(校正子),21,3.3 伴随式与标准阵列及译码,第i1，i2，it位有错：E=(0，ei1，0，ei2，0，eit，0，0),22,3.3 伴随式与标准阵列及译码,n，k，d码要纠正t个错误，则要求t 个错误的所有可能组合的错误图样，都应该有不同的伴随式与之对应，则其充要条件是H矩阵中任何2t列线性无关。ei1hi1+ei2hi2+eithitej1hj1+ej2hj2+ejt

9、hjtei1hi1+ei2hi2+eithit-ej1hj1-ej2hj2-eithjt0T定理:n，k，d线性分组码有最小距离等于d的充要条件是，H矩阵中任意d-1列线性无关。,23,3.3 伴随式与标准阵列及译码,(Singleton 限)n，k，d线性分组码的最大可能的最小距离等于n-k+1，即dn-k+1。若系统码的最小距离d=n-k+1，则称此码为极大最小距离可分码，简称MDS码。,24,3.3 伴随式与标准阵列及译码,汉明码（纠正单个错误）GF(2)上汉明码的H矩阵的列，是由所有的非零的二进制m维向量组成。该码有如下参数：n=2m-1，k=2m-1-m，R=(2m-1-m)(2m-

10、1)，d=3。纠正一个错误的n，k，d分组码，要求其H矩阵中任意两列线性无关，且不能全为0。若为二进制码，则要求H矩阵中每列互不相同，且不能全为0。,25,3.3 伴随式与标准阵列及译码,例 构造GF(2)上的7，4，3汉明码。n=2m-1，k=2m-1-m，R=(2m-1-m)(2m-1)，d=3。取m=3，所有23=8个三重为：000，100，010，001，011，101，110，111。若码字传输中第一位发生错误，则相应的伴随式S=(001)，它就是“1”的二进制表示，若第五位发生错误，伴随式S=(101)，是“5”的二进制表示。,26,3.3 伴随式与标准阵列及译码,27,3.3 伴

11、随式与标准阵列及译码,标准阵列n,k,d分组码的译码步骤可归结为以下三步：(1)由接收到的R，计算伴随式S=RHT；(2)若S=0，则认为接收无误。若S0，则由S找出错误图样；(3)由 和R找出。汉明码译码简单，由S可直接找到，其他码比较复杂。,28,3.3 伴随式与标准阵列及译码,以2k 个码字为基础，把n 维空间的2n 个元素划分陪集，则得到如下所示的译码表。2n-k 个陪集，称C1，E2，E3，为陪集首。按这种方法构成的表称为标准阵译码表，简称标准阵。,29,3.3 伴随式与标准阵列及译码,问题是：如何划分陪集使译码错误概率最小？挑选重量最轻的n 重为陪集首，放在标准阵中的第一列，而以全

12、为0码字作为子群的陪集首。也称为最小距离译码，在BSC下等效于最大似然译码。用这种标准阵译码，需要把2n 个n 重存储在译码器中。译码器的复杂性随n 指数增长，很不实用。简化译码表错误图样与伴随式一一对应。,30,3.3 伴随式与标准阵列及译码,6，3码标准阵,31,3.3 伴随式与标准阵列及译码,即使用简化译码表，译码器的复杂性还是很高的。例如，一个100，70分组码，一共有230109个伴随式及错误图样。,32,3.5 由一个已知码构造新码的简单方法,扩展码 设C是一个最小距离为d的二进制n，k，d线性分组码，若对每一个码字(cn-1，cn-2，c1，c0)增加一个校验元c0，满足以下校验

13、关系：cn-1+cn-2+c1+c0+c0=0 称c0为全校验位。,33,3.5 由一个已知码构造新码的简单方法,删余码 删余码是由扩展码的逆过程而得到的。它在原n，k 码C的基础上，删去一个校验元而构成，变为n-1，k 删余码C*。C*码的最小距离可能比原码小1，也可能不变。,34,3.6 用多个已知码构造新码的方法,直和 设C1和C2分别是n 1，k 1，d1和 n 2，k 2，d2二进制码，且n1=n2，C1C2=0，则定义C1和C2码的直和码C1C2=C是n，k1+k2，d C=(ab)aC1，bC2dmin d1，d2,35,3.6 用多个已知码构造新码的方法,笛卡儿积 由C1和C2

14、码的笛卡儿积C1C2得到的码是 C=C1C2=(a，b)aC1，bC2 C码是一个n 1+n 2，k 1+k 2，min d1，d2码。,36,3.6 用多个已知码构造新码的方法,直积(Kronecker积)C1和C2码的直积C1 C2=C，是一个n1n2，k1k2，d1d2码。式中，gij是C1码生成矩阵中第i行第j列元素。,37,3.7 线性码的重量分布与译码错误概率,设Ai是n，k，d分组码中重量为i的码字数目，则集合A0，A1，An称为该分组码的重量分布。称A(x)为码的重量估值算子，简称重量算子。例如7，4，3汉明码的重量分布为Ai=A0，A1，A2，A3，A4，A5，A6，A7=1，0，0，7，7，0，0，1其中，一个全0码字(A0=1)是任何线性码所必须有的。,38,3.7 线性码的重量分布与译码错误概率,定理：设二进制n，k线性分组码及其n，n-k对偶码的重量算子分别是：,则它们之间有如下关系：,称此式为马克威伦(MacWilliams)恒等式。,39,3.7 线性码的重量分布与译码错误概率,若码字等概发送，n，k，d二进制线性分组码的不可检错误概率,