中南大学信息论与编码讲义-第七章

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是一个随机矢量,它的分量是独立、同分布的随机变量，具 有相同的分布： P{Z=0}=1-(q-1)ε。 P{Z=z且z≠0}= ε 对于这个信道，z∈Vn(Fq),则 P(Z=z)=[1-(q-1)ε]n-WH(Z) εWH(Z) wH(Z)为z的汉明重量，被定义为z中非零分量的个数，即出现 错误的个数。
7.1 生成和一致校验矩阵
将这k个基底码字排列成一个k×n的矩阵G
g11 g G = 21 ... g k1 g12 g 22 ... gk 2 ... g1n ... g 2 n ... ... ... g kn
则G称为C的生成矩阵。
7.1 生成和一致校验矩阵
定义：令C是Fq上的一个(n,k)线性码。一个行空间等于C的k × n阶矩阵G称为C的生成矩阵。相反，如果G是元素取自Fq的一 个矩阵，则它的行空间称为由G生成的码。 由于k个基底即G的k个行矢量线性无关 , 矩阵G的秩一定等 于 k。当信息元确定后,码字仅由G矩阵决定, 因此称这k×n矩 阵 G为该 ( n, k ) 线 性分组码的生成矩阵。 将信息u映射为码字x的规则是： x=uG
第二部分 编码理论
第七章 线性码
第七章 线性码
• • • • • • 7.1 生成和一致校验矩阵 7.2 q进制对称信道上的伴随式译码 7.3 汉明几何和码的性能 7.4 汉明码 7.5 一般q进制对称信道上的伴随式译码 7.6 重量牧举多项式和MacWilliams恒等 式
7.1 生成和一致校验矩阵
7.1 生成和一致校验矩阵
如果G不具有这种形式，则可以通过列置换为[IkA]形式，然后 再对[-ATIn-k]进行逆置换而得到H。 例如有G1,G2和G3生成的一致校验矩阵是：
1 1 H1 = 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
1 1 0 0 0 H2 = 1 0 1 1 1
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:x∈C}
7.2 q进制对称信道上的伴随式 译码
• 错误图案
假定信道输出符号集AY=Fq,即输入与输出符号集相同。 因此如果传输的是x=(x1,x2,…,xn)∈Vn(Fq)，则接收矢量 y=(y1,y2,…,yn)也属于Vn(Fq)；两者的差值z=y-x称为错误图案。 如果zi≠0，我们就称在第i个位置上出现了一个错误。
0 1 1 1 1 0 0 H 3 = 1 0 1 1 0 1 0 生成和一致校验矩阵
• 定理7.1
令C是Fq上的一个(n,k)线性码，则存在唯一的一个k×n阶RRE 矩阵G,满足x∈C，当且仅当x在G的行空间内。另外，存在一 个(n-k)×n阶矩阵H，满足x∈C当且仅当HxT=0。如果码C被用 于一个无记忆信道，则不失一般性，可以假设存在一个k ×(n-k)阶矩阵A，使得： G=[IkA], H=[-ATIn-k] 在这种情况下，矢量u∈Vk(Fq)的编码由u→(u,uA)给出。
例 考虑码C2,它的一致校验矩阵是： 只有四个可能的伴随式:00,01,10,11。
伴随式 00 01 10 11 陪集首 00000 00100 01000 10000
1 1 0 0 0 H2 = 1 0 1 1 1
0 0 0 11 0 0 11 1 0 1 0 11 1 0 0 11
7.2 q进制对称信道上的伴随式 译码
如果ε≤1/q，则上式就是wH(Z)的递减函数，因此最有 可能的z是具有最小重量的z。 所以q进制对称信道上的伴随式译码算法如下： 1. 计算伴随式s=HyT 2. 在对应于s的陪集中找出最小重量矢量，称为z0。 3. 输出码字x=y-z0。
7.2 q进制对称信道上的伴随式 译码
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的错误图案。 推论：如果q=2,且H中≤e列的所有可能线性组合都不同，则 dmin(C) ≥2e+1,由此可知C能纠正重量≤e的错误图案。
00101 00001 0 11 0 1 10101
0 0 11 0 00010 0 11 1 0 1 0 11 0
11 0 0 1 111 0 1 10001 01001
11 0 1 0 111 1 0 10010 01010
111 0 0 11 0 0 0 10100 0 11 0 0
111 11 11 0 1 1 1 0 11 1 0 11 11
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的生成矩阵又是D的校验矩阵, 而H是D的生 成矩阵,又是C的校验矩阵.
7.3 汉明几何和码的性能
• 例题
1 1 H1 = 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
1 1 0 0 0 H2 = 1 0 1 1 1
0 1 1 1 1 0 0 H 3 = 1 0 1 1 0 1 0 1 1 0 1 0 0 1
7.1 生成和一致校验矩阵
例7.1 一个(5,1)线性码C1，具有生成矩阵G1=[1,1,1,1,1]. 显然C1仅含有两个码字00000和11111；速率R=1/5。 （重复编码） 例7.2 一个(5,3)线性码C2，具有生成矩阵
1 1 1 0 0 G2 = 0 0 1 1 0 1 1 1 1 1
7.3 汉明几何和码的性能
定义：码C的最小距离为： dmin(C)=min{dH(x,x′)： x,x′∈C, x≠x′} 定理7.2 码C={x1,x2,...,xM}能够纠正所有重量≤e的错误图案， 当且仅当dmin(C)≥2e+1。 定义：码C的最小重量 wmin(C)=min{wH(x):x∈C,x≠0}
7.3 汉明几何和码的性能
• 汉明几何
假设希望码C能够纠正汉明重量≤e的错误图案，即如果发 送xi, 接收到y= xi+z,如果wH(z)≤e，则译码器的输出x′=xi。 对于qSC，译码的最佳策略是使dH(xi,y)最小的那个码字。 如果采用这种几何译码策略，则码能够纠正所有重量≤e 的错误图案的充分必要条件是，每一对码字之间的距离都 ≥2e+1。 xi y xi xi y xi
7.1 生成和一致校验矩阵
可见G1和G3是RRE形式了，当G2不是。G2的唯一RRE生成矩 阵为：
1 1 0 0 1 ′ G2 = 0 0 1 0 1 0 0 0 1 1
7.1 生成和一致校验矩阵
定义：存在一个编码规则，使信息符号独立地出现在码字中， 就称为它是系统的。 反之,不具备“系统”特性的码叫非系统码。非系统码与 系 统码并无本质的区别,它的生成矩阵可以通过行运算转变为 系统形式,这个过程叫系统化。系统化不改变码集 , 只改变映射 规则。 所有的线性码都是系统的。 对于无记忆信道，对G进行列置换并不会改变码的性能， 因此在这种情况下总可以假设G=[IkA]。
7.3 汉明几何和码的性能
• 汉明距离
定义两个矢量x和y之间的汉明距离为： dH(x,y)={分量xi≠yi的个数}=wH(y-x) 它满足真正的测度所具有的下列性质： （a）d(x,x)=0 （b）如果x≠y,则d(x,y)>0 （c）d(x,y)=d(y,x) （d）d(x,y)≤d(x,z)+d(z,y)
1 0 G3 = 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 1 0 1 1 0 0 0 1 1 1 1
例7.3 一个(7,4)线性码C3，具有生成矩阵 （(7,4)含明码）
7.1 生成和一致校验矩阵
基底不是惟一的,生成矩阵也就不是惟一的。事实上,将k 个基底线性组合后产生另一组 k 个矢量 , 只要满足线性无关 的条件 , 依然可以作为基底张成一个码空间。不同的基底有 可能生成同一码集 , 但因编码涉及码集和映射两个因素 , 码 集一样而映射方法不同也不能说是同样的码。 基底的线性组合等效于生成矩阵 G 的行运算 , 可以 产生 一组 新的基底。