代數(shù)系統(tǒng)在計(jì)算機(jī)科學(xué)中的應(yīng)用

代數(shù)系統(tǒng)在計(jì)算機(jī)科學(xué)中的應(yīng)用第一頁(yè)，共四十二頁(yè)，編輯于2023年，星期五人們研究和考察現(xiàn)實(shí)世界中各種現(xiàn)象或過(guò)程，往往要借助某些數(shù)學(xué)工具。在代數(shù)中，可以用正整數(shù)集合上的加法運(yùn)算來(lái)描述企業(yè)產(chǎn)品的累計(jì)數(shù)，可以用集合之間的“并”、“交”運(yùn)算來(lái)描述單位與單位之間的關(guān)系等。我們所接觸過(guò)的數(shù)學(xué)結(jié)構(gòu)，連續(xù)的或離散的，常常是對(duì)研究對(duì)象（自然數(shù)、實(shí)數(shù)、多項(xiàng)式、矩陣、命題、集合乃至圖）定義各種運(yùn)算（加、減、乘，與、或、非，并、交、補(bǔ)），然后討論這些對(duì)象及運(yùn)算的有關(guān)性質(zhì)。第二頁(yè)，共四十二頁(yè)，編輯于2023年，星期五針對(duì)某個(gè)具體問(wèn)題選用適宜的數(shù)學(xué)結(jié)構(gòu)去進(jìn)行較為確切的描述，這就是所謂“數(shù)學(xué)模型”。可見(jiàn)，數(shù)學(xué)結(jié)構(gòu)在數(shù)學(xué)模型中占有極為重要的位置。而代數(shù)系統(tǒng)是一類(lèi)特殊的數(shù)學(xué)結(jié)構(gòu)——由對(duì)象集合及運(yùn)算組成的數(shù)學(xué)結(jié)構(gòu)，我們通常稱(chēng)它為代數(shù)結(jié)構(gòu)。它在計(jì)算機(jī)科學(xué)中有著廣泛的應(yīng)用，對(duì)計(jì)算機(jī)科學(xué)的產(chǎn)生和發(fā)展有重大影響；反過(guò)來(lái)，計(jì)算機(jī)科學(xué)的發(fā)展對(duì)抽象代數(shù)學(xué)又提出了新的要求，促使抽象代數(shù)學(xué)不斷涌現(xiàn)新概念，發(fā)展新理論。第三頁(yè)，共四十二頁(yè)，編輯于2023年，星期五格與布爾代數(shù)的理論成為電子計(jì)算機(jī)硬件設(shè)計(jì)和通訊系統(tǒng)設(shè)計(jì)中的重要工具。半群理論在自動(dòng)機(jī)和形式語(yǔ)言研究中發(fā)揮了重要作用。關(guān)系代數(shù)理論成為最流行的數(shù)據(jù)庫(kù)的理論模型。格論是計(jì)算機(jī)語(yǔ)言的形式語(yǔ)義的理論基礎(chǔ)。抽象代數(shù)規(guī)范理論和技術(shù)廣泛應(yīng)用于計(jì)算機(jī)軟件形式說(shuō)明和開(kāi)發(fā)，以及硬件體系結(jié)構(gòu)設(shè)計(jì)。有限域的理論是編碼理論的數(shù)學(xué)基礎(chǔ)，在通訊中發(fā)揮了重要作用。在計(jì)算機(jī)算法設(shè)計(jì)與分析中，代數(shù)算法研究占有主導(dǎo)地位。第四頁(yè)，共四十二頁(yè)，編輯于2023年，星期五糾錯(cuò)碼一、糾錯(cuò)碼概述我們知道，在計(jì)算機(jī)中和數(shù)據(jù)通信中，經(jīng)常需要將二進(jìn)制數(shù)字信號(hào)進(jìn)行傳遞，這種傳遞的距離近則數(shù)米、數(shù)毫米，遠(yuǎn)則超過(guò)數(shù)千公里。在傳遞住處過(guò)程中，由于存在著各種干擾，可能會(huì)使二進(jìn)制信號(hào)產(chǎn)生失真現(xiàn)象，即在傳遞過(guò)程中二進(jìn)制信號(hào)0可能會(huì)變成1，1可能會(huì)變成0。第五頁(yè)，共四十二頁(yè)，編輯于2023年，星期五

圖2.1是一個(gè)二進(jìn)制信號(hào)傳遞的簡(jiǎn)單模型，它有一個(gè)發(fā)送端和一個(gè)接收端，二進(jìn)制信號(hào)串X=x1x2…xn

從發(fā)送端發(fā)出經(jīng)傳輸介質(zhì)而至接收端。由于存在著干擾對(duì)傳輸介質(zhì)的影響，因而接收端收到的二進(jìn)制信號(hào)串中的可能不一定就與xi相等，從而產(chǎn)生了二進(jìn)制信號(hào)的傳遞錯(cuò)誤。發(fā)送端接收端X=x1x2…xn干擾圖2.1第六頁(yè)，共四十二頁(yè)，編輯于2023年，星期五

由于在計(jì)算機(jī)中和數(shù)據(jù)通信系統(tǒng)中的信號(hào)傳遞是非常的頻繁與廣泛，因此，如何防止傳輸錯(cuò)誤就變得相當(dāng)重要了，當(dāng)然，要解決這個(gè)問(wèn)題可以有不同的途徑。人們所想到的第一個(gè)途徑是提高設(shè)備的抗干擾能力和信號(hào)的抗干擾能力。但是，大家都知道，這種從物理角度去提高抗干擾能力并不能完全消除錯(cuò)誤的出現(xiàn)。第七頁(yè)，共四十二頁(yè)，編輯于2023年，星期五

第二個(gè)途徑就是我們所要談到的采用采用糾錯(cuò)碼（ErrorCorrectingCode）的方法以提高抗干擾能力。這種糾錯(cuò)碼的方法是從編碼上下功夫，使得二進(jìn)制數(shù)碼在傳遞過(guò)程中一旦出錯(cuò)，在接收端的糾錯(cuò)碼裝置就能立刻發(fā)現(xiàn)錯(cuò)誤，并將其糾正。由于這種方法簡(jiǎn)單易行，因此目前在計(jì)算機(jī)中和數(shù)據(jù)通信系統(tǒng)中被廣泛采用。采用這種方法后，二進(jìn)制信號(hào)傳遞模型就可以變?yōu)閳D2.2所示的模型了。第八頁(yè)，共四十二頁(yè)，編輯于2023年，星期五圖2.2通信系統(tǒng)模型信源信源編碼加密信道編碼信道信道譯碼解密信源譯碼信宿密鑰源噪聲密鑰源該模型按功能分為信源、編碼器、信道、譯碼器、信宿第九頁(yè)，共四十二頁(yè)，編輯于2023年，星期五

但是，為什么糾錯(cuò)碼具有發(fā)現(xiàn)錯(cuò)誤、糾正錯(cuò)誤的能力呢？糾錯(cuò)碼又是按什么樣的原理去編的呢？為了說(shuō)明這些問(wèn)題，我們首先介紹一些基本概念。第十頁(yè)，共四十二頁(yè)，編輯于2023年，星期五定義2.1

由0和1組成的串稱(chēng)為字（Word），一些字的集合稱(chēng)為碼（Code）。碼中的字稱(chēng)為碼字（CodeWord）。不在碼中的字稱(chēng)為廢碼（InvalidCode）。碼中的每個(gè)二進(jìn)制信號(hào)0或1稱(chēng)為碼元（CodeLetter）。我們下面舉出幾個(gè)關(guān)于糾錯(cuò)碼例子。第十一頁(yè)，共四十二頁(yè)，編輯于2023年，星期五例2.1

設(shè)有長(zhǎng)度為2的字，它們一共可有22=4個(gè)，它們所組成的字集S2={00，01，10，11}。當(dāng)選取編碼為S2時(shí)，這種編碼不具有抗干擾能力。因?yàn)楫?dāng)S2中的一個(gè)字如10，在傳遞過(guò)程中其第一個(gè)碼元1變?yōu)?，因而整個(gè)字成為00時(shí)，由于00也是S2中的字，故我們不能發(fā)現(xiàn)傳遞中是否出錯(cuò)。第十二頁(yè)，共四十二頁(yè)，編輯于2023年，星期五

當(dāng)我們選取S2的一個(gè)子集如C2={01，10}作為編碼時(shí)就會(huì)發(fā)生另一種完全不同的情況。因?yàn)榇藭r(shí)00和11均為廢碼，而當(dāng)01在傳遞過(guò)程中第一個(gè)碼元由0變?yōu)?，即整個(gè)字成為11時(shí)，由于11是廢碼，因而我們發(fā)現(xiàn)傳遞過(guò)程中出現(xiàn)了錯(cuò)誤。對(duì)10也有同樣的情況。01第一個(gè)碼元錯(cuò)成11第二個(gè)碼元錯(cuò)成0010第一個(gè)碼元錯(cuò)成00第二個(gè)碼元錯(cuò)成11第十三頁(yè)，共四十二頁(yè)，編輯于2023年，星期五

可見(jiàn)，這種編碼有一個(gè)缺點(diǎn)，即它只能發(fā)現(xiàn)錯(cuò)誤而不能糾正錯(cuò)誤，因此我們還需要選擇另一種能糾錯(cuò)的編碼。第十四頁(yè)，共四十二頁(yè)，編輯于2023年，星期五例2.2考慮長(zhǎng)度為3的字

它們一共可有23=8個(gè)，它們所組成的字集S3={000，001，010，011，100，101，110，111}

選取編碼C3={101，010}。利用此編碼我們不僅能發(fā)現(xiàn)錯(cuò)誤而且能糾正錯(cuò)誤。因?yàn)榇a字101出現(xiàn)單個(gè)錯(cuò)誤后將變?yōu)椋?01，111，100；而碼字010出現(xiàn)錯(cuò)誤后將變?yōu)?10，000，011。故如碼字101在傳遞過(guò)程中任何一個(gè)碼元出現(xiàn)了錯(cuò)誤，整個(gè)碼字只會(huì)變?yōu)?11、100或001，但是都可知其原碼為101。對(duì)于碼字010也有類(lèi)似的情況。故對(duì)編碼C3，我們不僅能發(fā)現(xiàn)錯(cuò)誤而且能糾正錯(cuò)誤。第十五頁(yè)，共四十二頁(yè)，編輯于2023年，星期五

當(dāng)然，上述編碼還有一個(gè)缺點(diǎn)，就是它只能發(fā)現(xiàn)并糾正單個(gè)錯(cuò)誤。當(dāng)錯(cuò)誤超過(guò)兩個(gè)碼元時(shí)，它就既不能發(fā)現(xiàn)錯(cuò)誤，更無(wú)法糾正了。第十六頁(yè)，共四十二頁(yè)，編輯于2023年，星期五二、糾錯(cuò)碼的糾錯(cuò)能力

前面例子中我們發(fā)現(xiàn)C2編碼僅能發(fā)現(xiàn)錯(cuò)誤，按C3編碼可發(fā)現(xiàn)并糾正單個(gè)錯(cuò)誤?？梢?jiàn)，不能的編碼具有不同的糾錯(cuò)能力。下面介紹編碼方式與糾錯(cuò)能力之間的聯(lián)系。第十七頁(yè)，共四十二頁(yè)，編輯于2023年，星期五設(shè)Sn是長(zhǎng)度為n的字集，即

Sn={x1x2…xn|xi=0或1,i=1,2,…,n}在Sn上定義二元運(yùn)算ο為：X，Y∈Sn,X=x1x2…xn,Y=y1y2…yn,Z=XοY=z1z2…zn其中，zi=xi+2yi(i=1,2,…,n)而運(yùn)算符+2為模2加運(yùn)算(即0+21=1+20=1,0+20=1+21=0)，我們稱(chēng)運(yùn)算ο為按位加。顯然，<Sn,ο>是一個(gè)代數(shù)系統(tǒng)，且運(yùn)算ο滿足結(jié)合律，它的幺元為00…0，每個(gè)元素的逆元都是它自身。因此，<Sn,ο>是一個(gè)群。第十八頁(yè)，共四十二頁(yè)，編輯于2023年，星期五定義2.2Sn的任一非空子集C，如果是<C,ο>群，即C是Sn的子群，則稱(chēng)碼C是群碼(GroupCode)。定義2.3

設(shè)X=x1x2…xn和Y=y1y2…yn是Sn中的兩個(gè)元素，稱(chēng)為X與Y的漢明距離（HammingDistance）。第十九頁(yè)，共四十二頁(yè)，編輯于2023年，星期五

從定義可以看出，X和Y的漢明距離是X和Y中對(duì)應(yīng)位碼元不同的個(gè)數(shù)。設(shè)S3中兩個(gè)碼字為：000和011，這兩個(gè)碼字的漢明距離為2。而000和111的漢明距離為3。關(guān)于漢明距離，我們有以下結(jié)論：（1）H(X,X)=0;

（2）H(X,Y)=H(Y,X);

（3）H(X,Y)+H(Y,Z)≥H(X,Z)。第二十頁(yè)，共四十二頁(yè)，編輯于2023年，星期五（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第二十一頁(yè)，共四十二頁(yè)，編輯于2023年，星期五定義2.4一個(gè)碼C中所有不同碼字的漢明距離的極小值稱(chēng)為碼C的最小距離（MinimumDistance）,記為dmin(C)。即例如，dmin(S2)=dmin(S3)=1，dmin(C2)=2，dmin(C3)=3。利用編碼C的最小距離，可以刻畫(huà)編碼方式與糾錯(cuò)能力之間的關(guān)系，我們有以下兩定理：第二十二頁(yè)，共四十二頁(yè)，編輯于2023年，星期五〖定理2.1〗一個(gè)碼C能檢查出不超過(guò)k個(gè)錯(cuò)誤的充分必要條件為dmin(C)≥k+1?！级ɡ?.2〗一個(gè)碼C能糾正k個(gè)錯(cuò)誤的充分必要條件是dmin(C)≥2k+1。第二十三頁(yè)，共四十二頁(yè)，編輯于2023年，星期五例子2.3對(duì)于C2={01，10}，因?yàn)閐min(C2)=2=1+1,所以C2可以檢查出單個(gè)錯(cuò)誤；對(duì)于C3={101，010}，因dmin(C3)=3，故C3能夠發(fā)現(xiàn)并糾正單個(gè)錯(cuò)誤；對(duì)于S2和S3分別包含了長(zhǎng)度為2、3的所有碼，因而dmin(S2)=dmin(S3)=1，從而S2、S3既不能檢查錯(cuò)誤也不能糾正錯(cuò)誤。從而我們知道一個(gè)編碼如果包含了某個(gè)長(zhǎng)度的所有碼字，則此編碼一定無(wú)抗干擾能力。第二十四頁(yè)，共四十二頁(yè)，編輯于2023年，星期五例子2.4

奇偶校驗(yàn)碼（Paritycode)的編碼我們知道，編碼S2={00，01，10，11}沒(méi)有抗干擾能力。但我們可以在S2的每個(gè)碼字后增加一位（叫奇偶校驗(yàn)位），這一位是這樣安排的，它使每個(gè)碼字所含1的個(gè)數(shù)為偶數(shù)，按這種方法編碼后S2就變?yōu)?/p>

S2′={000，011，101，110}而它的最小距離dmin(S2′)=2，故定理2.1可知，它可想出單個(gè)錯(cuò)誤。而事實(shí)也是如此，當(dāng)傳遞過(guò)程中發(fā)生單個(gè)錯(cuò)誤則碼字就變?yōu)楹衅鏀?shù)個(gè)1的廢碼。第二十五頁(yè)，共四十二頁(yè)，編輯于2023年，星期五類(lèi)似地，增加奇偶校驗(yàn)位使碼字所含1的個(gè)數(shù)為奇數(shù)時(shí)也可得到相同的效果。我們可以把上述結(jié)果推廣到Sn中去，不管n多大，只要增加一奇偶校驗(yàn)位總可能查出一個(gè)錯(cuò)誤。這種方法在計(jì)算機(jī)中是使用很普遍的一種糾錯(cuò)碼，它的優(yōu)點(diǎn)是所付出的代價(jià)較?。ㄖ辉黾右晃桓郊拥钠媾夹ｒ?yàn)位），而且這種碼的生成與檢查也很簡(jiǎn)單，它的缺點(diǎn)是不能糾正錯(cuò)誤。第二十六頁(yè)，共四十二頁(yè)，編輯于2023年，星期五三、糾錯(cuò)碼的選擇前面分析，我們發(fā)現(xiàn)S2無(wú)糾錯(cuò)能力，但在S2中選取C2后，C2具有發(fā)現(xiàn)單錯(cuò)的能力。同樣，S3無(wú)糾錯(cuò)能力，但在S3中選取C3后，C3具有糾正單錯(cuò)的能力。從這里可以看出，如何從一些編碼中選取一些碼字組成新碼，使其具有一定的糾錯(cuò)能力是一個(gè)很重要的課題。下面我們介紹一種很重要的編碼——漢明編碼，這種編碼能發(fā)現(xiàn)并糾正單個(gè)錯(cuò)誤。第二十七頁(yè)，共四十二頁(yè)，編輯于2023年，星期五（一）漢明編碼的特例設(shè)有編碼S4，S4中每個(gè)碼字為a1a2a3a4，若增加三位校驗(yàn)位a5a6a7，從而使它成為長(zhǎng)度為7的碼字a1a2a3a4a5a6a7。其中校驗(yàn)位a5a6a7應(yīng)滿足下列方程：a1+2a2+2a3+2a5=0（2－1）a1+2a2+2a4+2a6=0（2－2）a1+2a3+2a4+2a7=0（2－3）也就是說(shuō)要滿足：a5=a1+2a2+2a3

a6=a1+2a2+2a4

a7=a1+2a3+2a4第二十八頁(yè)，共四十二頁(yè)，編輯于2023年，星期五因此，a1,a2,a3,a4一旦確定，則校驗(yàn)位a5,a6,a7可根據(jù)上述方程唯一確定。這樣我們由S4就可以得到一個(gè)長(zhǎng)度為7的編碼C，如表2－1所示。第二十九頁(yè)，共四十二頁(yè)，編輯于2023年，星期五表2－1a1a2a3a4a5a6a7a1a2a3a4a5a6a70000000100011100010111001100001010110100100011111101100101001101100001010110111010100110011111010001110001111111第三十頁(yè)，共四十二頁(yè)，編輯于2023年，星期五

上述的編碼C能發(fā)現(xiàn)一個(gè)錯(cuò)誤并糾正單個(gè)錯(cuò)誤。因?yàn)槿绻鸆中碼字發(fā)生單錯(cuò)，則上述三個(gè)方程必定至少有一個(gè)等式不滿足；當(dāng)C中碼字發(fā)生單錯(cuò)后，不同的字位錯(cuò)誤可使方程中不同的等式不成立，如當(dāng)a2發(fā)生錯(cuò)誤時(shí)必有方程（2－1）、（2－2）不成立，而當(dāng)a3發(fā)生錯(cuò)誤時(shí)必有方程（2－1）、（2－3）不成立，方程中三個(gè)等式的8種組合可對(duì)應(yīng)a1~a7的七個(gè)碼元每個(gè)碼的錯(cuò)誤以及一個(gè)正確無(wú)誤的碼字。第三十一頁(yè)，共四十二頁(yè)，編輯于2023年，星期五為討論方便，我們建立三個(gè)謂詞：

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

這三個(gè)謂詞的真假與對(duì)應(yīng)等式是否成立相一致。我們建立三個(gè)集合S1，S2，S3分別對(duì)應(yīng)P1，P2，P3。令

S1＝｛a1,a2,a3,a5｝

S2＝｛a1,a2,a4,a6｝

S3＝｛a1,a3,a4,a7｝第三十二頁(yè)，共四十二頁(yè)，編輯于2023年，星期五顯然，Si是使Pi為假的所有出錯(cuò)字的集合。我們可構(gòu)成下面7個(gè)非空集合：從這七個(gè)集合我們可以決定出錯(cuò)位。例如，

即表示a3∈S2，a3∈S1，a3∈S3，所以a3出錯(cuò)，則必有P2為真，P1、P3為假。反之亦然。如此類(lèi)推，可得到表2－2所示的糾錯(cuò)對(duì)照表。從表中可看出這種編碼C能糾正一個(gè)錯(cuò)誤。第三十三頁(yè)，共四十二頁(yè)，編輯于2023年，星期五2－2糾錯(cuò)對(duì)照表P1P2P3出錯(cuò)碼元000a1001a2010a3011a4100a5101a6110a7111無(wú)第三十四頁(yè)，共四十二頁(yè)，編輯于2023年，星期五我們將上例加以抽象，首先將方程（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、Θ的轉(zhuǎn)置矩陣，這里加法運(yùn)算為＋2?？梢?jiàn)，一個(gè)編碼可由矩陣H確定，而它的糾錯(cuò)能力可由H的特性決定。下面討論矩陣H。第三十五頁(yè)，共四十二頁(yè)，編輯于2023年，星期五定義2.5重量（Weight）一個(gè)碼字X所含1的個(gè)數(shù)稱(chēng)為此碼字的重量，記為W(X)。

例如，碼字001011的重量為3，碼字100000的重量為1，碼字00…0的重量為0，通常將00…0記為0′或Θ。利用碼字的重量，我們有如下結(jié)論：（1）設(shè)有碼C，對(duì)任意X,Y∈C，有

H(X,Y)=H(X?Y,Θ)=W(X?Y)；第三十六頁(yè)，共四十二頁(yè)，編輯于2023年，星期五（2）群碼C中非零碼字的最小重量等于此群碼的最小距離。即（3）設(shè)H是k行n列矩陣，X=x1x2…xn,并設(shè)集合G＝｛X｜H·XT＝ΘT｝，這里加法運(yùn)算為＋2，則＜G，?＞是群，即G是群碼。上述介紹的漢明碼就是群碼。第三十七頁(yè)，共四十二頁(yè)，編輯于2023年，星期五定義2.6群碼G＝｛X｜H·XT＝ΘT｝稱(chēng)為由H生成的群碼，而G中每一個(gè)碼字稱(chēng)為由H生成的碼字，矩陣H稱(chēng)為