信息与编码课件...ppt

第二部分编码理论 第七章线性码 第七章线性码 7 1生成和一致校验矩阵7 2q进制对称信道上的伴随式译码7 3汉明几何和码的性能7 4汉明码7 5一般q进制对称信道上的伴随式译码7 6重量牧举多项式和MacWilliams恒等式 7 1生成和一致校验矩阵 定义 Fq上的一个 n k 线性码 是n维矢量空间Vn Fq x1 x2 xn xi Fq 的一个k维子空间 n称为码的长度 k称为为数 码的速率为k n 7 1生成和一致校验矩阵 n k 线性分组码是把信息流分割成一串前后独立的kbit信息组 再将每组信息元映射成由n个码元组成的码字 codeword 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重矢量 写成1 n的矩阵形式 gk gk1 gk2 gkn 7 1生成和一致校验矩阵 将这k个基底码字排列成一个k n的矩阵G 则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 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生成和一致校验矩阵 基底不是惟一的 生成矩阵也就不是惟一的 事实上 将k个基底线性组合后产生另一组k个矢量 只要满足线性无关的条件 依然可以作为基底张成一个码空间 不同的基底有可能生成同一码集 但因编码涉及码集和映射两个因素 码集一样而映射方法不同也不能说是同样的码 基底的线性组合等效于生成矩阵G的行运算 可以产生一组新的基底 7 1生成和一致校验矩阵 性质 如果G是C的生成矩阵 则任意与G行等价的矩阵也是C的生成矩阵 任意生成矩阵等价于一个行递减阶梯 RRE 矩阵 任意线性码都具有唯一的一个RRE生成矩阵 域F上RRE的矩阵的三个性质 a 每行最左边的非零元素是1 b 每个包含这样一个最左1元素的列中的其他元素都为0 c 如果第i行的最左非零元素出现在第ti列上 则t1 t2 tr 7 1生成和一致校验矩阵 可见G1和G3是RRE形式了 当G2不是 G2的唯一RRE生成矩阵为 7 1生成和一致校验矩阵 定义 存在一个编码规则 使信息符号独立地出现在码字中 就称为它是系统的 反之 不具备 系统 特性的码叫非系统码 非系统码与系统码并无本质的区别 它的生成矩阵可以通过行运算转变为系统形式 这个过程叫系统化 系统化不改变码集 只改变映射规则 所有的线性码都是系统的 对于无记忆信道 对G进行列置换并不会改变码的性能 因此在这种情况下总可以假设G IkA 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 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 形式 然后再对 ATIn k 进行逆置换而得到H 例如有G1 G2和G3生成的一致校验矩阵是 7 1生成和一致校验矩阵 定理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 给出 7 2q进制对称信道上的伴随式译码 假定信道输出符号集AY Fq 即输入与输出符号集相同 因此如果传输的是x x1 x2 xn Vn Fq 则接收矢量y y1 y2 yn 也属于Vn Fq 两者的差值z y x称为错误图案 如果zi 0 我们就称在第i个位置上出现了一个错误 错误图案 7 2q进制对称信道上的伴随式译码 伴随式 如果传输的是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 2q进制对称信道上的伴随式译码 对应于qn k个伴随式s 码C一共有qn k个陪集 每个陪集包含qk个元素 因此一旦接收方计算出s 就可以将z的搜寻范围从qn种可能降低到qk种可能 即搜寻范围是与s相对应的陪集元素 7 2q进制对称信道上的伴随式译码 假设信道是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 2q进制对称信道上的伴随式译码 如果 1 q 则上式就是wH Z 的递减函数 因此最有可能的z是具有最小重量的z 所以q进制对称信道上的伴随式译码算法如下 1 计算伴随式s HyT2 在对应于s的陪集中找出最小重量矢量 称为z0 3 输出码字x y z0 7 2q进制对称信道上的伴随式译码 例考虑码C2 它的一致校验矩阵是 只有四个可能的伴随式 00 01 10 11 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 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 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是线性码 则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的错误图案 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 线性分组码的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 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 噪声样本概率分布为 P Z 0 1 q 1 P Z z且z 0 对于一般q进制信道上噪声样本概率分布为 P Z 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中的错误图案 7 5一般q进制信道上的伴随式译码 这意味着 允许译码器输出一个码字x 或一个特殊的删除符号 假设发送的是x 接收的是y x z 则有三种可能 a 译码器输出x x 错误图案被纠正了 b 译码器输出x x 产生一个错误 c 译码器输出 检测到一个错误 7 5一般q进制信道上的伴随式译码 定义如果可以设计码C的译码器 它能够纠正E中的错误图案z 并能够纠正或检测F中的错误图案z 则称码C为E纠错 F检错码 定理7 4令C是Fq上的一个 n k 线性码 具有一致校验矩阵H 并令E F为Vn Fq 的子集 则C为E纠错 F检错码的充分必要条件是它具有下列性质 a z1 z2 E z1 z2 则Hz1T Hz1T b z1 E z2 F E 则Hz1T Hz1T 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的码字数目 显然A0 1 A 1 qk 7 6重量牧举多项式和MacWilliams恒等式 定理7 5令C是一个二进制线性码 用于输入符号集Ax 0 1 及输出符号集为AY的DMC上 并且采用最大似然准则译码 则最终的错误概率界限为 特别地 对于原始误比特为 的BSC 例7 6码C1仅含00000和11111两个码 则A z 1 z5 所以PE 32 1 5 2 7 6重量牧举多项式和MacWilliams恒等式 定理7 6 MacWilliams恒等式 令A z 是一个 n k 线性码C的重量牧举多项式 并令B z 是其对偶码C 的重量牧举多项式 则A z 与B z 的关系为 7 6重量牧