离散数学在计算机纠错码中的应用.pdf

第十五卷第四期 年月 云 南教育学院学报 匕 离散数学在计算机纠错码中的应用 陶跃华 云南师范大学计科系 摘要本文通过实例论述了怎样利用离散数学的集合论 群论和数理逻辑来 分析研究计算机纠错码的纠错能 力 是离散数学在计 算机科学 中的一个重要应用方 面 关键词离散数学纠错码汉明距离 计算 机科学在其研究 过程中需要 借助于 离散数学这个工具 离散数学对计算机发展 和计算机科学的研究起着 重要的作用 其中 利用离散数学中的群论 数理逻辑 集合论 来研究计算机中纠错码的发现差错和纠正 差错的能力 是离 散数学在计算 机科学中的 一个重要应用 研究纠 错码的纠错 能力是计 算机科学的一个重要 课题 也是 必须要解决 的问题 计算机 中的纠错码 计算机中 常常需要 将二进制数字信号 进行传递 这种 传 递的 距离近则数米 数毫 米 远则超过数千 公 里 在传递过程 中 由 于存在各种干挠 常常会使二进制信号产生 失真现象 为了 及时 发现并修正 错误 计算 机采用 校验码 对传 输的信息 进行 校 验和修 正 校验码的种类 很多 最常见的是 奇偶校 验码和海明码 由 所组成的 串称 为字 一 些字的集合称为码 码中的每个二进 制信号或称 为码元 码 中的 字称为码字 不在 码中的 字称为废码 例设有长度为的 字 它们一共有 二 个 它们所组成的字集为 若选取时 这种编码不具有 抗 干挠能力 因为当中的一个字例如在 传递过程中第一个码元变为 因而整个字 变为时 由于也为中的字 故不能 发现传递 中是否出错 若选取的一个子集 作为编码时 与不属于 因为与 均为废码 而当在传递过程中第一个码元 由变为 整个字变 为时 由于是废 码 所以我们发现传递过程 中发生 了错误 这种编码只能发现错误而不能纠正错误 例考虑长度 为的字 它们一 共有 个 在它 们所组成的字集 中 我选择编 码 因为码字出现错误后 变为第 三位码出错 而码 字出现错误后将变为 川 所以码字在传递过程中任 何一个码元出现了错误 整个码字就会变成 由此 可知原正确 码 为 对原 来正确的码字也有 类似的情况 故 对 我们不仅能发现错误而且能纠正错误 纠错码的纠错能力分析 从前面的例 例看出按编码仅 能发 现单个错误 按编码可发现单个错误并纠 正单个错误 从而我 们得知 不同 的编码具 有不同的纠错能力 为了研究编码方式与纠 错能力间的联系 我们 先定义一个代数系统 设 是长度为的字集 即 1994 2009 China Academic Journal Electronic Publishing House All rights reserved 云南教育学院学报 在 上定义一个运 算 设 二 二 则有 其中 二 兔而运 算符为按位加 中任意两个元素作运算后仍在 内 故它是封闭 的 因此 是一个 代数系统 又因为 满足 结合律 护一产一 它 的单位元是 它 的逆 元是它 自 己 因此 是群 对的任一 子集 如果 是群 则称码是群码 中两个元素 二 二 则与 的汉明距离定义为 艺 一个码字 的极小值称为码 即有 中所有不同码字的汉明距离 的最小距离 记为 而归 笋 下述两个定理 刻划了编码方式与纠错 能力间的关系 定理一个码能检查出不超过个错 误的充分必要条件是 定理码能纠正个错误的 充分必要 条件是 妻 由上述预备知识 我 们可以讨论纠错码 的发现错误和纠正错误的能力 例奇偶校验码 所谓奇偶校验码 就是将编码中的每 个码字后增加一位校验码 使每个码字所含 的个数 为 偶 数 个即偶校验码或奇 数个 即奇校验码 例如编码 没 有 发 现错误及纠正错误的能力 则由得到偶 校 验码 为 玉而 它的 最小距 离犷 由定理知 它 可以检 出单个错误 而犷不可 能 所以 它不能纠正错误 从例中看出无纠错能 力 由构 成的 即有 查出 单个错误的能力 如何 从一 些编码中选取一些码 字组 成新 码 使 其具 有一定的纠错能力 是一个很重 要的 课题 我们看例 例汉明码的一个特例 设 有 中每个码字为 若 增加 三位校验 位 从而使它成为 长度为的码字 尹产 其 中校 验位 应满足下列方程 即要满足 因此 一旦 确定 则根 据 方 程校 验位 亦可唯一确定 这 样 由就可以得到一个长度为的 编码 如表所示 菠菠 石石 表码的码表 这种 编 码能发 现一 个错误并 能 纠正 1994 2009 China Academic Journal Electronic Publishing House All rights reserved 一个错误 首 先 它能 发现一个错误因为如果 中码字 发生单错 则上 述 三个方程中 必定 至少有一个等式 不满足 其 次 它能 纠 正一个错误 因为当 中码 字发生 单 错后 不同 的字位 错误可使 方程 中不同 的等 式不成立 如当 发生 错 误时则必 有 方程 不 成立 而 当 发生错误时则必 有 方程 不 成 立 方程中三个等式的八种组合可 对应 一 的 七个码字 为讨论方便 起见 我 们建立三个谓 词 二 礴 一 这三个谓 词的真 假与 对应 等 式是否成 立相一致 我们建立三个集合 分别 对 应 我 们令 显然 是使为假的所有可能 出错 字位的集 合 可以构 成下 面 七个非空集 卜 自自 自门 自自 年第期 瓦自 门瓦 瓦自瓦自 一 从 这七个集合可以决 定出错位 例如 瓦门 门公 即表示嗜 任 所以如 出错 则必有 为负 妙 为假 反之亦然 以此类推 可以得到 如表 所示 的表 出错字母母 无无 码码 气气 人人 气气 纵纵 毛毛 表纠错对照表 这样就 可以看出 这种编码能纠正 一 个错误 综上所述 可以利用离 散 数学中的群 论 谓词 逻辑 集 合论知识来研究计 算机 中的纠错码的发 现 错误和纠正错误的能 力 参考资料 徐洁磐等编离散数学及其在计算机 中的应用 人民邮电出版社 自瓦门 门自瓦 瓦自 自 一