代数系统在计算机科学中的应用(new)综述.ppt

　　　人们研究和考察现实世界中各种现象或过程，往往要借助某些数学工具。在代数中，可以用正整数集合上的加法运算来描述企业产品的累计数，可以用集合之间的“并”、“交”运算来描述单位与单位之间的关系等。我们所接触过的数学结构，连续的或离散的，常常是对研究对象（自然数、实数、多项式、矩阵、命题、集合乃至图）定义各种运算（加、减、乘，与、或、非，并、交、补），然后讨论这些对象及运算的有关性质。 　　　针对某个具体问题选用适宜的数学结构去进行较为确切的描述，这就是所谓“数学模型”。可见，数学结构在数学模型中占有极为重要的位置。而代数系统是一类特殊的数学结构——由对象集合及运算组成的数学结构，我们通常称它为代数结构。它在计算机科学中有着广泛的应用，对计算机科学的产生和发展有重大影响；反过来，计算机科学的发展对抽象代数学又提出了新的要求，促使抽象代数学不断涌现新概念，发展新理论。 　　　格与布尔代数的理论成为电子计算机硬件设计和通讯系统设计中的重要工具。半群理论在自动机和形式语言研究中发挥了重要作用。关系代数理论成为最流行的数据库的理论模型。格论是计算机语言的形式语义的理论基础。抽象代数规范理论和技术广泛应用于计算机软件形式说明和开发，以及硬件体系结构设计。有限域的理论是编码理论的数学基础，在通讯中发挥了重要作用。在计算机算法设计与分析中，代数算法研究占有主导地位。 纠错码 一、纠错码概述 我们知道，在计算机中和数据通信中，经常需要将二进制数字信号进行传递，这种传递的距离近则数米、数毫米，远则超过数千公里。在传递住处过程中，由于存在着各种干扰，可能会使二进制信号产生失真现象，即在传递过程中二进制信号0可能会变成1，1可能会变成0。 图2.1是一个二进制信号传递的简单模型，它有一个发送端和一个接收端，二进制信号串X=x1x2…xn 从发送端发出经传输介质而至接收端。由于存在着干扰对传输介质的影响，因而接收端收到的二进制信号串 中的 可能不一定就与xi相等，从而产生了二进制信号的传递错误。 由于在计算机中和数据通信系统中的信号传递是非常的频繁与广泛，因此，如何防止传输错误就变得相当重要了，当然，要解决这个问题可以有不同的途径。人们所想到的第一个途径是提高设备的抗干扰能力和信号的抗干扰能力。但是，大家都知道，这种从物理角度去提高抗干扰能力并不能完全消除错误的出现。 第二个途径就是我们所要谈到的采用采用纠错码（Error Correcting Code）的方法以提高抗干扰能力。这种纠错码的方法是从编码上下功夫，使得二进制数码在传递过程中一旦出错，在接收端的纠错码装置就能立刻发现错误，并将其纠正。由于这种方法简单易行，因此目前在计算机中和数据通信系统中被广泛采用。采用这种方法后，二进制信号传递模型就可以变为图2.2所示的模型了。 图2.2　通信系统模型 但是，为什么纠错码具有发现错误、纠正错误的能力呢？纠错码又是按什么样的原理去编的呢？为了说明这些问题，我们首先介绍一些基本概念。 定义2.1 由0和1组成的串称为字（Word），一些字的集合称为码（Code）。码中的字称为码字（Code Word）。不在码中的字称为废码（Invalid Code）。码中的每个二进制信号0或1称为码元（Code Letter）。 我们下面举出几个关于纠错码例子。 例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也有同样的情况。 可见，这种编码有一个缺点，即它只能发现错误而不能纠正错误，因此我们还需要选择另一种能纠错的编码。 例2.2 考虑长度为3的字 它们一共可有23=8个，它们所组成的字集S3={000，001，010，011，100，101，110，111} 选取编码C3={101，010}。利用此编码我们不仅能