代数系统在计算机科学中的应用ppt课件.ppt

代数系统在计算机科学中的应用 人们研究和考察现实世界中各种现象或过程 往往要借助某些数学工具 在代数中 可以用正整数集合上的加法运算来描述企业产品的累计数 可以用集合之间的 并 交 运算来描述单位与单位之间的关系等 我们所接触过的数学结构 连续的或离散的 常常是对研究对象 自然数 实数 多项式 矩阵 命题 集合乃至图 定义各种运算 加 减 乘 与 或 非 并 交 补 然后讨论这些对象及运算的有关性质 针对某个具体问题选用适宜的数学结构去进行较为确切的描述 这就是所谓 数学模型 可见 数学结构在数学模型中占有极为重要的位置 而代数系统是一类特殊的数学结构 由对象集合及运算组成的数学结构 我们通常称它为代数结构 它在计算机科学中有着广泛的应用 对计算机科学的产生和发展有重大影响 反过来 计算机科学的发展对抽象代数学又提出了新的要求 促使抽象代数学不断涌现新概念 发展新理论 格与布尔代数的理论成为电子计算机硬件设计和通讯系统设计中的重要工具 半群理论在自动机和形式语言研究中发挥了重要作用 关系代数理论成为最流行的数据库的理论模型 格论是计算机语言的形式语义的理论基础 抽象代数规范理论和技术广泛应用于计算机软件形式说明和开发 以及硬件体系结构设计 有限域的理论是编码理论的数学基础 在通讯中发挥了重要作用 在计算机算法设计与分析中 代数算法研究占有主导地位 纠错码 一 纠错码概述我们知道 在计算机中和数据通信中 经常需要将二进制数字信号进行传递 这种传递的距离近则数米 数毫米 远则超过数千公里 在传递住处过程中 由于存在着各种干扰 可能会使二进制信号产生失真现象 即在传递过程中二进制信号0可能会变成1 1可能会变成0 图2 1是一个二进制信号传递的简单模型 它有一个发送端和一个接收端 二进制信号串X x1x2 xn从发送端发出经传输介质而至接收端 由于存在着干扰对传输介质的影响 因而接收端收到的二进制信号串中的可能不一定就与xi相等 从而产生了二进制信号的传递错误 由于在计算机中和数据通信系统中的信号传递是非常的频繁与广泛 因此 如何防止传输错误就变得相当重要了 当然 要解决这个问题可以有不同的途径 人们所想到的第一个途径是提高设备的抗干扰能力和信号的抗干扰能力 但是 大家都知道 这种从物理角度去提高抗干扰能力并不能完全消除错误的出现 第二个途径就是我们所要谈到的采用采用纠错码 ErrorCorrectingCode 的方法以提高抗干扰能力 这种纠错码的方法是从编码上下功夫 使得二进制数码在传递过程中一旦出错 在接收端的纠错码装置就能立刻发现错误 并将其纠正 由于这种方法简单易行 因此目前在计算机中和数据通信系统中被广泛采用 采用这种方法后 二进制信号传递模型就可以变为图2 2所示的模型了 图2 2通信系统模型 信源 信源编码 加密 信道编码 信道 信道译码 解密 信源译码 信宿 密钥源 噪声 密钥源 该模型按功能分为信源 编码器 信道 译码器 信宿 但是 为什么纠错码具有发现错误 纠正错误的能力呢 纠错码又是按什么样的原理去编的呢 为了说明这些问题 我们首先介绍一些基本概念 定义2 1 由0和1组成的串称为字 Word 一些字的集合称为码 Code 码中的字称为码字 CodeWord 不在码中的字称为废码 InvalidCode 码中的每个二进制信号0或1称为码元 CodeLetter 我们下面举出几个关于纠错码例子 例2 1设有长度为2的字 它们一共可有22 4个 它们所组成的字集S2 00 01 10 11 当选取编码为S2时 这种编码不具有抗干扰能力 因为当S2中的一个字如10 在传递过程中其第一个码元1变为0 因而整个字成为00时 由于00也是S2中的字 故我们不能发现传递中是否出错 当我们选取S2的一个子集如C2 01 10 作为编码时就会发生另一种完全不同的情况 因为此时00和11均为废码 而当01在传递过程中第一个码元由0变为1 即整个字成为11时 由于11是废码 因而我们发现传递过程中出现了错误 对10也有同样的情况 01 第一个码元错成11 第二个码元错成00 10 第一个码元错成00 第二个码元错成11 可见 这种编码有一个缺点 即它只能发现错误而不能纠正错误 因此我们还需要选择另一种能纠错的编码 例2 2考虑长度为3的字 它们一共可有23 8个 它们所组成的字集S3 000 001 010 011 100 101 110 111 选取编码C3 101 010 利用此编码我们不仅能发现错误而且能纠正错误 因为码字101出现单个错误后将变为 001 111 100 而码字010出现错误后将变为110 000 011 故如码字101在传递过程中任何一个码元出现了错误 整个码字只会变为111 100或001 但是都可知其原码为101 对于码字010也有类似的情况 故对编码C3 我们不仅能发现错误而且能纠正错误 当然 上述编码还有一个缺点 就是它只能发现并纠正单个错误 当错误超过两个码元时 它就既不能发现错误 更无法纠正了 二 纠错码的纠错能力 前面例子中我们发现C2编码仅能发现错误 按C3编码可发现并纠正单个错误 可见 不能的编码具有不同的纠错能力 下面介绍编码方式与纠错能力之间的联系 设Sn是长度为n的字集 即Sn x1x2 xn xi 0或1 i 1 2 n 在Sn上定义二元运算 为 X Y Sn X x1x2 xn Y y1y2 yn Z X Y z1z2 zn其中 zi xi 2yi i 1 2 n 而运算符 2为模2加运算 即0 21 1 20 1 0 20 1 21 0 我们称运算 为按位加 显然 是一个代数系统 且运算 满足结合律 它的幺元为00 0 每个元素的逆元都是它自身 因此 是一个群 定义2 2Sn的任一非空子集C 如果是群 即C是Sn的子群 则称码C是群码 GroupCode 定义2 3设X x1x2 xn和Y y1y2 yn是Sn中的两个元素 称为X与Y的汉明距离 HammingDistance 从定义可以看出 X和Y的汉明距离是X和Y中对应位码元不同的个数 设S3中两个码字为 000和011 这两个码字的汉明距离为2 而000和111的汉明距离为3 关于汉明距离 我们有以下结论 1 H X X 0 2 H X Y H Y X 3 H X Y H Y Z H X Z 3 H X Y H Y Z H X Z 的证明 证明 定义H xi yi 则H xi zi H xi yi H yi zi 从而 0 xi yi 1xi yi 定义2 4一个码C中所有不同码字的汉明距离的极小值称为码C的最小距离 MinimumDistance 记为dmin C 即例如 dmin S2 dmin S3 1 dmin C2 2 dmin C3 3 利用编码C的最小距离 可以刻画编码方式与纠错能力之间的关系 我们有以下两定理 定理2 1 一个码C能检查出不超过k个错误的充分必要条件为dmin C k 1 定理2 2 一个码C能纠正k个错误的充分必要条件是dmin C 2k 1 例子2 3 对于C2 01 10 因为dmin C2 2 1 1 所以C2可以检查出单个错误 对于C3 101 010 因dmin C3 3 故C3能够发现并纠正单个错误 对于S2和S3分别包含了长度为2 3的所有码 因而dmin S2 dmin S3 1 从而S2 S3既不能检查错误也不能纠正错误 从而我们知道一个编码如果包含了某个长度的所有码字 则此编码一定无抗干扰能力 例子2 4奇偶校验码 Paritycode 的编码 我们知道 编码S2 00 01 10 11 没有抗干扰能力 但我们可以在S2的每个码字后增加一位 叫奇偶校验位 这一位是这样安排的 它使每个码字所含1的个数为偶数 按这种方法编码后S2就变为S2 000 011 101 110 而它的最小距离dmin S2 2 故定理2 1可知 它可想出单个错误 而事实也是如此 当传递过程中发生单个错误则码字就变为含有奇数个1的废码 类似地 增加奇偶校验位使码字所含1的个数为奇数时也可得到相同的效果 我们可以把上述结果推广到Sn中去 不管n多大 只要增加一奇偶校验位总可能查出一个错误 这种方法在计算机中是使用很普遍的一种纠错码 它的优点是所付出的代价较小 只增加一位附加的奇偶校验位 而且这种码的生成与检查也很简单 它的缺点是不能纠正错误 三 纠错码的选择 前面分析 我们发现S2无纠错能力 但在S2中选取C2后 C2具有发现单错的能力 同样 S3无纠错能力 但在S3中选取C3后 C3具有纠正单错的能力 从这里可以看出 如何从一些编码中选取一些码字组成新码 使其具有一定的纠错能力是一个很重要的课题 下面我们介绍一种很重要的编码 汉明编码 这种编码能发现并纠正单个错误 一 汉明编码的特例 设有编码S4 S4中每个码字为a1a2a3a4 若增加三位校验位a5a6a7 从而使它成为长度为7的码字a1a2a3a4a5a6a7 其中校验位a5a6a7应满足下列方程 a1 2a2 2a3 2a5 0 2 1 a1 2a2 2a4 2a6 0 2 2 a1 2a3 2a4 2a7 0 2 3 也就是说要满足 a5 a1 2a2 2a3a6 a1 2a2 2a4a7 a1 2a3 2a4 因此 a1 a2 a3 a4一旦确定 则校验位a5 a6 a7可根据上述方程唯一确定 这样我们由S4就可以得到一个长度为7的编码C 如表2 1所示 表2 1 上述的编码C能发现一个错误并纠正单个错误 因为如果C中码字发生单错 则上述三个方程必定至少有一个等式不满足 当C中码字发生单错后 不同的字位错误可使方程中不同的等式不成立 如当a2发生错误时必有方程 2 1 2 2 不成立 而当a3发生错误时必有方程 2 1 2 3 不成立 方程中三个等式的8种组合可对应a1 a7的七个码元每个码的错误以及一个正确无误的码字 为讨论方便 我们建立三个谓词 P1 a1 a2 a7 a1 2a2 2a3 2a5 0P2 a1 a2 a7 a1 2a2 2a4 2a6 0P3 a1 a2 a7 a1 2a3 2a4 2a7 0这三个谓词的真假与对应等式是否成立相一致 我们建立三个集合S1 S2 S3分别对应P1 P2 P3 令S1 a1 a2 a3 a5 S2 a1 a2 a4 a6 S3 a1 a3 a4 a7 显然 Si是使Pi为假的所有出错字的集合 我们可构成下面7个非空集合 从这七个集合我们可以决定出错位 例如 即表示a3 S2 a3 S1 a3 S3 所以a3出错 则必有P2为真 P1 P3为假 反之亦然 如此类推 可得到表2 2所示的纠错对照表 从表中可看出这种编码C能纠正一个错误 2 2纠错对照表 我们将上例加以抽象 首先将方程 2 1 2 2 2 3 表示为矩阵形式 H XT T1110100其中H 11010101011001 X a1 a2 a3 a4 a5 a6 a7 0 0 0 XT T分别是X 的转置矩阵 这里加法运算为 2 可见 一个编码可由矩阵H确定 而它的纠错能力可由H的特性决定 下面讨论矩阵H 定义2 5重量 Weight 一个码字X所含1的个数称为此码字的重量 记为W X 例如 码字001011的重量为3 码字100000的重量为1 码字00 0的重量为0 通常将00 0记为0 或 利用码字的重量 我们有如下结论 1 设有码C 对任意X Y C 有H X Y H X Y W X Y 2 群码C中非零码字的最小重量等于此群码的最小距离 即 3 设H是k行n列矩阵 X x1x2 xn 并设集合G X H XT T 这里加法运算为 2 则 G 是群 即G是群码 上述介绍的汉明码就是群码 定义2 6群码G X H XT T 称为由H生成的群码 而G中每一个码字称为由H生成的码字 矩阵H称为一致校验矩阵 UniformCheckMatrix 现在我们介绍矩阵列向量的概念 设矩阵H为 此时矩阵H可记为H h1h2h3 hn 而hi叫做矩阵H的第i个列向量 ColumnVector 我们有如下结论 1 一致校验矩阵H生成一个重量为p的码字的充分必要条件是在H中存在p个列向量 它们的按位加为 T 2 由H生成的群码的最小距离等于H中列向量按位加为 T的最小列向量数 这个结论建立了最小距离与列向量之间的联系 前面结论我们知道 一个码的纠错能力由其最小距离决定 故有 一个群码的纠错能力可由其一致校验矩阵H中列向量按位加为 T的最小列向量数决定 故只要选取适当的H就可使其生成的码达到预定的纠错能力 对于前面所述的汉明码 它的一致校验矩阵H中没有零向量 且各列向量之间均互不相同 但它的第二 三 四列向量的按位加为 T 由此结论可知这个码的最小距离为3 而且可知此群必能纠正单个错误 将上述汉明码推广到一般情况 码C的每一码字X由信息位x1x2 xm及附加校验位xm 1xm 2 xm k组成 其形式为X x1x2 xmxm 1xm 2 xm