第3章线性分组码.ppt
第3章 线性分组码 1第第3章章 线性分组码线性分组码o 3.1 线性分组码的基本概念线性分组码的基本概念 o 3.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 o 3.3 伴随式与标准阵列及其它译码伴随式与标准阵列及其它译码 o 3.4 线性码的覆盖半径 o 3.5 由一个已知码构造新码的简单方法由一个已知码构造新码的简单方法 o 3.6 用多个已知码构造新码的方法用多个已知码构造新码的方法 o 3.7 线性码的重量分布与译码错误概率线性码的重量分布与译码错误概率 o 3.8 线性码的纠错能力第3章 线性分组码 23.1 线性分组码的基本概念线性分组码的基本概念 o 线性空间n 设设V 是一个非空集合是一个非空集合,P 是一个数域是一个数域,在集合在集合V 中定义中定义了一种代数运算，叫做了一种代数运算，叫做加法加法:即对在即对在V 中都存在唯一中都存在唯一的一个元素的一个元素，称，称为与的的和和，记为：，记为：；在；在P与与V的元素之间还定义了一种运算，的元素之间还定义了一种运算，叫做叫做数量乘法数量乘法：即：即在在V中都存在唯一的一个元素中都存在唯一的一个元素与它们对应，称与它们对应，称为为 的的数量乘积数量乘积，记为，记为 如果加法和数量乘法如果加法和数量乘法还满足下述规则，则称还满足下述规则，则称V 为数域为数域P上的上的线性空间线性空间：,VkP k 与与.k 第3章 线性分组码 33.1 线性分组码的基本概念线性分组码的基本概念 加法满足下列四条规则：加法满足下列四条规则：对对,V都有都有V中的一个元素中的一个元素，使得，使得 在在V中有一个元素中有一个元素0，对，对,0V有有（具有这个性质的元素（具有这个性质的元素0称为称为V的的零元素零元素）;（称为称为 的的负元素负元素）0 ()(),V 第3章 线性分组码 43.1 线性分组码的基本概念线性分组码的基本概念 1 ()()k lkl 数量乘法与加法满足下列两条规则：数量乘法与加法满足下列两条规则：()klkl 数量乘法满足下列两条规则数量乘法满足下列两条规则:()kkk第3章 线性分组码 53.1 线性分组码的基本概念线性分组码的基本概念 o 线性空间的性质n 零元素是唯一的零元素是唯一的n 负元素是唯一的，负元素是唯一的，-唯一唯一n 关于关于0元素有元素有n 如果如果V 00,00,(1),()kkkk 如果如果k0，那么，那么k0或或 0.第3章 线性分组码 63.1 线性分组码的基本概念线性分组码的基本概念 o 线性分组码定义n n,k线性分组码是GF(q)上的n维线性空间中的一个k维子空间。n 线性分组码的基本特性：线性结构。即如果 c1、c2 分别是信息序列 m1、m2的码字，则 c1+c2 必定是信息序列 m1+m2 的码字。两码字C1和C2之间的距离d(C1,C2)必等于第三个码字C1+C2的汉明重量。n,k,d线性分组码的最小距离等于非零码字的最小重量,()minimiCn kdw C第3章 线性分组码 73.1 线性分组码的基本概念线性分组码的基本概念 o GF(2)上n，k，d线性分组码中，任何两个码字C1，C2之间有如下关系：w(C1+C2)=w(C1)+w(C2)-2w(C1C2)或 d(C1，C2)w(C1)+w(C2)式中，C1C2是两个码字的内积。o GF(2)上线性分组码任3个码字C1，C2，C3之间的汉明距离，满足以下三角不等式d(C1，C2)+d(C2，C3)d(C1，C3)o 任何n，k，d线性分组码，码字的重量或全部为偶数，或者奇数重量的码字数等于偶数重量的码字数。第3章 线性分组码 83.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 o n，k，d分组码o 在n 维线性空间Vn 中，如何找出满足一定要求的，有2k 个矢量组成的k 维线性子空间Vn,k。o 在满足给定条件(码的最小距离d或码率R)下，如何从已知的k 个信息元求得r=n-k 个校验元。第3章 线性分组码 93.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 o 码的生成矩阵（k 维线性子空间）n 由于n,k,d线性分组码是一个k维线性空间。因此必可找到k个线性无关的矢量，能张成该线性空间。设 是k个线性无关的矢量，则对任意kCCC,21C，可有：kkmmmCCCC2211mGCCCkkmmm2121,G称为该分组码的生成矩阵第3章 线性分组码 103.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 n 例：一个7,3 码，m2 m1 m0 c6 c5 c4 c3 c2 c1 c0，如果码字的生成规则为：21010 0 1 1 100 10 0 1 1 10 0 1 1 1 0 1Cmmm6251403202210121010 cmcmcmcmmcmmmcmmcmm 若用矩阵形式表示这些线性方程组，则：第3章 线性分组码 113.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 o 则矩阵 就是该7,3 码的生成矩阵。注：1)生成矩阵生成矩阵G中的每一行都是一个码字中的每一行都是一个码字2)任意任意k个线性独立的码字都可以作为生成矩阵个线性独立的码字都可以作为生成矩阵3)给定一个给定一个n,k,d线性分组码，其生成矩阵可有多个线性分组码，其生成矩阵可有多个10 0 1 1 100 10 0 1 1 10 0 1 1 1 0 1G第3章 线性分组码 123.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 o 码的校验矩阵(求r=n-k 个校验元)n-k个校验位可用k个已知的信息位表示出来个校验位个信息位knknknkknnncccccc02121knknnnnnknknknnnknnnknknknknknnnknnnknknchchchcchchchcchchchc,022,011,00,222,211,22,122,111,11第3章 线性分组码 133.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 000100010001021)(,011,0,21,2,11,1ccchhhhhhnnnknknnknknnknknknnkn列行，校验矩阵校验矩阵校验矩阵H与任意一个码字之积为零，因此有TT0H G1,111,221,12,112,222,20,110,220,0000n knnn knnn kn kn kn kn knnn knnn kn kn kn knnnnn kn khchchcchchchcchchchcc 第3章 线性分组码 143.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 n 例36542654165406541101111111101011cccccccccccccccc c6 +c4+c3 =0 c6+c5+c4 +c2 =0 c6+c5 +c1 =0 c5+c4 +c0=0第3章 线性分组码 153.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 1000110010001100101110001101H c6 +c4+c3 =0 c6+c5+c4 +c2 =0 c6+c5 +c1 =0 c5+c4 +c0=0第3章 线性分组码 163.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 o 系统码、对偶码和缩短码n 系统码n 若信息组以不变的形式在码组的任意k 位(通常在最前面：cn-1，cn-2，cn-k)中出现的码称为系统码，生成矩阵和校验矩阵应该具有性质PIGkknTIPHk 位信息位 n-k 位校验位 0knkTIPPIHG第3章 线性分组码 173.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 o 7，3，4码PIG310111001110010011100141000110010001100101110001101IPHT第3章 线性分组码 183.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 o 对偶码设C是n,k,d码，则它的对偶码C是 CxV n,(n-k)；对所有yC使xy=0 式中，xy为x与y的内积。n 由G生成的n,k,d码C与由H生成的n,n-k,d码C互为对偶码。TT0H G第3章 线性分组码 193.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 o 缩短码 缩短码是k 维子空间Vn,k 中取前i位均为0的码字组成的一个子集,该子集组成了一个n i,k-i分组码。n n i,k-i缩短码的纠错能力至少与原n,k 码相同。n n i,k-i缩短码是n,k 码缩短i位得到的，因而码率R 比原码要小，但纠错能力不一定比原码强。第3章 线性分组码 203.3 伴随式与标准阵列及译码伴随式与标准阵列及译码o 伴随式(校正子)o 设发送的码字C=(cn-1，cn-2，c1，c0)，通过有扰信道传输，信道产生的错误图样错误图样 E=(en-1，en-2，e1，e0)。接收端译码器收到的n 重为R=(rn-1，rn-2，r1，r0)，R=C+E，ri=ci+ei，ci，ri，eiGF(q)或GF(2)中。o RHT=(C+E)HT=CHT+EHT=EHT 令 S=RHT=EHT 称为接收向量R的伴随式伴随式(校正子校正子)第3章 线性分组码 213.3 伴随式与标准阵列及译码伴随式与标准阵列及译码第i1，i2，it位有错：E=(0，ei1，0，ei2，0，eit，0，0)1210nnHhhhh121210112200TnTnTiiitTTTTTiiiiitithhSE Heeehhe he he h第3章 线性分组码 223.3 伴随式与标准阵列及译码伴随式与标准阵列及译码o n，k，d码要纠正t个错误，则要求t 个错误的所有可能组合的错误图样，都应该有不同的伴随式与之对应，则其充要条件是H矩阵中任何2t列线性无关。ei1hi1+ei2hi2+eithitej1hj1+ej2hj2+ejthjtei1hi1+ei2hi2+eithit-ej1hj1-ej2hj2-eithjt0To 定理:n，k，d线性分组码有最小距离等于d的充要条件是，H矩阵中任意d-1列线性无关。第3章 线性分组码 233.3 伴随式与标准阵列及译码伴随式与标准阵列及译码o(Singleton 限)n，k，d线性分组码的最大可能的最小距离等于n-k+1，即dn-k+1。o 若系统码的最小距离d=n-k+1，则称此码为极大最小距离可分码，简称MDS码。第3章 线性分组码 243.3 伴随式与标准阵列及译码伴随式与标准阵列及译码o 汉明码（纠正单个错误）o GF(2)上汉明码的H矩阵的列，是由所有的非零的二进制m维向量组成。o 该码有如下参数：n=2m-1，k=2m-1-m，R=(2m-1-m)(2m-1)，d=3。o 纠正一个错误的n，k，d分组码，要求其H矩阵中任意两列线性无关，且不能全为0。若为二进制码，则要求H矩阵中每列互不相同，且不能全为0。第3章 线性分组码 253.3 伴随式与标准阵列及译码伴随式与标准阵列及译码o 例 构造GF(2)上的7，4，3汉明码。n=2m-1，k=2m-1-m，R=(2m-1-m)(2m-1)，d=3。o 取m=3，所有23=8个三重为：000，100，010，001，011，101，110，111。o 若码字传输中第一位发生错误，则相应的伴随式S=(001)，它就是“1”的二进制表示，若第五位发生错误，伴随式S=(101)，是“5”的二进制表示。101010111001101111000H第3章 线性分组码 263.3 伴随式与标准阵列及译码伴随式与标准阵列及译码3100110101011100011011IPHTpIG41111000110010001100101010001第3章 线性分组码 273.3 伴随式与标准阵列及译码伴随式与标准阵列及译码o 标准阵列n,k,d分组码的译码步骤可归结为以下三步：(1)由接收到的R，计算伴随式S=RHT；(2)
