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

1、1第五節(jié) 循環(huán)碼循環(huán)碼是線性分組碼中一類重要的碼，它是以現(xiàn)代代數(shù)理論作為基礎(chǔ)建立起來的。循環(huán)碼的編碼和譯碼設(shè)備都不太復(fù)雜，且檢錯(cuò)糾錯(cuò)的能力較強(qiáng)，目前在理論和實(shí)踐上都有較大的發(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)督位碼組編號(hào)6a5a4a3a2a1a0a100000002001011130101110401110015100101161011100711001018111

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

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

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

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

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

7、形成的新序列仍為一（許用）碼組，由于兩個(gè)相同的碼組相加得一個(gè)全0序列，所以循環(huán)碼一定包含全0碼組。(n,k)循環(huán)碼共有2k個(gè)不同碼組，從中找到一個(gè)碼組：其前面其前面的（的（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的碼多項(xiàng)式的碼多項(xiàng)式。用表示這一碼多項(xiàng)式，即1000)(1110 xaxaxxgknknkn碼全101000121aaakn 15第k位及第n位必須為“1”，是因?yàn)椋喝舻趎位不為1，該

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

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

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

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

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

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

14、)除xn-i所得的余式，由該式中多項(xiàng)式的系數(shù)就可得到碼的系統(tǒng)形式的生成矩陣G和H矩陣。 )()()()(2211xrxxrxxrxxGknknnnnn282、多項(xiàng)式除法電路多項(xiàng)式除法電路由r級(jí)線性移位寄存器組成。包括r個(gè)模2加法器、最多r+1個(gè)模2常數(shù)乘法器和r級(jí)移位寄存器。給定兩個(gè)多項(xiàng)式m(x)和g(x)。則多項(xiàng)式除法電路如圖所示012211)(mxmxmxmxmkkkk 0111)(gxgxgxgxgrrrr 1g02g13g2rgr-1.商輸出輸入m(x)gr29多項(xiàng)式除法電路舉例356)(xxxxm1)(3xxxg123商輸出輸入0 0 01011實(shí)際電路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)碼編碼的硬件實(shí)現(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 個(gè)單位時(shí)間遲延。先編碼后發(fā)送（不能同時(shí)進(jìn)行）。 輸入 移位寄存器 移位次數(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方法二、：改進(jìn)型電路（ 發(fā)送信息與編碼同時(shí)進(jìn)行進(jìn)行。）35對(duì)于(n,k)循環(huán)碼，移位k次后便得到余數(shù)。提前了 r=n-k 個(gè)單位時(shí)間

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

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

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

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

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