代数系统在计算机科学中的应用.pptVIP

　　　　　　　表2－1 a1 a2 a3 a4 a5 a6 a7 a1 a2 a3 a4 a5 a6 a7 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 1 0 1 0 0 1 0 0 0 1 1 1 1 1 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 0 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 第30页，共45页，编辑于2022年，星期一 　上述的编码C能发现一个错误并纠正单个错误。因为如果C中码字发生单错，则上述三个方程必定至少有一个等式不满足；当C中码字发生单错后，不同的字位错误可使方程中不同的等式不成立，如当a2发生错误时必有方程（2－1）、（2－2）不成立，而当a3发生错误时必有方程（2－1）、（2－3）不成立，方程中三个等式的8种组合可对应a1~a7的七个码元每个码的错误以及一个正确无误的码字。 第31页，共45页，编辑于2022年，星期一 　为讨论方便，我们建立三个谓词： 　　　P1(a1,a2,…,a7): a1 +2 a2 +2 a3 +2 a5=0 　　　P2(a1,a2,…,a7): a1 +2 a2 +2 a4 +2 a6=0 　　　P3(a1,a2,…,a7): a1 +2 a3 +2 a4 +2 a7=0 这三个谓词的真假与对应等式是否成立相一致。 　　我们建立三个集合S1，S2，S3分别对应P1，P2，P3。令 　　　　S1＝｛a1,a2,a3,a5｝ S2＝｛a1,a2,a4,a6｝ 　　　　S3＝｛a1,a3,a4,a7｝ 第32页，共45页，编辑于2022年，星期一 代数系统的应用 * 代数系统在计算机科学中的应用 第1页，共45页，编辑于2022年，星期一 　　　人们研究和考察现实世界中各种现象或过程，往往要借助某些数学工具。在代数中，可以用正整数集合上的加法运算来描述企业产品的累计数，可以用集合之间的“并”、“交”运算来描述单位与单位之间的关系等。我们所接触过的数学结构，连续的或离散的，常常是对研究对象（自然数、实数、多项式、矩阵、命题、集合乃至图）定义各种运算（加、减、乘，与、或、非，并、交、补），然后讨论这些对象及运算的有关性质。 第2页，共45页，编辑于2022年，星期一 　　　针对某个具体问题选用适宜的数学结构去进行较为确切的描述，这就是所谓“数学模型”。可见，数学结构在数学模型中占有极为重要的位置。而代数系统是一类特殊的数学结构——由对象集合及运算组成的数学结构，我们通常称它为代数结构。它在计算机科学中有着广泛的应用，对计算机科学的产生和发展有重大影响；反过来，计算机科学的发展对抽象代数学又提出了新的要求，促使抽象代数学不断涌现新概念，发展新理论。 第3页，共45页，编辑于2022年，星期一 　　　格与布尔代数的理论成为电子计算机硬件设计和通讯系统设计中的重要工具。半群理论在自动机和形式语言研究中发挥了重要作用。关系代数理论成为最流行的数据库的理论模型。格论是计算机语言的形式语义的理论基础。抽象代数规范理论和技术广泛应用于计算机软件形式说明和开发，以及硬件体系结构设计。有限域的理论是编码理论的数学基础，在通讯中发挥了重要作用。在计算机算法设计与分析中，代数算法研究占有主导地位。 第4页，共45页，编辑于2022年，星期一 纠错码 一、纠错码概述 我们知道，在计算机中和数据通信中，经常需要将二进制数字信号进行传递，这种传递的距离近则数米、数毫米，远则超过数千公里。在传递住处过程中，由于存在着各种干扰，可能会使二进制信号产生失真现象，即在传递过程中二进制信号0可能会变成1，1可能会变成0。 第5页，共45页，编辑于2022年，星期一 图2.1是一个二进制信号传递的简单模型，它有一个发送端和一个接收端，二进制信号串X=x1x2…xn 从发送端发出经传输介质而至接收端。由于存在着干扰对传输介质的影响，因而接收端收到的二进制信号串 中的 可能不一定就与xi相等，从而产生了二进制信号的传递错误。 发送端 接收端 X=x1x2 …xn 干扰 图2.1 第6页，共45页，编辑于2022年，星期一 由于在计算机中和数据通信系统中的信号传递是非常的频繁与广泛，因此，如何防止传输错误就变得相当重要了，当然，要解决这个问题可