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

代数系统在计算机科学中的应用第一页，共四十二页，2022年，8月28日人们研究和考察现实世界中各种现象或过程，往往要借助某些数学工具。在代数中，可以用正整数集合上的加法运算来描述企业产品的累计数，可以用集合之间的“并”、“交”运算来描述单位与单位之间的关系等。我们所接触过的数学结构，连续的或离散的，常常是对研究对象（自然数、实数、多项式、矩阵、命题、集合乃至图）定义各种运算（加、减、乘，与、或、非，并、交、补），然后讨论这些对象及运算的有关性质。第二页，共四十二页，2022年，8月28日针对某个具体问题选用适宜的数学结构去进行较为确切的描述，这就是所谓“数学模型”。可见，数学结构在数学模型中占有极为重要的位置。而代数系统是一类特殊的数学结构——由对象集合及运算组成的数学结构，我们通常称它为代数结构。它在计算机科学中有着广泛的应用，对计算机科学的产生和发展有重大影响；反过来，计算机科学的发展对抽象代数学又提出了新的要求，促使抽象代数学不断涌现新概念，发展新理论。第三页，共四十二页，2022年，8月28日格与布尔代数的理论成为电子计算机硬件设计和通讯系统设计中的重要工具。半群理论在自动机和形式语言研究中发挥了重要作用。关系代数理论成为最流行的数据库的理论模型。格论是计算机语言的形式语义的理论基础。抽象代数规范理论和技术广泛应用于计算机软件形式说明和开发，以及硬件体系结构设计。有限域的理论是编码理论的数学基础，在通讯中发挥了重要作用。在计算机算法设计与分析中，代数算法研究占有主导地位。第四页，共四十二页，2022年，8月28日纠错码一、纠错码概述我们知道，在计算机中和数据通信中，经常需要将二进制数字信号进行传递，这种传递的距离近则数米、数毫米，远则超过数千公里。在传递住处过程中，由于存在着各种干扰，可能会使二进制信号产生失真现象，即在传递过程中二进制信号0可能会变成1，1可能会变成0。第五页，共四十二页，2022年，8月28日

图2.1是一个二进制信号传递的简单模型，它有一个发送端和一个接收端，二进制信号串X=x1x2…xn

从发送端发出经传输介质而至接收端。由于存在着干扰对传输介质的影响，因而接收端收到的二进制信号串中的可能不一定就与xi相等，从而产生了二进制信号的传递错误。发送端接收端X=x1x2…xn干扰图2.1第六页，共四十二页，2022年，8月28日

由于在计算机中和数据通信系统中的信号传递是非常的频繁与广泛，因此，如何防止传输错误就变得相当重要了，当然，要解决这个问题可以有不同的途径。人们所想到的第一个途径是提高设备的抗干扰能力和信号的抗干扰能力。但是，大家都知道，这种从物理角度去提高抗干扰能力并不能完全消除错误的出现。第七页，共四十二页，2022年，8月28日

第二个途径就是我们所要谈到的采用采用纠错码（ErrorCorrectingCode）的方法以提高抗干扰能力。这种纠错码的方法是从编码上下功夫，使得二进制数码在传递过程中一旦出错，在接收端的纠错码装置就能立刻发现错误，并将其纠正。由于这种方法简单易行，因此目前在计算机中和数据通信系统中被广泛采用。采用这种方法后，二进制信号传递模型就可以变为图2.2所示的模型了。第八页，共四十二页，2022年，8月28日图2.2通信系统模型信源信源编码加密信道编码信道信道译码解密信源译码信宿密钥源噪声密钥源该模型按功能分为信源、编码器、信道、译码器、信宿第九页，共四十二页，2022年，8月28日

但是，为什么纠错码具有发现错误、纠正错误的能力呢？纠错码又是按什么样的原理去编的呢？为了说明这些问题，我们首先介绍一些基本概念。第十页，共四十二页，2022年，8月28日定义2.1

由0和1组成的串称为字（Word），一些字的集合称为码（Code）。码中的字称为码字（CodeWord）。不在码中的字称为废码（InvalidCode）。码中的每个二进制信号0或1称为码元（CodeLetter）。我们下面举出几个关于纠错码例子。第十一页，共四十二页，2022年，8月28日例2.1

设有长度为2的字，它们一共可有22=4个，它们所组成的字集S2={00，01，10，11}。当选取编码为S2时，这种编码不具有抗干扰能力。因为当S2中的一个字如10，在传递过程中其第一个码元1变为0，因而整个字成为00时，由于00也是S2中的字，故我们不能发现传递中是否出错。第十二页，共四十二页，2022年，8月28日

当我们选取S2的一个子集如C2={01，10}作为编码时就会发生另一种完全不同的情况。因为此时00和11均为废码，而当01在传递过程中第一个码元由0变为1，即整个字成为11时，由于11是废码，因而我们发现传递过程中出现了错误。对10也有同样的情况。01第一个码元错成11第二个码元错成0010第一个码元错成00第二个码元错成11第十三页，共四十二页，2022年，8月28日

可见，这种编码有一个缺点，即它只能发现错误而不能纠正错误，因此我们还需要选择另一种能纠错的编码。第十四页，共四十二页，2022年，8月28日例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，我们不仅能发现错误而且能纠正错误。第十五页，共四十二页，2022年，8月28日

当然，上述编码还有一个缺点，就是它只能发现并纠正单个错误。当错误超过两个码元时，它就既不能发现错误，更无法纠正了。第十六页，共四十二页，2022年，8月28日二、纠错码的纠错能力

前面例子中我们发现C2编码仅能发现错误，按C3编码可发现并纠正单个错误。可见，不能的编码具有不同的纠错能力。下面介绍编码方式与纠错能力之间的联系。第十七页，共四十二页，2022年，8月28日设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)，我们称运算ο为按位加。显然，<Sn,ο>是一个代数系统，且运算ο满足结合律，它的幺元为00…0，每个元素的逆元都是它自身。因此，<Sn,ο>是一个群。第十八页，共四十二页，2022年，8月28日定义2.2Sn的任一非空子集C，如果是<C,ο>群，即C是Sn的子群，则称码C是群码(GroupCode)。定义2.3

设X=x1x2…xn和Y=y1y2…yn是Sn中的两个元素，称为X与Y的汉明距离（HammingDistance）。第十九页，共四十二页，2022年，8月28日

从定义可以看出，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)。第二十页，共四十二页，2022年，8月28日（3）H(X,Y)+H(Y,Z)≥H(X,Z)的证明证明：定义

H(xi,yi)=则

H(xi,zi)≤H(xi,yi)+H(yi,zi)从而0xi=yi1xi≠yi第二十一页，共四十二页，2022年，8月28日定义2.4一个码C中所有不同码字的汉明距离的极小值称为码C的最小距离（MinimumDistance）,记为dmin(C)。即例如，dmin(S2)=dmin(S3)=1，dmin(C2)=2，dmin(C3)=3。利用编码C的最小距离，可以刻画编码方式与纠错能力之间的关系，我们有以下两定理：第二十二页，共四十二页，2022年，8月28日〖定理2.1〗一个码C能检查出不超过k个错误的充分必要条件为dmin(C)≥k+1。〖定理2.2〗一个码C能纠正k个错误的充分必要条件是dmin(C)≥2k+1。第二十三页，共四十二页，2022年，8月28日例子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既不能检查错误也不能纠正错误。从而我们知道一个编码如果包含了某个长度的所有码字，则此编码一定无抗干扰能力。第二十四页，共四十二页，2022年，8月28日例子2.4

奇偶校验码（Paritycode)的编码我们知道，编码S2={00，01，10，11}没有抗干扰能力。但我们可以在S2的每个码字后增加一位（叫奇偶校验位），这一位是这样安排的，它使每个码字所含1的个数为偶数，按这种方法编码后S2就变为

S2′={000，011，101，110}而它的最小距离dmin(S2′)=2，故定理2.1可知，它可想出单个错误。而事实也是如此，当传递过程中发生单个错误则码字就变为含有奇数个1的废码。第二十五页，共四十二页，2022年，8月28日类似地，增加奇偶校验位使码字所含1的个数为奇数时也可得到相同的效果。我们可以把上述结果推广到Sn中去，不管n多大，只要增加一奇偶校验位总可能查出一个错误。这种方法在计算机中是使用很普遍的一种纠错码，它的优点是所付出的代价较小（只增加一位附加的奇偶校验位），而且这种码的生成与检查也很简单，它的缺点是不能纠正错误。第二十六页，共四十二页，2022年，8月28日三、纠错码的选择前面分析，我们发现S2无纠错能力，但在S2中选取C2后，C2具有发现单错的能力。同样，S3无纠错能力，但在S3中选取C3后，C3具有纠正单错的能力。从这里可以看出，如何从一些编码中选取一些码字组成新码，使其具有一定的纠错能力是一个很重要的课题。下面我们介绍一种很重要的编码——汉明编码，这种编码能发现并纠正单个错误。第二十七页，共四十二页，2022年，8月28日（一）汉明编码的特例设有编码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+2a3

a6=a1+2a2+2a4

a7=a1+2a3+2a4第二十八页，共四十二页，2022年，8月28日因此，a1,a2,a3,a4一旦确定，则校验位a5,a6,a7可根据上述方程唯一确定。这样我们由S4就可以得到一个长度为7的编码C，如表2－1所示。第二十九页，共四十二页，2022年，8月28日表2－1a1a2a3a4a5a6a7a1a2a3a4a5a6a70000000100011100010111001100001010110100100011111101100101001101100001010110111010100110011111010001110001111111第三十页，共四十二页，2022年，8月28日

上述的编码C能发现一个错误并纠正单个错误。因为如果C中码字发生单错，则上述三个方程必定至少有一个等式不满足；当C中码字发生单错后，不同的字位错误可使方程中不同的等式不成立，如当a2发生错误时必有方程（2－1）、（2－2）不成立，而当a3发生错误时必有方程（2－1）、（2－3）不成立，方程中三个等式的8种组合可对应a1~a7的七个码元每个码的错误以及一个正确无误的码字。第三十一页，共四十二页，2022年，8月28日为讨论方便，我们建立三个谓词：

P1(a1,a2,…,a7):a1+2a2+2a3+2a5=0

P2(a1,a2,…,a7):a1+2a2+2a4+2a6=0

P3(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｝第三十二页，共四十二页，2022年，8月28日显然，Si是使Pi为假的所有出错字的集合。我们可构成下面7个非空集合：从这七个集合我们可以决定出错位。例如，

即表示a3∈S2，a3∈S1，a3∈S3，所以a3出错，则必有P2为真，P1、P3为假。反之亦然。如此类推，可得到表2－2所示的纠错对照表。从表中可看出这种编码C能纠正一个错误。第三十三页，共四十二页，2022年，8月28日2－2纠错对照表P1P2P3出错码元000a1001a2010a3011a4100a5101a6110a7111无第三十四页，共四十二页，2022年，8月28日我们将上例加以抽象，首先将方程（2－1）、（2－2）、（2－3）表示为矩阵形式：

H·XT＝ΘT

1

1

1

0

1

0

0其中H＝1

1

0

1

0

1

0

1

0

1

1

0

0

1，X＝(a1,a2,a3,a4,a5,a6,a7),Θ=(0,0,0),XT、ΘT分别是X、Θ的转置矩阵，这里加法运算为＋2。可见，一个编码可由矩阵H确定，而它的纠错能力可由H的特性决定。下面讨论矩阵H。第三十五页，共四十二页，2022年，8月28日定义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)；第三十六页，共四十二页，2022年，8月28日（2）群码C中非零码字的最小重量等于此群码的最小距离。即（3）设H是k行n列矩阵，X=x1x2…xn,并设集合G＝｛X｜H·XT＝ΘT｝，这里加法运算为＋2，则＜G，◦＞是群，即G是群码。上述介绍的汉明码就是群码。第三十七页，共四十二页，2022年，8月28日定义2.6群码G＝｛X｜H·XT＝ΘT｝称为由H生成的群码，而G中每一个码字称为由H生成的码字，矩阵H称