信息与编码课件...ppt

1、第二部分 编码理论,第七章 线性码,第七章 线性码,7.1 生成和一致校验矩阵 7.2 q进制对称信道上的伴随式译码 7.3 汉明几何和码的性能 7.4 汉明码 7.5 一般q进制对称信道上的伴随式译码 7.6 重量牧举多项式和MacWilliams恒等式,7.1 生成和一致校验矩阵,定义： Fq上的一个(n,k)线性码，是n维矢量空间Vn(Fq)=(x1,x2,xn):xiFq的一个k维子空间；n称为码的长度，k称为为数。码的速率为k/n。,7.1 生成和一致校验矩阵,(n,k)线性分组码是把信息流分割成一串前后独立的kbit信息组,再将每组信息元映射成由n个码元组成的码字(codeword

2、)。k信息元组可以写成矢量u=(u1,u2,uk) 或矩阵u1,u2,uk的形式。码字C可写成 c= c1, ,cn-1. 线性分组码码空间C是由k个线性无关的基底g1 , , gk 张成的k维n重子空间,码空间的所有码字都可以写成k个基底的线性组合，即 C=u1g1+ukgk。 这里gk是n重矢量。写成1n的矩阵形式： gk=gk1,gk2,gkn,7.1 生成和一致校验矩阵,将这k个基底码字排列成一个kn的矩阵G,则G称为C的生成矩阵。,7.1 生成和一致校验矩阵,定义：令C是Fq上的一个(n,k)线性码。一个行空间等于C的k n阶矩阵G称为C的生成矩阵。相反，如果G是元素取自Fq的一个矩

3、阵，则它的行空间称为由G生成的码。 由于k个基底即G的k个行矢量线性无关 , 矩阵G的秩一定等于 k。当信息元确定后,码字仅由G矩阵决定, 因此称这kn矩阵 G为该 ( n, k ) 线 性分组码的生成矩阵。 将信息u映射为码字x的规则是： x=uG,7.1 生成和一致校验矩阵,例7.1 一个(5,1)线性码C1，具有生成矩阵G1=1,1,1,1,1. 显然C1仅含有两个码字00000和11111；速率R=1/5。 （重复编码） 例7.2 一个(5,3)线性码C2，具有生成矩阵,例7.3 一个(7,4)线性码C3，具有生成矩阵 （(7,4)含明码）,7.1 生成和一致校验矩阵,基底不是惟一的,

4、生成矩阵也就不是惟一的。事实上,将k个基底线性组合后产生另一组 k 个矢量 , 只要满足线性无关的条件 , 依然可以作为基底张成一个码空间。不同的基底有可能生成同一码集 , 但因编码涉及码集和映射两个因素 , 码集一样而映射方法不同也不能说是同样的码。 基底的线性组合等效于生成矩阵 G 的行运算 , 可以 产生一组 新的基底。,7.1 生成和一致校验矩阵,性质：如果G是C的生成矩阵，则任意与G行等价的矩阵也是C的生成矩阵。 任意生成矩阵等价于一个行递减阶梯(RRE)矩阵，任意线性码都具有唯一的一个RRE生成矩阵。 域F上RRE的矩阵的三个性质： （a）每行最左边的非零元素是1. （b）每个包含

5、这样一个最左1元素的列中的其他元素都为0。 （c）如果第i行的最左非零元素出现在第ti列上，则t1t2.tr。,7.1 生成和一致校验矩阵,可见G1和G3是RRE形式了，当G2不是。G2的唯一RRE生成矩阵为：,7.1 生成和一致校验矩阵,定义：存在一个编码规则，使信息符号独立地出现在码字中，就称为它是系统的。 反之,不具备“系统”特性的码叫非系统码。非系统码与系 统码并无本质的区别,它的生成矩阵可以通过行运算转变为系统形式,这个过程叫系统化。系统化不改变码集 , 只改变映射规则。 所有的线性码都是系统的。 对于无记忆信道，对G进行列置换并不会改变码的性能，因此在这种情况下总可以假设G=IkA

6、。,7.1 生成和一致校验矩阵,与任何一个(n,k)分组线性码的码空间C相对应,一定存在一个对 偶空间D。事实上, 码空间基底数k只是 n维n重空间全部 n个基底的一部分,若能找出另外n-k个基底,也就找到了对偶空间D。 既然用k个基底能产生一个(n,k)分组线性码,那么也就能用n-k个 基底产生包含2n-k个码字的(n,n-k)分组线性码,称(n,n-k)码是(n,k )码的对偶码。 将D空间的n-k个基底排列起来可构成一个(n-k) n矩阵,将这个矩阵称为码空间C的校验矩阵H,而它正是(n,n-k )对偶码的生成矩阵,它的每一行是对偶码的一个码字。 C和D的对偶是相互的,G是C的生成矩阵又

7、是D的校验矩阵,而H是D的生 成矩阵,又是C的校验矩阵.,7.1 生成和一致校验矩阵,由于C的基底和D的基底正交,空间C和空间D也正交,它们互为零空间。因此,(n,k) 线性码的任意码字x一定正交于其对偶码的 任意一个码字,也必定正交于校验矩阵H的任意一个行矢量 , 即 xHT= 0或HxT=0 该式可以用来检验一个 n重矢量是否为码字: 若等式成立( 得零矢量), 该n重必为码字,否则不是码字。 由于生成矩阵的每个行矢量都是一个码字, 因此必有 GHT=0 对于G=IkA, 必然有H=-ATIn-k。,7.1 生成和一致校验矩阵,如果G不具有这种形式，则可以通过列置换为IkA形式，然后再对-

8、ATIn-k进行逆置换而得到H。 例如有G1,G2和G3生成的一致校验矩阵是：,7.1 生成和一致校验矩阵,定理7.1,令C是Fq上的一个(n,k)线性码，则存在唯一的一个kn阶RRE矩阵G,满足xC，当且仅当x在G的行空间内。另外，存在一个(n-k)n阶矩阵H，满足xC当且仅当HxT=0。如果码C被用于一个无记忆信道，则不失一般性，可以假设存在一个k (n-k)阶矩阵A，使得： G=IkA, H=-ATIn-k 在这种情况下，矢量uVk(Fq)的编码由u(u,uA)给出。,7.2 q进制对称信道上的伴随式译码,假定信道输出符号集AY=Fq,即输入与输出符号集相同。因此如果传输的是x=(x1,

9、x2,xn)Vn(Fq)，则接收矢量y=(y1,y2,yn)也属于Vn(Fq)；两者的差值z=y-x称为错误图案。如果zi0，我们就称在第i个位置上出现了一个错误。,错误图案,7.2 q进制对称信道上的伴随式译码,伴随式,如果传输的是x,输出的是y。引进矢量s=HyT,称为y的伴随式。伴随式最重要的特性是，它只依赖于错误图案z而不依赖于所传输的码字，即 s=HyT=H(x+z)T=HzT 由于y是已知的，则只要知道了z，就能求得x。伴随式提供了z的一些信息，但不够充分。因为对于一个固定的s，方程HzT=s的解的集合形成了码C的一个陪集，即一个具有如下形式的Vn(Fq)的子集：C+z0=x+z0

10、:xC,7.2 q进制对称信道上的伴随式译码,对应于qn-k个伴随式s,码C一共有qn-k个陪集；每个陪集包含qk个元素。因此一旦接收方计算出s，就可以将z的搜寻范围从qn种可能降低到qk种可能，即搜寻范围是与s相对应的陪集元素。,7.2 q进制对称信道上的伴随式译码,假设信道是q进制对称信道(qSC)，即如果X是表示信道输入的随机矢量，Y是表示信道输出的随机矢量，则Y=X+Z，Z是一个随机矢量,它的分量是独立、同分布的随机变量，具有相同的分布： PZ=0=1-(q-1)。 PZ=z且z0= 对于这个信道，zVn(Fq),则 P(Z=z)=1-(q-1)n-WH(Z) WH(Z) wH(Z)为

11、z的汉明重量，被定义为z中非零分量的个数，即出现错误的个数。,7.2 q进制对称信道上的伴随式译码,如果1/q，则上式就是wH(Z)的递减函数，因此最有可能的z是具有最小重量的z。 所以q进制对称信道上的伴随式译码算法如下： 1. 计算伴随式s=HyT 2. 在对应于s的陪集中找出最小重量矢量，称为z0。 3. 输出码字x=y-z0。,7.2 q进制对称信道上的伴随式译码,例 考虑码C2,它的一致校验矩阵是： 只有四个可能的伴随式:00,01,10,11。,7.3 汉明几何和码的性能,汉明距离,定义两个矢量x和y之间的汉明距离为： dH(x,y)=分量xiyi的个数=wH(y-x) 它满足真正

12、的测度所具有的下列性质： （a）d(x,x)=0 （b）如果xy,则d(x,y)0 （c）d(x,y)=d(y,x) （d）d(x,y)d(x,z)+d(z,y),7.3 汉明几何和码的性能,汉明几何,假设希望码C能够纠正汉明重量e的错误图案，即如果发送xi, 接收到y= xi+z,如果wH(z)e，则译码器的输出x=xi。 对于qSC，译码的最佳策略是使dH(xi,y)最小的那个码字。 如果采用这种几何译码策略，则码能够纠正所有重量e的错误图案的充分必要条件是，每一对码字之间的距离都2e+1。,7.3 汉明几何和码的性能,定义：码C的最小距离为： dmin(C)=mindH(x,x)： x,

13、xC, xx 定理7.2 码C=x1,x2,.,xM能够纠正所有重量e的错误图案，当且仅当dmin(C)2e+1。 定义：码C的最小重量 wmin(C)=minwH(x):xC,x0,7.3 汉明几何和码的性能,如果C是线性码，则x-x也是C的一个码字， 因为dH(x, x)=wH(x-x)，则dmin(C)=wmin(C)。 这样计算量从qk(qk-1)/2减少到qk 。 定理7.3 如果C是Fq上的一个(n,k)线性码，具有一致校验矩阵H，则dmin(C)=H中线性相关列的最小数目。因此如果H中任意2t及更少的列所组成的子集都是线性无关的，则这个码能够纠正所有重量t的错误图案。 推论：如果

14、q=2,且H中e列的所有可能线性组合都不同，则dmin(C) 2e+1,由此可知C能纠正重量e的错误图案。,7.3 汉明几何和码的性能,例题,H1的任意4列或更少列的子集是不相关的，但5列相关。故dmin(C1)=5；而H2中的第3、4列相关，故dmin(C2)=2；因H3中的列不为零也不相同，故dmin(C3)3,但H3中的第1、2、3相关。故dmin(C3)=3.,7.4 汉明码,定义 令H是一个m(2m-1)阶二进制矩阵，H的列是Vm(F2)中以某种顺序排列的2m-1个非零矢量。则在F2上，一致校验矩阵为H的线性码被称码长为2m-1的汉明码。,7.4 汉明码,完备码,(n,k)线性分组码

15、的n个码元中,无一差错的图案有Cn0个, , t个差错的图案有Cnt 个。另一方面,(n,k)分组码有2n-k个伴随式, 假 如该码的纠错能力是t,则对于任何一个重量小于等于t的差错图案,都应有一个伴随式与之对应,即伴随式的数目应满足条件： 2n-k Cn0+.+ Cnt 如果能使等式成立的(n,k)线性分组码，称为完备码。,7.4 汉明码,完备码特性,围绕2k个码字、汉明距d=(dmin-1)/2的所有球都是不相交的,每一个接收码字都落在这些球中之一,因此接收码离发送码 的距离至多为t,这时所有重量t的差错图案都能用最佳(最小距离)译码器得到纠正。 迄今发现的完备码有t=1的汉明码, t =

16、 3 的高莱码,以及长度n为奇数、由两个码字组成、满足 dmin= n的任何二进制码,还有三进制t=3的(11, 6)码。,7.4 汉明码,汉明码特性,（1）H中的列是2m-1个二进制数字的一个排列。（定义） （2）汉明码是纠错能力t=1的线性码。 （3）汉明码是完备码。 （4）汉明码非常容易实现伴随式译码。,7.4 汉明码,汉明码译码,1. 计算伴随式s=HyT。 2. 如果s=0,输出x=y。 3. 否则s等于H的i列，则错误图案z在第i位上为1，其它位为0,输出x=y-z。,7.5 一般q进制信道上的伴随式译码,对于qSC,噪声样本概率分布为： PZ=0=1-(q-1) PZ=z且z0=

17、 对于一般q进制信道上噪声样本概率分布为：PZ=z=p(z)。 这样伴随式译码方式如下： 1. 计算伴随式s=HyT。 2. 在对应于s的陪集中，寻找最大的P(z)的矢量，称之为z0。 3. 输出码字x=y-z0。,7.5 一般q进制信道上的伴随式译码,这种译码方式存在两个难点： （1）步骤2很难实现。 （2）实际很难获取p(z)，只能通过经验获取，即估计。 令F为Vn(Fq)的一个子集，将F看作信道上具有“中等”以上发生的概率的错误图案的集合；E为F的一个子集，将E看作是具有“高”发生概率的错误图案的集合。给定一个线性码C，希望设计一个译码器，它能够检测到F中的错误图案，并能纠正E中的错误图

18、案。,7.5 一般q进制信道上的伴随式译码,这意味着，允许译码器输出一个码字x或一个特殊的删除符号“?”。假设发送的是x，接收的是y=x+z，则有三种可能： （a）译码器输出x=x。（错误图案被纠正了） （b）译码器输出xx。 （产生一个错误） （c）译码器输出“?”。（检测到一个错误）,7.5 一般q进制信道上的伴随式译码,定义 如果可以设计码C的译码器，它能够纠正E中的错误图案z，并能够纠正或检测F中的错误图案z，则称码C为E纠错、F检错码。 定理7.4 令C是Fq上的一个(n,k)线性码，具有一致校验矩阵H，并令EF为Vn(Fq)的子集。则C为E纠错、F检错码的充分必要条件是它具有下列性质： （a）z1,z2E, z1z2,则Hz1THz1T （b）z1E, z2F-E,则Hz1THz1T,7.5 一般q进制信道上的伴随式译码,例7.4 令C是(7,3)码，具有： 令E=z：wH(z) 1, F=z：wH(z) 2 则C为E纠错、F检错码,7.6 重量牧举多项式和MacWilliams恒等式,如果C是一个(n,k)线性码，则它的重量牧举多项式为 A(z)=A0+A1z+.+AnZn 其中Ai表示码C中汉明重量为i的