《代数系统在计算机科学中的应用优秀课件.ppt》由会员分享，可在线阅读，更多相关《代数系统在计算机科学中的应用优秀课件.ppt（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、代数系统在计算机科代数系统在计算机科学中的应用学中的应用第1页，本讲稿共45页人们研究和考察现实世界中各种现象或过程，往人们研究和考察现实世界中各种现象或过程，往往要借助某些数学工具。在代数中，可以用正整数集往要借助某些数学工具。在代数中，可以用正整数集合上的加法运算来描述企业产品的累计数，可以用集合上的加法运算来描述企业产品的累计数，可以用集合之间的合之间的“并并”、“交交”运算来描述单位与单位之间运算来描述单位与单位之间的关系等。我们所接触过的数学结构，连续的或离散的关系等。我们所接触过的数学结构，连续的或离散的，常常是对研究对象（自然数、实数、多项式、矩的，常常是对研究对象（自然数、实数
2、、多项式、矩阵、命题、集合乃至图）定义各种运算（加、减、乘，阵、命题、集合乃至图）定义各种运算（加、减、乘，与、或、非，并、交、补），然后讨论这些对象及运与、或、非，并、交、补），然后讨论这些对象及运算的有关性质。算的有关性质。第2页，本讲稿共45页针对某个具体问题选用适宜的数学结构去进行较为确针对某个具体问题选用适宜的数学结构去进行较为确切的描述，这就是所谓切的描述，这就是所谓“数学模型数学模型”。可见，数学结构在。可见，数学结构在数学模型中占有极为重要的位置。而代数系统是一类特殊数学模型中占有极为重要的位置。而代数系统是一类特殊的数学结构的数学结构由对象集合及运算组成的数学结构，由对象集合
3、及运算组成的数学结构，我们通常称它为代数结构。它在计算机科学中有着广我们通常称它为代数结构。它在计算机科学中有着广泛的应用，对计算机科学的产生和发展有重大影响；泛的应用，对计算机科学的产生和发展有重大影响；反过来，计算机科学的发展对抽象代数学又提出了新反过来，计算机科学的发展对抽象代数学又提出了新的要求，促使抽象代数学不断涌现新概念，发展新理的要求，促使抽象代数学不断涌现新概念，发展新理论。论。第3页，本讲稿共45页格与布尔代数的理论成为电子计算机硬件设计和通讯格与布尔代数的理论成为电子计算机硬件设计和通讯系统设计中的重要工具。半群理论在自动机和形式语言研系统设计中的重要工具。半群理论在自动机
4、和形式语言研究中发挥了重要作用。关系代数理论成为最流行的数据库究中发挥了重要作用。关系代数理论成为最流行的数据库的理论模型。格论是计算机语言的形式语义的理论基础。的理论模型。格论是计算机语言的形式语义的理论基础。抽象代数规范理论和技术广泛应用于计算机软件形式说明抽象代数规范理论和技术广泛应用于计算机软件形式说明和开发，以及硬件体系结构设计。有限域的理论是编码理和开发，以及硬件体系结构设计。有限域的理论是编码理论的数学基础，在通讯中发挥了重要作用。在计算机算法论的数学基础，在通讯中发挥了重要作用。在计算机算法设计与分析中，代数算法研究占有主导地位。设计与分析中，代数算法研究占有主导地位。第4页，
5、本讲稿共45页纠错码纠错码一、纠错码概述一、纠错码概述 我们知道，在计算机中和数据通信中，我们知道，在计算机中和数据通信中，经常需要将二进制数字信号进行传递，这经常需要将二进制数字信号进行传递，这种传递的距离近则数米、数毫米，远则超种传递的距离近则数米、数毫米，远则超过数千公里。在传递住处过程中，由于存过数千公里。在传递住处过程中，由于存在着各种干扰，可能会使二进制信号产生在着各种干扰，可能会使二进制信号产生失真现象，即在传递过程中二进制信号失真现象，即在传递过程中二进制信号0可可能会变成能会变成1，1可能会变成可能会变成0。第5页，本讲稿共45页 图图2.1是一个二进制信号传递的简单模型，它
6、有是一个二进制信号传递的简单模型，它有一个发送端和一个接收端，二进制信号串一个发送端和一个接收端，二进制信号串X=x1x2xn 从发送端发出经传输介质而至接收端。由从发送端发出经传输介质而至接收端。由于存在着干扰对传输介质的影响，因而接收端收到于存在着干扰对传输介质的影响，因而接收端收到的二进制信号串的二进制信号串 中的中的 可能不一定可能不一定就与就与xi相等，从而产生了二进制信号的传递错误。相等，从而产生了二进制信号的传递错误。发送端发送端接收端接收端X=x1x2 xn干扰干扰图图2.1第6页，本讲稿共45页 由于在计算机中和数据通信系统中的由于在计算机中和数据通信系统中的信号传递是非常的
7、频繁与广泛，因此，如何信号传递是非常的频繁与广泛，因此，如何防止传输错误就变得相当重要了，当然，要防止传输错误就变得相当重要了，当然，要解决这个问题可以有不同的途径。人们所想解决这个问题可以有不同的途径。人们所想到的第一个途径是提高设备的抗干扰能力和到的第一个途径是提高设备的抗干扰能力和信号的抗干扰能力。但是，大家都知道，这信号的抗干扰能力。但是，大家都知道，这种从物理角度去提高抗干扰能力并不能完全种从物理角度去提高抗干扰能力并不能完全消除错误的出现。消除错误的出现。第7页，本讲稿共45页 第二个途径就是我们所要谈到的采用采用纠错码第二个途径就是我们所要谈到的采用采用纠错码（Error Cor
8、recting Code）的方法以提高抗干扰能力。）的方法以提高抗干扰能力。这种纠错码的方法是从编码上下功夫，使得二进制这种纠错码的方法是从编码上下功夫，使得二进制数码在传递过程中一旦出错，在接收端的纠错码装数码在传递过程中一旦出错，在接收端的纠错码装置就能立刻发现错误，并将其纠正。由于这种方法置就能立刻发现错误，并将其纠正。由于这种方法简单易行，因此目前在计算机中和数据通信系统中简单易行，因此目前在计算机中和数据通信系统中被广泛采用。采用这种方法后，二进制信号传递模被广泛采用。采用这种方法后，二进制信号传递模型就可以变为图型就可以变为图2.2所示的模型了。所示的模型了。第8页，本讲稿共45页
9、图图2.2通信系统模型通信系统模型信信源源信信源源编编码码加加密密信信道道编编码码信道信道信信道道译译码码解解密密信信源源译译码码信信宿宿密密钥钥源源噪声噪声密密钥钥源源该模型按功能分为信源、编码器、信道、译码器、信宿该模型按功能分为信源、编码器、信道、译码器、信宿第9页，本讲稿共45页 但是，为什么纠错码具有发现错误、纠但是，为什么纠错码具有发现错误、纠正错误的能力呢？纠错码又是按什么样的原正错误的能力呢？纠错码又是按什么样的原理去编的呢？为了说明这些问题，我们首先理去编的呢？为了说明这些问题，我们首先介绍一些基本概念。介绍一些基本概念。第10页，本讲稿共45页定义定义2.1 由由0和和1组
10、成的串称为字（组成的串称为字（Word），一），一些字的集合称为码（些字的集合称为码（Code）。码中的字称）。码中的字称为码字（为码字（Code Word）。不在码中的字称为）。不在码中的字称为废码（废码（Invalid Code）。码中的每个二进制）。码中的每个二进制信号信号0或或1称为码元（称为码元（Code Letter）。）。我们下面举出几个关于纠错码例子。我们下面举出几个关于纠错码例子。第11页，本讲稿共45页例例2.12.1 设有长度为设有长度为2的字，它们一共可有的字，它们一共可有22=4个，它们所组成的字集个，它们所组成的字集S2=00，01，10，11。当选取编码为。当选取
11、编码为S2时，这种编码不具有时，这种编码不具有抗干扰能力。因为当抗干扰能力。因为当S2中的一个字如中的一个字如10，在，在传递过程中其第一个码元传递过程中其第一个码元1变为变为0，因而整个，因而整个字成为字成为00时，由于时，由于00也是也是S2中的字，故我们中的字，故我们不能发现传递中是否出错。不能发现传递中是否出错。第12页，本讲稿共45页 当我们选取当我们选取S2的一个子集如的一个子集如C2=01，10作为编码作为编码时就会发生另一种完全不同的情况。时就会发生另一种完全不同的情况。因为此时因为此时00和和11均为废码，而当均为废码，而当01在传递过程中第在传递过程中第一个码元由一个码元由
12、0变为变为1，即整个字成为，即整个字成为11时，由于时，由于11是废是废码，因而我们发现传递过程中出现了错误。对码，因而我们发现传递过程中出现了错误。对10也也有同样的情况。有同样的情况。01第一个码元错成第一个码元错成11第二个码元错成第二个码元错成0010第一个码元错成第一个码元错成00第二个码元错成第二个码元错成11第13页，本讲稿共45页 可见，这种编码有一个缺点，即它只能可见，这种编码有一个缺点，即它只能发现错误而不能纠正错误，因此我们还需要发现错误而不能纠正错误，因此我们还需要选择另一种能纠错的编码。选择另一种能纠错的编码。第14页，本讲稿共45页例例2.2 2.2 考虑长度为考虑
13、长度为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或或
14、001，但是都可知其原码为，但是都可知其原码为101。对于码字对于码字010也有类似的情况。故对编码也有类似的情况。故对编码C3，我们不仅能，我们不仅能发现错误而且能纠正错误。发现错误而且能纠正错误。第15页，本讲稿共45页 当然，上述编码还有一个缺点，就是当然，上述编码还有一个缺点，就是它只能发现并纠正单个错误。当错误超过两它只能发现并纠正单个错误。当错误超过两个码元时，它就既不能发现错误，更无法纠个码元时，它就既不能发现错误，更无法纠正了。正了。第16页，本讲稿共45页二、纠错码的纠错能力二、纠错码的纠错能力 前面例子中我们发现前面例子中我们发现C2编码仅能发现编码仅能发现错误，按错误，按
15、C3编码可发现并纠正单个错误。可编码可发现并纠正单个错误。可见，不能的编码具有不同的纠错能力。下面见，不能的编码具有不同的纠错能力。下面介绍编码方式与纠错能力之间的联系。介绍编码方式与纠错能力之间的联系。第17页，本讲稿共45页设设Sn是长度为是长度为n的字集，即的字集，即 Sn=x1x2xn|xi=0或或1,i=1,2,n在在Sn上定义二元运算上定义二元运算为：为：X，YSn,X=x1x2xn,Y=y1y2yn,Z=X Y=z1z2zn其中，其中，zi=xi+2 yi(i=1,2,n)而运算符而运算符+2为模为模2加运算加运算(即即0+21=1+20=1,0+20=1+21=0)，我们称运算
16、我们称运算为按位为按位加。加。显然，显然，是一个代数系统，且运算是一个代数系统，且运算满足结满足结合律，它的幺元为合律，它的幺元为000，每个元素的逆元都是它自，每个元素的逆元都是它自身。因此，身。因此，是一个群。是一个群。第18页，本讲稿共45页定义定义2.22.2 Sn的任一非空子集的任一非空子集C，如果是，如果是群，即群，即C是是Sn的子群，则称码的子群，则称码C是群码是群码(Group Code)。定义定义2.32.3 设设X=x1x2 xn 和和Y=y1y2 yn 是是Sn中的两个中的两个元素，称元素，称为为X与与Y的的汉明距离汉明距离（Hamming Distance）。）。第19
17、页，本讲稿共45页 从定义可以看出，从定义可以看出，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)。第20页，本讲稿共45页（3）H(X,Y)+H(Y,Z)H(X,Z)的的证证明明证明：定义证明：定义H(xi,yi)=则则H(xi,zi)H
18、(xi,yi)+H(yi,zi)从而从而0 xi=yi1 xiyi第21页，本讲稿共45页定义定义2.42.4一个码一个码C中所有不同码字的汉明距离的中所有不同码字的汉明距离的极小值称为码极小值称为码C的最小距离（的最小距离（Minimum Distance）,记为记为dmin(C)。即。即例如，例如，dmin(S2)=dmin(S3)=1，dmin(C2)=2，dmin(C3)=3。利用编码利用编码C的最小距离，可以刻画编码方式与纠的最小距离，可以刻画编码方式与纠错能力之间的关系，我们有以下两定理：错能力之间的关系，我们有以下两定理：第22页，本讲稿共45页定理定理2.1一个码一个码C能检查
19、出不超过能检查出不超过k个错误个错误的充分必要条件为的充分必要条件为dmin(C)k+1。定理定理2.2 一个码一个码C能纠正能纠正k个错误的充分必个错误的充分必要条件是要条件是dmin(C)2k+1。第23页，本讲稿共45页例子例子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)
20、=1，从而，从而S2、S3既不能检查错误也不能既不能检查错误也不能纠正错误。从而我们知道一个编码如果包含了某个长度纠正错误。从而我们知道一个编码如果包含了某个长度的所有码字，则此编码一定无抗干扰能力。的所有码字，则此编码一定无抗干扰能力。第24页，本讲稿共45页例子例子2.42.4奇偶校验码（奇偶校验码（Parity code)Parity code)的编码的编码我们知道，编码我们知道，编码S2=00，01，10，11没有抗干扰能没有抗干扰能力。但我们可以在力。但我们可以在S2的每个码字后增加一位（叫奇偶校验的每个码字后增加一位（叫奇偶校验位），这一位是这样安排的，它使每个码字所含位），这一位
21、是这样安排的，它使每个码字所含1的个数的个数为偶数，按这种方法编码后为偶数，按这种方法编码后S2就变为就变为S2=000，011，101，110而它的最小距离而它的最小距离dmin(S2)=2，故定理，故定理2.1可知，它可可知，它可想出单个错误。而事实也是如此，当传递过程中发生想出单个错误。而事实也是如此，当传递过程中发生单个错误则码字就变为含有奇数个单个错误则码字就变为含有奇数个1的废码。的废码。第25页，本讲稿共45页类似地，增加奇偶校验位使码字所含类似地，增加奇偶校验位使码字所含1的个数为奇数时也可得到相同的效果。的个数为奇数时也可得到相同的效果。我们可以把上述结果推广到我们可以把上述
22、结果推广到Sn中去，不中去，不管管n多大，只要增加一奇偶校验位总可能查多大，只要增加一奇偶校验位总可能查出一个错误。这种方法在计算机中是使用很出一个错误。这种方法在计算机中是使用很普遍的一种纠错码，它的优点是所付出的代普遍的一种纠错码，它的优点是所付出的代价较小（只增加一位附加的奇偶校验位），价较小（只增加一位附加的奇偶校验位），而且这种码的生成与检查也很简单，它的缺而且这种码的生成与检查也很简单，它的缺点是不能纠正错误。点是不能纠正错误。第26页，本讲稿共45页三、纠错码的选择三、纠错码的选择前面分析，我们发现前面分析，我们发现S2无纠错能力，但无纠错能力，但在在S2中选取中选取C2后，后，
23、C2具有发现单错的能力。具有发现单错的能力。同样，同样，S3无纠错能力，但在无纠错能力，但在S3中选取中选取C3后，后，C3具有纠正单错的能力。从这里可以看出，具有纠正单错的能力。从这里可以看出，如何从一些编码中选取一些码字组成新码，如何从一些编码中选取一些码字组成新码，使其具有一定的纠错能力是一个很重要的课使其具有一定的纠错能力是一个很重要的课题。题。下面我们介绍一种很重要的编码下面我们介绍一种很重要的编码汉汉明编码，这种编码能发现并纠正单个错误。明编码，这种编码能发现并纠正单个错误。第27页，本讲稿共45页（一）汉明编码的特例（一）汉明编码的特例设有编码设有编码S4，S4中每个码字为中每个
24、码字为a1a2a3a4，若增加三位校验位若增加三位校验位a5a6a7，从而使它成为长度，从而使它成为长度为为7的码字的码字a1a2a3a4 a5a6a7。其中校验位。其中校验位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第28页，本讲稿共45页因此，因此，a1,a2,a3,a4一旦确定，则校验位一旦确定，则校验位a5,a6,a7
25、可可根据上述方程唯一确定。这样我们由根据上述方程唯一确定。这样我们由S4就可以就可以得到一个长度为得到一个长度为7的编码的编码C，如表，如表21所示。所示。第29页，本讲稿共45页表表21a1a2a3a4a5a6a7a1a2a3a4a5a6a70000000100011100010111001100001010110100100011111101100101001101100001010110111010100110011111010001110001111111第30页，本讲稿共45页 上述的编码上述的编码C能发现一个错误并纠正单个错误。因为能发现一个错误并纠正单个错误。因为如果如果C中码字
26、发生单错，则上述三个方程必定至少有一个等中码字发生单错，则上述三个方程必定至少有一个等式不满足；当式不满足；当C中码字发生单错后，不同的字位错误可使方中码字发生单错后，不同的字位错误可使方程中不同的等式不成立，如当程中不同的等式不成立，如当a2发生错误时必有方程（发生错误时必有方程（21）、（）、（22）不成立，而当）不成立，而当a3发生错误时必有方程（发生错误时必有方程（21）、（）、（23）不成立，方程中三个等式的）不成立，方程中三个等式的8种组合可对应种组合可对应a1a7的七个码元每个码的错误以及一个正确无误的码字。的七个码元每个码的错误以及一个正确无误的码字。第31页，本讲稿共45页为
27、讨论方便，我们建立三个谓词：为讨论方便，我们建立三个谓词：P1(a1,a2,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第32页，本讲稿共45页显然，显然，Si是使是使Pi为假的所有出错字的集合。我们可构为假的
28、所有出错字的集合。我们可构成下面成下面7个非空集合：个非空集合：从这七个集合我们可以决定出错位。例如，从这七个集合我们可以决定出错位。例如，即表示即表示a3S2，a3S1，a3S3，所以，所以a3出出错，则必有错，则必有P2为真，为真，P1、P3为假。反之亦然。如此类推，为假。反之亦然。如此类推，可得到表可得到表22所示的纠错对照表。从表中可看出这种编码所示的纠错对照表。从表中可看出这种编码C能纠正一个错误。能纠正一个错误。第33页，本讲稿共45页22纠错对照表纠错对照表P1P2P3出错码元出错码元000a1001a2010a3011a4100a5101a6110a7111无无第34页，本讲稿
29、共45页我们将上例加以抽象，首先将方程（我们将上例加以抽象，首先将方程（21）、（）、（22）、（）、（23）表示为矩阵形式：）表示为矩阵形式：HXTT 1110100其中其中H1101010 1011001，X(a1,a2,a3,a4,a5,a6,a7),=(0,0,0),XT、T分分别别是是X、的的转转置矩置矩阵阵，这这里加法运算里加法运算为为2。可可见见，一个，一个编码编码可由矩可由矩阵阵H确定，而它的确定，而它的纠错纠错能力能力可由可由H的特性决定。下面的特性决定。下面讨论讨论矩矩阵阵H。第35页，本讲稿共45页定义定义2.52.5重量（重量（WeightWeight）一个码字一个码字
30、X所含所含1的个数称为此码字的重的个数称为此码字的重量，记为量，记为W(X)。例如，码字例如，码字001011的重量为的重量为3，码字，码字100000的重量为的重量为1，码字，码字000的重量为的重量为0，通常将，通常将000记为记为0或或。利用。利用码码字的重量，我字的重量，我们们有如下有如下结论结论：（1）设设有有码码C，对对任意任意X,YC，有，有H(X,Y)=H(XY,)=W(XY)；第36页，本讲稿共45页（2）群码）群码C中非零码字的最小重量等于此群码的中非零码字的最小重量等于此群码的最小距离。即最小距离。即（3）设）设H是是k行行n列矩阵，列矩阵，X=x1x2xn,并并设设集集
31、合合GXHXTT，这这里加法运算里加法运算为为2，则则G，是群，即是群，即G是群是群码。码。上述介绍的汉明码就是群码。上述介绍的汉明码就是群码。第37页，本讲稿共45页定义定义2.6群码群码GXHXTT称称为为由由H生生成的群成的群码，而码，而G中每一个码字称为由中每一个码字称为由H生成的码生成的码字，矩阵字，矩阵H称为一致校验矩阵（称为一致校验矩阵（Uniform Check Matrix）。第38页，本讲稿共45页现在我们介绍矩阵列向量的概念，设矩阵现在我们介绍矩阵列向量的概念，设矩阵H为为此时矩阵此时矩阵H可记为可记为 H（h1 h2 h3 hn)而而hi叫做矩阵叫做矩阵H的第的第i个列
32、向量（个列向量（Column Vector).第39页，本讲稿共45页我们有如下结论：我们有如下结论：（1）一致校验矩阵）一致校验矩阵H生成一个重量为生成一个重量为p的码字的充分必要条件是的码字的充分必要条件是在在H中存在中存在p个列向量，它们的按位加为个列向量，它们的按位加为T。（2）由）由H生成的群码的最小距离等于生成的群码的最小距离等于H中列向量按位加为中列向量按位加为T的的最小列向量数。最小列向量数。这这个个结论结论建立了最小距离与列向量之建立了最小距离与列向量之间间的的联联系。前面系。前面结结论论我我们们知道：一个知道：一个码码的的纠错纠错能力由其最小距离决定。故有：能力由其最小距离
33、决定。故有：一个群一个群码码的的纠错纠错能力可由其一致校能力可由其一致校验验矩矩阵阵H中列向量按位加中列向量按位加为为T的最小列向量数决定。的最小列向量数决定。第40页，本讲稿共45页故只要故只要选选取适当的取适当的H就可使其生成的就可使其生成的码码达到达到预预定的定的纠错纠错能力。能力。对于前面所述的汉明码，它的一致校对于前面所述的汉明码，它的一致校验矩阵验矩阵H中没有零向量，且各列向量之间均中没有零向量，且各列向量之间均互不相同，但它的第二、三、四列向量的按互不相同，但它的第二、三、四列向量的按位加为位加为T，由此，由此结论结论可知可知这这个个码码的最小距的最小距离离为为3，而且可知此群必
34、能，而且可知此群必能纠纠正正单单个个错误错误。第41页，本讲稿共45页将上述汉明码推广到一般情况，码将上述汉明码推广到一般情况，码C的每一码字的每一码字X由信息位由信息位x1x2xm及附加校验位及附加校验位xm+1xm+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）其中其中第42页，本讲稿共45页码码C的任一码字均满足方程的任一码字均满
35、足方程 HXTT令令n=m+k，我，我们们称称这这种种码为码为（n,m）码码。要使要使码码C能能纠纠正正单单个个错误错误，由前面，由前面结论结论可可知，只要知，只要对对H作适当作适当赋值赋值，使得，使得H的列向量的列向量均不相同且无零列向量，均不相同且无零列向量，这样这样可保可保证证C的最的最小距离大于小距离大于2，即要求，即要求H中的中的Q的列向量均不的列向量均不为为，不出，不出现现I中的中的k个向量且互不相同。个向量且互不相同。第43页，本讲稿共45页Q的列向量是的列向量是k维的，故可有维的，故可有2k个不同的列向量，而供个不同的列向量，而供Q选择的列向量是这选择的列向量是这2k 个列向量
36、中除去个列向量中除去I中的中的k个列向量及个列向量及零列向量以外的所有零列向量以外的所有2k-k-1个列向量。故我们可在这些个列向量。故我们可在这些列向量中任选列向量中任选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具有纠具有纠正单个错误的能力。正单个错误的能力。第44页，本讲稿共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为上述的汉明码。为上述的汉明码。第45页，本讲稿共45页