7交大通信技術(shù)基礎(chǔ)課件6b54

1、1第五節(jié) 循環(huán)碼循環(huán)碼是線性分組碼中一類重要的碼，它是以現(xiàn)代代數(shù)理論作為基礎(chǔ)建立起來的。循環(huán)碼的編碼和譯碼設(shè)備都不太復(fù)雜，且檢錯糾錯的能力較強，目前在理論和實踐上都有較大的發(fā)展。一、循環(huán)碼的循環(huán)特性循環(huán)碼是一種線性分組碼，且為系統(tǒng)碼，即前位為信息碼，后位為監(jiān)督碼，它除了具有線性分組碼的封閉性外，還具有循環(huán)性：即循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后（將最后端的碼元移至左端，或相反）所得到的碼組仍為它的一許用碼組。2(7,3)循環(huán)碼：信息位監(jiān)督位碼組編號6a5a4a3a2a1a0a100000002001011130101110401110015100101161011100711001018111

2、00103一般來說，若 是一個(n,k)循環(huán)碼的碼組，則下列也都是該循環(huán)碼的碼組。),(0121aaaann ),(1032 nnnaaaa),(2143 nnnnaaaa),(1210aaaan 41、碼多項式為了便于用代數(shù)理論來研究循環(huán)碼，把長為n的碼組與(n-1)次多項式建立一一對應(yīng)的關(guān)系，即把碼組中各碼元當(dāng)作是一個多項式的系數(shù)。若碼組則相應(yīng)的多項式表示為（7，3）循環(huán)碼中的任一碼組可以表示為),(0121aaaaAnn 012211)(axaxaxaxAnnnn 012233445566)(axaxaxaxaxaxaxA5這種多項式中，x只是碼元位置的標(biāo)記。例如上式表示第7碼組中，a6

3、、 a5、 a2和 a0為“1”，其它均為零。我們對x的取值并不關(guān)心，多項式中的存在只表示該對應(yīng)碼位上是“1”碼，否則為“0”碼，我們稱這種多項式為碼多項式。例如表中第7碼組可表示為：由此可知碼組和碼多項式本質(zhì)上是一回事，只是表示方法不同而已。1010011)(23456xxxxxxxA1256xxx62、碼多項式的按模運算（1）整數(shù)的模n運算如果一整數(shù)m可以表示成：Q為整數(shù)，則稱在模n運算下有：如：可見：在模n運算下，一整數(shù)等于其被n除得的余數(shù)。npnpQnm，），（模npm ），（模2011），（模213217（2）碼多項式的模運算由于碼多項式的系數(shù)為二進制，所以按模2運算，在模2運算中，

4、用加法代替減法。)()()()(xRxQxNxF），（模)()()(xNxRxF），（模1133xx），（模1113224xxxxx81024 xx13xxxx 0412 xx913x113x13x10在循環(huán)碼中，若T(x)是一個長度為n的許用碼組，則xiT(x)在模(xn+1)運算下，也是一個許用碼組。），（模1)()(nixxTxTx012211)(axaxaxaxTnnnn 112211)( ninnininninnixaxaxaxaxTxiininxaxaxa01122 11)() 1)()() 1)()()(22110112211221101122112211221101122112

5、21101122112211inininiininninninininiininnininininninininiininninninininiininninnininninniaxaxaxaxaxaxaxaxaxaxaxaxaxaaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxTx 12結(jié)論：一個長為n的循環(huán)碼，它必定是按模(xn+1)運算的一個余式。1)(256xxxxTT(x)是T(x)代表的碼組向左循環(huán)移位i次的結(jié)果。舉例：舉例： 是(7,3)循環(huán)碼的一個許用碼組，則x3T(x)在模(x7+1)運算下，也是一個許用碼組。inininiininaxaxax

6、axaxaxT 221101111)(133、循環(huán)碼的生成矩陣G在討論線性分組碼時已經(jīng)指出：若找到了碼的生成矩陣G，就可以由k個信息位得出整個碼組，而且生成矩陣的每一行都是一個碼組。如(7,4)線性分組碼：當(dāng)a6a5a4a3=1000，則碼組A就等于G的第一行；當(dāng)a6a5a4a3 =0100，則碼組A等于G的第二行，等等。由于G是k行n列矩陣，因此，如能找到k個已知碼組，就能構(gòu)成矩陣G。這k個已知碼組必須是線性不相關(guān)的，否則，給定的信息位與編出的碼組就不是一一對應(yīng)的。1101010111111000010000100001GGaaaaA345614循環(huán)碼具有封閉性，即碼中任意兩碼組按位模2和后

7、形成的新序列仍為一（許用）碼組，由于兩個相同的碼組相加得一個全0序列，所以循環(huán)碼一定包含全0碼組。(n,k)循環(huán)碼共有2k個不同碼組，從中找到一個碼組：其前面其前面的（的（k kl l）位都是）位都是0 0，而第，而第k k位及第位及第n n位為位為l l，即冪次大于，即冪次大于n-kn-k的的系數(shù)為系數(shù)為0 0，x xn-kn-k及及x x0 0的系數(shù)為的系數(shù)為l l，而其他系數(shù)為，而其他系數(shù)為O O或或1 1的碼多項式的碼多項式。用表示這一碼多項式，即1000)(1110 xaxaxxgknknkn碼全101000121aaakn 15第k位及第n位必須為“1”，是因為：若第n位不為1，該

8、碼組右移后將成為前k位都是0，而后（n-k）位不都為0，這是不可能的（按全0是一碼組的要求，信息位全為0，則監(jiān)督位也必定全為0），所以，第n位必定是“1”。同理，也可證明，第k位也必須是“l(fā)”。稱g(x)為生成多項式。由g(x)可得到生成矩陣G(x) )()()()()(21xgxxgxgxxgxxGkk16在前面介紹的(7,3)循環(huán)碼中，n-k=4，因此，表中唯一的一個4次碼多項式代表的碼組是第2組001011，相對應(yīng)的碼多項式（即生成多項式）為：1)(24xxxxg1000000000)()()()(2423523462xxxxxxxxxxxxgxxgxgxxG11101000111010

9、0011101G17G它不符合IkQ形式，所以此生成矩陣不是典型的。不過G可通過線性變換成為典型的生成矩陣，如將G矩陣中第一行與第三行相加（101ll000010111=1001011）后取代第一行，此時便成為典型的生成矩陣。111010001110101101001G18循環(huán)碼的許用碼組可表示為：)()()()()(2456456xgxxgxgxaaaxGaaaxT)()(4526xgaxaxa由此可見：任一循環(huán)碼多項式都是g(x)的倍式，即都可被g(x)整除，而且任一次數(shù)不大于(k-1)的多項式乘g(x)都是碼多項式。195、如何尋找(n,k)循環(huán)碼的生成多項式任一循環(huán)碼多項式T(x)都是

10、g(x)的倍式。這樣，循環(huán)碼組也可寫成：循環(huán)碼的生成多項式也是一個碼組，即有：T(x)為一(n-k)次多項式，則xkT(x)為一n次多項式。)()()(xgxhxT1)()(1)(nnkxxTxQxxTx)()(xgxT1)(xQ20碼多項式必定是(xn+1)的一個因式。循環(huán)碼的生成多項式g(x)應(yīng)該是(xn+1)的一個（n-k）次因子。)() 1()(xTxxTn)()(1xhxxgxkn21例如：例如： (x7+1)可以分解為： x7+1=(x+1)(x3+x2+1)(x3+x+1)為了求出（7,3）循環(huán)碼的生成多項式g(x)，就要從上式中找到一個n-k=4次的因式。從上式不難看出，這樣的

11、因式有兩個，即：1) 1)(1(2423xxxxxx1) 1)(1(2343xxxxxx22二、循環(huán)碼的編碼方法編碼的任務(wù)是在已知信息位的條件下求得循環(huán)碼的碼組，而我們要求得到的是系統(tǒng)碼，即碼組前k位為信息位，后n-k位是監(jiān)督位。設(shè)信息位的碼多項式用(n,k)循環(huán)碼的碼多項式的最高冪次為n-1次，而信息位是在它的最前面k位，因此信息位在循環(huán)碼的碼多項式中應(yīng)表現(xiàn)為 xn-km(x)多項式（最高冪次為n-1）。顯然它從冪次xn-k-1起至x0的(n-k)位的系數(shù)都為0。012211)(mxmxmxmxmkkkk knknnknkknxmxmxmxmxmx 0112211)(23其中q(x)為冪次小

12、于k的商多項式，而r(x)為冪次小于n-k的余式。上式表明，多項式xn-km(x)為g(x)的倍式。xn-km(x)必定是由g(x)生成的循環(huán)碼中的碼字，而r(x)即為該碼字的監(jiān)督碼元所對應(yīng)的多項式。)()()()()(xgxrxqxgxmxkn)()()()(xgxqxrxmxkn241、循環(huán)碼的編碼規(guī)則(1)根據(jù)給定的(n,k)值選定生成多項式g(x)，即從(xn+1)的因子中選取一個(n-k)次多項式作為g(x)；(2)用xn-k乘m(x)。這一運算的物理意義是把信息位后附加上(n-k)個“0”。例如，信息位為110，它相當(dāng)于m(x)=x2 + x，當(dāng)n-k=7-3=4時， xn-km(

13、x)= x4(x2 + x )= x6 + x5，它相當(dāng)于1100000。（3）用g(x)除xn-km(x)，得到商q(x)和余式r(x)，即：)()()()()(xgxrxqxgxmxkn25例如，如選用 作為生成多項式，則1)(24xxxxg1)()(2456xxxxxxgxmxkn101111011111011111000001112422xxxxxx26(4)編出的碼組T(x)為本例中， 這就是表中的第7碼組。可見，這樣編出的循環(huán)碼就是系統(tǒng)碼了。)()()(xrxmxxTkn11001011011100000)(xA27由此可得到以多項式表示的系統(tǒng)循環(huán)碼的生成矩陣為其中rn-i是g(x

14、)除xn-i所得的余式，由該式中多項式的系數(shù)就可得到碼的系統(tǒng)形式的生成矩陣G和H矩陣。 )()()()(2211xrxxrxxrxxGknknnnnn282、多項式除法電路多項式除法電路由r級線性移位寄存器組成。包括r個模2加法器、最多r+1個模2常數(shù)乘法器和r級移位寄存器。給定兩個多項式m(x)和g(x)。則多項式除法電路如圖所示012211)(mxmxmxmxmkkkk 0111)(gxgxgxgxgrrrr 1g02g13g2rgr-1.商輸出輸入m(x)gr29多項式除法電路舉例356)(xxxxm1)(3xxxg123商輸出輸入0 0 01011實際電路30除法過程節(jié)拍輸入序列寄存器

15、內(nèi)容輸出000010110001000101100020001011003000101104000011150011116010117100111113323356xxxxxxxxxx3113 xx3560 xxx123xxx3460 xxx45xx 2350 xxx234xxxxxx240 xx03103xx1第4 次 移位后的反饋第4 次 移位后的寄存器內(nèi)容第5 次 移位后的反饋第6 次 移位后的反饋第6 次 移位后的寄存器內(nèi)容第7 次 移位后的反饋第7 次 移位后的寄存器內(nèi)容第5 次 移位后的寄存器內(nèi)容323、循環(huán)碼編碼的硬件實現(xiàn)方法一：使用上述的除法電路例如：(7,3)循環(huán)碼+D0+D

16、1+數(shù)據(jù)輸入1D2D3xx2x4S數(shù)據(jù)輸出1)(24xxxxg33(7,3)循環(huán)碼共需要移位 n=7 次。從信息碼到達(dá)輸入端至輸出端產(chǎn)生余數(shù)，其間有 r=n-k=4 個單位時間遲延。先編碼后發(fā)送（不能同時進行）。 輸入 移位寄存器 移位次數(shù) m D0 D1 D2 D3 i 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 2 0 0 1 1 0 3 0 0 0 1 1 4 0 1 1 1 1 5 0 1 0 0 1 6 0 1 0 1 0 734方法二、：改進型電路（ 發(fā)送信息與編碼同時進行進行。）35對于(n,k)循環(huán)碼，移位k次后便得到余數(shù)。提前了 r=n-k 個單位時間

17、。364、編碼的軟件實現(xiàn)（1）方法一（對應(yīng)硬件電路一） n位信息碼元后面補（n-k）個0g(x)對應(yīng)的（n-k+1）位碼元寄存器1寄存器237（高位）余數(shù)（低位）g(x)對應(yīng)的碼元寄存器1寄存器2mi信息碼元異或（）方法二（對應(yīng)硬件電路二） 38三、循環(huán)碼的解碼方法接收端解碼的要求有兩種：檢錯和糾錯。(1)檢錯譯碼達(dá)到檢錯目的解碼原理十分簡單：利用碼組多項式T(x)是g(x)的倍式的編碼原理進行解碼。編碼器輸出：接收碼多項式： E(x)為差錯多項式（對應(yīng)于錯碼矩陣E）。)()()(xrxmxxTkn)()()(xExTxR39可見：當(dāng)接收到的碼組沒有差錯（即 E(x)=0 ）時， R(x)=T

18、(x) ，R(x)能被g(x)整除。)()()(xgxqxT)()()()()()()()()()(xgxExqxgxExgxgxqxgxR從循環(huán)碼的編碼原理可知，T(x)是g(x)的倍式，即：)()()()()(xgxExTxgxR40qE(x)是商，rE(x)是余式。因此：接收端可以根據(jù)余式rE(x)是否為零來判斷接收碼組是否有錯。檢錯譯碼步驟：計算R(x)的余式r(x)（伴隨式S(x)）；根據(jù)r(x)是否為零來判斷接收碼組R(x)是否有錯。)()()()()(xgxrxqxgxREE當(dāng)接收到的碼組出現(xiàn)差錯（即 E(x) 0），且差錯的數(shù)目在碼的檢驗范圍之內(nèi)時，將有：41循環(huán)碼檢錯解碼的硬

19、件實現(xiàn)主要部分是一個除法器和緩沖移位寄存器。42解碼電路的除法器與發(fā)送編碼器的電路相同。43(2) 糾錯譯碼在接收端為糾錯而采用的解碼方法要比檢錯復(fù)雜得多。為了能夠糾錯，要求每個可糾正的錯誤圖樣必須與一個特定的余式（伴隨式）有一一對應(yīng)關(guān)系。糾錯譯碼步驟：計算R(x)的余式r(x)（伴隨式S(x)）；根據(jù)S(x)得到差錯多項式E(x)（錯誤圖樣）；計算 R(x) - E(x) = T(x)。糾錯譯碼設(shè)備的復(fù)雜程度主要取決于由伴隨式找到錯誤圖樣的識別電路或組合邏輯電路的復(fù)雜性。44)()()(xExTxR），（模），（模），（模)()()()()()()()(xgxExgxExTxgxRxS45（

20、7,4）循環(huán)漢明碼能糾正一個錯誤。設(shè)接收碼為 a6a5a4a3a2a1a01)(3xxxg 錯碼位置 錯誤圖樣E 伴隨式S a0 0000001 001 a1 0000010 010 a2 0000100 100 a3 0001000 011 a4 0010000 110 a5 0100000 111 a6 1000000 101 46定理： 若 則：譯碼時，只有知道一個代表圖樣的伴隨式，其他錯誤圖樣的伴隨式由此代表圖樣伴隨式在伴隨式計算電路中得到。代表伴隨式：是指第一位開頭為非0的錯誤圖樣對應(yīng)的伴隨式。），（模)()()(xgxRxS），（模)()()(xgxRxxSii），（模)()()(

21、xgxSxxSii），（模)()()()(xgxSxaxSa），（模)()()()(xgxRxaxSa47(7,4)循環(huán)漢明碼譯碼電路譯碼過程共需要 2n=14 個節(jié)拍。糾錯信號“1”也反饋到伴隨式計算電路輸入端，對伴隨式進行修正，以消去該錯誤對伴隨式的影響（此后伴隨式為0）。484950有錯碼的接收碼組也有可能被整除，這時的錯碼就不能檢出了，這種錯誤稱為不可檢錯誤。不可檢錯誤中的碼組錯碼數(shù)必定超過了這種編碼的檢錯能力。)()()()()()()()()()(xgxExqxgxExgxgxqxgxR51四、縮短循環(huán)碼已知循環(huán)碼的生成多項式應(yīng)該是（xn+1）的一個（n-k）次因子，但有時（xn+1）多項式的因子個數(shù)比較少，因此在給定長度n下碼的數(shù)目也較少。為了增加（n,k）碼的數(shù)目，以便選擇，循環(huán)碼經(jīng)常采用縮短形式。在（n,k）循環(huán)碼的2k個碼組集合中，