【文章內(nèi)容簡介】 ，P矩陣的取值依具體情況而定。系統(tǒng)碼和非系統(tǒng)碼在糾檢錯性能以及抗干擾性能上是完全一樣的。但由于系統(tǒng)碼的表達和構(gòu)造簡單，因此常被人們采用。 線性分組碼與校驗矩陣令φ表示一個GF(2)上的(n,k)線性分組碼，則必有一個秩為nk的(nk)n階矩陣H滿足：φ={C|H?CT=0,?C∈Vn} 式（33）其中，Vn是長度為n的GF(2)上的n維線性空間，稱矩陣H為φ的一個校驗矩陣或者監(jiān)督矩陣。而且監(jiān)督矩陣和生成矩陣可以相互轉(zhuǎn)化，尤其對系統(tǒng)矩陣來說它們滿足關(guān)系：若， G = [Ik P] 式（34）則， H = [PT Ink] 式（35）上式中，Ik代表k階單位矩陣，P矩陣的取值依具體情況而定?？梢哉f，校驗矩陣反映了已編碼序列各碼字之間的線性約束關(guān)系，在線性分組碼的譯碼過程中起重要作用。 編譯碼過程分析 線性分組碼的編碼以上引入了生矩陣和校驗矩陣，下面對其編碼過程分析，對于任意給定的k位信息序列：U=[u1,u2,?,uk]，將他與生成矩陣（這里假設(shè)為系統(tǒng)矩陣）G=[Ik P] 相乘，可以求編碼后的n個碼字： 1,2,?,ck,?,c0=[u1,u2?,uk]? 1 0 ? 0 p11 p12 ? p1nk0 1 ? 0 p21 p22 ? p2nk? ? ? ? ? 0 0 ? 1 pk1 pk2 ? pknk 式（36）容易看到，k個信息位經(jīng)過編碼之后變?yōu)閚位，且前k位碼字保持不變，相當(dāng)于在原來的碼字后面直接加了nk個多余比特，也就是監(jiān)督碼元。顯然，其編碼效率為k/n。為了更清楚的表示編碼過程，可以假設(shè)生成矩陣為非系統(tǒng)矩陣：G = g11?g1n???gk1?gkn=g1?gk 式（37）k位信息碼U=[u1,u2,?,uk]的編碼過程重寫如下： C=U?G= u1g1+u2g2+?+ukgk 式（38）對某一碼字而言： i= u1g1i+u2g2i+…+ukgki 式（39）其中，uk和gij 均取自二進制的0和1。這是利用生成矩陣的一般編碼過程，在這一過程中編解碼十分容易實現(xiàn)，同時又提供了強大的糾錯和檢錯能力。 線性分組碼的譯碼假定系統(tǒng)采用一個GF(2)上的(n,k)分組碼來通信，其校驗矩陣為H。若發(fā)送的已編碼碼字為：C =[1,2,??,c0]，在傳輸過程中，信道產(chǎn)生的誤碼(錯誤圖樣)為E=[en1,en2,?,e0]，則接收端得到的碼組為V=C⊕E=[vn1,vn2,?,v0]。我們可以定義一個向量：S = V?HT，并稱向量S為伴隨式。根據(jù)線性分組碼的性質(zhì)C?HT=0可得 ：S=E?HT 式（310）看到，S取值僅與錯誤圖樣E有關(guān)，所以只要求出伴隨式S，便可恢復(fù)出發(fā)送碼字，這提供了一種簡便易行的譯碼思路。具體來講，當(dāng)伴隨式S=0時，表明接收碼字v沒有錯誤，即：C=V。反之，接收碼字V有錯，且C=V⊕E。由于H矩陣是一個nk行n列的矩陣，所以S是一個nk維矢量，它可以給出nk個獨立的方程，然而傳輸?shù)牟铄eE則是一個n維矢量，有n種可能取值，所以S并不能唯一確定E。對某個給定的S，E可以有2k個的解，即同一個伴隨式可以得到2k個錯誤圖樣，而真正的錯誤圖樣是其中之一。在接收端，譯碼器的作用便是從這些候選錯誤矢量中確定出一個能夠使平均錯判概率最小的矢量。在二進制對稱信道信道下，最可能的錯誤圖樣也就是漢明重量最小的接收碼組，也就是非零碼字最少的碼組。 Hamming碼的設(shè)計與編解碼過程分析 Hamming碼簡介以上內(nèi)容從原理上描述了線性分組碼編碼和譯碼。下面具體來說明在給定n、k的情況下，如何設(shè)計一種高效率的線性分組碼——Hamming碼。Hamming碼是1950年由漢明首先構(gòu)造的，它是一種能糾正一位錯碼的效率最高的分組碼?；蛘哒f，Hamming碼是一種糾正單個錯誤的完備碼，即SEC(Single Error Correcting)碼。這種編碼不僅具有良好的性能，而且編譯碼電路非常簡單，易于實現(xiàn)。所以，從20世紀50年代問世以來，它最先被用于磁芯存儲器，60年代初用于大型計算機，70年代在MOS存儲器中得到應(yīng)用，后來在中小型計算機中普遍采用，目前常用于RFID系統(tǒng)中多位錯誤的糾正?？傊琀amming碼在提高系統(tǒng)可靠性方面獲得了廣泛的應(yīng)用。Hamming碼的構(gòu)造必須滿足關(guān)系式： 碼長：n=2m1 信息位：k=2m1m 監(jiān)督位：nk=m,且m≥3 最小距離：dmin=3 上式中，n 為碼元總位數(shù)，m為監(jiān)督碼元位數(shù)。Hamming碼能糾正單個錯誤，所以每一種錯誤圖樣不能相同且與伴隨式一一對應(yīng)。這就要求監(jiān)督矩陣H中，任意兩列線性無關(guān)且不為0，而一個m行的H矩陣，最多只能有2m1列，即為Hamming碼碼長。Hamming碼的構(gòu)造原理類似于偶校驗碼。偶校驗碼是在信息碼元后增加一位監(jiān)督碼元，使包括信息碼元和監(jiān)督碼元的總碼元中1的個數(shù)為偶數(shù)，這種關(guān)系用數(shù)學(xué)式子表示為：1⊕2⊕?⊕c0=S 式（311）因為在偶監(jiān)督碼中非零碼字的個數(shù)為偶數(shù)，所以在正確傳輸時，必有 S = 0。這樣，就可以在接收端通過計算S的值判斷傳輸有無出錯：S = 0，無錯； S = 1，有錯。Hamming碼的編碼與之類似，只是將監(jiān)督碼元增加到多位。也就是說，要指示n位碼元中所有一位錯碼的情況，就必須滿足條件： r個監(jiān)督碼元有2r種組合方式，全零用來表示無錯傳輸，剩下2r1種情況用來表示2r1種錯誤。如果2r1=n，則可以指出所有n位單比特錯誤。 (7,4)漢明碼的設(shè)計下面我們通過構(gòu)造（7，4）漢明碼來分析這一過程。由信息位k=4，且2r1=n可得：r=3，現(xiàn)取r=3，則n=7。用c6，c5，?，c0表示這7個碼元，用S=[s1,s2,s3]表示三位矯正子，也就是前面提到的伴隨式[9]?？闪谐鲂Ｕ拥娜≈蹬c錯碼位置的對應(yīng)關(guān)系之一：表31校正子與錯碼位置對應(yīng)關(guān)系s1，s2，s3錯碼位置000001010100011101110111無錯a0a1a2a3a4a5a6根據(jù)表中關(guān)系，不難看出這種（7,4）漢明碼所對應(yīng)的線性約束方程如下： s1=c6⊕c5⊕c4⊕c2 s2=c6⊕c5⊕c3⊕c1 式（312） s3=c6⊕c4⊕c3⊕c0 若無錯，必有：0=c6⊕c5⊕c4⊕c2 0=c6⊕c5⊕c3⊕c1 式（313） 0=c6⊕c4⊕c3⊕c0 將上面方程組移項整理得： c2=c6⊕c5⊕c4 c1=c6⊕c5⊕c3 式（314） c0=c6⊕c4⊕c3 寫為矩陣形式有：c6,c5,c4,c3?P=(c2,c1,c0)其中，P= 1 1 1 1 1 0 1 0 1 0 1 1 由此可得生成矩陣的典型形式：G=I4 P=1 0 0 0 1 1 10 1 0 0 1 1 00 0 1 0 1 0 10 0 0 1 0 1 1 式（315）接下來，用U表示未編碼的信息碼組[u1,u2,u3,u4]，用C表示編碼后的信息碼組[c6,c5,?,c0]。那么，根據(jù)關(guān)系式：C=U?G，我們就可以得到編碼后的7位信息序列。假設(shè)信息輸入為U=[1010]，則有C=U?G=1010?1 0 0 0 1 1 10 1 0 0 1 1 00 0 1 0 1 0 10 0 0 1 0 1 1=[1010010] 式（316）其他編碼的對應(yīng)關(guān)系如下：表32信息位與監(jiān)督位對應(yīng)關(guān)系0000000100100011010001010110011110001001101010111100110111101111000011101110110101011000111100010001001010100111信息位 監(jiān)督位信息位 監(jiān)督位c6,c5,c4,c3 c2,c1,c0c6 , c5, c4, c3 c2,c1,c0討論過編碼，再來看譯碼。將約束方程變化形式為：1 1 1 0 1 0 01 1 0 1 0 1 01 0 1 1 0 0 1?c6c5?c0=000 式（317）上式簡記為：C?HT=0，其中，H=1 1 1 0 1 0 01 1 0 1 0 1 01 0 1 1 0 0 1，C=[c6,c5,c4,c3,c2,c1,c0 ]。 這里的H就是典型的監(jiān)督矩陣。設(shè)接收碼字為V，則在無錯情況下，一定可以得到同樣的關(guān)系式：V?HT=0 ；否則，V?HT≠0，此時接收碼字對應(yīng)的錯誤圖樣是E=C⊕V。檢錯能力方面，根據(jù)誤碼個數(shù)與最小漢明距離的關(guān)系dmin=3≥e+1可知，碼組至少可以檢測出1個或2個比特錯誤。糾錯能力方面，由dmin≥2t+1可知，它可以保證糾正一位錯碼。又根據(jù)前面的分析結(jié)果，錯誤圖樣滿足關(guān)系：S=V?HT=E?HT，S是伴隨式（或矯正子）。顯然，E有128種可能值，而S只有8種，因此一般情況下取這16種圖樣中漢明重量最小的作為最優(yōu)結(jié)果。假設(shè)譯碼器收到的碼字為：[0100000]，那么計算可得對應(yīng)的伴隨式：S=V?HT=0100000?111110101011100001=[110] 式（318）看到伴隨式S也就是監(jiān)督矩陣H的第二列，即接收碼字的第二位出錯，可糾正錯誤圖樣為[0100000]，將此錯誤圖樣與接收碼字相加就得到了譯碼結(jié)果[0000000]。下面是錯誤圖樣和伴隨式的對應(yīng)關(guān)系：表33錯誤圖樣和伴隨式的對應(yīng)關(guān)系0000000000000100000100001000000010000100000100000100000000000101001110010111011101111111伴隨式 可糾正錯誤圖樣 糾錯個數(shù)有了上述對應(yīng)關(guān)系，將接收到的碼字V與監(jiān)督矩陣H相乘求出伴隨式S，然后通過查表立即可得錯誤圖樣E，從而利用C=V⊕E較為準確的譯碼。但是應(yīng)該清楚的是，這里的譯碼為最大似然譯碼，譯碼結(jié)果只保證正確的概率取到最大，而非一定正確。 循環(huán)碼及其描述方法 概念循環(huán)碼(Cyclic Code)同樣是線性分組碼中重要的子類，它除了線性分組碼具有的一般性質(zhì)外，還具有循環(huán)性，即循環(huán)碼允許集合中任意碼字循環(huán)移位所得的碼字仍為該碼組集合中的一個碼字。循環(huán)碼的兩個最引人矚目的特點是：（1） 可以用反饋線性移位寄存器很容易的實現(xiàn)其編碼和伴隨式計算。（2） 由于循環(huán)碼有許多固有的代數(shù)結(jié)構(gòu)，從而可以找到各種簡單實用的譯碼方法。正是由于上述特點，在目前的計算機糾錯系統(tǒng)中所使用的線性分組碼幾乎都是循環(huán)碼。而且近來發(fā)現(xiàn)的許多新型分組碼都與循環(huán)碼密切相關(guān)，所以無論在理論還是現(xiàn)實中，對它的研究都有著十分重要的意義。 循環(huán)碼的表示在Hamming碼的分析中，我們曾引入生成矩陣和校驗矩陣作為它的描述工具，現(xiàn)在，考慮到循環(huán)碼自身特點，我們引入生成多項式，這樣便可以運用數(shù)學(xué)語言使整個描述過程更加條理、清楚。設(shè)碼長為n的循環(huán)碼表示為：[1,2,?,c0] ，如果把碼組中各碼元的取值當(dāng)作多項式的系數(shù)，把碼元的相對位置看作其次數(shù)，那么這一碼組可以用多項式表示如下：cx= 1?xn1+2?xn2+?+c0 式（319）在此，x只被看作一個表示碼元位置的記號，我們所關(guān)心的是它前面的系數(shù)取值。對于一個(n，k)循環(huán)碼來說，如果碼字集合中所有碼多項式都是某一多項式的倍式，則稱這一多項式為該碼組的生成多項式。生成多項式一般用g(x)表示，它是碼字集合中唯一一個冪次為r=nk的碼多項式，也是xn+1的所有因式中次數(shù)最低的碼多項式。即：gx=xr+gr1?xr1+…+g1?x +1 式（320）另外，循環(huán)碼的生成矩陣也常用多項式形式表示，即：Gx= xk1?gxxk2?gx?x ?gxgx 式（321）為了便于對循環(huán)碼的編譯，通常還定義監(jiān)督多項式，令：hx=xn+1g(x)=xk+hk1?xk1+…+h1?x +1 式（322）式中，g(x)是常數(shù)項為