代数系统在计算机科学中的应用课件.ppt

1、代数系统的应用代数系统的应用1代数系统的应用代数系统的应用2人们研究和考察现实世界中各种现象或过程，人们研究和考察现实世界中各种现象或过程，往往要借助某些数学工具。在代数中，可以用正往往要借助某些数学工具。在代数中，可以用正整数集合上的加法运算来描述企业产品的累计数，整数集合上的加法运算来描述企业产品的累计数，可以用集合之间的可以用集合之间的“并并”、“交交”运算来描述单运算来描述单位与单位之间的关系等。我们所接触过的数学结位与单位之间的关系等。我们所接触过的数学结构，连续的或离散的，常常是对研究对象（自然构，连续的或离散的，常常是对研究对象（自然数、实数、多项式、矩阵、命题、集合乃至图）数、

2、实数、多项式、矩阵、命题、集合乃至图）定义各种运算（加、减、乘，与、或、非，并、定义各种运算（加、减、乘，与、或、非，并、交、补），然后讨论这些对象及运算的有关性质。交、补），然后讨论这些对象及运算的有关性质。代数系统的应用代数系统的应用3针对某个具体问题选用适宜的数学结构去进针对某个具体问题选用适宜的数学结构去进行较为确切的描述，这就是所谓行较为确切的描述，这就是所谓“数学模型数学模型”。可见，数学结构在数学模型中占有极为重要的位可见，数学结构在数学模型中占有极为重要的位置。而代数系统是一类特殊的数学结构置。而代数系统是一类特殊的数学结构由对由对象集合及运算组成的数学结构，我们通常称它为象集

3、合及运算组成的数学结构，我们通常称它为代数结构。它在计算机科学中有着广泛的应用，代数结构。它在计算机科学中有着广泛的应用，对计算机科学的产生和发展有重大影响；反过来，对计算机科学的产生和发展有重大影响；反过来，计算机科学的发展对抽象代数学又提出了新的要计算机科学的发展对抽象代数学又提出了新的要求，促使抽象代数学不断涌现新概念，发展新理求，促使抽象代数学不断涌现新概念，发展新理论。论。代数系统的应用代数系统的应用4格与布尔代数的理论成为电子计算机硬件设格与布尔代数的理论成为电子计算机硬件设计和通讯系统设计中的重要工具。半群理论在自计和通讯系统设计中的重要工具。半群理论在自动机和形式语言研究中发挥

4、了重要作用。关系代动机和形式语言研究中发挥了重要作用。关系代数理论成为最流行的数据库的理论模型。格论是数理论成为最流行的数据库的理论模型。格论是计算机语言的形式语义的理论基础。抽象代数规计算机语言的形式语义的理论基础。抽象代数规范理论和技术广泛应用于计算机软件形式说明和范理论和技术广泛应用于计算机软件形式说明和开发，以及硬件体系结构设计。有限域的理论是开发，以及硬件体系结构设计。有限域的理论是编码理论的数学基础，在通讯中发挥了重要作用。编码理论的数学基础，在通讯中发挥了重要作用。在计算机算法设计与分析中，代数算法研究占有在计算机算法设计与分析中，代数算法研究占有主导地位。主导地位。代数系统的应

5、用代数系统的应用5纠错码纠错码一、纠错码概述一、纠错码概述 我们知道，在计算机中和数据通信中，我们知道，在计算机中和数据通信中，经常需要将二进制数字信号进行传递，这经常需要将二进制数字信号进行传递，这种传递的距离近则数米、数毫米，远则超种传递的距离近则数米、数毫米，远则超过数千公里。在传递住处过程中，由于存过数千公里。在传递住处过程中，由于存在着各种干扰，可能会使二进制信号产生在着各种干扰，可能会使二进制信号产生失真现象，即在传递过程中二进制信号失真现象，即在传递过程中二进制信号0可可能会变成能会变成1，1可能会变成可能会变成0。代数系统的应用代数系统的应用6 图图2.1是一个二进制信号传递的

6、简单模型，它有是一个二进制信号传递的简单模型，它有一个发送端和一个接收端，二进制信号串一个发送端和一个接收端，二进制信号串X=x1x2xn 从发送端发出经传输介质而至接收端。从发送端发出经传输介质而至接收端。由于存在着干扰对传输介质的影响，因而接收端收由于存在着干扰对传输介质的影响，因而接收端收到的二进制信号串到的二进制信号串 中的中的 可能不一可能不一定就与定就与xi相等，从而产生了二进制信号的传递错误。相等，从而产生了二进制信号的传递错误。nxxxX.21ix发送端发送端接收端接收端X=x1x2 xnnxxxX.21干扰干扰图图2.1代数系统的应用代数系统的应用7 由于在计算机中和数据通信

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

8、二个途径就是我们所要谈到的采用采用纠错码（错码（Error Correcting Code）的方法以提高抗）的方法以提高抗干扰能力。这种纠错码的方法是从编码上下功夫，干扰能力。这种纠错码的方法是从编码上下功夫，使得二进制数码在传递过程中一旦出错，在接收使得二进制数码在传递过程中一旦出错，在接收端的纠错码装置就能立刻发现错误，并将其纠正。端的纠错码装置就能立刻发现错误，并将其纠正。由于这种方法简单易行，因此目前在计算机中和由于这种方法简单易行，因此目前在计算机中和数据通信系统中被广泛采用。采用这种方法后，数据通信系统中被广泛采用。采用这种方法后，二进制信号传递模型就可以变为图二进制信号传递模型就

9、可以变为图2.2所示的模型所示的模型了。了。代数系统的应用代数系统的应用9图图2.2通信系统模型通信系统模型信信源源信信源源编编码码加加密密信信道道编编码码信道信道信信道道译译码码解解密密信信源源译译码码信信宿宿密密钥钥源源噪声噪声密密钥钥源源该模型按功能分为信源、编码器、信道、译码器、信宿该模型按功能分为信源、编码器、信道、译码器、信宿代数系统的应用代数系统的应用10 但是，为什么纠错码具有发现错误、纠但是，为什么纠错码具有发现错误、纠正错误的能力呢？纠错码又是按什么样的正错误的能力呢？纠错码又是按什么样的原理去编的呢？为了说明这些问题，我们原理去编的呢？为了说明这些问题，我们首先介绍一些基

10、本概念。首先介绍一些基本概念。代数系统的应用代数系统的应用11定义定义2.1 由由0和和1组成的串称为字（组成的串称为字（Word），一），一些字的集合称为码（些字的集合称为码（Code）。码中的字称）。码中的字称为码字（为码字（Code Word）。不在码中的字称为）。不在码中的字称为废码（废码（Invalid Code）。码中的每个二进制）。码中的每个二进制信号信号0或或1称为码元（称为码元（Code Letter）。）。 我们下面举出几个关于纠错码例子。我们下面举出几个关于纠错码例子。 代数系统的应用代数系统的应用12例例2.12.1 设有长度为设有长度为2的字，它们一共可有的字，它们一

11、共可有22=4个，它们所组成的字集个，它们所组成的字集S2=00，01，10，11。当选取编码为。当选取编码为S2时，这种编码不具有时，这种编码不具有抗干扰能力。因为当抗干扰能力。因为当S2中的一个字如中的一个字如10，在，在传递过程中其第一个码元传递过程中其第一个码元1变为变为0，因而整，因而整个字成为个字成为00时，由于时，由于00也是也是S2中的字，故我中的字，故我们不能发现传递中是否出错。们不能发现传递中是否出错。 代数系统的应用代数系统的应用13 当我们选取当我们选取S2的一个子集如的一个子集如C2=01，10作为作为编码时就会发生另一种完全不同的情况。编码时就会发生另一种完全不同的

12、情况。 因为此时因为此时00和和11均为废码，而当均为废码，而当01在传递过在传递过程中第一个码元由程中第一个码元由0变为变为1，即整个字成为，即整个字成为11时，时，由于由于11是废码，因而我们发现传递过程中出现了是废码，因而我们发现传递过程中出现了错误。对错误。对10也有同样的情况。也有同样的情况。 01第一个码元错成第一个码元错成11第二个码元错成第二个码元错成0010第一个码元错成第一个码元错成00第二个码元错成第二个码元错成11代数系统的应用代数系统的应用14 可见，这种编码有一个缺点，即它只能可见，这种编码有一个缺点，即它只能发现错误而不能纠正错误，因此我们还需发现错误而不能纠正错

13、误，因此我们还需要选择另一种能纠错的编码。要选择另一种能纠错的编码。代数系统的应用代数系统的应用15例例2.2 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。故如码字。

14、故如码字101在传递过程中任何一个码元出在传递过程中任何一个码元出现了错误，整个码字只会变为现了错误，整个码字只会变为111、100或或001，但，但是都可知其原码为是都可知其原码为101。对于码字。对于码字010也有类似的也有类似的情况。故对编码情况。故对编码C3，我们不仅能发现错误而且能，我们不仅能发现错误而且能纠正错误。纠正错误。代数系统的应用代数系统的应用16 当然，上述编码还有一个缺点，就是当然，上述编码还有一个缺点，就是它只能发现并纠正单个错误。当错误超过它只能发现并纠正单个错误。当错误超过两个码元时，它就既不能发现错误，更无两个码元时，它就既不能发现错误，更无法纠正了。法纠正了。

15、代数系统的应用代数系统的应用17二、纠错码的纠错能力二、纠错码的纠错能力 前面例子中我们发现前面例子中我们发现C2编码仅能发现编码仅能发现错误，按错误，按C3编码可发现并纠正单个错误。编码可发现并纠正单个错误。可见，不能的编码具有不同的纠错能力。可见，不能的编码具有不同的纠错能力。下面介绍编码方式与纠错能力之间的联系。下面介绍编码方式与纠错能力之间的联系。代数系统的应用代数系统的应用18设设Sn是长度为是长度为n的字集，即的字集，即 Sn=x1x2xn|xi=0或或1,i=1,2,n在在Sn上定义二元运算上定义二元运算为：为： X，YSn,X=x1x2xn, Y=y1y2yn, Z=X Y=z

16、1z2zn其中，其中，zi=xi +2 yi(i=1,2,n)而运算符而运算符+2为模为模2加运算加运算(即即0+21=1+20=1,0+20=1+21=0)， 我们称运算我们称运算为按位为按位加。加。 显然，显然，是一个代数系统，且运算是一个代数系统，且运算满足结满足结合律，它的幺元为合律，它的幺元为000，每个元素的逆元都是它自，每个元素的逆元都是它自身。因此，身。因此， 是一个群。是一个群。代数系统的应用代数系统的应用19定义定义2.22.2 Sn的任一非空子集的任一非空子集C，如果是，如果是群，群，即即C是是Sn的子群，则称码的子群，则称码C是群码是群码(Group Code)。定义定

17、义2.32.3 设设X=x1x2 xn 和和Y=y1y2 yn 是是Sn中的两个中的两个元素，称元素，称为为X与与Y的的汉明距离汉明距离（Hamming Distance）。）。 niiiyxYXH12)(),(代数系统的应用代数系统的应用20 从定义可以看出，从定义可以看出，X和和Y的汉明距离是的汉明距离是X和和Y中对应位码元不同的个数。设中对应位码元不同的个数。设S3中两中两个码字为：个码字为：000和和011，这两个码字的汉明距，这两个码字的汉明距离为离为2。而。而000和和111的汉明距离为的汉明距离为3。关于汉。关于汉明距离，我们有以下结论：明距离，我们有以下结论：（1）H(X,X)

18、=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)从而从而0 xi=yi1 xiyi),(),(),(),(),(),(11ZYHYXHzyHyxHzxHZXHniiiniiiniii 代数系统的应用代数系统的应用22定义定义2.42.4一个码一个码C中所有不同码字的汉明距中所有不同码字的汉明距离的极小值称为码离的极小值称为码C的最小距离（的最小距离（Minimum Dista

19、nce）,记为记为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(

20、C) 2k+1。代数系统的应用代数系统的应用24例子例子2.32.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既不能检查既不能检查错误也不能纠正错误。从而我们知道一个编码如错误也不能纠正错误。从而我们知道一个编码如果包含了某个长度的所有码字，则此编码一定无果包

21、含了某个长度的所有码字，则此编码一定无抗干扰能力。抗干扰能力。代数系统的应用代数系统的应用25例子例子2.42.4奇偶校验码（奇偶校验码（Parity code)Parity code)的编码的编码我们知道，编码我们知道，编码S2=00，01，10，11没有抗没有抗干扰能力。但我们可以在干扰能力。但我们可以在S2的每个码字后增加一的每个码字后增加一位（叫奇偶校验位），这一位是这样安排的，它位（叫奇偶校验位），这一位是这样安排的，它使每个码字所含使每个码字所含1的个数为偶数，按这种方法编码的个数为偶数，按这种方法编码后后S2就变为就变为S2=000，011，101，110而它的最小距离而它的最小

22、距离dmin(S2)=2，故定理，故定理2.1可知，可知，它可想出单个错误。而事实也是如此，当传递过它可想出单个错误。而事实也是如此，当传递过程中发生单个错误则码字就变为含有奇数个程中发生单个错误则码字就变为含有奇数个1的废的废码。码。代数系统的应用代数系统的应用26类似地，增加奇偶校验位使码字所含类似地，增加奇偶校验位使码字所含1的个数为奇数时也可得到相同的效果。的个数为奇数时也可得到相同的效果。我们可以把上述结果推广到我们可以把上述结果推广到Sn中去，中去，不管不管n多大，只要增加一奇偶校验位总可能多大，只要增加一奇偶校验位总可能查出一个错误。这种方法在计算机中是使查出一个错误。这种方法在

23、计算机中是使用很普遍的一种纠错码，它的优点是所付用很普遍的一种纠错码，它的优点是所付出的代价较小（只增加一位附加的奇偶校出的代价较小（只增加一位附加的奇偶校验位），而且这种码的生成与检查也很简验位），而且这种码的生成与检查也很简单，它的缺点是不能纠正错误。单，它的缺点是不能纠正错误。代数系统的应用代数系统的应用27三、纠错码的选择三、纠错码的选择前面分析，我们发现前面分析，我们发现S2无纠错能力，但无纠错能力，但在在S2中选取中选取C2后，后，C2具有发现单错的能力。具有发现单错的能力。同样，同样，S3无纠错能力，但在无纠错能力，但在S3中选取中选取C3后，后，C3具有纠正单错的能力。从这里可

24、以看出，具有纠正单错的能力。从这里可以看出，如何从一些编码中选取一些码字组成新码，如何从一些编码中选取一些码字组成新码，使其具有一定的纠错能力是一个很重要的课使其具有一定的纠错能力是一个很重要的课题。题。下面我们介绍一种很重要的编码下面我们介绍一种很重要的编码汉汉明编码，这种编码能发现并纠正单个错误。明编码，这种编码能发现并纠正单个错误。代数系统的应用代数系统的应用28（一）汉明编码的特例（一）汉明编码的特例设有编码设有编码S4，S4中每个码字为中每个码字为a1a2a3a4，若增加三位校验位若增加三位校验位a5a6a7，从而使它成为长度，从而使它成为长度为为7的码字的码字a1a2a3a4 a5

25、a6a7。其中校验位。其中校验位a5a6a7应满足下列方程：应满足下列方程：a1 +2 a2 +2 a3 +2 a5=0（21）a1 +2 a2 +2 a4 +2 a6=0 （22） a1 +2 a3 +2 a4 +2 a7=0 （23）也就是说要满足：也就是说要满足：a5= a1 +2 a2 +2 a3 a6= a1 +2 a2 +2 a4 a7= a1 +2 a3 +2 a4代数系统的应用代数系统的应用29因此，因此，a1,a2,a3,a4一旦确定，则校验位一旦确定，则校验位a5,a6,a7可可根据上述方程唯一确定。这样我们由根据上述方程唯一确定。这样我们由S4就可以就可以得到一个长度为得

26、到一个长度为7的编码的编码C，如表，如表21所示。所示。代数系统的应用代数系统的应用30表表21a1a2a3a4a5a6a7a1a2a3a4a5a6a70000000100011100010111001100001010110100100011111101100101001101100001010110111010100110011111010001110001111111代数系统的应用代数系统的应用31 上述的编码上述的编码C能发现一个错误并纠正单个错误。能发现一个错误并纠正单个错误。因为如果因为如果C中码字发生单错，则上述三个方程必定至中码字发生单错，则上述三个方程必定至少有一个等式不满足

27、；当少有一个等式不满足；当C中码字发生单错后，不同中码字发生单错后，不同的字位错误可使方程中不同的等式不成立，如当的字位错误可使方程中不同的等式不成立，如当a2发发生错误时必有方程（生错误时必有方程（21）、（）、（22）不成立，而当）不成立，而当a3发生错误时必有方程（发生错误时必有方程（21）、（）、（23）不成立，）不成立，方程中三个等式的方程中三个等式的8种组合可对应种组合可对应a1a7的七个码元每的七个码元每个码的错误以及一个正确无误的码字。个码的错误以及一个正确无误的码字。代数系统的应用代数系统的应用32为讨论方便，我们建立三个谓词：为讨论方便，我们建立三个谓词：P1(a1,a2,

28、a7): a1 +2 a2 +2 a3 +2 a5=0P2(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。令。令S1a1,a2,a3,a5 S2a1,a2,a4,a6S3a1,a3,a4,a7代数系统的应用代数系统的应用33显然，显然，Si是使是使Pi为假的所有出错字的集合。我为假的所有出错字的集合。我们可构成下面们可构成下面7个非空集

29、合：个非空集合：,3211SSSa,3212SSSa,3213SSSa,3214SSSa,3215SSSa,3216SSSa,3217SSSa从这七个集合我们可以决定出错位。例如，从这七个集合我们可以决定出错位。例如，即表示即表示a3S2， a3S1， a3S3，所以所以a3出错，则必有出错，则必有P2为真，为真，P1、P3为假。反之亦然。为假。反之亦然。如此类推，可得到表如此类推，可得到表22所示的纠错对照表。从表中所示的纠错对照表。从表中可看出这种编码可看出这种编码C能纠正一个错误。能纠正一个错误。,3213SSSa代数系统的应用代数系统的应用3422纠错对照表纠错对照表P1P2P3出错码

30、元出错码元000a1001a2010a3011a4100a5101a6110a7111无无代数系统的应用代数系统的应用35我们将上例加以抽象，首先将方程（我们将上例加以抽象，首先将方程（21）、）、（22）、（）、（23）表示为矩阵形式：）表示为矩阵形式：HXTT 1110100其中其中H1101010 1011001，X(a1,a2,a3,a4,a5,a6,a7), =(0,0,0),XT、 T分别是分别是X、的转置矩阵，这里加法运算为的转置矩阵，这里加法运算为2。可见，一个编码可由矩阵可见，一个编码可由矩阵H确定，而它的纠错确定，而它的纠错能力可由能力可由H的特性决定。下面讨论矩阵的特性决

31、定。下面讨论矩阵H。代数系统的应用代数系统的应用36定义定义2.52.5重量（重量（WeightWeight）一个码字一个码字X所含所含1的个数称为此码字的的个数称为此码字的重量，记为重量，记为W(X)。例如，码字例如，码字001011的重量为的重量为3，码字，码字100000的的重量为重量为1，码字，码字000的重量为的重量为0，通常将，通常将000记为记为0或或。利用码字的重量，我们有如下结论：。利用码字的重量，我们有如下结论：（1）设有码）设有码C，对任意，对任意X,YC，有，有H(X,Y)=H(X Y, )=W(X Y)；代数系统的应用代数系统的应用37（2）群码）群码C中非零码字的最

32、小重量等于此中非零码字的最小重量等于此群码的最小距离。即群码的最小距离。即)()(minminCdZWCZZ （3）设）设H是是k行行n列矩阵，列矩阵，X=x1x2xn,并设集并设集合合GXHXTT，这里加法运算为，这里加法运算为2，则则G， 是群，即是群，即G是群是群码。码。上述介绍的汉明码就是群码。上述介绍的汉明码就是群码。代数系统的应用代数系统的应用38定义定义2.6群码群码GXHXTT称为由称为由H生成的群生成的群码，而码，而G中每一个码字称为由中每一个码字称为由H生成生成的码字，矩阵的码字，矩阵H称为一致校验矩阵（称为一致校验矩阵（Uniform Check Matrix） 。代数系

33、统的应用代数系统的应用39现在我们介绍矩阵列向量的概念，设矩阵现在我们介绍矩阵列向量的概念，设矩阵H为为nihhhhhhhhhhhhhHmiiiimnmmnn, 2 , 1,21212222111211令此时矩阵此时矩阵H可记为可记为 H（h1 h2 h3 hn)而而hi叫做矩阵叫做矩阵H的第的第i个列向量（个列向量（Column Vector).mjmijijijihhhhhhhh2122121代数系统的应用代数系统的应用40我们有如下结论：我们有如下结论：（1）一致校验矩阵）一致校验矩阵H生成一个重量为生成一个重量为p的码字的充分必的码字的充分必要条件是在要条件是在H中存在中存在p个列向量

34、，它们的按位加为个列向量，它们的按位加为T 。（2）由）由H生成的群码的最小距离等于生成的群码的最小距离等于H中列向量按位加中列向量按位加为为T的最小列向量数。的最小列向量数。这个结论建立了最小距离与列向量之间的联系。这个结论建立了最小距离与列向量之间的联系。前面结论我们知道：一个码的纠错能力由其最小距离前面结论我们知道：一个码的纠错能力由其最小距离决定。故有：一个群码的纠错能力可由其一致校验矩决定。故有：一个群码的纠错能力可由其一致校验矩阵阵H中列向量按位加为中列向量按位加为T的最小列向量数决定。的最小列向量数决定。代数系统的应用代数系统的应用41故只要选取适当的故只要选取适当的H就可使其生

35、成的码达到就可使其生成的码达到预定的纠错能力。预定的纠错能力。对于前面所述的汉明码，它的一致校对于前面所述的汉明码，它的一致校验矩阵验矩阵H中没有零向量，且各列向量之间均中没有零向量，且各列向量之间均互不相同，但它的第二、三、四列向量的互不相同，但它的第二、三、四列向量的按位加为按位加为T，由此结论可知这个码的最小，由此结论可知这个码的最小距离为距离为3，而且可知此群必能纠正单个错误。，而且可知此群必能纠正单个错误。代数系统的应用代数系统的应用42将上述汉明码推广到一般情况，码将上述汉明码推广到一般情况，码C的每一码字的每一码字X由信息位由信息位x1x2xm及附加校验位及附加校验位xm+1xm

36、+2xm+k组成，组成，其形式为其形式为X x1x2xm xm+1xm+2xm+kX中信息位与校验位之间的关系如下：中信息位与校验位之间的关系如下：xm+i=qi1x1+2qi2x2+2+2qimxm,(i=1,2,k)而而qij0,1（i=1,2,k;j=1,2,m),作矩阵作矩阵H为为H（Qkm Ikk）其中其中kkkmkkmmIqqqqqqqqqQ10101,212222111211代数系统的应用代数系统的应用43码码C的任一码字均满足方程的任一码字均满足方程 HXTT令令n=m+k，我们称这种码为（，我们称这种码为（n,m）码。）码。要使码要使码C能纠正单个错误，由前面结论可能纠正单个

37、错误，由前面结论可知，只要对知，只要对H作适当赋值，使得作适当赋值，使得H的列向量的列向量均不相同且无零列向量，这样可保证均不相同且无零列向量，这样可保证C的最的最小距离大于小距离大于2，即要求，即要求H中的中的Q的列向量均的列向量均不为不为，不出现，不出现I中的中的k个向量且互不相同。个向量且互不相同。代数系统的应用代数系统的应用44Q的列向量是的列向量是k维的，故可有维的，故可有2k个不同的列向个不同的列向量，而供量，而供Q选择的列向量是这选择的列向量是这2k 个列向量中除去个列向量中除去I中的中的k个列向量及零列向量以外的所有个列向量及零列向量以外的所有2k-k-1个列个列向量。故我们可

38、在这些列向量中任选向量。故我们可在这些列向量中任选m个列向量组个列向量组成成Q。所以。所以m与与k必须满足：必须满足： m2k-k-1 或或 2km+k+1=n+1 或或 kloglog2 2(n+1)(n+1)因此只要码因此只要码C中校验位位数中校验位位数k满足：满足： kloglog2 2(n+1)(n+1)，总可以在总可以在2k-k-1个列向量任选个列向量任选m个列向量组成个列向量组成Q,而而使使C具有纠正单个错误的能力。具有纠正单个错误的能力。代数系统的应用代数系统的应用45从上述分析也可看出如何组织具有一定要求从上述分析也可看出如何组织具有一定要求的纠错能力的纠错码。的纠错能力的纠错码。例子：设例子：设n=7, kloglog2 2(n+1)=log(n+1)=log2 28=3,8=3,我们取我们取k=3,k=3,则则m=4,m=4,所以一致校验矩阵所以一致校验矩阵H H中中Q Q应有四个列向量。而应有四个列向量。而2k-k-123-3-1=4，故，故Q可由四个列向量唯一确定，它们可由四个列向量唯一确定，它们是：是：即即H为上述的汉明码。为上述的汉明码。100110101010110010111H10101因而,11,1,1,110