代数系统在计算机科学中应用(new)

代数系统的应用*代数系统的应用*　　　人们研究和考察现实世界中各种现象或过程，往往要借助某些数学工具。在代数中，可以用正整数集合上的加法运算来描述企业产品的累计数，可以用集合之间的“并”、“交”运算来描述单位与单位之间的关系等。我们所接触过的数学结构，连续的或离散的，常常是对研究对象（自然数、实数、多项式、矩阵、命题、集合乃至图）定义各种运算（加、减、乘，与、或、非，并、交、补），然后讨论这些对象及运算的有关性质。代数系统的应用*　　　针对某个具体问题选用适宜的数学结构去进行较为确切的描述，这就是所谓“数学模型”。可见，数学结构在数学模型中占有极为重要的位置。而代数系统是一类特殊的数学结构——由对象集合及运算组成的数学结构，我们通常称它为代数结构。它在计算机科学中有着广泛的应用，对计算机科学的产生和发展有重大影响；反过来，计算机科学的发展对抽象代数学又提出了新的要求，促使抽象代数学不断涌现新概念，发展新理论。代数系统的应用*　　　格与布尔代数的理论成为电子计算机硬件 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 和通讯系统设计中的重要工具。半群理论在自动机和形式语言研究中发挥了重要作用。关系代数理论成为最流行的数据库的理论模型。格论是计算机语言的形式语义的理论基础。抽象代数 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 理论和技术广泛应用于计算机软件形式说明和开发，以及硬件体系结构设计。有限域的理论是编码理论的数学基础，在通讯中发挥了重要作用。在计算机算法设计与分析中，代数算法研究占有主导地位。代数系统的应用*纠错码一、纠错码概述我们知道，在计算机中和数据通信中，经常需要将二进制数字信号进行传递，这种传递的距离近则数米、数毫米，远则超过数千公里。在传递住处过程中，由于存在着各种干扰，可能会使二进制信号产生失真现象，即在传递过程中二进制信号0可能会变成1，1可能会变成0。代数系统的应用*图2.1是一个二进制信号传递的简单模型，它有一个发送端和一个接收端，二进制信号串X=x1x2…xn从发送端发出经传输介质而至接收端。由于存在着干扰对传输介质的影响，因而接收端收到的二进制信号串中的可能不一定就与xi相等，从而产生了二进制信号的传递错误。代数系统的应用*由于在计算机中和数据通信系统中的信号传递是非常的频繁与广泛，因此，如何防止传输错误就变得相当重要了，当然，要解决这个问题可以有不同的途径。人们所想到的第一个途径是提高设备的抗干扰能力和信号的抗干扰能力。但是，大家都知道，这种从物理角度去提高抗干扰能力并不能完全消除错误的出现。代数系统的应用*第二个途径就是我们所要谈到的采用采用纠错码（ErrorCorrectingCode）的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 以提高抗干扰能力。这种纠错码的方法是从编码上下功夫，使得二进制数码在传递过程中一旦出错，在接收端的纠错码装置就能立刻发现错误，并将其纠正。由于这种方法简单易行，因此目前在计算机中和数据通信系统中被广泛采用。采用这种方法后，二进制信号传递模型就可以变为图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第二个码元错成0010第一个码元错成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)，我们称运算ο为按位加。显然，<Sn,ο>是一个代数系统，且运算ο满足结合律，它的幺元为00…0，每个元素的逆元都是它自身。因此，<Sn,ο>是一个群。代数系统的应用*定义2.2Sn的任一非空子集C，如果是<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)从而0xi=yi1xi≠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，如 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 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=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｝代数系统的应用*　　显然，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＝Θ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。代数系统的应用*定义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+k　　X中信息位与校验位之间的关系如下：　　　　xm+i=qi1x1+2qi2x2+2···+2qimxm,(i=1,2,…,k)而qij∈｛0,1｝（i=1,2,…,k;j=1,2,…,m),作矩阵H为　　　　　　H＝（Qk×mIk×k）其中代数系统的应用*码C的任一码字均满足方程　　　　　　H·XT＝ΘT令n=m+k，我们称这种码为（n,m）码。　　要使码C能纠正单个错误，由前面结论可知，只要对H作适当赋值，使得H的列向量均不相同且无零列向量，这样可保证C的最小距离大于2，即要求H中的Q的列向量均不为Θ，不出现I中的k个向量且互不相同。代数系统的应用*　　　Q的列向量是k维的，故可有2k个不同的列向量，而供Q选择的列向量是这2k个列向量中除去I中的k个列向量及零列向量以外的所有2k-k-1个列向量。故我们可在这些列向量中任选m个列向量组成Q。所以m与k必须满足：m≤2k-k-1或2k≥m+k+1=n+1或k≥log2(n+1)　因此只要码C中校验位位数k满足：k≥log2(n+1)，总可以在2k-k-1个列向量任选m个列向量组成Q,而使C具有纠正单个错误的能力。代数系统的应用*　　从上述分析也可看出如何组织具有一定要求的纠错能力的纠错码。例子：设n=7,k≥log2(n+1)=log28=3,我们取k=3,则m=4,所以一致校验矩阵H中Q应有四个列向量。而2k-k-1＝23-3-1=4，故Q可由四个列向量唯一确定，它们是：即H为上述的汉明码。