信息论与编码第6章2ppt课件.ppt

1 信道编码 2 6 3线性分组码 3 线性分组码 4 G gk 1 gk 210 g g T 线性分组码的码空间C是由k个线性无关的基底gk 1 g1 g0张成的k维n重子空间 所有码字都可写成k个基底的线性组合 即c mk 1gk 1 m1g1 m0g0如果gi表示第i个基底 并写成行矩阵的形式gi gi n 1 gi n 2 gi1 gi0 k个基底可以排列成k行n列的形式 如下所示 g k 1 1 g11 g01 g k 1 n 1 g1 n 1 g0 n 1 g k 1 0 g10 g00 6 3 1生成矩阵和校验矩阵 5 码空间中任何一个码字都可以写成基底的线性组合 即 C cn 1 cn 2 c1 c0 mk 1gk 1 mk 2gk 2 m1g1 m0g0 mG 当信息元确定后 码字仅由G矩阵决定 因此我们称这k n矩阵G为该 n k 线性分组码的生成矩阵 如果已知线性分组码的生成矩阵 则任何一个k位信息组对应的码字都可以由mG运算得到 生成矩阵 6 n k 线性分组码共有多少个码字 问题 答 2k个码字 7 想要保证 n k 线性分组码能够构成k维n重子空间 G的k个行矢量gk 1 g1 g0必须是线性无关的 只有这样才符合作为基底的条件 由于k个基底即G的k个行矢量线性无关 矩阵G的秩一定等于k 由于基底不是唯一的 所以G也就不是唯一的 不同的基底有可能生成同一码集 但因编码涉及码集和映射两个因素 码集一样而映射方法不同也不能说是同样的码 生成矩阵G k n 的特点 8 已知 7 4 线性分组码的生成矩阵为如果输入的四位信息组为m 0 1 1 0 时 其对应的码字为 举例 9 n k 码的任何生成矩阵都可以通过行运算 不改变码集 只改变映射规则 简化成 系统形式 Ik是k k单位矩阵 P是k n k 矩阵 系统形式的生成矩阵 10 前k位由单位矩阵Ik决定 等于把信息组m原封不动搬到码字的前k位 其余的n k位叫冗余位或一致校验位 是前k个信息位的线性组合 这样生成的 n k 码叫做系统码 若生成矩阵G不具备系统形式 则生成的码叫做非系统码 系统化不改变码集 只是改变了映射规则 系统码 11 已知 7 3 线性分组码的生成矩阵为如果输入的三位信息组为m 0 1 1 时 其对应的码字为 特点 码字的前面k位就是信息组中的k位 而后面的校验位为信息组的线性组合 系统码 12 n维n重空间有相互正交的n个基底 选择k个基底构成码 空间C 选择另外的 n k 个基底构成空间D C和D是对偶的 空间构成 13 将D空间的n k个基底排列起来可构成一个 n k n矩阵 称为校验矩阵H 也称监督矩阵 用来校验接收到的码字是否是正确的 即 若c为码空间C中的任意码字 则若不满足此等式 则c必定不是码空间C中的码字 校验矩阵 14 G是 n k 码的生成矩阵 H是它的校验矩阵 H是 n n k 对偶码的生成矩阵 它的每一行是对偶码的一个码字 G则是它的校验矩阵 GHT 0 H PT In k 二进制时 负号可省略 校验矩阵 15 校验矩阵与生成矩阵的关系 16 某线性分组码 其生成矩阵是 求 1 计算码集 列出信息组与码字的映射关系 2 将该码系统化处理后 计算系统码码集并列出映射关系 3 计算系统码的校验矩阵H 若收码r 100110 检验它是否码字 4 根据系统码生成矩阵画出编码器电原理图 111010 G 110001 011101 例6 2 17 码集与映射关系 信息000001010011100101110111 码字000000011101110001101100111010100111001011010110 系统码字000000001011010110011101100111101100110001111010 例6 2 18 二元 6 3 线性分组码编码器 例6 2 19 下面是某线性二元码的全部码字 求n k的值 构造这码的生成矩阵G 构成这码的一致校验矩阵H C1 000000C2 001111 C3 010001 C4 011110 C5 100011 C6 101100 C7 C8 111101 举例 20 定义差错图案EE en 1 e1 e0 R C rn 1 cn 1 r1 c1 r0 c0 二进制码中模2加与模2减是等同的 因此有 E R C及 R C E 6 3 2伴随式与标准阵列译码 21 因为CHT 0 所以RHT C E HT CHT EHT EHT如果收码无误 必有R C即E 0 则EHT 0 RHT 0 如果收码有误 即E 0 则RHT EHT 0 在HT固定的前提下 RHT仅仅与差错图案E有关 而与发送码C无关 定义RHT的运算结果为伴随式SS sn k 1 s1 s0 RHT EHT 伴随式的定义 22 只要E正确 译出的码也就是正确的 从物理意义上看 伴随式S并不反映发送的码字是什么 而只是反映信道对码字造成怎样的干扰 差错图案E是n重矢量 共有2n个可能的组合 而伴随式S是 n k 重矢量 只有2n k个可能的组合 因此不同的差错图案可能有相同的伴随式 接收端收到R后 因为已知HT 可求出S RHT 如果能知道对应的E 则通过C R E而求得C 伴随式的意义 23 译码过程框图 译码过程 24 差错图案E的求解 1 25 上述方程组中有n个未知数en 1 e1 e0 却只有n k个方程 可知方程组有多解 在有理数或实数域中 少一个方程就可能导致无限多个解 而在二元域中 少一个方程导致两个解 少两个方程四个解 以此类推 少n n k k个方程导致每个未知数有2k个解 概率译码 把所有2k个解的重量 差错图案E中1的个数 作比较 选择其中最轻者作为E的估值 该方法概念上很简单但计算效率不高 差错图案E的求解 2 26 依据 若BSC信道的差错概率是p 则长度n的码中错误概率 出错越少的情况 发生概率越大 E的重量越轻 所以该译码方法实际上体现了最小距离译码准则 即最大似然译码 显然 在进行概率译码时 每接收一个码字就要解一次线性方程 非常复杂麻烦 但如果n k不太大 我们可以预先把不同校正子S情况下的所有方程组都预先解出来 将各种情况下的最大概率译码输出列成一个标准阵列译码表 这样 在实际译码时就不必解方程 只要查译码表就可以了 差错图案E的求解依据 27 伴随式S的数目是有限的2n k个 如果n k不太大 我们可以预先把不同S下的方程组解出来 把各种情况下的最大概率译码输出列成一个码表 这样 在实时译码时就不必再去解方程 而只要象查字典那样查一下码表就可以了 这样构造的表格叫做标准阵列译码表 表中所列码字是接收到的码字R 将没有任何差错时的收码R放在第一行 收码等于发码R C C Ci i 0 1 2k 1 差错图案为全零E0 0 0 0 伴随式为全零S0 0 0 0 由于有2k个码字 码表有2k列 标准阵列译码表的构成 28 在第2到第n 1的n行中差错图案的所有重量为1 共n个 如果 1 n 2n k 再在下面行写出全部带有2个差错的图案 共 n 个 2 如果总行数 1 n 差错的图案 以此类推 直到放满2n k行 每行一个Ej 对应一个不同的伴随式Sj 这样 表的行数2n k正好等于伴随式的数目 n 2 仍然小于2n k 再列出带有3个 标准阵列译码表的构成 29 标准阵列译码表 30 解 1 构造标准阵列译码表 分别以信息组m 00 01 10 11 及已知的G求得4个许用码字为C1 00000 C2 10111 C3 01101 C4 11010 一个 5 2 系统线性码的生成矩阵是设收码R 10101 构造标准阵列译码表 译出发码 求出校验矩阵 例6 3 31 列出方程组 s2 e4h24 e3h23 e2h22 e1h21 e0h20 e4 e3 e2s1 e4h14 e3h13 e2h12 e1h11 e0h10 e4 e1s0 e4h04 e3h03 e2h02 e1h01 e0h00 e4 e3 e0由RHT确定S后 对应的E可以有2k 22 4 个解 究竟取哪一个作为差错图样E的解 最简单明了的处理方法是概率译码 即对所有2k个解的重量 差错图样E中1的个数 进行比较 选择重量最小的作为E的估值 由于E R C E重量最小 就是R和C的汉明距离最小 例6 3 32 例6 3 33 例6 3 标准阵列译码表 34 将接收码R 10101译码可选以下三种方法之一译码 直接搜索码表 查得 10101 所在列的子集头是 10111 因此译码输出取为 10111 先求伴随式RHT 10101 HT 010 S4 确定S4所在行 再沿着行对码表作一维搜索找到 10101 最后顺着所在列向上找出码字 10111 先求出伴随式RHT 010 S4并确定S4所对应的陪集首 差错图案 E4 00010 再将陪集首与收码相加得到码字C R E4 10101 00010 10111 例6 3 35 对例6 3的分析在制定标准阵列译码表的过程中 由S决定差错图案E时只有前6行真正体现了最大似然译码准则 而第7 8行的差错图案选择不是唯一的 比如第7行可有 00011 和 10100 两个选择 如果当时选的不是 00011 而是 10100 那么码表第7行就不是现在这样了 那么在译码时最后的结果也就不一样了 为什么会出现这种情况呢 伴随式的个数2n k与n k及纠错能力t有一定的数量关系 例6 3 36 N重码矢c cn 1 cn 2 c1 c0 可与N维矢量空间XN中的一个点对应 全体码字所对应的点构成矢量空间里的一个子集 发码一定在这个子集里 传输无误时的收码也一定位于该子集 当出现差错时 接收的N重矢量 对应到子集外空间某一点 对应到该子集 却对应到该子集的另一点上 6 3 3码距 纠错能力 MDC码及重量谱 37 dmin 3td 7d 5 C1 C2 C3 C4 C5 码集各码字间的距离是不同的 码距最小者决定码的特性 称之为最小距离dmin 这里dmin 3 纠错能力是1 检错能力是2 码距 38 dmin min w Ci Ci C及Ci 0 定理6 1任何最小距离dmin的线性分组码 其检错能力为 dmin 1 纠错能力t为 最小距离dmin表明码集中各码字差异的程度 差异越大越容易区分 抗干扰能力就越强 是衡量分组码性能的最重要的指标之一 定理6 2线性分组码的最小距离等于码集中非零码字的最小重量 纠错能力 39 于 n k 1 即 dmin n k 1 定理6 3 n k 线性分组码最小距离等于dmin的充要条件是 校验矩阵H中有 dmin 1 列线性无关 定理6 4 n k 线性分组码的最小距离必定小于等 纠错能力 40 例 H 7 4 线性码 各列都不相同 任意2列之和不等于0 2列线性无关 任意2列之和一定等于矩阵中某一列 任意3列线性相关 所以该码的最小距离为3 小于n k 1 4 纠错能力 41 d0 2t 1 1 为检测e个错码 要求最小码距d0 e 1 2 为纠正t个错码 要求最小码距 3 为纠正t个错码 同时检测e个错码 要求最小码距d0 t e 1 最小码距与检错能力图示 42 n k 线性码最小距离dmin的上边界是n k我们设计的 n k 线性码的dmin达到了n k达到了设计性能的极点 因此 dmin n k为极大最小距离码 MDC Maximized 1 如果 1 就是 1的码称minimum DistanceCode 1 二进制码中 除了将一位信息重复n次的 n 1 码外 不存在其它二进制MDC码 2 非二进制码中 MDC码是存在的 如RS码 reed solomon MDC码 MaximizedminimumDistanceCode 43 含义 在码长n的码集里 包含重量为0的码字A0个 重量为1的码字A1个 重量为n的码字An个 纠错能力t只是说明距离t的差错一定能纠 并非说距离大于t的差错一定不能纠 除非完备码 总体的 平均的纠错能力不但与最小距离有关 而且与其余码距或者说与码字的重量分布特性有关 把码距 码重 的分布特性称为距离 重量 谱 其中最小重量就是dmin 当所有码距相差不大时 重量谱为窄谱 性能较好 重量谱多项式表示 重量谱 44 任何一个二元 n k 线性分组码都有2n k个伴随式 假如该码的纠错能力是t 则对于任何一个重量小于等于t的差错图案 都应有一个伴随式与之对应 也就是说 伴随式的数目满足条件 上式称作汉明限 任何一个纠t码都应满足上述条件 6 3 4完备码 Perfectcode 45 某二元 n k 线性分组码能使等式 成立 即该码的伴随式数目不多不少恰好和不大于t个差错的图案数目相等 相当于在标准译码阵列中能将所有重量不大于t的差错图案选作陪集首 而没有一个陪集首的重量大于t 这时的校验位得到最充分的利用 这样的二元 n k 线性分组码称为完备码 2 n k ti 0 n I 完备码 46 汉明码的纠错能力t 1 既有二进制的 也有非二进制的 二进制时 汉明码码长n和信息位k服从以下规律 n k 2m 1 2m 1 m 其中m n k 是正整数 当m 3 4 5 6