說明教案成果

華僑大學通信工程 ： : 上次課循環(huán)碼C

g1x0C(x)cxn1 C(i)(x)xiC(x)g1x0

g(x)

xnk

h(x)hkxk

xn1g(x)h(x)

xk1g(x) xk2g(x) G(x)

H(x)

h*(x) n

xnk2h*(x)C(x)m(x)x r(x)

xnk1h*(x)r(x)m(x)xnkmodg(x)InInk

g(x)

Hc2xns(x)R(x)modg(x) SRHTc2xn4.3.7常用的循循環(huán)冗在數(shù)據(jù)通信中，信息都是先劃分成小塊再組裝成幀后組包) 的，一般都留有、、或位用作差錯校驗。k位kn,ki)縮短循環(huán)碼的特點。只要以一個選定的i,k)循環(huán)碼為基礎，改變i的值得到任何信息這種應用下的縮短循環(huán)碼稱為循環(huán)冗 (CRC3循環(huán)冗 是系統(tǒng)的縮短循環(huán)碼，碼的結構如圖所示(n-i)(k-i)圖中，碼字用碼多項式C(x)表示，r(x)是xnkm(x除g(x)后的余式，g(x)為n-k次多項式，它們之間滿足C(x)xnkm(x)r(x) 如果傳輸過程無差錯，則接收碼字R(x)應等于發(fā)送碼C(x)，這時R(x)能被g(x)整除；如果不能整除，則說明輸過程中出現(xiàn)了誤

C(x)+e(x)=C(x)+eg g g 4.3.7]某g(x)x4x1CxRx解：本題信息碼字多項式m(x

1，k=6，從生多項式g(x)的階數(shù)得校驗位數(shù)r等于4，因此n=10g1x0xnkm(x)g(x)g1x0r(x)xnkm(x)modx4(x5x41)modx3

g(x)

xnk 于是，發(fā)送碼字多項式C(xxnkm(xr(xx9x8x4x3對應的發(fā)送碼字為 在接收端，Rxgx不為“0”，則說明一定有差錯 例4.3.8假設m(x)x6x4x31，即信息碼字為 g(x)x4x31，求 解由題得x4m(x)x10x8x7用g(x)去除 ，有是冗余r(x)所以，發(fā)送為6如果本例的發(fā)送碼字(10110011010)經(jīng)傳輸后受噪聲在接收端變成為(10110011100)。求余式求得余式不為零，表示接有錯誤再是C(x)，而C(x)+e(x)。若e(x)g則這種差錯就能檢測出e(x)g那么由于接收到的碼字多項式仍然可被g(x)整除，錯誤檢測不出來，也即發(fā)生了漏檢 理論上可以證明，循環(huán)冗 的檢錯能力如下 長度n-k的突發(fā)錯誤④n-k+1位的突發(fā)性錯誤，查出概率為1-2-(r-⑤對于多于n-k+1位的突發(fā)性錯誤，查出概率為1-2-r8CRC-12，其生成

g(x)x12x11x3x2xCRC-16，其生成多項

g(x)

x2CRC-CCITT(ITU)，其生成多項式g(xCRC-32，其生成多項

x15x5g(x)

x26x23x22x16x12x11

x8x7x5x4x2x1余 的編譯碼程通用采硬件實為除法運算易于用移位寄器和2加法來實，可以度。著集電路藝的展環(huán)冗余碼的產(chǎn)生校均集電產(chǎn)，送能自動成速大大高。9BCHBCHBCH等一系列優(yōu)點。本原BCH碼與非本原BCH二進制本原BCH碼具有下n2mnk 2t式中m(3)和糾錯能力t(<2m-1)是任意的正整BCH碼的碼長為n

1n

1的因通常稱前者為本原BCH碼，稱后者為非本原BCH碼BCHBCH這里我們重點討論BCH碼的實際應用，即利用已知BCH碼表格，構造出對應生成多項式的BCH碼表4.4.1(P109)給出的是一些本原BCH碼的有關參[例4.3.9m=4n24115的二元BCH解：①若t1，則查表可得g(x)x4x故可構成一個(15,11)BCH碼，可糾正單個錯誤。顯然，糾單個錯誤的本原BCH碼就是前面所述的循環(huán)漢明碼t2，則查表可得其生成多g(x)(x4x1)(x4x3x2x1)x8x7x6x41故可構成一個(15,7)BCH碼，具有糾正兩個錯誤的能③若t3，則查表可得其生成多項式g(x)(x4x1)(x4x3x2x1)(x2xx10x8x5x4x2x可構成一個(15,)BCHBCHCRS的情況，得到了RS（Reed-Solomon）碼。(n,kRS碼中，輸入信號分成k*m比特一組，每組包括k個符號，每個符號由m比特組成，而不是前面介紹的二元BCH碼中的一個比一個可糾正t個錯誤的RS碼有如下參數(shù)碼長：n2m信息位：

位符號位符號

(2mk

監(jiān)督位：nk2t位符m(nk)2mt比特最小碼距n2t1位符號 或mdminm(2t1)比特S有：總長度為總長度為

b1(t1)m1b2(t3)m

比特的單個突發(fā)錯比特的兩個突發(fā)錯誤總長度為it2i1)m2i1比特的i個突發(fā)錯20世紀70 始，RS碼在 器、器、DVB(數(shù)字電視廣播標準)、磁 、光纖信中得到了廣泛的應]m=4的RS碼的參解：已知t=3，m=4，求碼距dmin2t1監(jiān)督位：nk2t

個符號，或24信息位knnk156

個符號，或36比特碼長

n

個符號，或60比特所以該碼應為：(1,)S60,36RS碼的編碼過程與BCH碼一樣，也是除以同樣可以用帶反饋的移位寄存器是硬算法，從而造成了一定程度的增益損失。 (J.M.Wozencraft)提出了序列的譯 (J.L.Massey)提出效果稍差但卷積碼是組碼，與分組碼的主要差別是它是一種有的編碼，即在任意時段，編的nk(L。

Elias,1923-n,N=L1和k可以同的條件下，（較?。?。一、卷積 卷積碼編碼的原理圖如圖4.4.1所示 卷積碼具有以下特點下面，用具體實例說明各種描述方法例4.4.1設二元卷積碼的 結構如下圖所示，如果輸信息流為m(10111)，求 的輸出碼字序列C1 C2 端)、L=3(即三級移位寄存器)所組成的有限狀態(tài)的 系。離散卷若輸入信息序則對應輸出為兩個碼字C2C2

(c1,c1 (c2,c2 其相應編碼由輸入信息序列m和編 m m式中“*”表示卷積運算，G1,G2為編 是當輸入信息為[1000….]時，所觀察到的兩個輸出序列(2,1,3)卷積碼 有L=3級寄存器，其沖激響應至可持續(xù)到L+1=4位，由圖4.4.4可寫出沖激響應G1(1011),G2經(jīng) 后，兩個輸出序列合并為一個輸出碼字序列C(c1,c2,c1,c2 i當輸入信息序列為m(10111)，利用離散卷積運算來進行具體的計算。第一路 c1的各位碼元值可由式i（P115）計算，為：C1(10111)(1011) 其具體的運算過程10111011011101110111000000m

G1(1011),G2所C1 同理可計算C2 所以，最后(2,1,3)卷積碼 輸出的碼字序列為C(11010001010100生成矩陣上述沖激響應G1G2又稱為生成序列，若將該生成序列G1進行交織，并構成如下生成矩陣(L=3時g1g g1g g1g g1g G

g g g g g g g g g1g g1g g1g g1g2 3上述編碼方程可改寫成如下矩陣C矩陣G稱為卷積碼的生成矩陣)］顯然當輸入信息序列為一無限序列時［即m)］生成矩陣則為一個半無限m

g1g g1g g1g g1g G

g g g g g g g g g1g g1g g1g g1g2

3碼多項G110111x2x3G211111xx2x3m10111)1x2x3x4則卷積碼可以用下列碼多項式形C1mG1(1x2x3x4)(1x2x3)1x2x3x4x2x4x5x6x3x5x61x7 C2mG2(1x2x3x4)(1xx2x31xx3x4x5 因而，其輸出的碼字序列C(11010001010100例4.4.3設二元(2,1,2)卷積碼的編 )，求其輸出碼字序列。則由圖4.4.6G1(111)1xx2,G2(101)1如果輸入信息流為 )，則其對應的多項式表示式為m1x2x3因此輸出的碼序列為C1mG1(1x2x3x4)(1xx21x2x22x33x42x51xx4x6 C2mG2(1x2x3x4)(1x212x2x32x4x5 即：C111000011001除了上述三種比較形象的狀態(tài)圖、樹圖和格圖來描述下面，以上述二元（2,1,2）卷積碼為例討論卷積碼狀態(tài)由圖4.4.6可知，移位寄存器總的可能狀態(tài)數(shù)為2 22a00,b10,c01,d11來表示表元（1設輸入信息序列其狀態(tài)圖可以按以下步驟輸輸 輸輸(00)(11)(10)(00)(01)(10)(01)(11)狀 輸狀輸輸輸狀樹圖如果要展示出編的輸入、輸出所有可能的情況，則可采用樹圖描述，它是將上述編的狀態(tài)圖按時間展開得到狀C(11100001100111 ：：狀00”作為樹根，對每個時刻可l分為兩個分支：當1=0則向上，即“0”1=1則向下，即“1”l1l2下兩個分支，并推進到相應的二級節(jié)點(l’=2)，依此類推，a,b,,d表示編對于特定輸入信息))而經(jīng)過的狀態(tài)為(a)bcbddcaa在輸入上述特定信息序列時，樹圖中的路徑如粗線所示結構重復性太多 (2,1, 圖中實線表示輸入為“0入為“1”82發(fā)所延伸的樹結構完全—任給定一個輸入信息序列格圖就存一條定如 其輸出編碼為即為圖中粗黑線所表示的卷積碼的Trellis若編碼信息序列 則編碼過程即為在Trellis圖上尋找一條路得到C111000011001

格圖是研究維特比譯碼算法的重二、卷積碼1967(tb。。維特比算的本依在同刻l=L+1,L+2,…,L+l，對格中相列的每點對應編 中該態(tài)，按最大然準比較有以為終點的路徑，只保留一條具有大似值或等于最似值的路徑保留的路徑稱為幸存徑，而其他徑堵，用。保留下幸l=L+l下的一條路徑就是所要求的最大似然譯碼的解。由此可見，維特比算法的主要優(yōu)使得每次局部都等效于全局最優(yōu)的一部分，它滿足②局部及例4.4.4對最簡單的(2,1,2）卷積碼，設發(fā)送的信息序m

，經(jīng)過編碼后輸出的碼組(字)為C(111000011001接收到的信號序列為：R(101001011001試用維特比算法譯 L=2，對給定的輸入信息序列l(wèi)=5，則l’=l+L+1=8，在圖中用l’=0,1,…,7來表示。BS(4.4.6和(4.4.4.4.10和圖 R(101001011001

aab1011序號2|輸入碼距aab002002cbd11111daab0000300003cbd001140011acb11101110cdd110111015序號4|輸入daab111011111011bcd1110004111000cab11010141101014dcd001