九章基本信道編碼技術(shù)說明

1、現(xiàn)代數(shù)字通信的兩個基本理1、現(xiàn)代數(shù)字通信的兩個基本理論基礎(chǔ)：信息論和糾錯編碼；2、通信中信源編碼，信道編碼和數(shù)據(jù)轉(zhuǎn)換編碼常常同時使用；本章介紹信道編碼的基本的概念、也介紹最為常用的糾錯編碼，即分組碼，循環(huán)碼和卷積信道數(shù)據(jù)信源信數(shù)據(jù)信道信源分組糾用于糾分組信道編碼器的輸分組糾用于糾分組信道編碼器的輸入是一列長度為k的字符序列m，其中字符是信源字符表M中取值miM,m(m0,m1,,mk1i0,1,2,,k信道編碼器把輸入消息序列映射成由n個信道字符組成的碼字ciM,c(c0,c1,c2,,cn1i0,2,,nnk－冗余位長度或稱校驗碼Rnm0,m1,,mk 分組編碼二元對T表示碼字中符號錯誤數(shù)目P(Tt)二元對T表示碼字中符號錯誤數(shù)目P(Tt)Ctpt(1ntP{Tt}1P{TP(Tt)Cpnjj,njE{(TT)2}np(1t 1- P 1 1-信道容 C1H(p)1plogp(1p)log(19.1.3檢錯是9.1.3檢錯是指當(dāng)碼字在信道上傳輸發(fā)生錯誤時，譯碼器能發(fā)現(xiàn)傳輸有誤；糾錯則是指譯碼器能自動糾正這個錯誤檢測錯[例9.1.1]3次重復(fù)編碼，（n3,k1,r2“0”→“000”，“1”→“11糾正糾正錯[例9.1.2][例9.1.2]r3的重復(fù)碼“0”→“000糾正檢測“1”→“111自動重發(fā)請求（ARQ）在半雙工或雙自動重發(fā)請求（ARQ）在半雙工或雙工情況下，收端發(fā)現(xiàn)有誤時，可以通過反向信道對方重發(fā)一次，直到正確接收到為止。這種通過檢測錯誤，發(fā)而且自動請求重發(fā)的通信方式稱為ARQ1、等待式p，要成功傳送碼字，發(fā)方平均要發(fā)碼字碼字出錯概1N1NN步3、選擇性重發(fā)最大似然譯碼和最小Hamming距離譯c(c0,c最大似然譯碼和最小Hamming距離譯c(c0,c1,,cn1erc(e1,e2,,en1發(fā)送碼字接收序列二元錯誤矢量erci0,1,2,,niiierc(e0,e1,,en10)11)二元對稱信mcre信道信道最大后驗概率譯碼?argmaxP(ci|ci最大后驗概率譯碼?argmaxP(ci|ci最大似然譯碼準(zhǔn)則：cargmaxP(r|ci先等ci|r)P(ci)P(r|ci最大后驗概率譯碼＝最大irc的Hamming距離為d指這兩個序列有d位不同dH(rci)序列r和ci兩個對于差錯概率為p的二元對稱信pP(r|c)pd(1logP(r|c)nlog(1p)dp1cargmaxP(r|cicargmindH(r,ci最小Hamming距離與檢錯、糾錯能力最小Hamming距離與檢錯、糾錯能力把二個長度為n的序列uv之間的HammingdH(uv)定義和v之間對應(yīng)分量取不同值的u定義9.1.1長度為n的分組碼C的最小Hamming距離dd dH(ci,cjci,cjC,i分組碼的三個最重碼字長度n，信息位數(shù)目k，最小Hamming距離對于一個k）分組碼來說，最小Hamming距d與糾錯、檢力有如下關(guān)定理9.1.1任定理9.1.1任何一個（n,k）分組碼，若要在任何碼能檢測e個隨機(jī)錯誤，則要求最小Hamming距離d≥e+1能糾正t個隨機(jī)錯誤，則要求d≥2t+1c.能糾正t個隨機(jī)錯誤，同時檢測出(≥t)個錯誤，則要求d≥t+e+1[證明§9.2線性分組編碼的生成矩陣和校驗矩陣線性分組碼的基本特§9.2線性分組編碼的生成矩陣和校驗矩陣線性分組碼的基本特征是它具有“線性”的結(jié)即兩個碼字合仍是碼字，對于二元碼，即兩個碼字之和仍為碼字?？梢岳脭?shù)學(xué)工具線性空間來研究線性分組碼，使得編碼器和譯碼器的實現(xiàn)更為簡單。定義9.2.1一個碼率為Rkn的線性分組碼（n,k），k比特的消矢量m(m0m1mk1線性地n比特c(c0c1,cn1{0,1j0,1,n1mi{01i0,1,k線性映射c1cm1212mc22全體碼字集合稱為碼字空間C，它n維空間中的一個kg0(g00,g01,,g0,n1g0(g00,g01,,g0,n1g1(g10,g11,,g1,n1gk1(gk10,gk11,,gk1,n1k個線性獨立的二元n消息cm0g0m1mk1m所m(m0,m1,,mk1g矩G1 k1[例9.2.1]G生成的（6,3）線 0G 1 cm0g0m1g1m2g2,mi0,1,i1,2,m(01 cg1g2成矩列交GG成矩列交GG系統(tǒng)生成矩陣生成系統(tǒng)線Ikkr=n-k校驗k系統(tǒng)線性碼的校驗H]mGHTcrcHT[例例9.2.1中的（6.3）線性碼的校H[例例9.2.1中的（6.3）線性碼的校Hm01m2cHTcmm29.2.2u(u0,u19.2.2u(u0,u1,,un1v(vpvr,vn1)內(nèi)積和uvuvu1v1u和vn維空間中與一個k維子空間正交的所有矢量的全體構(gòu)成一個n-維空間，它稱為的對偶空間，或稱的正交補，用C⊥定義9.2.2生成矩陣為G，校驗矩陣為H的（n,k）線性分組碼CC⊥是一個生成矩陣為H，校驗矩陣為G的n–k）線性分組線性分組碼的最小Hamming距離和最小Hamming定義9.2.3線性分組碼的最小Hamming距離和最小Hamming定義9.2.3一個n維矢量的Hamming重量wH(v)定義為該矢量中非量的個數(shù)，對于二元矢量也就是矢量中“1”分量的個c1,c2c1c2因dH(ci,cj)cicci,cjwH(cicj所cicci,cjminwHc線性分組碼的最小Hamming距離等于該碼中非零碼字的最[例由9.2.3中生成矩陣所生成的線性分組碼總共有8設(shè)cc0c1,cn1ccHcih為Hi設(shè)cc0c1,cn1ccHcih為HihhhhhHhhhhk1,n1kkkk012iw，則相w列的和為若碼字重量如果一個線性分組碼的最小Hamming距離為d，也就是說該最小Hamming重量為d，則它的校驗矩陣H中任意d–1線性線性分組碼c，從信道接收到的二元矢v發(fā)送的二元碼字矢，錯ev線性分組碼c，從信道接收到的二元矢v發(fā)送的二元碼字矢，錯evc(e0,e1,,en1最大似然譯碼法則要求把v譯成與之距離最近的碼字。完全譯碼器把接收到的二元矢量v譯成與它最近碼字c；限定距離t譯碼器，選與v最近的碼字c，dH(c,v)時，則譯器就譯成c；當(dāng)dH(cv)t時，譯碼器聲稱糾錯失敗一、標(biāo)準(zhǔn)陣cc0e2e1c1,e2c1c2e1c2e2c2k2e1k2ck2e c2 2e2e2c2二元 k）線性碼C，若二元 k）線性碼C，若是任意一個非碼字n維矢量，則稱的一個陪集，其中aCaccC}為稱為陪集意二個倍集或者不相交或者重合，所以標(biāo)準(zhǔn)陣列是線性碼的陪集分解v，若它落在標(biāo)準(zhǔn)陣列中的第j行，則可能的對于任何接收到的誤形式是該行中的所有矢量，最大似然譯碼準(zhǔn)則要求把與接收矢量近的碼字譯為發(fā)送碼字，所以相當(dāng)于在第j行中為錯誤形式，即把該行的首項作為錯誤對于限定矩離譯碼來說，不需要構(gòu)造出完整的標(biāo)準(zhǔn)陣列，只需重量不大于的陪集首項所對應(yīng)的陪集。若接收到的矢量沒有出現(xiàn)在這個不完整陣列表中，則說明這時發(fā)生了不可糾正的錯誤。[例一個具有4個碼字，能糾錯一位的（6，2）線性碼C={(000000),(010101),(101010),陪集首[例一個具有4個碼字，能糾錯一位的（6，2）線性碼C={(000000),(010101),(101010),陪集首項重量不大于1的不完全陣列如果一個線性碼的標(biāo)準(zhǔn)陣列中的陪集首項正好是所有重量不大元矢量，該線性碼稱為完備碼t的00000010101010111111000000101010101111110000101011101001111000010010001011111101001000111010001110110100000010111011011110000110100010101111 二、伴隨式接收矢量v所對應(yīng)的伴隨式s是一個二、伴隨式接收矢量v所對應(yīng)的伴隨式s是一個rnk維矢量svHT1、v相應(yīng)的伴隨s為零矢量的充要條件是v為一個碼字e0,0,1,0,,,1第c,2、第a第bseihihahbhc則i3、二個矢量出現(xiàn)在的同一陪集中的充要條件是他們具有相同的伴隨式所以伴隨式與陪集一一對應(yīng)s如果接收到矢量為v，首先計算出它的伴隨式，如，則表示s收到的是碼字，沒有錯。如果不為0，則根查出對應(yīng)的錯誤形譯碼錯誤概誤碼M1P{譯碼輸出c|ci被發(fā)送M1譯碼錯誤概誤碼M1P{譯碼輸出c|ci被發(fā)送M1錯誤形式陪集首項|}iMiP{錯誤形式陪集首項n1ipi(1p)i為重量為 的陪集首項數(shù)目誤比 k9.2.6二元Hamming定義9.2.4長度為n=2r–1（r≥2）的二元Hamming碼是一個9.2.6二元Hamming定義9.2.4長度為n=2r–1（r≥2）的二元Hamming碼是一個矢量組成[例對于系統(tǒng)（7.4）Hamming碼，它的校驗矩1011011110000100001000100011101GH011從一個已知線性分組碼來從一個已知線性分組碼來構(gòu)造一個新的線性分組碼縮短（cn–1HammingHr(2r–1,2r–1–r例（15,11,(2r–1,2r–2–r,4)例（15,10,(2r,2r–1–r,例（16,11,§9.3線性碼的糾錯能力是由給定n,§9.3線性碼的糾錯能力是由給定n,k條件下，最小距離d的上，下界限來表征的。下面3個定理給出關(guān)于最小距離d的上限。定理（Singleton限任何線性（n,k）碼的最小Hammingddnk定理9.3.2（Hamming限長度為n，能 個錯誤的二元分組碼所含有碼字?jǐn)?shù)MtM2nC定理（Plotkin限長度為n，碼字?jǐn)?shù)為M的分組碼，它的最小Hamming距離dd2(M定理（Varsharmov-Gilbert下限可以構(gòu)成定理（Varsharmov-Gilbert下限可以構(gòu)成一個最小距離為d的dk）線性分組碼，其中參數(shù)dnk j2j循環(huán)碼定義與碼字的多項v(v0,v1,,vn1循環(huán)碼定義與碼字的多項v(v0,v1,,vn1,v,v,,) 一個（n,k）線性碼定義，若它的每個碼字矢量的循環(huán)移位是該碼的碼字，則我們稱為循環(huán)碼[例一個由4個碼字構(gòu)成的，最小重量為3的（6，2）循環(huán)C{(000000),(010101),(101010),用多項式表示碼字矢v(x)vxv(v,v,,x) 012xv(x)v(1)(x)(xn因v(1)(x)xmod(xn9.4.2定理9.4.1循環(huán)碼C中次數(shù)最低的非零碼字多項式是唯一rxxrg9.4.2定理9.4.1循環(huán)碼C中次數(shù)最低的非零碼字多項式是唯一rxxrg(x)gx是碼C中一個次數(shù)最[證明]r01的非零碼字多項式。若不是唯一的，則必然存在另一個次數(shù)為的碼多項式 g'(x)g'0g'1xg'rxrxr由于是線性的，所g(x)g'(x)(g0g'0)(g1g'1)x(gr1g'r1)xr1這與假設(shè)g(x)是次數(shù)最低非零碼字多項式相矛rg(x)g0g1xgr1xr是（nk）循環(huán)碼C定理g01最低次數(shù)非零碼多項式，則常數(shù)[證明]g0 rg(x)g1xg2x rx(g1g2xgr1rxr1xrggx與假設(shè)矛盾所r12xrg(x)gxxrg(x)gxx是（n,k）循環(huán)碼C定理9.4.3r01次數(shù)最低的非零碼字多項式，則任何一個次數(shù)不大于n–1的二元多項式當(dāng)且僅當(dāng)它是g(x)倍式時，才可成為一個碼字多項[證明]充分性令v(x)是次數(shù)不大于n–1的二元多項式，且是g(x)的倍式v(x)(a0a1xanr1xnr1)g(x)ag(x)axg(x) xnr1g(x) nr上式中的被加項均是碼字多項式，所以v(x)必要性是也一個碼字多項式是碼 中一個碼字多項式，用g(x)令得v(x)a(x)g(x)b(x)v(x)a(x)gb(x)次數(shù)小于g(x)總結(jié)上面3條定理定理9.4.4在一個總結(jié)上面3條定理定理9.4.4在一個二元（nk）循環(huán)碼中，存在唯一的次數(shù)為n–k的碼字多項式g(x)，使得每個碼字多項式都是g(x)的倍式，反之每個次數(shù)不大于n–1而且為gx)倍式的多項式均對應(yīng)于一個碼字多項式。所有次數(shù)不大于n–1，而且是g(x)倍式的多項式是由一切形xnru(x)uxnr01多項式與g(x)相乘的結(jié)果，總共有2n–r個。故2n–r應(yīng)該等于，即rn。稱g(x)為這個k）循環(huán)碼的生成多項式，u(x)為消息多項式[例9.4.2]由gx1生成的（6.2）循環(huán)碼的碼生成多項式必須滿足一些條件生成多項式必須滿足一些條件xkgxxkxkxkg[證明nk12xn11xkxn1xknk1b(x)是g(x)連續(xù)向右移位k次后所得多項式，故b(x)是一個碼字多項式bxuxgx即故1xkgxuxgxxkuxgxg(x是xn1的因式9.4.6若g(x是n–k次多項式，而且是xn1的因式，則g(x生成個（n,9.4.6若g(x是n–k次多項式，而且是xn1的因式，則g(x生成個（n,k）循環(huán)碼[證明]令g(x)是xn+1的一個次數(shù)為n–k的因式，vxagxaxgxxk1gxk01aax xk1k01是一個次數(shù)小于或等于（n–1）的多項式，且g的倍式?？偣灿衚個這樣多項式。這些多項式組成一個（n,k）線性分組碼下面證明這個線性分組碼是循環(huán)的(x)的一個倍式，xvxvxvx21xnxn01vxk01v1gx,xgx,,xk1gx所以v(1)(x)也是g(x)的倍式。從而(x)也的性組合，所以(x)也是一個碼字多項式1可分解成：x[例9.4.3]多項gx1xx3生成的（7,4）循環(huán)§9.5系統(tǒng)循環(huán)碼的編碼及譯9.5.1在k）系統(tǒng)循環(huán)碼中 位§9.5系統(tǒng)循環(huán)碼的編碼及譯9.5.1在k）系統(tǒng)循環(huán)碼中 位消息位集中在碼字矢量的右側(cè)（最高位）構(gòu)成系統(tǒng)循環(huán)碼的步驟如下xk1、用xnk乘以消息多項式m(xmxk01xnkm(x)，得到余b(x)（校驗位多項式2、用生成多項式g(x)3、構(gòu)成碼字多項式c(x)xnkm(x；[例9.5.1]考慮由g(x)1xx3生成的（7.4）循環(huán)碼，消息多項m(x)1xx3，求相應(yīng)的系統(tǒng)碼字多項式xnkm(x)x3m(x)x3x5m(x)g(x)(1xx2x3)12c(x)x3m(x)1x4x53c9.5.2一、多項式c(x)a(x)b)(ab)xb9.5.2一、多項式c(x)a(x)b)(ab)xb0011+多項式a(xb(x)的系數(shù)依次從高到低位輸入模2加法器，和式的系數(shù)從高到低位依次二、多項式+++++c,c,…, a,a,…, ka(x)axb(x)bbxb01k01b)xkrrc(x)a(x)abxk(aa rk1 (a1b0a0b1)xaa)xkr(aba rk rk DDDD多項式乘法的另一種實現(xiàn)電DDDD+++++c,c,…, 多項式乘法的另一種實現(xiàn)電DDDD+++++c,c,…, a0,a1,…,a(x)1xb(x)1x[例c(x)a(x)b(x)1x++DDDD三、多項式g(x)gxd(x)dx01r0nd(x)q(x三、多項式g(x)gxd(x)dx01r0nd(x)q(x)g(x)r(x)0deg(r(x))d0,…,DDDDDD++++++q(x)出現(xiàn)在輸出端，寄存器中保存的是余r(x)在n次移位后，商多項。g(x)xd(x)x5x4x3[例x11x7xx3xDDDDDD++++四、乘一個多項式后，再除一個多項式的電路a(x)axkaxkk10h(x)四、乘一個多項式后，再除一個多項式的電路a(x)axkaxkk10h(x)hhxrrxhxa(x)h(x)q(x)g(x)r(x)rr10g(x)grxgxg10rDDDDDD+++++++乘以多項式xx1xxxx1DDDDD+++++x乘以多項式xx1xxxx1DDDDD+++++xx1，再除以xx41的電乘以多項DDDDDD++++++DDDDD9.5.3一個 k）系統(tǒng)循環(huán)碼的編碼過程由三步組成xk1、用x9.5.3一個 k）系統(tǒng)循環(huán)碼的編碼過程由三步組成xk1、用xnk乘以消息多項式m(x)mxk01xnkm(x)，得到余b(x)（校驗位多項式2、用生成多項式g(x)3、構(gòu)成碼字多項式c(x)xnkm(x；++++①②門 [例9.5.4]考慮由g(x)1xx3生成的[例9.5.4]考慮由g(x)1xx3生成的（7.4）系統(tǒng)循環(huán)碼++①輸移位寄存器中內(nèi)000（初始狀態(tài)110（第一次移位101（第二次移位100（第三次移位100（第四次移位②1101輸出完整碼字為DDD門循環(huán)碼的譯碼及其伴隨由于循環(huán)碼的循環(huán)結(jié)構(gòu)，使得伴隨式有如下性質(zhì)s(x循環(huán)碼的譯碼及其伴隨由于循環(huán)碼的循環(huán)結(jié)構(gòu)，使得伴隨式有如下性質(zhì)s(x是接收多項式r(x)rx定理的伴01g(x)的伴隨xs(x)(xr(x)s式，則用生成多項環(huán)位移一位r(1)除所得的余xr(x)rn1(xn1)r(1)[證明由r(1)(x)(xn1)故r(x)q(x)g(x)s(x)若r(x)利1h(x)g(x)r(1)(x)h(x)xq(x)]g(x)得r除以g(x)的余式，我們記之為s(1)的伴隨式是xs(x)。于類似的，把r(x)r(x)的伴隨多項連續(xù)循環(huán)移位i次，所得的多項s(x除類似的，把r(x)r(x)的伴隨多項連續(xù)循環(huán)移位i次，所得的多項s(x除以g(x)后的余式s(i)(x)++++(i計算接收多項式r(x)以及(x)的伴隨式電由g(x)1xx3生成的（7,4）[例門DDD++sn-k-門門循環(huán)碼的通用譯碼1、計算接收多項式r循環(huán)碼的通用譯碼1、計算接收多項式r(x)對應(yīng)的伴隨s(x)；s(x)，查表尋找對應(yīng)的錯誤多項式（陪集首項2、根據(jù)伴隨3、把接收多項式和錯誤多項式相加就糾正了相應(yīng)的錯誤++ s1梅吉特（Meggitt）錯誤形式分為二大類E1{梅吉特（Meggitt）錯誤形式分為二大類E1{e(x)|en1E0{e(x)|en1通過對接收到矢量r(x)對每位糾錯目的逐次循環(huán)移位，每次檢測、糾正首位錯誤，達(dá)門+門+門門門1、緩沖寄存器和伴隨式寄存器1、緩沖寄存器和伴隨式寄存器清零，門1，門2，門4接通，門3，門52、門1、門2斷開，門3、門4、門5接通置i=0，檢查伴隨式s(x)對應(yīng)的形式是否屬E1，若是則E1錯誤形式匹配電路輸出“1”，否則輸出“0”3、i=i+1，緩存器輸出最高位緩存內(nèi)容，與E1錯誤形式匹配電路輸出en-相加，糾正該位接收符號的錯誤。同時把en-1反饋到伴隨式計算與寄路的輸入，以消除該位錯誤對于伴隨式的影響。緩存器和伴隨寄存器時作一次循環(huán)位移，得到新的字(i(x)和它對應(yīng)的伴隨(i)x)4、利用新的伴隨式s(i)x)來檢查是否與E錯誤形式相匹配，若是則E11誤匹配電路輸出“1”，否則輸出“0”5、若i=n則譯碼結(jié)束，不然重復(fù)第3[例9.5.6][例9.5.6]g(x)1xx3生成的（7,4）循環(huán)碼，這個碼的最小對應(yīng)的伴隨式示于下E1{e6E0{e0(x),e1(x),e2(x),e3(x),e4(x),e5+門DDD++門門DDDDDDD門門+門DDD++門門DDDDDDD門門§9.69.6.1Hamming循環(huán)由GF(2)上m次本原多項式生成的長度1(m的循環(huán)碼(2m1,21m)Hamming對所有§9.69.6.1Hamming循環(huán)由GF(2)上m次本原多項式生成的長度1(m的循環(huán)碼(2m1,21m)Hamming對所有i0,12,2m2m，用生成多項g(x)xmia(x)g(x)b b(x) i x ci(x)1這m)碼字線性獨立，故這些碼字構(gòu)成生成矩陣bbbbbbbb10001001bbbbGbbb00mmmm2222010000bbb2m0bbbH2010000bbb2m0bbbH2m001bm 可以證明中無全零列矢量，無二列矢量相同，故可糾正全部一位錯誤生成多項式的表示：常用八進(jìn)制數(shù)字表示生成多項式；g(x)x3xg(x)x4xg(x)x7x3八進(jìn)制八進(jìn)制八進(jìn)制二進(jìn)制00101二進(jìn)制01001二進(jìn)制010001009.6.2BCH2m1），存在具有如下參數(shù)的9.6.2BCH2m1），存在具有如下參數(shù)的BCH對于任何正整mt（1、碼長n2、校驗位數(shù)目nk3、最小距離d2tBCH碼的生成多項式的構(gòu)成是GF(2m)的本原元，考慮的如下冪序列,2,3,4,,的最小多項式，則滿足所列參數(shù)要求的im令是碼生成多項式ig(x)LCM[m1(x),m2(x),m3(x),,m2t利用共軛元具有相同最小多項式的特點，則生成多項式可以寫成g(x)LCM[m(x),m(x),, 2t[例9.6.1]在GF[24]上構(gòu)造長度為 1[例9.6.1]在GF[24]上構(gòu)造長度為 115，分別能糾一位和兩位錯誤BCH長度為15的能糾一位錯誤的BCH碼的生成多項式以1和2為根g(x)(x1)(x2)(x4)(x8)xgx)的八進(jìn)制表示為“23”；生成(15，11)Hamming碼x長度為15，能糾正二位錯誤的BCH碼的生成多項式以1 ,324g(x)(x1)(x2)(x4)(x8)(x3)(x6)(x12)(x9(x4x1)(x4x3x2x1)xxxxg()的八進(jìn)制表示為“723”；生成(15，7)BCH碼，能糾正任意二位錯誤9.6.3Reed-Solomon(R-S)RS碼是一類非二進(jìn)制9.6.3Reed-Solomon(R-S)RS碼是一類非二進(jìn)制的BCH碼，具有很強的糾錯能力。RS碼的碼元的符號域和根域相同。能糾正t個錯誤的R-S碼具有如下參數(shù)：nq碼長校驗位數(shù)目nk最小距離：d2tR-S碼的最小距離為校驗位數(shù)目加1，達(dá)到了Singleton限界當(dāng)q2m，RS碼的碼元符號取自GF(2m，碼字長度為n1。一能糾位符號錯誤的RS碼的生成多項式g(x)(x)(x2)(x3)(x2t為GF(2m)的本原元其[注意GF(2m)中元素可用長度為m的二元矢量表示，長度為的字用二進(jìn)制符號表示長度為m(2m1)，能糾正mt個二進(jìn)制符號錯[例一個符號取自GF（23），長度為7，能糾正2個八進(jìn)制錯誤的碼的生成多項式為g(x)(x)([例一個符號取自GF（23），長度為7，能糾正2個八進(jìn)制錯誤的碼的生成多項式為g(x)(x)(x2)(x3)(x4)3xx23x3x的根。信息位長度為3，監(jiān)督位長度為4其為本原多項m(x)ii，系統(tǒng)碼x對于消息多項ic(x)3xx23x3x0c(x)6xx22x3c1(x)x 2542 601000001311110010101G生成矩陣00101H校驗矩陣用二元矢量來表示GF用二元矢量來表示GF(23信息位長度為9比特。例如m(6,5,2的元素，則（7,3）RS碼字長度為21c(6,5,2)G(10,8,4,0,6,5,2(3,2,4,0,6,5,2c(110,001,011,000,101,111,對于BCH碼和RS碼的譯碼，已經(jīng)有一些很有效的代數(shù)算法，糾錯§9.7§9.7不僅和當(dāng)前的一組k個輸入比特有關(guān)，而且和以前M個時刻的輸入組Rk/關(guān)，所以卷積碼可用參數(shù)組（nkM）來描述。編碼速對于卷積碼來說，約束長度KM1也是一個重要參數(shù)。卷積碼的構(gòu)成和代M級數(shù)據(jù)幀移位寄存器(kM比特k kn123…M[例]（2,1,2）卷積碼編碼器+(v(1),v(1),v(1)012m[例]（2,1,2）卷積碼編碼器+(v(1),v(1),v(1)012m(v(2),v(2),v(2)v(2)+012一、卷積碼編碼器的沖擊響應(yīng)和生成矩長度)時，系統(tǒng)輸出序列沖激響應(yīng)是當(dāng)系統(tǒng)輸入序列為m0010上例中兩個沖擊響應(yīng)為mm二個輸出編碼序列模2卷積運v(2)mg(jmi1,v(jg(jg(jg(j)l l l l DDg(1)g(2)g(1)g(2)g(1)g(2)g(1)g(2)00112233g(1),g(2)g(1)g(2)g(1)g(2)g(1)g(2)g(1)g(2)00112233g(1),g(2)g(1)g(2)g(1)g(2)g(1)g(2)00112233Gg(1)g(2)g(1)g(2)g(1)g(2)g(1)g(2)00112233vm編碼方程[例]（3,2,1）卷積碼編碼器+21g(2)21mv2D+21m2v+g(1)[例]（3,2,1）卷積碼編碼器+21g(2)21mv2D+21m2v+g(1),g(2),gg(1),g(2),gg(1),g(2),gg(1),g(2),g (1),g(2),gg(1),g(2),gg(1),g(2),gg ,g(2),gg g(1),g(2),gg(1),g(2),gg,g(,gG1,M 1,M 1,M g(1),g(2),gg(1),g(2),gg ,g( ,g2,M 2,M 2,M vmDv(1)m(1)g(1)m(2) v(2)m(1)g(2)m(2)g(2) v(3) m(1)g(3)m(2) Gm(11,vmG(011,二、卷積碼編碼器的多項用多項式表示輸入、輸出、和沖擊響應(yīng)序列m(i)(x)m二、卷積碼編碼器的多項用多項式表示輸入、輸出、和沖擊響應(yīng)序列m(i)(x)m(i)m(i)xm(i)x2 012v(j)(x)v(j)v(j)xv(j)x2 j1,2,012g(j)(x)g(jg(j)xg(j)xMii輸入、輸出關(guān)系v(1)(x)m(1)(x)g(1)(x)m(2)(x)g(1)12v(2)(x)m(1)(x)g(2)(x)m(2)g(2)12v(3)(x)m(1)(x)g(3)(x)m(2)(x)g(3)12矩陣表示輸入、輸出關(guān)系v(1)(x),v(2)(x),v(3)(x)(m(1)(x),m(2)(x))g(1)g(2) g(3)(x)G(x)111g(1)g(2) g(3)(x) 21卷積碼的圖描述和 S0一、卷積碼的樹圖 0 1 3S0 卷積碼的圖描述和 S0一、卷積碼的樹圖 0 1 3S0 S1Sm(1101002 S0S1S2S3二、卷二、卷積碼的網(wǎng)格狀態(tài)S0出發(fā)，輸入序列mS0S1S3S2S1S2S0三、卷積碼的狀態(tài)卷積碼編碼器是一個有三、卷積碼的狀態(tài)卷積碼編碼器是一個有限狀態(tài)機(jī)，因此可以用狀態(tài)轉(zhuǎn)移圖來描述（2,1,2）卷積碼對應(yīng)的狀m(110100從S0狀態(tài)出發(fā)，卷積碼的重線性分組碼中，碼字重量分布對于分組卷積碼的重線性分組碼中，碼字重量分布對于分組碼的性能有重要的影響ig“1”SSSE012修正狀態(tài)轉(zhuǎn)移2、每條路徑的總增益等于沿此路徑的各分支增益之積，相應(yīng)的碼字等于路徑增益中的冪次用狀態(tài)變量Z0，Z1，Z2，Z3，ZE分別表示從S0出發(fā)用狀態(tài)變量Z0，Z1，Z2，Z3，ZE分別表示從S0出發(fā)，終止于S3和E的所有路徑增益和D2ZZ102DZ1DZDZ1DZD22ZZZT(D) 1D5(12D4D2Dl1D52D64D78D8從重量分布公式可見，重量為(l5)在分支增益上添加其它的因子，還能獲得非零碼字的其它結(jié)構(gòu)信息。分在分支增益上添加其它的因子，還能獲得非零碼字的其它結(jié)構(gòu)信息。分支增益中因子N的指數(shù)j表示相應(yīng)輸入k個比特消息的重量（輸入據(jù)中“1”的個數(shù)），另外每個分支增益中增加一個因子L，表示一個j長度SSSE012含有輸入重量、輸出重量和支長度信息的修正狀態(tài)轉(zhuǎn)移D5L3T(D,L,N)ZE/1DL(1D5L3ND6L4(1L)N2D7L5(1L)2NNlDl5Ll3(1Z1D2 Z2DLZ1DLZ DNLZ D2LZ 9.7.49.7.4輸入信息比特錯誤+m+E惡性碼例DD卷積卷積碼的Viterbi譯碼算Viterbit算法等價于在加權(quán)圖上求最短路徑；Viterbi算法是卷積碼的最似然譯碼算法考慮圖9.7.2所示的(2,1,2)卷積碼，它的生成多項式矩陣G(x)(1xx2,1x2編碼器狀態(tài)從S0起始，并回到S0。前面M個時刻，對應(yīng)于起始階段；而后M編碼器狀態(tài)從S0起始，并回到S0。前面M個時刻，對應(yīng)于起始階段；而后M個時刻，通過輸入M個“0”，使譯碼器返回S0mivj長度為kL的消息序m(m0m1,mL1v(v0,v1,,vLM1r(r,r,,rn)接收到序列LM jYY二元硬判決信道高斯信道vr在接收時，發(fā)送序的似然函數(shù)LMLMP(r|v)logP(r|v)log|viP(ri|vi最大似然估計碼字序為?argmaxlogP(r|LMlog路徑v的度量(r|□logP(r||viiLM(ri|viLMlog路徑v的度量(r|□logP(r||viiLM(ri|vi(ri|vilogP(ri|vi分支度量所以一條路徑的度量為該路徑上各分支度量之和一條路徑前l(fā)個分支所構(gòu)成的部分路徑度量表示為l(r|(r|vl10ii1、硬判決P(r|v)(1pdiiip(r|v)dnlog(1p)iii1ipLMLM(r|v)(ri|vi)di(LMp最大似然譯最小Hamming距離譯2+EErixinini1,xini2,,xin2+EErixinini1,xini2,,xinninxEn1|x)P(r|v)iiii2jnD常nn(ri|vi)logP(ri|vi)C jLMn(r|v)xijD(LM選互相關(guān)最大的路最大似然譯Viterbi譯碼rViterbi譯碼r(00,01,10,00,00,00,m(0,0,0,0,0,0,接收序列最后幸存路判定發(fā)送序列以作為前向動態(tài)規(guī)劃解的ViterbiM）卷積碼為例，說明Viterbi算法是在加權(quán)網(wǎng)格以作為前向動態(tài)規(guī)劃解的ViterbiM）卷積碼為例，說明Viterbi算法是在加權(quán)網(wǎng)格圖上尋找最路徑值的前向動態(tài)規(guī)劃解卷積碼編碼器輸入序列m(m0,m1,m2mi編碼器具有M個寄存器，在tkT時刻編碼器狀態(tài)),,,kkkkkT時刻編碼器輸出碼字 f(mk,k))f(mk,mk1,,mk狀態(tài)轉(zhuǎn)移kkLM(r|v)(ri|viLM[ri|f(mi,mi1,,限定路徑起始于全零狀態(tài)，最后終止于全零狀態(tài)，m1 mM限定路徑起始于全零狀態(tài)，最后終止于全零狀態(tài)，m1 mMmL1mLM最大似然譯碼就是在網(wǎng)絡(luò)圖上尋找一條滿足初始和終止條件的路,0,m,m,,MML01L1使得路徑度量值為最大LM[ri|f(mi,mi1,,miMJjJk(k)Jk(mk1,mk2,,mkMk1[r|f(m,,,iiiiikM{mj遞歸計算Jk1(k1)Jk1(mk,mk1,,mkM遞歸計算Jk1(k1)Jk1(mk,mk1,,mkM1[ri|f(mi,mi1,,miMkk|f(mi,mi1,,miM)]{mjk1}kMj[rf(m,,,kkkkmaxJk(mk1,mk2,,mk)[rk|f(mk,,mkmkmaxJk(mk1,,mkM1,0)[rk|f(mk,,mkM1,,1)[r|f(m,, ,,kkMkMkkJ0(00)J0[0(0,0,,0)]J0(00)初始條件為對于二元對稱信道 min， ，(ri,vi)dH(ri,vi實現(xiàn)Viterbi譯碼算法的一些實現(xiàn)Viterbi譯碼算法的一些具體一、譯碼器存貯器數(shù)在Viterbi譯碼中，對每個狀態(tài)必須提供存貯器來寄存幸存路徑及其度量狀態(tài)數(shù)M指數(shù)地增長，一般M取10左右二、路徑存貯的截截短譯碼器的路徑存貯：對每條幸存路徑只寄存其最個消息據(jù)，其中L。譯碼器處理了接收序列的組數(shù)據(jù)后，譯碼貯器就滿了，必須作出強制性判決，確定第一個消息數(shù)據(jù)比特，在任何時刻k(k)，強制性判決可以有下面3種可能方1、在2M條幸存1、在2M條幸存路徑中，任選一條，并把該路徑中第時刻（即退時刻）的消息數(shù)據(jù)為譯碼輸出比特2、在2M個可能的第(k)時刻消息數(shù)據(jù)中選一個出現(xiàn)次數(shù)最多的數(shù)為譯碼輸出比3、 時刻條幸存路徑中，具有最大部分路徑度量的那一條的(k時刻消息數(shù)據(jù)作為譯碼輸出比特狀態(tài)同步譯碼器可能從一個未知的編碼狀態(tài)開始工作，或者說譯碼器在開始工作時，可能處在任何一個狀態(tài)中；譯碼器的所有狀態(tài)寄存器，必須都初始o(jì)n比特同步位同步錯誤，則所有幸存路徑的度量沒有明顯差別，以此作同步識別四、分四、分支度量的量化精在軟判決信道上卷積碼譯碼比硬判決信道具有性能上優(yōu)越，一般信輸出量化電平數(shù)越多，性能越好；但8電平（Q=8）量化所得的性能無量化理想情況下性能僅相差無幾(0.25dB)9.8.4卷積碼Viterbi譯碼輸出序列中平均9.8.4卷積碼Viterbi譯碼輸出序列中平均錯誤比特Pb總的傳輸比特數(shù)一、節(jié)點錯誤概圖中橫貫全零狀態(tài)的全零路，代表正確路；下面實線通路是由tri算法所選擇的，譯碼器輸出路徑。它和正確路有不重合的地方，表明出了錯誤。按tri算法，在這些不重合的路徑片段上正確路所積累的路徑度量小于不正確路徑的路徑度量積累。我們把這種錯誤稱為發(fā)生在節(jié)點i，j和k上的節(jié)點錯誤。在節(jié)點j出現(xiàn)節(jié)點錯誤的必要，但并非充分的積累了更大的路徑度量jikj上的節(jié)點錯誤概[(r|v')j上的節(jié)點錯誤概[(r|v')(r|v'V'(jV'(Pr{(r|v')(r|Pe(j)v'V'(j可以證明成對錯誤概率為Pr{(r|v')(r|v)}P0(r)P1(r)ZZP0(r)1(r)，P0(r)P(r|v0)1(r)P(r|vrddH(v,v')wH(vddPr{(r|v')(r|Pe(j)所v'Bd(jddA(d)Z其中Bd(