




版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、2022-4-91第七章:第七章:線(xiàn)性分組碼7.1 分組碼的概念分組碼的概念7.2 線(xiàn)性分組碼線(xiàn)性分組碼7.4 循環(huán)碼循環(huán)碼7.5 卷積碼卷積碼2022-4-927.2 線(xiàn)性分組碼線(xiàn)性分組碼實(shí)用糾錯(cuò)譯碼算法的預(yù)備知識(shí):差錯(cuò)向量和伴隨式實(shí)用糾錯(cuò)譯碼算法的預(yù)備知識(shí):差錯(cuò)向量和伴隨式定義定義6.1.8 設(shè):信道的輸入為碼字u;信道的輸出為向量y。稱(chēng)向量e=y- u為差錯(cuò)向量差錯(cuò)向量,或差錯(cuò)圖樣差錯(cuò)圖樣。(請(qǐng)注意,此時(shí)y=u+e;向量的加減法是對(duì)應(yīng)分量的(modD) 加減法)定義定義6.1.9(p195) 設(shè)信道的輸出為y。記s=yHT其中H是一致校驗(yàn)矩陣。稱(chēng)N-L維行向量s為y的伴隨式伴隨式。 有以
2、下的結(jié)論。 2022-4-937.2 線(xiàn)性分組碼線(xiàn)性分組碼(1)當(dāng)兩個(gè)差錯(cuò)向量相同時(shí),它們的伴隨式相同。這就是說(shuō),伴隨式s的值僅僅與信道傳輸錯(cuò)誤有關(guān),與輸入信道的碼字無(wú)關(guān)。證明 s=yHT=(u+e)HT=uHT+eHT= eHT。證完。(2)兩個(gè)差錯(cuò)向量的伴隨式相同,當(dāng)且僅當(dāng)它們的差向量是碼字。證明 設(shè)有兩個(gè)差錯(cuò)向量e(1)和e(2)。e(1)HT=e(2)HT,當(dāng)且僅當(dāng)(e(1)-e(2)HT=全0的N-L維行向量,當(dāng)且僅當(dāng)(e(1)-e(2)是碼字。證完。2022-4-947.2 線(xiàn)性分組碼線(xiàn)性分組碼(3)給定一個(gè)差錯(cuò)向量e。則與e具有相同伴隨式的所有差錯(cuò)向量恰好是e加上所有碼字。換句話(huà)
3、說(shuō)。設(shè)s是一個(gè)伴隨式。以s為伴隨式的全體差錯(cuò)向量, 就是以s為伴隨式的一個(gè)差錯(cuò)向量加上全體碼字。(4)伴隨式s是N-L維行向量,因此有DN-L個(gè)不同的伴隨式。差錯(cuò)向量e是N維行向量,因此有DN個(gè)不同的差錯(cuò)向量。具有相同伴隨式的差錯(cuò)向量的個(gè)數(shù)為DL。DLDN-L=DN。 定義定義 在以s為伴隨式的全體差錯(cuò)向量中,Hamming重量最小的差錯(cuò)向量稱(chēng)為s的陪集首的陪集首,記為e(s)。(s可能有不止一個(gè)Hamming重量最小的差錯(cuò)向量,任意選擇一個(gè)作為陪集首e(s)即可)2022-4-957.2 線(xiàn)性分組碼線(xiàn)性分組碼(5)對(duì)信道的輸出向量y,計(jì)算伴隨式計(jì)算伴隨式s=yHT,以,以s為地址查找為地址查
4、找陪集首陪集首e(s),計(jì)算,計(jì)算u=y- e(s)。則u就是在所有碼字中與y的Hamming距離最小的碼字。證明 首先,u=y- e(s)是碼字。這是因?yàn)閡HT=yHT- e(s)HT=s-s=全0的N-L維行向量。其次,對(duì)任意另一個(gè)碼字c,(y- c)HT=yHT- cHT=yHT=s。這就是說(shuō),(y- c)是以s為伴隨式的一個(gè)差錯(cuò)向量。另一方面,(y- u)=e(s)是以s為伴隨式的Hamming重量最小的差錯(cuò)向量。所以w(y- u)w(y- c),即d(y, u)w(y, c)。證完。 2022-4-967.2 線(xiàn)性分組碼線(xiàn)性分組碼實(shí)用糾錯(cuò)譯碼算法實(shí)用糾錯(cuò)譯碼算法預(yù)計(jì)算預(yù)計(jì)算 對(duì)每個(gè)伴
5、隨式(即N-L維行向量)s,尋找s的陪集首e(s),并以s為地址存儲(chǔ)e(s)。(預(yù)計(jì)算的總體計(jì)算量很大,但有許多技巧可以大幅度地減少計(jì)算量)現(xiàn)場(chǎng)糾錯(cuò)譯碼現(xiàn)場(chǎng)糾錯(cuò)譯碼 (1)對(duì)信道的輸出向量y,計(jì)算伴隨式s=yHT。(2)以s為地址查找陪集首e(s)。(3)將輸出向量y譯為碼字u=y- e(s)。結(jié)束。u就是在所有碼字中與y的Hamming距離最小的碼字。 2022-4-977.2 線(xiàn)性分組碼線(xiàn)性分組碼現(xiàn)場(chǎng)糾錯(cuò)譯碼的計(jì)算量現(xiàn)場(chǎng)糾錯(cuò)譯碼的計(jì)算量 計(jì)算量最大的是第(2)步。因?yàn)閟是N-L維行向量,所以查找s的計(jì)算量是logDN-L=(N-L)logD (而不是DN-L)??傊?jì)算量遠(yuǎn)遠(yuǎn)小于直接使用
6、最小距離準(zhǔn)則的計(jì)算量DL。 2022-4-987.2 線(xiàn)性分組碼線(xiàn)性分組碼線(xiàn)性分組碼的檢錯(cuò)能力和糾錯(cuò)能力線(xiàn)性分組碼的檢錯(cuò)能力和糾錯(cuò)能力定義定義6.1.3 線(xiàn)性分組碼的最小最小Hamming距離距離定義為兩個(gè)不同碼字的Hamming距離的最小值,記為dmin。線(xiàn)性分組碼的最小最小Hamming重量重量定義為非全0碼字的Hamming重量的最小值,記為wmin。2022-4-997.2 線(xiàn)性分組碼線(xiàn)性分組碼引理引理1 dmin=wmin。證明 設(shè)兩個(gè)不同的碼字u(1)和u(2),使得dmin=d(u(1) , u(2)=w(u(1)-u(2)。注意到(u(1)-u(2)是一個(gè)非全0碼字,所以dmi
7、nwmin。設(shè)一個(gè)非全0碼字u,使得wmin=w(u)=w(u-全0碼字)=d(u, 全0碼字)。所以dminwmin。證完。 2022-4-9107.2 線(xiàn)性分組碼線(xiàn)性分組碼引理引理2 設(shè)信道的輸入為碼字u,信道的輸出為向量y,差錯(cuò)向量為e=y-u。則(1)當(dāng)w(e)dmin,yHT肯定不是全0的N-L維向量,因而發(fā)現(xiàn)信道傳輸錯(cuò)誤。(2)當(dāng)w(e)(dmin-1)/2(下方取整),由上述實(shí)用糾錯(cuò)譯碼算法肯定將y譯為真正的原發(fā)碼字u,而不會(huì)將y譯為其它碼字。 2022-4-9117.2 線(xiàn)性分組碼線(xiàn)性分組碼證明(1)當(dāng)w(e)(dmin-1)/2w(e)=d(y,u)。因此,所有碼字中,u與y
8、的Hamming距離最小。證完。2022-4-9127.2 線(xiàn)性分組碼線(xiàn)性分組碼引理引理3 設(shè)信道的輸入為碼字u,信道的輸出為向量y,差錯(cuò)向量為e=y-u。當(dāng)w(e)(dmin-1)/2(下方取整),由上述實(shí)用糾錯(cuò)譯碼算法未必將y譯為u。證明 設(shè)信道的輸入為碼字u,設(shè)另一個(gè)碼字c恰好滿(mǎn)足d(c, u)= dmin。設(shè)輸出向量是這樣的y:d(c, u)= d(c, y)+d(y,u); (三角不等式變?yōu)榈仁剑﹚(e)=d(y,u)=(dmin-1)/2+1(dmin-1)/2。請(qǐng)注意,這樣的輸出向量y存在!而且此時(shí)d(c, y)= d(c, u)-d(y,u)=dmin-(dmin-1)/2+1
9、=dmin-1-(dmin-1)/2。2022-4-913d(y,u)=(dmin-1)/2+1;d(c, y)=dmin-1-(dmin-1)/2。當(dāng)dmin是奇數(shù)時(shí),d(y,u)=(dmin-1)/2+1,d(c, y)= (dmin-1)/2,故d(c, y)(dmin-1)/2 ,則未必e(s)=e,因而未必c=u。換句話(huà)說(shuō),如果w(e)(dmin-1)/2 ,則e一定是s=eHT的陪集首;如果w(e)(dmin-1)/2 ,則e未必是s=eHT的陪集首。2022-4-9157.2 線(xiàn)性分組碼線(xiàn)性分組碼定理定理6.1.4 設(shè)真正的差錯(cuò)向量為e。w(e)t時(shí)肯定正確譯碼,當(dāng)且僅當(dāng)dmin
10、2t+1。推論推論 設(shè)真正的差錯(cuò)向量為e??隙ㄕ_譯碼肯定正確譯碼的概率為2/ ) 1(0minmin)1 ()2/ ) 1()(dttNttNppCdewP2022-4-9167.2 線(xiàn)性分組碼線(xiàn)性分組碼定理6.1.4說(shuō)明,dmin是線(xiàn)性分組碼糾錯(cuò)能力的一個(gè)指標(biāo)。dmin越大,(dmin-1)/2就越大,肯定正確譯碼的概率也越大。當(dāng)N比L大得越多,碼字在所有N維向量中占的比例越小,越容易使得dmin大。問(wèn)題是,當(dāng)N和L都確定時(shí),如何設(shè)計(jì)碼使得dmin大。糾正一種誤解:dmin越大,肯定正確譯碼的概率越大。決不能說(shuō):dmin越大,正確譯碼的概率越大。(怎么回事?)“肯定正確譯碼”=w(e)(d
11、min-1)/2;“不能肯定正確譯碼”=w(e)(dmin-1)/2。請(qǐng)注意:P(肯定正確譯碼)+ P(不能肯定正確譯碼)=1。這就是說(shuō),“肯定正確譯碼”的概率越大,“不能肯定正確譯碼” 的概率越小。然而,“正確譯碼”=“肯定正確譯碼”“不能肯定正確譯碼中的一部分”。一個(gè)線(xiàn)性分組碼,dmin小,肯定正確譯碼的概率小,但“不能肯定正確譯碼中的一部分” 的概率很大,則正確譯碼的概率也可能很大。2022-4-9177.2 線(xiàn)性分組碼線(xiàn)性分組碼問(wèn)答問(wèn)答回答“肯定正確譯碼”、“不能肯定正確譯碼”、“肯定不能正確譯碼”。(1)w(e)(dmin-1)/2;(2)w(e)(dmin-1)/2;(3)e是一個(gè)
12、碼字;(4)e不是一個(gè)碼字。2022-4-9187.2 線(xiàn)性分組碼線(xiàn)性分組碼例例6.1.8 求一致校驗(yàn)矩陣;碼字集合;譯碼預(yù)計(jì)算(簡(jiǎn)化計(jì)算量)。 顯然是系統(tǒng)碼。100011010101001110G011100101010110001H2022-4-9197.2 線(xiàn)性分組碼線(xiàn)性分組碼信息向量碼字000 000000100 011100010 101010001 110001110 110110101 101101011 011011111 000111伴隨式s陪集首e(s)000 000000100 100000010 010000001 001000110 000100101 000010011 000001111 1001002022-4-9207.2 線(xiàn)性分組碼線(xiàn)性分組碼dmin=3;(dmin-1)/2=1。當(dāng)真正的差錯(cuò)向量的Hamming重量不超過(guò)1時(shí),肯定正確譯碼;當(dāng)真正的差錯(cuò)向量的Hamming重量超過(guò)1時(shí),未必正確譯碼。肯定正確譯碼的概率為(1-p)6+6(1-p)5p。正確譯碼的概率為(1-p)6+6(1-p)5p+(1-p)4p2。若p=10-2,則(1-p
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- T-ZSM 0052-2024“領(lǐng)跑者”評(píng)價(jià)技術(shù)要求 普通型立式帶鋸床
- T-ZSA 227-2024 低慢小無(wú)人駕駛航空器車(chē)載式預(yù)警處置系統(tǒng)
- 2025年度村級(jí)林業(yè)資源監(jiān)測(cè)村級(jí)護(hù)林員職責(zé)合同
- 2025年度美甲服務(wù)連鎖品牌合作協(xié)議
- 二零二五年度汽車(chē)維修保養(yǎng)抵押借款合同
- 2025年度美發(fā)店員工勞動(dòng)合同及員工福利政策
- 二零二五年度個(gè)人心理咨詢(xún)服務(wù)合同
- 2025年度消防車(chē)輛抵押借款合同范本
- 二零二五年度直播平臺(tái)用戶(hù)行為數(shù)據(jù)分析合同
- 2025年度石材石材加工定制采購(gòu)協(xié)議
- 2024年湖南省岳陽(yáng)市中考數(shù)學(xué)一模試卷
- DZ∕T 0080-2010 煤炭地球物理測(cè)井規(guī)范(正式版)
- 2024年國(guó)家公務(wù)員考試時(shí)事政治必考試題庫(kù)(完整版)
- 否定副詞“不”和“沒(méi)有”比較研究
- 售樓部銷(xiāo)售禮儀培訓(xùn)內(nèi)容
- (高清版)DZT 0347-2020 礦山閉坑地質(zhì)報(bào)告編寫(xiě)規(guī)范
- 2024年不停電電源UPS相關(guān)項(xiàng)目營(yíng)銷(xiāo)計(jì)劃書(shū)
- 重汽重卡培訓(xùn)課件
- 干式變壓器培訓(xùn)課件
- 公司SWOT分析表模板
- 2023年上海中考語(yǔ)文試卷(附答案)
評(píng)論
0/150
提交評(píng)論