版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
1、第6節(jié)霍夫曼碼霍夫曼碼1.1952年霍夫曼(Huffman)提出的,是歷史記錄中第一個最優(yōu)即時碼。2.二元霍夫曼碼的構(gòu)造方法:根據(jù)信源符號的概率自底向上地構(gòu)造碼樹,步驟二元霍夫曼碼的構(gòu)造方法:根據(jù)信源符號的概率自底向上地構(gòu)造碼樹,步驟如下:如下:(1)將信源U的n個符號ui按概率p(ui)從大到小排列,構(gòu)成碼樹的葉節(jié)點。(2)將兩個最小的概率值相加,構(gòu)成二者的父節(jié)點。(3)將所有沒有父節(jié)點的概率值按從大到小重新排列。(4)重復(fù)(2)與(
2、3)直到根節(jié)點出現(xiàn),即步驟(2)中兩個概率值相加=1.例6110.5,0.25,0.125,0.125解:1)畫出碼樹包括各節(jié)點對應(yīng)的概率值。2)平均碼長:2)編碼效率:3)信源熵(信源的信息傳輸率):4)信源的相對熵率(信源的信息傳輸效率):3.二分組霍夫曼碼二分組霍夫曼碼例6120.7,0.3結(jié)論結(jié)論:對于“小消息信源”,必須用分組長度較大的霍夫曼碼,才能獲得較大的編碼效率與較好的壓縮效果。這是提高編碼效率的重要途徑。4.最優(yōu)分組碼
3、最優(yōu)分組碼定義定義1.令S為一離散信源,用一個新符號取代S中兩個概率最小的信源符號,并把這兩個最小概率合并為該新符號的概率,而其它信源符號及其概率不變,所得的信源S(1)稱為信源S的(一次)縮減信源縮減信源,并稱S為S(1)的擴展信源。擴展信源。n步縮減信源步縮減信源S(n).2.令C是信源S的一個即時碼,其中有兩個碼字w’與w’’長度最大且相等,用其最大真前綴替換C中的w’與w’’所得的即時碼C(1)稱為C的(一次)縮減縮減碼,碼,并
4、稱C為C(1)的擴展碼。與擴展碼。與n步縮減碼分別記為和步縮減碼分別記為和Cn。顯然,信源每縮減一次,其符號總數(shù)減1;即時碼每縮減一次其碼字總數(shù)減1.引理引理1令C為即時碼,C(1)是碼C的一個縮減碼,則兩個碼的平均碼長之間有如下關(guān)系:LC=LC(1)p’p’’其中p’與p’’分別是C中被合并的兩個碼字的概率。證明證明設(shè)S有q個符號,概率分別為pi,碼C中對應(yīng)的碼字長為li,其中對應(yīng)于概率p’的碼字長記為l’,則(1)碼長不同導(dǎo)致信源編
5、碼器不能勻速輸出碼元符號,因此不能直接與信道連接。解決辦法是添加緩沖寄存器。(2)存在差錯擴散的問題。解決辦法是使用糾錯碼提高數(shù)據(jù)的抗干擾能力。(3)霍夫曼碼的編譯碼都需要查找碼本,碼本太大的話,占用內(nèi)存大且費時。因此,不能對太大的擴展信源進行編碼。為進一步提高編碼效率,需要改用非分組碼,例如算術(shù)碼、字典碼。(4)霍夫曼碼屬于概率匹配碼,需要知道信源的統(tǒng)計特性,且不能適應(yīng)信源概率變化??筛挠镁哂凶赃m應(yīng)性的算術(shù)編碼,或字典碼。第7節(jié)算術(shù)碼
6、算術(shù)碼仍設(shè)U為離散無記憶信源。1.特點:特點:1)非分組碼,全序列編碼:是一個非分組碼,全序列編碼:是一個雙射,可將任意長的:01fU?信源序列編碼為“一個”碼字。2)用信源序列S的累積概率F(S)的一個近似值作為S的碼字,該近似值的長度由S的自信息量或概率p(S)確定。2.累積概率累積概率||||()()lexTSTSFSpT????注意注意,累積概率值中不含p(S)。遞推公式遞推公式:(用樹圖說明)()()()()FSuFSpSFu
7、??3.累積概率區(qū)間累積概率區(qū)間長度相同的信源序列的累積概率有如下關(guān)系:1210()()()1()()()miiiFSFSFSFSFSpS?????????將單位區(qū)間[01]劃分為若干不相交的小區(qū)間:稱為序列S的累積概率區(qū)間累積概率區(qū)間。[()()())SIFSFSpS??用樹圖說明各累積概率區(qū)間的包含與不相交關(guān)系用樹圖說明各累積概率區(qū)間的包含與不相交關(guān)系。4.編碼方法編碼方法基本思想基本思想:(1)計算信源序列S的“累積概率”F(S)
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 基于算術(shù)碼的聯(lián)合信源信道編解碼研究.pdf
- Turbo碼 和 LDPC碼.doc
- 必出二碼和拖碼
- 掃描碼及鍵盤碼
- 凌云2故障碼
- 信道極化和極化碼:極化碼與LDPC碼級聯(lián)關(guān)鍵技術(shù)研究.pdf
- cdma地址碼及擴頻碼
- 卷積碼和LDPC碼的研究與應(yīng)用.pdf
- 代數(shù)幾何碼與LDPC碼.pdf
- 碼參數(shù)可配置的BCH碼和RS碼通用譯碼算法研究及其軟件實現(xiàn).pdf
- 信息論編碼課程設(shè)計--霍夫曼碼研究與設(shè)計
- 用線性碼構(gòu)造認(rèn)證碼.pdf
- 角碼2.dwg
- 噴泉碼度分布優(yōu)化和LT碼譯碼算法研究.pdf
- 卷積碼和Turbo碼的聯(lián)合信源信道譯碼.pdf
- 以線性分組碼為子碼的混合LDPC碼構(gòu)造.pdf
- 角碼2.dwg
- 某些循環(huán)碼和線性碼權(quán)重分布的研究.pdf
- 卷積碼和循環(huán)碼識別技術(shù)研究.pdf
- 3585.可分碼和強可分碼的上界及構(gòu)造
評論
0/150
提交評論