汉明码编译码文档

第一章第一章 绪论绪论 1 1 差错控制编码 1 1 概述 数字信号在传输过程中 由于受到干扰的影响 码元波形将变坏 接收端 收到后可能发生错误判决 由于乘性干扰引起的码间串扰 可以采用均衡的办 法来纠正 而加性干扰的影响则需要用其他办法解决 在设计数字通信系统时 应该首先从合理选择调制制度 解调方法以及发送功率等方面考虑 使加性干 扰不足以影响到误码率要求 在仍不能满足要求时 就要考虑采用差错控制措 施了 从差错控制角度看 按加性干扰引起的错码分布规律不同 信道可以分为 3 类 即随机信道 突发信道和混合信道 在随机信道中 错码的出现是随机 的 而且错码之间是统计独立的 在突发信道中 错码是成串集中出现的 而 且在短促的时间段之间存在较长的无错码区间 把既存在随机错码又存在突发 错码的的信道称为混合信道 对于不同类型的信道 应该采用不同的差错控制 技术 1 2 纠错编码原理 我们把信息码分组 为每组信息码附加若干监督码的编码称为分组码 block code 在分组码中 监督码元仅监督本码组中的信息码元 分组码一般 用符号 n k 表示 其中 n 是码组的总位数 又称为码组的长度 码长 k 是码组中信息码元的数目 n k r 为码组中的监督码元的数目 或者称为监督 位数目 分组码的结构如图 2 示 图中前 k 位为信息位 后面附加 r 个监督位 其中 an 1到 ar为 k 个信息位 ar 1到 a0为 r 个监督位 an 1an 2 arar 1 ao 图 4 分组码的结构 在分组码中 把码组中 1 的个数称为码组的重量 简称码重 把两个码 组中对应位上数字不同的位数称为码组的距离 简称为码距 码距又称为汉明 距离 我们把某种编码中各个码组之间距离的最小值称为最小码距 d0 一种编码的最小距离的大小直接关系着这种编码的检错与纠错能力 1 为检测 e 个错码 要求最小码距 d0大于等于 e 1 2 为了纠正 t 个错码 要求最小码距 d0大于等于 2t 1 3 为纠正 t 个错码同时检测 e 个错码 要求最小码距 d0大于等于 e t 1 e t 1 3 汉明码编码 Hamming码中文称作汉明码 汉明码是由汉明于1950年提出的 具有纠正 一位错误能力的线性分组码 它的突出特点是 编译码电路简单 易于硬件实现 用软件实现编译码算法时 软件效率高 而且性能比较好 1 3 1 汉明码的定义 若一致监督矩阵H 的列是由不全为0且互不相同的所有二进制m m 2的正 整数 重组成 则由此H矩阵得到的线性分组码称为 2m 1 2m 1 m 3 汉明码 1 3 2 汉明码的构造特点 1 绐定一个m 我们由二进制m 重组成线性分组码的监督矩阵H 由二 进制m重来标定一个发生错误的位置 由此可知 二进制m 重共有2 种位组合 去掉一个全为0的位组合 则余下共有2m 1种位组合 故汉明码的最大码长 n 2m 1 2 由上面分析 我们可以知道 m 即是汉明码监督位的位数 故一个 汉明码中 信息位的位数k n m 2m 1 m 3 汉明码的距离为 3 因此可以纠正 1 位错误 检出 2 位错误 1 3 3 汉明码编码的主要算法 汉明码的编码就是如何根据信息位数k 求出纠正一个错误的监督矩阵H 然后根据H求出信息位所对应的码字 构造汉明码监督矩阵H的方法很多 这里 仅介绍一种 1 根据已知的信息位数k 从汉明不等式中求出校验位数m n k 2 在每个码字C C1 C2 C2m 1 中 用c02 c12 cn 12作为监督位 剩下 的位作为信息位 3 用二进制数字表示2m 1 列 得到2m 1列和m行监督矩阵H 4 用3步的H形成HCT 0 从而得出m个监督方程 5 将已知的信息代入方程组 然后求出满足上述方程组的监督位c i 0 1 m一1 例如 用以上方法 很容易求出 7 4 3 汉明码的监督矩阵 1 1 1 1 1 1 0 0 1 1 0 0 0 0 H H 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 1 及编码所对应的码字为C 011001 1 4 主要应用领域 1 4 1 钢丝绳张力检测系统 随着现代通信技术和计算机技术的高速发展 无线数字通信的应用越来越 广泛 钢丝绳张力检测系统将数字无线通信 测量和计算机技术结合在一起 其 功能是将电梯 缆车或提升机钢丝绳张力检测信息转换成数字信号 通过无线 方式传送给控制中心 由控制中心对原始数据进行处理 分析和计算 输出人 们想要的结果 做出相应的判断与控制 因此 钢丝绳张力的检测系统对使用 钢丝绳的提升设备的安全运行起着至关重要的作用 1 4 2数字存储系统 随着PC机的日益普及 存储对象的日渐多元化 用户对存储需求不断升级 如何保证数据稳定 高速传输 RAID Redundant Array of Independent Disk 独立冗余磁盘阵列解决了这个难题 并且成为目前存储的主流技术 RAID之所以 实现数据高速 可靠的传输 一个关键的核心技术就是应用了一定 的差错控制编码技术 在RAID 众多系列中最复杂的RAID 2中就采用了 汉明码 Hamming Code 差错控制编码技术 它在数据存储及移动过程中进行差错控 制 对传输过程 中出现的差错自动进行纠正 保证了数据传输的安全可靠性 1 4 3保密通信技术 随着计算机网络的发展及应用的普及 特别是在军事指挥 情报系统 银行 系统的应用 通信的可靠性及保密性要求越来越高 这就要求研制新的高可靠 性及保密性通信技术 接收端不仅能从接收到的信息中检测出传输过程中的错 误而且能纠正之 针对IBM PC微计算机之间通信过程中的纠错技术提出了一种 在通信计算机之间不增加任何硬件设备的情况下 仅用编写一段纠错编码 发送 端 和纠错译码 接收端 的软件方法达到计算机通信纠错和保密的目的 即利用 汉明码编码实现检错 纠错的具体方案 这样做的优点是 在保持一定功能和 相应速度的前提下 采用软件方法 不仅可以提高通信过程的可靠性 而且还 可以提高通信系统本身的可靠性 第二章第二章 7 4 7 4 汉明码的编码原理汉明码的编码原理 2 1 基本构造 对于码组长度为 n 信息码元为 k 位 监督码元为 r n k 位的分组码 常记作 n k 码 如果满足 2r 1 n 则有可能构造出纠正一位或一位以上 错误的线性码 下面我们通过 7 4 汉明码的例子来说明如何具体构造这种码 设分组 码 n k 中 k 4 为能纠正一位误码 要求r 3 现取r 3 则 n k r 7 我们用a0ala2a3a4a5a6表示这7个码元 用S1 S2 S3表示由三个监 督方程式计算得到的校正子 并假设三位S1 S2 S3校正子码组与误码位置的对 应关系如表1所示 S1S2S3 错码位置 S1S2S3 错码位置 001 a0 101 a4 010 al 110 a5 100 a2 111 a6 011 a3 000 无错码 表1 校正子和错码位置关系 由表可知 当误码位置在a2 a4 a5 a6时 校正子S1 1 否则S1 0 因此有 S1 a6 a5 a4 a2 同理有S2 a6 a5 a3 a1和S3 a6 a4 a3 a0 在编码时 a6 a5 a4 a3为信息码元 a2 a1 a0为监督码元 则监督码元可由以下监督 方程唯一确定 a6 a5 a4 a2 0 a6 a5 a3 a1 0 1 1 1 a6 a4 a3 a0 0 也即 a2 a6 a5 a4 a1 a6 a5 a3 1 1 2 a0 a6 a4 a3 由上面方程可得到表 2 所示的 16 个许用码组 在接收端收到每个码组后 计算 出 S1 S2 S3 如果不全为 0 则表示存在错误 可以由表 1 确定错误位置并予 以纠正 举个例子 假设收到码组为 0000011 可算出 S1S2S3 011 由表 1 可知 在 a3上有一误码 通过观察可以看出 上述 7 4 码的最小码距为 dmin 3 纠正一个误码或检测两个误码 如果超出纠错能力则反而会因 乱纠 出现新 的误码 信息位 监督位 信息位 监督位 a6a5a4a3 a2a1a0 a6a5a4a3 a2a1a0 0000 0001 0010 0011 0100 0101 0110 0111 000 011 101 110 110 101 011 000 1000 1001 1010 1011 1100 1101 1110 1111 111 100 010 001 001 010 100 111 表2 7 4 汉明码的许用码组 2 2 监督矩阵 上面有提到过 线性码是指信息位和监督位满足一组线性代数方程的码 式 1 1 1 就是这样的例子 现在将它改写成 1 a6 1 a5 1 a4 0 a3 1 a2 0 a1 0 a0 0 1 a6 1 a5 0 a4 1 a3 0 a2 1 a1 0 a0 0 1 1 3 1 a6 0 a5 1 a4 1 a3 0 a2 0 a1 1 a0 0 我们可以将式 1 1 3 表示成如下的矩阵形式 a a6 6 a a5 5 1 1 1 1 1 1 0 0 1 1 0 0 0 0 a a4 4 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 a a3 3 0 0 1 1 4 1 1 0 0 1 1 1 1 0 0 0 0 1 1 a a2 2 0 0 a a1 1 a a0 0 式 1 1 4 还可以简记为 H AT 0T 或 A HT 0 1 1 5 其中 1 1 1 1 1 1 0 0 1 1 0 0 0 0 H H 1 1 1 1 0 0 1 1 0 0 1 1 0 0 A A a a6 6a a5 5a a4 4a a3 3a a2 2a a1 1a a0 0 0 0 000000 1 1 0 0 1 1 1 1 0 0 0 0 1 1 上角 T 表示将矩阵转置 例如HT是H的转置 即HT的第一行为H的第一列 第 二行为第二列 我们将H H称为监督矩阵 parity check matrix 只要监督矩阵H给定 编码 时监督位和信息位的关系就完全确定了 由 1 1 4 和 1 1 5 都可以看出 H 的行数就是监督关系式的数目r H的每一行中的 1 的位置表示相应码元之间 存在的监督关系 式 1 1 4 中的H矩阵可以分为两部分 1 1 1 1 1 1 0 0 1 0 0 H H 1 1 1 1 0 0 1 1 0 1 0 PIPIr r 1 1 6 1 1 0 0 1 1 1 1 0 0 1 式中 P P为r k阶矩阵 I Ir r为r r阶单位方阵 2 3 生成矩阵 由代数理论可知 H矩阵的的各行应该是线性无关的 否则将得不到r个线性 无关的监督关系式 从而也得不到r个独立的监督位 若一矩阵可以写成PIr的 矩阵形式 则其各行一定是线性无关的 因为容易验证Ir的各行是线性无关的 故PIr的各行也是线性无关的 类似于 1 1 1 改成 1 1 4 那样 1 1 2 可以改写成 a a6 6 a a2 2 1 1 1 1 1 1 0 0 a a5 5 a a1 1 1 1 1 1 0 0 1 1 a a4 4 1 1 7 a a0 0 1 1 0 0 1 1 1 1 a a3 3 或者 1 1 1 1 1 1 a a2 2a a1 1a a0 0 a a6 6a a5 5a a4 4a a3 3 1 1 1 1 0 0 a a6 6a a5 5a a4 4a a3 3 Q Q 1 1 8 1 1 0 0 1 1 0 0 1 1 1 1 其中 Q Q为一个k r阶矩阵 它为P P的转置 即 Q Q P PT 式 1 1 8 表示 在信息位给定后 用信息位的行矩阵乘矩阵Q Q就产生出监督 位 我们将Q Q的左边加上一个k k阶单位方阵 就构成一个矩阵G G 1 0 0 0 1 1 1 1 1 1 G G I IK KQ Q 0 1 0 0 1 1 1 1 0 0 1 1 9 0 0 1 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 1 1 G称为生成矩阵 generator matrix 因为由它可产生整个码组 即有 a a6 6a a5 5a a4 4a a3 3a a2 2a a1 1a a0 0 a a6 6a a5 5a a4 4a a3 3 G G A A 2 2 0 第三章第三章 7 4 7 4 汉明码编码的设计汉明码编码的设计 3 1 7 4 汉明码的编码思路 7 4 汉明码的编码就是将输入的四位信息码编成七位的汉明码 即加入三 位监督位 根据式 2 2 0 A A a6 a5 a4 a3 G G 可知 信息码与生成矩阵 G G 的乘积就是编好以后的 7 4 汉明码 而生成矩阵 G G 又是已知的 由式 1 1 9 得 1 0 0 0 1 1 1 1 1 1 G G 0 1 0 0 1 1 1 1 0 0 0 0 1 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 1 1 所以 可以得出如下方程组 a6 a6 a5 a5 a4 a4 a3 a3 2 2 1 a2 a6 a5 a4 a1 a6 a5 a3 a0 a6 a4 a3 根据式 2 2 1 就可以编出编码程序了 3 2 7 4 汉明码的编码程序设计 根据 7 4 汉明码的编码原理 首先画出程序设计的流程图 图 6 编码流程图 输入信息码 a3a2a1a0 输出 7 4 汉明码 b6b5b4b3b2b1b0 首先 输入信息码 a3a2a1a0 即使用以下语句 port a in std logic vector 3 downto 0 然后 根据式 2 2 1 就可以得到监督位与信息码之间的对应关系 使用异或 运算 即 b 6 a 3 b 5 a 2 b 4 a 1 b 3 a 0 b 2 a 3 xor a 2 xor a 1 b 1 a 3 xor a 2 xor a 0 b 0 a 3 xor a 1 xor a 0 最后 将算好的监督位与原来输入的信息一起输出 就是编码结束了 第四章第四章 编译程序的调试与分析编译程序的调试与分析 4 1 7 4 汉明码的编码程序的编译 4 1 1 在 max plus 中采用原理图输入如下所示 步骤一 指定设计项目名字 步骤二 建立一个新的图形文件 步骤三 输入图元和功能符号 步骤四 命名引脚和链接逻辑符号 编译结果如下 4 1 2在在max plus 采用文本输入法 7 4 汉明码的编码程序如下 library ieee use ieee std logic 1164 all entity bm is port a in std logic vector 3 downto 0 b out std logic vector 6 downto 0 end bm architecture strc of bm is begin b 6 a 3 b 5 a 2 b 4 a 1 b 3 a 0 b 2 a 3 xor a 2 xor a 1 b 1 a 3 xor a 2 xor a 0 b 0 a 3 xor a 1 xor a 0 end strc 文本编辑如下 编译结果 4 2 7 4 汉明码的编码程序的仿真 在 max plus 采用波形编辑器 先建立一个仿真通道文件 bm scf 如下图示 编辑的 wdf 文件如图所示 编译结果如下 4 3 7 4 汉明码的编码程序的编译和仿真分析 按照上述编码程序的编写思路 编写好程序 点击 进行编译 出现一些错误 列举如下 Error 1表明在使用 std logic vector 时 没有打开可以使用这个函数