《第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 分别是信
3、息序列 m1、m2的码字,则 c1+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
4、, C3)d(C1, C3) 任何n , k , d线性分组码, 码字的重量或全部为偶数, 或者奇数重量的码字数等于偶数重量的码字数。,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个线性无关的
5、矢量,则对任意,,可有:,G称为该分组码的生成矩阵,10,3.2 码的一致校验矩阵与生成矩阵,例:一个7, 3 码,m2 m1 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 码
6、的一致校验矩阵与生成矩阵,校验矩阵H与任意一个码字之积为零,因此有,14,3.2 码的一致校验矩阵与生成矩阵,例,c6 +c4+c3 =0 c6+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 )中出现的码称为系统码,生成矩阵和校验矩阵应该具有
7、性质,17,3.2 码的一致校验矩阵与生成矩阵,7, 3, 4码,18,3.2 码的一致校验矩阵与生成矩阵,对偶码 设C是n , k , d码, 则它的对偶码C是 CxV n , (n -k ); 对所有yC使xy=0 式中, 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位得
8、到的, 因而码率R 比原码要小, 但纠错能力不一定比原码强。,20,3.3 伴随式与标准阵列及译码,伴随式(校正子) 设发送的码字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)中。 RHT=(C+E)HT=CHT+EHT=EHT 令 S=RHT=EHT 称为接收向量R的伴随式(校正子),21,3.3 伴随式与标准阵列及译码,第i1, i
9、2, , it位有错: E =(0, , ei1, 0, , ei2, 0, , eit, 0, , 0) ,22,3.3 伴随式与标准阵列及译码,n , k , d码要纠正t个错误, 则要求t 个错误的所有可能组合的错误图样, 都应该有不同的伴随式与之对应,则其充要条件是H矩阵中任何2t列线性无关。 ei1hi1+ei2hi2+eithitej1hj1+ej2hj2+ejthjt ei1hi1+ei2hi2+eithit-ej1hj1-ej2hj2-eithjt0T 定理:n , k , d线性分组码有最小距离等于d的充要条件是, H矩阵中任意d-1列线性无关。,23,3.3 伴随式与标准阵
10、列及译码,(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-1), d=3。 纠正一个错误的n , k , d分组码, 要求其H矩阵中任意两列线性无关, 且不能全为0。 若为二进制码, 则要求H矩阵中每列互不相同, 且不能
11、全为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 伴随式与标准阵列及译码,标准阵列 n , k , d分组码的译码步骤可归结为以下三步: (1)
12、 由接收到的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 重为陪集首, 放在标准阵中的第一列, 而以全为0码字作为子群的陪集首
13、。 也称为最小距离译码,在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,
14、 满足以下校验关系: 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, bC2 dmin d1, d2,35,3.
15、6 用多个已知码构造新码的方法,笛卡儿积 由C1和C2码的笛卡儿积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二进制线性分组码的不可检错误概率,
链接地址:https://www.31doc.com/p-2979518.html