搜索
代数系统的应用1代数系统的应用2人们研究和考察现实世界中各种现象或过程，往往要借助某些数学工具。在代数中，可以用正整数集合上的加法运算来描述企业产品的累计数，可以用集合之间的“并”、“交”运算来描述单位与单位之间的关系等。我们所接触过的数学结构，连续的或离散的，常常是对研究对象（自然数、实数、多项式、矩阵、命题、集合乃至图）定义各种运算（加、减、乘，与、或、非，并、交、补），然后讨论这些对象及运算的有关性质。代数系统的应用3针对某个具体问题选用适宜的数学结构去进行较为确切的描述，这就是所谓“数学模型”。可见，数学结构在数学模型中占有极为重要的位置。而代数系统是一类特殊的数学结构——由对象集合及运算组成的数学结构，我们通常称它为代数结构。它在计算机科学中有着广泛的应用，对计算机科学的产生和发展有重大影响；反过来，计算机科学的发展对抽象代数学又提出了新的要求，促使抽象代数学不断涌现新概念，发展新理论。代数系统的应用4格与布尔代数的理论成为电子计算机硬件设计和通讯系统设计中的重要工具。半群理论在自动机和形式语言研究中发挥了重要作用。关系代数理论成为最流行的数据库的理论模型。格论是计算机语言的形式语义的理论基础。抽象代数规范理论和技术广泛应用于计算机软件形式说明和开发，以及硬件体系结构设计。有限域的理论是编码理论的数学基础，在通讯中发挥了重要作用。在计算机算法设计与分析中，代数算法研究占有主导地位。代数系统的应用5纠错码一、纠错码概述我们知道，在计算机中和数据通信中，经常需要将二进制数字信号进行传递，这种传递的距离近则数米、数毫米，远则超过数千公里。在传递住处过程中，由于存在着各种干扰，可能会使二进制信号产生失真现象，即在传递过程中二进制信号0可能会变成1，1可能会变成0。代数系统的应用6图2.1是一个二进制信号传递的简单模型，它有一个发送端和一个接收端，二进制信号串X=x1x2…xn从发送端发出经传输介质而至接收端。由于存在着干扰对传输介质的影响，因而接收端收到的二进制信号串中的可能不一定就与xi相等，从而产生了二进制信号的传递错误。nxxxX...21ix发送端接收端X=x1x2…xnnxxxX...21干扰图2.1代数系统的应用7由于在计算机中和数据通信系统中的信号传递是非常的频繁与广泛，因此，如何防止传输错误就变得相当重要了，当然，要解决这个问题可以有不同的途径。人们所想到的第一个途径是提高设备的抗干扰能力和信号的抗干扰能力。但是，大家都知道，这种从物理角度去提高抗干扰能力并不能完全消除错误的出现。代数系统的应用8第二个途径就是我们所要谈到的采用采用纠错码（ErrorCorrectingCode）的方法以提高抗干扰能力。这种纠错码的方法是从编码上下功夫，使得二进制数码在传递过程中一旦出错，在接收端的纠错码装置就能立刻发现错误，并将其纠正。由于这种方法简单易行，因此目前在计算机中和数据通信系统中被广泛采用。采用这种方法后，二进制信号传递模型就可以变为图2.2所示的模型了。代数系统的应用9图2.2通信系统模型信源信源编码加密信道编码信道信道译码解密信源译码信宿密钥源噪声密钥源该模型按功能分为信源、编码器、信道、译码器、信宿代数系统的应用10但是，为什么纠错码具有发现错误、纠正错误的能力呢？纠错码又是按什么样的原理去编的呢？为了说明这些问题，我们首先介绍一些基本概念。代数系统的应用11定义2.1由0和1组成的串称为字（Word），一些字的集合称为码（Code）。码中的字称为码字（CodeWord）。不在码中的字称为废码（InvalidCode）。码中的每个二进制信号0或1称为码元（CodeLetter）。我们下面举出几个关于纠错码例子。代数系统的应用12例2.1设有长度为2的字，它们一共可有22=4个，它们所组成的字集S2={00，01，10，11}。当选取编码为S2时，这种编码不具有抗干扰能力。因为当S2中的一个字如10，在传递过程中其第一个码元1变为0，因而整个字成为00时，由于00也是S2中的字，故我们不能发现传递中是否出错。代数系统的应用13当我们选取S2的一个子集如C2={01，10}作为编码时就会发生另一种完全不同的情况。因为此时00和11均为废码，而当01在传递过程中第一个码元由0变为1，即整个字成为11时，由于11是废码，因而我们发现传递过程中出现了错误。对10也有同样的情况。01第一个码元错成11第二个码元错成0010第一个码元错成00第二个码元错成11代数系统的应用14可见，这种编码有一个缺点，即它只能发现错误而不能纠正错误，因此我们还需要选择另一种能纠错的编码。代数系统的应用15例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，我们不仅能发现错误而且能纠正错误。代数系统的应用16当然，上述编码还有一个缺点，就是它只能发现并纠正单个错误。当错误超过两个码元时，它就既不能发现错误，更无法纠正了。代数系统的应用17二、纠错码的纠错能力前面例子中我们发现C2编码仅能发现错误，按C3编码可发现并纠正单个错误。可见，不能的编码具有不同的纠错能力。下面介绍编码方式与纠错能力之间的联系。代数系统的应用18设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,ο是一个群。代数系统的应用19定义2.2Sn的任一非空子集C，如果是C,ο群，即C是Sn的子群，则称码C是群码(GroupCode)。定义2.3设X=x1x2…xn和Y=y1y2…yn是Sn中的两个元素，称为X与Y的汉明距离（HammingDistance）。niiiyxYXH12)(),(代数系统的应用20从定义可以看出，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)。代数系统的应用21（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),(),(),(),(),(),(11ZYHYXHzyHyxHzxHZXHniiiniiiniii代数系统的应用22定义2.4一个码C中所有不同码字的汉明距离的极小值称为码C的最小距离（MinimumDistance）,记为dmin(C)。即例如，dmin(S2)=dmin(S3)=1，dmin(C2)=2，dmin(C3)=3。利用编码C的最小距离，可以刻画编码方式与纠错能力之间的关系，我们有以下两定理：)),((,)(minminYXHCYXCdYX代数系统的应用23〖定理2.1〗一个码C能检查出不超过k个错误的充分必要条件为dmin(C)≥k+1。〖定理2.2〗一个码C能纠正k个错误的充分必要条件是dmin(C)≥2k+1。代数系统的应用24例子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既不能检查错误也不能纠正错误。从而我们知道一个编码如果包含了某个长度的所有码字，则此编码一定无抗干扰能力。代数系统的应用25例子2.4奇偶校验码（Paritycode)的编码我们知道，编码S2={00，01，10，11}没有抗干扰能力。但我们可以在S2的每个码字后增加一位（叫奇偶校验位），这一位是这样安排的，它使每个码字所含1的个数为偶数，按这种方法编码后S2就变为S2′={000，011，101，110}而它的最小距离dmin(S2′)=2，故定理2.1可知，它可想出单个错误。而事实也是如此，当传递过程中发生单个错误则码字就变为含有奇数个1的废码。代数系统的应用26类似地，增加奇偶校验位使码字所含1的个数为奇数时也可得到相同的效果。我们可以把上述结果推广到Sn中去，不管n多大，只要增加一奇偶校验位总可能查出一个错误。这种方法在计算机中是使用很普遍的一种纠错码，它的优点是所付出的代价较小（只增加一位附加的奇偶校验位），而且这种码的生成与检查也很简单，它的缺点是不能纠正错误。代数系统的应用27三、纠错码的选择前面分析，我们发现S2无纠错能力，但在S2中选取C2后，C2具有发现单错的能力。同样，S3无纠错能力，但在S3中选取C3后，C3具有纠正单错的能力。从这里可以看出，如何从一些编码中选取一些码字组成新码，使其具有一定的纠错能力是一个很重要的课题。下面我们介绍一种很重要的编码——汉明编码，这种编码能发现并纠正单个错误。代数系统的应用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+2a3a6=a1+2a2+2a4a7=a1+2a3+2a4代数系统的应用29因此，a1,a2,a3,a4一旦确定，则校验位a5,a6,a7可根据上述方程唯一确定。这样我们由S4就可以得到一个长度为7的编码C，如表2－1所示。代数系统的应用30表2－1a1a2a3a4a5a6a7a1a2a3a4a5a6a70000000100011100010111001100001010110100100011111101100101001101100001010110111010100110011111010001110001111111代数系统的应用31上述的编码C能发现一个错误并纠正单个错误。因为如果C中码字发生单错，则上述三个方程必定至少有一个等式不满足；当C中码字发生单错后，不同的字位错误可使方程中不同的等式不成立，如当a2发生错误时必有方程（2－1）、（2－2）不成立，而当a3发生错误时必有方程（2－1）、（2－3）不成立，方程中三个等式的8种组合可对应a1~a7的七个码元每个码的错误以及一个正确无误的码字。代数系统的应用32为讨论方便，我们建立三个谓词：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｝代数系统的应用33显然，Si是使Pi为假的所有出错字的集合。我们可构成下面7个非