代數(shù)系統(tǒng)在計算機科學中的應用

1、代數(shù)系統(tǒng)在計算機科學中的應用第1頁，共45頁，2022年，5月20日，13點32分，星期日人們研究和考察現(xiàn)實世界中各種現(xiàn)象或過程，往往要借助某些數(shù)學工具。在代數(shù)中，可以用正整數(shù)集合上的加法運算來描述企業(yè)產(chǎn)品的累計數(shù)，可以用集合之間的“并”、“交”運算來描述單位與單位之間的關(guān)系等。我們所接觸過的數(shù)學結(jié)構(gòu)，連續(xù)的或離散的，常常是對研究對象（自然數(shù)、實數(shù)、多項式、矩陣、命題、集合乃至圖）定義各種運算（加、減、乘，與、或、非，并、交、補），然后討論這些對象及運算的有關(guān)性質(zhì)。第2頁，共45頁，2022年，5月20日，13點32分，星期日針對某個具體問題選用適宜的數(shù)學結(jié)構(gòu)去進行較為確切的描述，這就是所謂“

2、數(shù)學模型”。可見，數(shù)學結(jié)構(gòu)在數(shù)學模型中占有極為重要的位置。而代數(shù)系統(tǒng)是一類特殊的數(shù)學結(jié)構(gòu)由對象集合及運算組成的數(shù)學結(jié)構(gòu)，我們通常稱它為代數(shù)結(jié)構(gòu)。它在計算機科學中有著廣泛的應用，對計算機科學的產(chǎn)生和發(fā)展有重大影響；反過來，計算機科學的發(fā)展對抽象代數(shù)學又提出了新的要求，促使抽象代數(shù)學不斷涌現(xiàn)新概念，發(fā)展新理論。第3頁，共45頁，2022年，5月20日，13點32分，星期日格與布爾代數(shù)的理論成為電子計算機硬件設計和通訊系統(tǒng)設計中的重要工具。半群理論在自動機和形式語言研究中發(fā)揮了重要作用。關(guān)系代數(shù)理論成為最流行的數(shù)據(jù)庫的理論模型。格論是計算機語言的形式語義的理論基礎。抽象代數(shù)規(guī)范理論和技術(shù)廣泛應用于計

3、算機軟件形式說明和開發(fā)，以及硬件體系結(jié)構(gòu)設計。有限域的理論是編碼理論的數(shù)學基礎，在通訊中發(fā)揮了重要作用。在計算機算法設計與分析中，代數(shù)算法研究占有主導地位。第4頁，共45頁，2022年，5月20日，13點32分，星期日糾錯碼一、糾錯碼概述 我們知道，在計算機中和數(shù)據(jù)通信中，經(jīng)常需要將二進制數(shù)字信號進行傳遞，這種傳遞的距離近則數(shù)米、數(shù)毫米，遠則超過數(shù)千公里。在傳遞住處過程中，由于存在著各種干擾，可能會使二進制信號產(chǎn)生失真現(xiàn)象，即在傳遞過程中二進制信號0可能會變成1，1可能會變成0。第5頁，共45頁，2022年，5月20日，13點32分，星期日 圖2.1是一個二進制信號傳遞的簡單模型，它有一個發(fā)送

4、端和一個接收端，二進制信號串X=x1x2xn 從發(fā)送端發(fā)出經(jīng)傳輸介質(zhì)而至接收端。由于存在著干擾對傳輸介質(zhì)的影響，因而接收端收到的二進制信號串 中的 可能不一定就與xi相等，從而產(chǎn)生了二進制信號的傳遞錯誤。發(fā)送端接收端X=x1x2 xn干擾圖2.1第6頁，共45頁，2022年，5月20日，13點32分，星期日 由于在計算機中和數(shù)據(jù)通信系統(tǒng)中的信號傳遞是非常的頻繁與廣泛，因此，如何防止傳輸錯誤就變得相當重要了，當然，要解決這個問題可以有不同的途徑。人們所想到的第一個途徑是提高設備的抗干擾能力和信號的抗干擾能力。但是，大家都知道，這種從物理角度去提高抗干擾能力并不能完全消除錯誤的出現(xiàn)。第7頁，共45

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

6、、譯碼器、信宿第9頁，共45頁，2022年，5月20日，13點32分，星期日 但是，為什么糾錯碼具有發(fā)現(xiàn)錯誤、糾正錯誤的能力呢？糾錯碼又是按什么樣的原理去編的呢？為了說明這些問題，我們首先介紹一些基本概念。第10頁，共45頁，2022年，5月20日，13點32分，星期日定義2.1 由0和1組成的串稱為字（Word），一些字的集合稱為碼（Code）。碼中的字稱為碼字（Code Word）。不在碼中的字稱為廢碼（Invalid Code）。碼中的每個二進制信號0或1稱為碼元（Code Letter）。 我們下面舉出幾個關(guān)于糾錯碼例子。 第11頁，共45頁，2022年，5月20日，13點32分，星期

7、日例2.1 設有長度為2的字，它們一共可有22=4個，它們所組成的字集S2=00，01，10，11。當選取編碼為S2時，這種編碼不具有抗干擾能力。因為當S2中的一個字如10，在傳遞過程中其第一個碼元1變?yōu)?，因而整個字成為00時，由于00也是S2中的字，故我們不能發(fā)現(xiàn)傳遞中是否出錯。 第12頁，共45頁，2022年，5月20日，13點32分，星期日 當我們選取S2的一個子集如C2=01，10作為編碼時就會發(fā)生另一種完全不同的情況。 因為此時00和11均為廢碼，而當01在傳遞過程中第一個碼元由0變?yōu)?，即整個字成為11時，由于11是廢碼，因而我們發(fā)現(xiàn)傳遞過程中出現(xiàn)了錯誤。對10也有同樣的情況。

8、01第一個碼元錯成11第二個碼元錯成0010第一個碼元錯成00第二個碼元錯成11第13頁，共45頁，2022年，5月20日，13點32分，星期日 可見，這種編碼有一個缺點，即它只能發(fā)現(xiàn)錯誤而不能糾正錯誤，因此我們還需要選擇另一種能糾錯的編碼。第14頁，共45頁，2022年，5月20日，13點32分，星期日例2.2 考慮長度為3的字 它們一共可有23=8個，它們所組成的字集S3=000，001，010，011，100，101，110，111 選取編碼C3=101，010。利用此編碼我們不僅能發(fā)現(xiàn)錯誤而且能糾正錯誤。 因為碼字101出現(xiàn)單個錯誤后將變?yōu)椋?01，111，100；而碼字010出現(xiàn)錯誤

9、后將變?yōu)?10，000，011。故如碼字101在傳遞過程中任何一個碼元出現(xiàn)了錯誤，整個碼字只會變?yōu)?11、100或001，但是都可知其原碼為101。對于碼字010也有類似的情況。故對編碼C3，我們不僅能發(fā)現(xiàn)錯誤而且能糾正錯誤。第15頁，共45頁，2022年，5月20日，13點32分，星期日 當然，上述編碼還有一個缺點，就是它只能發(fā)現(xiàn)并糾正單個錯誤。當錯誤超過兩個碼元時，它就既不能發(fā)現(xiàn)錯誤，更無法糾正了。第16頁，共45頁，2022年，5月20日，13點32分，星期日二、糾錯碼的糾錯能力 前面例子中我們發(fā)現(xiàn)C2編碼僅能發(fā)現(xiàn)錯誤，按C3編碼可發(fā)現(xiàn)并糾正單個錯誤?？梢姡荒艿木幋a具有不同的糾錯能力。

10、下面介紹編碼方式與糾錯能力之間的聯(lián)系。第17頁，共45頁，2022年，5月20日，13點32分，星期日設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)， 我們稱運算為按位加。 顯然，是一個代數(shù)系統(tǒng)，且運算滿足結(jié)合律，它的幺元為000，每個元素的逆元都是它自身。因此， 是一個群。第18頁，共45頁，2022年，5月20日，13點32分，星期日定義2

11、.2 Sn的任一非空子集C，如果是群，即C是Sn的子群，則稱碼C是群碼(Group Code)。定義2.3 設X=x1x2 xn 和Y=y1y2 yn 是Sn中的兩個元素，稱為X與Y的漢明距離（Hamming Distance）。 第19頁，共45頁，2022年，5月20日，13點32分，星期日 從定義可以看出，X和Y的漢明距離是X和Y中對應位碼元不同的個數(shù)。設S3中兩個碼字為：000和011，這兩個碼字的漢明距離為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)。第20

12、頁，共45頁，2022年，5月20日，13點32分，星期日（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第21頁，共45頁，2022年，5月20日，13點32分，星期日定義2.4一個碼C中所有不同碼字的漢明距離的極小值稱為碼C的最小距離（Minimum Distance）,記為dmin(C)。即例如， dmin(S2)= dmin(S3)=1， dmin(C2)=2， dmin(C3)=3。利用編碼C的最小距離，可以刻畫編碼方式與糾錯能力之間的關(guān)系，我們有以下兩定理：第22頁，共4

13、5頁，2022年，5月20日，13點32分，星期日定理2.1一個碼C能檢查出不超過k個錯誤的充分必要條件為dmin(C) k+1。定理2.2 一個碼C能糾正k個錯誤的充分必要條件是dmin(C) 2k+1。第23頁，共45頁，2022年，5月20日，13點32分，星期日例子2.3對于C2=01，10，因為dmin(C2)=2=1+1,所以C2可以檢查出單個錯誤；對于C3=101，010，因dmin(C3)=3，故C3能夠發(fā)現(xiàn)并糾正單個錯誤；對于S2和S3分別包含了長度為2、3的所有碼，因而dmin(S2)= dmin(S3)=1，從而S2、S3既不能檢查錯誤也不能糾正錯誤。從而我們知道一個編碼

14、如果包含了某個長度的所有碼字，則此編碼一定無抗干擾能力。第24頁，共45頁，2022年，5月20日，13點32分，星期日例子2.4奇偶校驗碼（Parity code)的編碼我們知道，編碼S2=00，01，10，11沒有抗干擾能力。但我們可以在S2的每個碼字后增加一位（叫奇偶校驗位），這一位是這樣安排的，它使每個碼字所含1的個數(shù)為偶數(shù)，按這種方法編碼后S2就變?yōu)镾2=000，011，101，110而它的最小距離dmin(S2)=2，故定理2.1可知，它可想出單個錯誤。而事實也是如此，當傳遞過程中發(fā)生單個錯誤則碼字就變?yōu)楹衅鏀?shù)個1的廢碼。第25頁，共45頁，2022年，5月20日，13點32分，

15、星期日類似地，增加奇偶校驗位使碼字所含1的個數(shù)為奇數(shù)時也可得到相同的效果。我們可以把上述結(jié)果推廣到Sn中去，不管n多大，只要增加一奇偶校驗位總可能查出一個錯誤。這種方法在計算機中是使用很普遍的一種糾錯碼，它的優(yōu)點是所付出的代價較?。ㄖ辉黾右晃桓郊拥钠媾夹ｒ炍唬?，而且這種碼的生成與檢查也很簡單，它的缺點是不能糾正錯誤。第26頁，共45頁，2022年，5月20日，13點32分，星期日三、糾錯碼的選擇前面分析，我們發(fā)現(xiàn)S2無糾錯能力，但在S2中選取C2后，C2具有發(fā)現(xiàn)單錯的能力。同樣，S3無糾錯能力，但在S3中選取C3后，C3具有糾正單錯的能力。從這里可以看出，如何從一些編碼中選取一些碼字組成新碼，

16、使其具有一定的糾錯能力是一個很重要的課題。下面我們介紹一種很重要的編碼漢明編碼，這種編碼能發(fā)現(xiàn)并糾正單個錯誤。第27頁，共45頁，2022年，5月20日，13點32分，星期日（一）漢明編碼的特例設有編碼S4，S4中每個碼字為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 +

17、2 a2 +2 a4 a7= a1 +2 a3 +2 a4第28頁，共45頁，2022年，5月20日，13點32分，星期日因此，a1,a2,a3,a4一旦確定，則校驗位a5,a6,a7可根據(jù)上述方程唯一確定。這樣我們由S4就可以得到一個長度為7的編碼C，如表21所示。第29頁，共45頁，2022年，5月20日，13點32分，星期日表21a1a2a3a4a5a6a7a1a2a3a4a5a6a70000000100011100010111001100001010110100100011111101100101001101100001010110111010100110011111010001110

18、001111111第30頁，共45頁，2022年，5月20日，13點32分，星期日 上述的編碼C能發(fā)現(xiàn)一個錯誤并糾正單個錯誤。因為如果C中碼字發(fā)生單錯，則上述三個方程必定至少有一個等式不滿足；當C中碼字發(fā)生單錯后，不同的字位錯誤可使方程中不同的等式不成立，如當a2發(fā)生錯誤時必有方程（21）、（22）不成立，而當a3發(fā)生錯誤時必有方程（21）、（23）不成立，方程中三個等式的8種組合可對應a1a7的七個碼元每個碼的錯誤以及一個正確無誤的碼字。第31頁，共45頁，2022年，5月20日，13點32分，星期日為討論方便，我們建立三個謂詞：P1(a1,a2,a7): a1 +2 a2 +2 a3 +2

19、 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頁，2022年，5月20日，13點32分，星期日顯然，Si是使Pi為假的所有出錯字的集合。我們可構(gòu)成下面7個非空集合：從這七個集合我們可以決定出錯位。例如，即表示a3S2， a3S1， a3S3，所以a3出錯，則必有P2為真，P1、P3為假。反

20、之亦然。如此類推，可得到表22所示的糾錯對照表。從表中可看出這種編碼C能糾正一個錯誤。第33頁，共45頁，2022年，5月20日，13點32分，星期日22糾錯對照表P1P2P3出錯碼元000a1001a2010a3011a4100a5101a6110a7111無第34頁，共45頁，2022年，5月20日，13點32分，星期日我們將上例加以抽象，首先將方程（21）、（22）、（23）表示為矩陣形式：HXTT 1110100其中H1101010 1011001，X(a1,a2,a3,a4,a5,a6,a7), =(0,0,0),XT、 T分別是X、的轉(zhuǎn)置矩陣，這里加法運算為2?？梢?，一個編碼可由矩

21、陣H確定，而它的糾錯能力可由H的特性決定。下面討論矩陣H。第35頁，共45頁，2022年，5月20日，13點32分，星期日定義2.5重量（Weight）一個碼字X所含1的個數(shù)稱為此碼字的重量，記為W(X)。例如，碼字001011的重量為3，碼字100000的重量為1，碼字000的重量為0，通常將000記為0或。利用碼字的重量，我們有如下結(jié)論：（1）設有碼C，對任意X,YC，有H(X,Y)=H(XY, )=W(XY)；第36頁，共45頁，2022年，5月20日，13點32分，星期日（2）群碼C中非零碼字的最小重量等于此群碼的最小距離。即（3）設H是k行n列矩陣，X=x1x2xn,并設集合GXHX

22、TT，這里加法運算為2，則G，是群，即G是群碼。上述介紹的漢明碼就是群碼。第37頁，共45頁，2022年，5月20日，13點32分，星期日定義2.6群碼GXHXTT稱為由H生成的群碼，而G中每一個碼字稱為由H生成的碼字，矩陣H稱為一致校驗矩陣（Uniform Check Matrix） 。第38頁，共45頁，2022年，5月20日，13點32分，星期日現(xiàn)在我們介紹矩陣列向量的概念，設矩陣H為此時矩陣H可記為 H（h1 h2 h3 hn)而hi叫做矩陣H的第i個列向量（Column Vector).第39頁，共45頁，2022年，5月20日，13點32分，星期日我們有如下結(jié)論：（1）一致校驗矩陣

23、H生成一個重量為p的碼字的充分必要條件是在H中存在p個列向量，它們的按位加為T 。（2）由H生成的群碼的最小距離等于H中列向量按位加為T的最小列向量數(shù)。這個結(jié)論建立了最小距離與列向量之間的聯(lián)系。前面結(jié)論我們知道：一個碼的糾錯能力由其最小距離決定。故有：一個群碼的糾錯能力可由其一致校驗矩陣H中列向量按位加為T的最小列向量數(shù)決定。第40頁，共45頁，2022年，5月20日，13點32分，星期日故只要選取適當?shù)腍就可使其生成的碼達到預定的糾錯能力。對于前面所述的漢明碼，它的一致校驗矩陣H中沒有零向量，且各列向量之間均互不相同，但它的第二、三、四列向量的按位加為T，由此結(jié)論可知這個碼的最小距離為3，而且可知此群必能糾正單個錯誤。第41頁，共45頁，2022年，5月20日，13點32分，星期日將上