差錯(cuò)控制編碼第三次課

循環(huán)碼循環(huán)碼除具有線性碼的一般性質(zhì)外,還具有循環(huán)性

即任一碼組循環(huán)一位以后，仍為該循環(huán)碼中的一個(gè)許用碼組。一、循環(huán)碼的特點(diǎn)線性分組碼7章差錯(cuò)控制編碼循環(huán)碼舉例——(7,3)循環(huán)碼碼組信息位監(jiān)督位碼組信息位監(jiān)督位編號(hào)a6a5a4a3a2a1a0編號(hào)a6a5a4a3a2a1a000000000410010111001011151011100201011106110010130111001711100107章差錯(cuò)控制編碼例如A=0010111(1)A(x)=0x6+0x5+1x4+0x3+1x2+1x1+1x0=x4+x2+x+1

xA(x)=x5+x3+x2+x

A=0101110(2)2、碼多項(xiàng)式——碼組的多項(xiàng)式表示7章差錯(cuò)控制編碼二、循環(huán)碼的運(yùn)算1、碼多項(xiàng)式的按模運(yùn)算若一個(gè)整數(shù)m,若可以表示為則：m≡

p(模n)7章差錯(cuò)控制編碼多項(xiàng)式F(x)被n次多項(xiàng)式N(x)除，得到商式q(x)和一個(gè)次數(shù)小于n的余式R(x)，即碼多項(xiàng)式系數(shù)仍按模2運(yùn)算，即只取值0和1則寫(xiě)為F(x)≡

R(x)

(模N(x))7章差錯(cuò)控制編碼7章差錯(cuò)控制編碼例如7章差錯(cuò)控制編碼在循環(huán)碼中，若T(x)是一個(gè)長(zhǎng)為n的許用碼組，則在按模運(yùn)算下，亦是一個(gè)許用碼組。則T’（X）也是該編碼碼組中的一個(gè)許用碼組7章差錯(cuò)控制編碼2．循環(huán)碼的生成矩陣G

若能找到k個(gè)線性無(wú)關(guān)的碼組,就能構(gòu)成矩陣G。在循環(huán)碼中，一個(gè)(n，k)碼有2k個(gè)不同碼組，若用g(x)表示其中前(k-1)位皆為0的碼組，即

g(x)=0…1x…xk位n-k位則g(x)、xg(x)，x2g(x)，…，xk-1g(x)都是碼組，而且這k個(gè)碼組是線性無(wú)關(guān)的。因此可以用來(lái)構(gòu)成循環(huán)碼的生成矩陣G。

7章差錯(cuò)控制編碼例表9—6的循環(huán)碼,唯一的一個(gè)(n-k)次碼多項(xiàng)式代表的碼組是0010111，相對(duì)應(yīng)的碼多項(xiàng)式為一旦確定了g(x)，則整個(gè)(n．k)循環(huán)碼就被確定了。因此,循環(huán)碼的生成矩陣G可以寫(xiě)成7章差錯(cuò)控制編碼這個(gè)生成矩陣不是系統(tǒng)碼的生成矩陣，可以通過(guò)行變換，變換成系統(tǒng)碼的生成矩陣。

g(x)＝x4+x2+x+1將此g(x)代入上式，得到7章差錯(cuò)控制編碼g(x)的性質(zhì)：g(x)必須是一個(gè)常數(shù)項(xiàng)a0=1；次數(shù)為(n-k)次；唯一的(n-k)次多項(xiàng)式；我們稱這唯一的g(x)為碼的生成多項(xiàng)式。g(x)是xn+1的因式（見(jiàn)后面分析）。7章差錯(cuò)控制編碼說(shuō)明g(x)是xn+1的因式。因?yàn)槿未a多項(xiàng)式T(x)都是g(x)的倍式，所以有

T(x)=h(x)g(x)g(x)本身也是一個(gè)碼組，其次數(shù)為n-k次。把它循環(huán)移位k次仍為一個(gè)碼組。所以xkg(x)是n次多項(xiàng)式，在模xn+1運(yùn)算下，所以即7章差錯(cuò)控制編碼因?yàn)閤kg(x)是n次的，所以Q(x)=1。所以所以即g(x)是xn+1的因式。這樣就可以通過(guò)對(duì)xn+1的因式分解得到g(x).7章差錯(cuò)控制編碼最高次冪n-kg(x)是一個(gè)常數(shù)項(xiàng)為1最多k-1個(gè)連0是的一個(gè)因式；循環(huán)碼的生成多項(xiàng)式生成多項(xiàng)式7章差錯(cuò)控制編碼任意一碼組多項(xiàng)式可表示為：一個(gè)k位的信息碼組Ｄ＝［dk-1,dk-2,…….d0]信息碼多項(xiàng)式:T(x)=d(x)g(x)循環(huán)碼7章差錯(cuò)控制編碼d(x)代入T(X)得：不大于n-1次的多項(xiàng)式7章差錯(cuò)控制編碼假如輸入信息碼元mk-1mk-2…m0則例：求（7，4）循環(huán)碼的生成多項(xiàng)式g(x),當(dāng)信息碼組D=[1010]時(shí)，求輸出碼組7章差錯(cuò)控制編碼

若能找到k個(gè)線性無(wú)關(guān)的碼組,就能構(gòu)成矩陣G。

g(x)、xg(x)，x2g(x)，…，xk-1g(x)都是許用碼組，而且這k個(gè)碼組是線性無(wú)關(guān)的。因此可以用來(lái)構(gòu)成循環(huán)碼的生成矩陣G。循環(huán)碼的生成矩陣G7章差錯(cuò)控制編碼例表9—6的循環(huán)碼,唯一的一個(gè)(n-k)次碼多項(xiàng)式代表的碼組是0010111，相對(duì)應(yīng)的碼多項(xiàng)式為因此,循環(huán)碼的生成矩陣G可以寫(xiě)成7章差錯(cuò)控制編碼這個(gè)生成矩陣不是系統(tǒng)碼的生成矩陣，可以通過(guò)行變換，變換成系統(tǒng)碼的生成矩陣。

g(x)＝x4+x2+x+1將此g(x)代入上式，得到7章差錯(cuò)控制編碼循環(huán)碼的編碼系統(tǒng)碼編碼：

信息碼后附加n-k個(gè)0

非系統(tǒng)碼編碼：T(x)=m(x)g(x)除以g(x)，得余式r(x)；237章差錯(cuò)控制編碼監(jiān)督位信息位例

(7,3)循環(huán)碼m(x)=x2+x,g(x)=x4+x2+

x+1r(x)7章差錯(cuò)控制編碼a+b+cd+輸入m輸出feS（7，3）碼編碼器四、硬件實(shí)現(xiàn)——固定除式的多項(xiàng)式除法移位寄存器的級(jí)數(shù)等于生成多項(xiàng)式的次數(shù)是否有反饋由g(x)中的的非零系數(shù)對(duì)應(yīng)，g(x)中有此項(xiàng)，有反饋。7章差錯(cuò)控制編碼7章差錯(cuò)控制編碼7章差錯(cuò)控制編碼信息碼元輸入移存器反饋輸出mabcddf0000001111011110011101010100010100000101100001000000011校驗(yàn)碼元a+b+cd+輸入m輸出feS7章差錯(cuò)控制編碼2．循環(huán)碼的解碼方法——檢錯(cuò)若碼組在傳輸中發(fā)生錯(cuò)誤，則R(x)除以g(x)時(shí)可能有余項(xiàng)—碼多項(xiàng)式T(x)應(yīng)能被生成多項(xiàng)式g(x)整除若接收碼組與發(fā)送碼組相同，即R(x)=T(x)，則接收碼組R(x)必定能被g(x)整除由接收多項(xiàng)式除以生成多項(xiàng)式得到余式r(x)r(x)=0接收碼組無(wú)錯(cuò)r(x)≠0有錯(cuò)7章差錯(cuò)控制編碼檢錯(cuò)電路圖接收碼組緩沖移位寄存器除法電路反相與門(mén)重發(fā)指令輸出信息碼余式等于1時(shí)輸出1余式等于0時(shí)輸出07章差錯(cuò)控制編碼

(1)根據(jù)