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