【文章內(nèi)容簡介】 或 (32)設分組碼（）中，為了糾正一位錯碼，則由式(32)可知需要監(jiān)督位數(shù)。若取，那么碼長。用表示這7個碼元，用,來表示三個監(jiān)督關系式的值，那么的值與錯碼位置的對應關系可以規(guī)定如下表31：表31 的值與錯碼位置的對應關系錯碼位置錯碼位置 無錯由表一可以看出，僅當一錯碼位置出現(xiàn)在、或時，為1；否則為0。也就是說、和四個碼元構(gòu)成監(jiān)督關系式： (33)同理，、和也構(gòu)成監(jiān)督關系式 ： (34)還有、 和構(gòu)成監(jiān)督關系式 ： (35)在發(fā)送端編碼時，信息位、和的值決定于輸入信號，因此它們是隨機的。而監(jiān)督位、和 應根據(jù)信息位的取值按照監(jiān)督關系來確定，也就是監(jiān)督位應使上述的、和的值為0，來表示碼組中沒有錯碼，即： (36) 由上式解出的監(jiān)督位為 ： (37) 故如給出信息位后，可以根據(jù)式(37) 得出監(jiān)督位，結(jié)果見下表32：表32 信息位對應的監(jiān)督位信息位監(jiān)督位信息位監(jiān)督位0000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111當接收端收到各個碼組時，可先按式(33)，(34)，(35)計算出，和的值，再根據(jù)它們的值按照表二判斷錯碼的具體位置。按照這種方法構(gòu)成的碼稱為漢明碼。其中表二所列的（7，4）漢明碼的最小碼距，由糾檢錯編碼定理可知，這種碼能糾正一位錯碼或檢測兩個錯碼。并且漢明碼的編碼效率是。則當n很大時，編碼效率接近于1。所以，漢明碼是一種高效碼。 線性分組碼的相關概念由于線性碼是指信息位和監(jiān)督位滿足一組線性方程的碼，式(36)就是這樣一組線性方程，可以將它改寫為： (38) 上述式中的“+”都指的是模二加，其中式(38)還能表示成如下的矩陣相乘形式： 其中：右上標“T”表示將矩陣轉(zhuǎn)置。上式中的H稱為監(jiān)督矩陣，只要監(jiān)督矩陣H給定，編碼時監(jiān)督位和信息位的關系就確定了。且H的行數(shù)就是監(jiān)督位r的數(shù)目。式(37)若變成矩陣的形式則為： = = Q (39)式中Q是一個階矩陣，式(39)表示只要給定信息位，再用信息位乘以矩陣Q,就可以得到監(jiān)督位。若將矩陣Q的左邊加上階單位方陣就可構(gòu)成新矩陣G (310) 矩陣G稱為生成矩陣，由它可以生成整個碼組，即 (311) 或 (312) 由此可知，若找到了生成矩陣G ，那么編碼方法就完全確定了。式(312)中的矩陣A是一n列的行矩陣，它的n個元素就是碼組中的n個碼元，所以發(fā)送的碼組就是A，因為碼組在傳輸過程中可能由于干擾而引入差錯，故接收端收到的碼組可能和A不同。設接收到的碼組為矩陣B，它是一n列行矩陣，即： (313) 則發(fā)送碼組與接收碼組的差為 (模二加) 或 (314)上式中的E就是傳輸中產(chǎn)生的錯碼行矩陣 (315) 其中 當ei =0，則表示該位接收碼元無錯；當ei =1，則表示該位接收碼元有錯。其中錯碼矩陣稱為錯誤圖樣。當接收碼組有錯時，B與監(jiān)督矩陣的轉(zhuǎn)置相乘的積記為S，即： (316)上式中的S稱為校正子。由于，因此校正子S只和E有關。可以通過S求得E，然后進行誤碼糾正。 循環(huán)碼 循環(huán)碼的概念在線性分組碼中，有一種重要的碼稱為循環(huán)碼。它是在嚴密的代數(shù)學理論基礎上建立起來的。循環(huán)碼的編碼和解碼設備都不太復雜，并且檢錯（糾錯）的能力較強，這些特點有助于按照所要求的糾錯能力系統(tǒng)地構(gòu)造這類碼，并簡化解碼方法。目前，循環(huán)碼在理論上和實踐上都有了較大的發(fā)展。循環(huán)碼除了具有線性碼的一般性質(zhì)外，還具有循環(huán)性，也就是循環(huán)碼中任何一個碼組向左或者向右循環(huán)移位仍然是這個碼組集合里的碼組。即如果是一個循環(huán)碼組，則、…也是該編碼中的碼組。在代數(shù)編碼理論中，把這種碼組中各碼元看作是一個多項式的系數(shù)，即一個長為n的碼組可以表示成： (317) 這種多項式中，x僅是碼元位置的標記。因此我們并不關心x的取值。這種多項式有時稱為碼多項式。在整數(shù)運算中，有模n運算。在模n運算下，一整數(shù)m等于其被n除得之余數(shù)。在碼多項式運算中也有類似的按模運算。若一任意多項式被一n次多項式除，得到商式和一個次數(shù)小于n的余式，即則寫為 (模) (318)這時，碼多項式系數(shù)仍按模2運算，即只取值0和1。不過注意，在模2運算中，用加法代替了減法。在循環(huán)碼中，若是一個長為n的許用碼組，則在按模運算下，亦是一個許用碼組。 循環(huán)碼的生成矩陣有了生成矩陣G，就可以由 k個信息位得出整個碼組，而且生成矩陣G的每一行都是一個碼組。由于G是k行n列矩陣，因此，若能找到k個已知碼組，就能構(gòu)成矩陣G。如前所述，這k個已知碼組必須是線性不相關的，否則，給定的信息位與編出的碼組就不是一一對應的。在循環(huán)碼中，一個(n，k)碼有個不同碼組。若用表示其中前()位皆為0的碼組，則，，…，都是碼組，而且這k個碼組是線性無關的。因此它們可以用來構(gòu)成此循環(huán)碼的生成矩陣G。在循環(huán)碼中除全0碼組外，再沒有連續(xù)k位均為0的碼組，即連0的長度最多只能有位。因此必須是一個常數(shù)項不為0的次多項式，而且，這個還是這種(n，k)碼中次數(shù)為的唯一的一個多項式。我們稱這唯一的次多項式為碼的生成多項式。一旦確定了，則整個(n，k)循環(huán)碼就被確定了。所有碼多項式都可被整除，而且任一次數(shù)不大于的多項式乘都是碼多項式。循環(huán)碼的生成多項式應該是的一個次因式。選用的生成多項式不同，產(chǎn)生出的循環(huán)碼碼組也不同。 循環(huán)碼的編碼方法循環(huán)碼的編碼步驟:，其次數(shù)小于k。用乘，這一運算實際上是把信息碼后附加上個0。，得到商和余式。 (319)上述三步運算，在用硬件實現(xiàn)時，可以由除法電路來實現(xiàn)。除法電路的主體由一些移存器和模2加法器組成。用這種方法編出的碼組，前面是原來的k個信息位，后面是個監(jiān)督位。 循環(huán)碼的解碼方法循環(huán)碼的解碼:接收端解碼的要求有兩個:檢錯和糾錯。達到檢錯目的的解碼原理十分簡單。當傳輸中未發(fā)生錯誤時，接收碼組與發(fā)送碼組相同，即，故接收碼組必定能被整除；若碼組在傳輸中發(fā)生錯誤，則被除時可能除不盡而有余項。因此，我們就以余項是否為零來判別碼組中有無錯碼。根據(jù)這一原理構(gòu)成的解碼器的核心就是一個除法電路和緩沖移存器，而且這里的除法電路與發(fā)送端編碼器中的除法電路相同。需要指出，有錯碼的接收碼組也有可能被整除，這時的錯碼就不能檢出了。這種錯誤稱為不可檢錯誤。不可檢錯誤中的錯碼數(shù)必定超過了這種編碼的檢錯能力。在接收端為了能夠糾錯，要求每個可糾正的錯誤圖樣必須與一個特定余式有一一對應關系，這里，錯誤圖樣是指錯碼矩陣E的各種具體取值的圖樣，余式是指接收碼組被生成多項式除所得的余式。糾錯可按下述步驟進行:,得出余式；；,便得到已糾正錯誤的原發(fā)送碼組。糾錯解碼器由一4級反饋移位寄存器組成的除法電路和一緩沖移位寄存器組成.給定一(n,k)循環(huán)碼組集合，使前個高階信息數(shù)字全為零，于是得到有個碼組的集合，然后從這些碼組中刪去這i個零信息位數(shù)字，最終得到一種新的(，)的線性碼，我們稱這種碼為縮短循環(huán)碼。縮短循環(huán)碼與產(chǎn)生該碼的原循環(huán)碼至少具有相同的糾錯能力，縮短循環(huán)碼的編碼和譯碼可用原循環(huán)碼使用的電路完成。 循環(huán)冗余校驗碼CRC碼 循環(huán)碼特別適合于檢測錯誤，不僅因為它有很強的檢測能力，而且由于編碼器和錯誤檢測電路都不太復雜。循環(huán)冗余校驗碼又叫CRC碼，是常用的檢測錯誤碼。CRC碼是由兩部分組成，前部分是信息碼，就是需要校驗的信息，后部分是校驗碼，如果CRC碼共長n個bit，信息碼長k個bit，就稱為(n，k)碼。它的編碼規(guī)則是：首先將原信息碼(kbit)左移r位運用一個生成多項式（也可看成二進制數(shù)）用模2除上面的式子，得到的余數(shù)就是校驗碼。非常簡單，要說明的：模2除