《信息論與編碼》-第20講-信道編碼

《信息論與編碼》_第20講_信道編碼第一頁，共26頁。2回顧線性分組碼碼字間的關(guān)系生成矩陣一致校驗矩陣與生成矩陣的關(guān)系錯誤圖樣與伴隨式陪集與譯碼第二頁，共26頁。6.3線性分組碼原理6.3.1漢明距離與漢明重量6.3.2漢明距離與漢明重量間關(guān)系6.3.3線性分組碼譯碼6.3.4檢錯與糾錯第三頁，共26頁。6.3.1漢明距離、漢明重量最小Hamming距離

線性分組碼的最小Hamming距離定義為兩個不同碼字的Hamming距離的最小值，記為dmin。 區(qū)別：漢明距離與最小漢明距離第四頁，共26頁。6.3.1漢明距離、漢明重量最小Hamming重量 線性分組碼的最小Hamming重量定義為非全0碼字的Hamming重量的最小值，記為wmin。區(qū)別：漢明重量與最小漢明重量第五頁，共26頁。6.3.2漢明距離與漢明重量關(guān)系定理1線性分組碼的最小漢明距離等于最小漢明重 量，即dmin=wmin。證明：設(shè)兩個不同的碼字u(1)和u(2)，使得dmin=d(u(1),u(2))=w(u(1)-u(2))。注意到(u(1)-u(2))是一個非全0碼字，所以dmin≥wmin。設(shè)一個非全0碼字u，使得wmin=w(u)=w(u-全0碼字)=d(u,全0碼字)。所以dmin≤wmin。 證完。第六頁，共26頁。6.3.2漢明距離與漢明重量關(guān)系定理2設(shè)信道的輸入為碼字u，信道的輸出為向量y，差錯向量為e=y-u。則（1）當(dāng)w(e)<dmin，yHT肯定不是全0的N-L維向量，因而發(fā)現(xiàn)信道傳輸錯誤。（2）當(dāng)w(e)≤[(dmin-1)/2]（下方取整），由上述實用糾錯譯碼算法肯定將y譯為真正的原發(fā)碼字u，而不會將y譯為其它碼字。第七頁，共26頁。6.3.2漢明距離與漢明重量關(guān)系證明（1）當(dāng)w(e)<dmin，e肯定不是碼字。 因此yHT=eHT≠全0的N-L維向量。注：原因？第八頁，共26頁。6.3.2漢明距離與漢明重量關(guān)系（2）當(dāng)w(e)≤[(dmin-1)/2]（下方取整），則y與任意另一個碼字c的Hamming距離 d(c,y)≥d(c,u)-d(y,u)（三角不等式） ≥dmin-d(y,u)=dmin-w(e) ≥dmin-[(dmin-1)/2]>[(dmin-1)/2] ≥w(e)=d(y,u)。因此，所有碼字中,u與y的Hamming距離最小。第九頁，共26頁。6.3.3線性分組碼譯碼定理1設(shè)信道的輸入為碼字u，信道的輸出為向量y，差錯向量為e=y-u。當(dāng)w(e)>[(dmin-1)/2]（下方取整），由上述實用糾錯譯碼算法未必將y譯為u。證明設(shè)信道的輸入為碼字u，設(shè)另一個碼字c恰好滿足d(c,u)=dmin。第十頁，共26頁。6.3.3線性分組碼譯碼設(shè)輸出向量是這樣的y：

d(c,u)=d(c,y)+d(y,u)；（三角不等式變?yōu)榈仁剑﹚(e)=d(y,u)=[(dmin-1)/2]+1>[(dmin-1)/2]。請注意，這樣的輸出向量y存在！而且此時d(c,y)=d(c,u)-d(y,u)=dmin-{[(dmin-1)/2]+1}=dmin-1-[(dmin-1)/2]。d(y,u)=[(dmin-1)/2]+1；

d(c,y)=dmin-1-[(dmin-1)/2]。第十一頁，共26頁。當(dāng)dmin是奇數(shù)時， d(y,u)=(dmin-1)/2+1，d(c,y)=(dmin-1)/2， 故d(c,y)<d(y,u)。當(dāng)dmin是偶數(shù)時， d(y,u)=dmin/2，d(c,y)=dmin/2， 故d(c,y)=d(y,u)。即,當(dāng)dmin是奇數(shù)時,將y譯為c而不是u；當(dāng)dmin是偶數(shù)時,將y譯為c或u都符合最小距離準(zhǔn)則。說明 設(shè)信道真正的輸入碼字為u，信道的輸出向量為y，真正的差錯向量為e=y-u。第十二頁，共26頁。6.3.3線性分組碼譯碼采用實用糾錯譯碼算法： 接收y→計算伴隨式s=yHT→以s為地址查找e(s)→計算c=y-e(s)→認(rèn)為陪集首e(s)就是差錯向量；認(rèn)為c就是輸入碼字。由定理得，如果w(e)≤[(dmin-1)/2]

，則e(s)=e，因而c=u。 如果w(e)>[(dmin-1)/2]

，則未必e(s)=e，因而未必c=u。換句話說，如果w(e)≤[(dmin-1)/2]

，則e一定是s=eHT的陪集首；如果w(e)>[(dmin-1)/2]

，則e未必是s=eHT的陪集首。第十三頁，共26頁。6.3.3線性分組碼譯碼說明設(shè)信道真正的輸入碼字為u，信道的輸出向量為y，真正的差錯向量為e=y-u。第十四頁，共26頁。6.3.4檢錯與糾錯定理

設(shè)真正的差錯向量為e。w(e)≤t時肯定正確譯 碼，當(dāng)且僅當(dāng)dmin≥2t+1。推論設(shè)真正的差錯向量為e。肯定正確譯碼的概率為第十五頁，共26頁。說明

dmin是線性分組碼糾錯能力的一個指標(biāo)。dmin越大，[(dmin-1)/2]就越大，肯定正確譯碼的概率也越大。當(dāng)N比L大得越多，碼字在所有N維向量中占的比例越小，越容易使得dmin大。問題是，當(dāng)N和L都確定時，如何設(shè)計碼使得dmin大。糾正一種誤解： dmin越大，肯定正確譯碼的概率越大。決不能說：dmin越大，正確譯碼的概率越大。（怎么回事？）6.3.4檢錯與糾錯第十六頁，共26頁?！翱隙ㄕ_譯碼”={w(e)≤[(dmin-1)/2]}；“不能肯定正確譯碼”={w(e)>[(dmin-1)/2]}。注意： P(肯定正確譯碼)+P(不能肯定正確譯碼)=1。 這就是說，“肯定正確譯碼”的概率越大，“不能肯定正確譯碼”的概率越小?！罢_譯碼”=“肯定正確譯碼”∪“不能肯定正確譯碼中的一部分”。6.3.4檢錯與糾錯第十七頁，共26頁。6.3.4檢錯與糾錯 一個線性分組碼，dmin小，肯定正確譯碼的概率小，但“不能肯定正確譯碼中的一部分”的概率很大，則正確譯碼的概率也可能很大。第十八頁，共26頁?！翱隙ㄕ_譯碼”={w(e)≤[(dmin-1)/2]}；“不能肯定正確譯碼”={w(e)>[(dmin-1)/2]}。注意： P(肯定正確譯碼)+P(不能肯定正確譯碼)=1。 這就是說，“肯定正確譯碼”的概率越大，“不能肯定正確譯碼”的概率越小。6.3.4檢錯與糾錯第十九頁，共26頁。6.3.4檢錯與糾錯練習(xí)回答“肯定正確譯碼”、“不能肯定正確譯碼”、“肯定不能正確譯碼”。（1）w(e)≤[(dmin-1)/2]；（2）w(e)>[(dmin-1)/2]；（3）e是一個碼字；（4）e不是一個碼字。第二十頁，共26頁。例

求一致校驗矩陣；碼字集合；譯碼預(yù)計算（簡化計算量）。顯然是系統(tǒng)碼。第二十一頁，共26頁。信息向量→碼字000→000000100→011100010→101010001→110001110→110110101→101101011→011011111→000111伴隨式s→陪集首e(s)000→000000100→100000010→010000001→001000110→000100101→000010011→000001111→100100第二十二頁，共26頁。觀察有，dmin=3；[(dmin-1)/2]=1。當(dāng) 真正的差錯向量的Hamming重量不超過1時，肯定正確譯碼；當(dāng) 真正的差錯向量的Hamming重量超過1時，未必正確譯碼。第二十三頁，共26頁?？隙ㄕ_譯碼的概率為(1-p)6+6(1-p)5p。正確譯碼的概率為(1-p)6+6(1-p)5p+(1-p)4p2。若p=10-2，則(1-p)6=0.9415；

(1-p)6+6(1-p)5p=0.9986；

(1-p)