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

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