信源編碼(1)_離散信源編碼11.11_第1頁
信源編碼(1)_離散信源編碼11.11_第2頁
信源編碼(1)_離散信源編碼11.11_第3頁
信源編碼(1)_離散信源編碼11.11_第4頁
信源編碼(1)_離散信源編碼11.11_第5頁
已閱讀5頁,還剩60頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)

文檔簡介

1、第5章 信源編碼編碼的意義編碼的意義編碼定義編碼定義最佳編碼方法信源編碼的目的:信源編碼的目的: 1、便于信道的傳輸、便于信道的傳輸 例如:語音信號的數(shù)字傳輸例如:語音信號的數(shù)字傳輸 2、提高有效性、提高有效性 例:設(shè)某計算機終端用來控制檢查流水線上產(chǎn)品的質(zhì)量,按優(yōu)、中、劣三級來分類記錄。從統(tǒng)計中已知產(chǎn)品在三級中的比例為優(yōu)、劣各占1/4,中占1/2。以下研究如何將檢查結(jié)果編成二進制碼,以通過網(wǎng)絡(luò)傳送到主機中進行存儲和處理。第一種編碼方法: 產(chǎn) 品 等級出現(xiàn)概率編碼優(yōu)1/411中1/210劣1/400平均編碼長度:L1=1/4*2+1/2*2+1/4*2 =2bit/符號產(chǎn) 品 等級出現(xiàn)概率編碼

2、優(yōu)1/41中1/210劣1/400第二種編碼方法平均編碼長度:L2=1/4*1+1/2*2+1/4*2 =1.75bit/符號產(chǎn) 品 等級出現(xiàn)概率編碼優(yōu)1/411中1/21劣1/400第三種編碼方法平均編碼長度:L3=1/4*2+1/2*1+1/4*2 =1.5bit/符號結(jié)論: 1、不同的編碼方法,平均的編碼長度不一樣 2、L1L2L3結(jié)論:概率越大,用的碼越短,則平均編碼長度則越小。二、編碼定義1、等長碼和變長碼 如果一種碼的各個碼字都是由同樣多個碼元構(gòu)成的,則成為等長碼。例如:00,01,103、碼樹 碼樹是表示元素之間的結(jié)構(gòu)層次的方法。5、平均編碼長度 設(shè)N個碼字中的第I個碼字的長度為

3、ni,他所代表的編碼對象xi的概率為p(xi),則碼字的平均編碼長度為: L=p(xi) ni6、編碼效率 最小的平均編碼長度和實際的編碼長度的比值。 Lmin=H(X)/logD =Lmin/L 編碼的剩余度r=1- 產(chǎn) 品 等級出現(xiàn)概率編碼優(yōu)1/411中1/21劣1/400例:平均編碼長度:L3=1/4*2+1/2*1+1/4*2 =1.5bit/符號Lmin=1.5 =1三、最佳編碼方法 滿足兩個條件:1、唯一可譯性 2、碼長是最小的l 目的:提高通信的有效性。目的:提高通信的有效性。l 途徑:通過壓縮信源的冗余度來實現(xiàn)。途徑:通過壓縮信源的冗余度來實現(xiàn)。l 方法:壓縮每個信源符號的平均

4、比特數(shù)或信方法:壓縮每個信源符號的平均比特數(shù)或信源的碼率。同樣多的信息用較少的碼率來傳源的碼率。同樣多的信息用較少的碼率來傳送,使單位時間內(nèi)傳送的平均信息量增加,送,使單位時間內(nèi)傳送的平均信息量增加,從而提高通信的有效性。從而提高通信的有效性。使序列中的各個符號盡可能地互相獨立,即解使序列中的各個符號盡可能地互相獨立,即解除相關(guān)性;除相關(guān)性;使編碼中各個符號出現(xiàn)的概率盡可能地相等,使編碼中各個符號出現(xiàn)的概率盡可能地相等,即概率均勻化。即概率均勻化。理論基礎(chǔ):是信息論中的兩個編碼定理:理論基礎(chǔ):是信息論中的兩個編碼定理:n 無失真編碼定理。只適用于離散信源。只適用于離散信源。n 限失真編碼定理。

5、對于連續(xù)信源,只能在對于連續(xù)信源,只能在失真受限制的情況下進行失真受限制的情況下進行限失真編碼。1110110100 0111011010 110010 10100 125. 0125. 025. 05 . 04321DCBAaaaa碼碼碼碼碼碼碼碼概概率率消消息息判斷以下碼字是否可分離?異前置碼即時碼可分離有延時可分離分離不可分離不可例例5.1.112121.()().()( )1nnniiaaap ap ap ap a設(shè)有離散無記憶信源設(shè)有離散無記憶信源12香農(nóng)編碼方法的步驟香農(nóng)編碼方法的步驟按信源符號的的順序排隊)(.)()(21napapap不妨設(shè)不妨設(shè)個個碼碼字字的的累累加加概概率率

6、表表示示第第,用用令令iijapapja1),(0)(011( )( ) 1jajiip ap a22log( )1 log( )iiiikp akp a 確定 ,使其滿足()ajiipaka把用二進制表示,用小數(shù)點后的 位作為 的碼字3405. 01 . 015. 02 . 025. 025. 0)(654321aaaaaaXPX設(shè)有一單符號離散無記憶信源設(shè)有一單符號離散無記憶信源試對該信源編二進制香農(nóng)碼。試對該信源編二進制香農(nóng)碼。11110595. 005. 01101485. 01 . 010137 . 015. 010035 . 02 . 001225. 025. 0002025. 0

7、)(654321aaaaaakapija碼字碼字10)()(jiijaapap617 .2)(iiikapKKmLKR2log()2.42325H X (X)89.75%HR對概率按m進行分組,使每組盡可能相等;給每個分組分配一個碼元;對每個分組重復(fù)2、3步,直到不可分為止。1234按信源符號的概率的順序排隊)(.)()(21napapap不妨設(shè)不妨設(shè)04. 008. 016. 018. 022. 032. 0)(654321aaaaaaXPX設(shè)有一單符號離散無記憶信源設(shè)有一單符號離散無記憶信源試對該信源編二進制費諾碼。試對該信源編二進制費諾碼。1a2a3a4a5a6a32. 022. 018

8、. 016. 008. 004. 0001010011000110110111011111編碼過程編碼過程)/(35. 2)(synbitXHmLKR2log%92.97)(RXH61)/(4 .2)(iiikapK符符號號比比特特可以看出本例中費諾碼有較高的編碼效率。費可以看出本例中費諾碼有較高的編碼效率。費諾碼比較適合于每次分組概率都很接近的信源。諾碼比較適合于每次分組概率都很接近的信源。00000111111a2a3a4a5a6a將信源符號順序排隊。給位,將其概率相加后合并作為一個新的符號,與剩下的符號一起,。給中概率最小的二個符號各分配一個碼位。重復(fù)步驟2、3直至概率和為1。21430

9、4. 005. 006. 007. 01 . 01 . 018. 04 . 0)(87654321aaaaaaaaXPX設(shè)有一單符號離散無記憶信源設(shè)有一單符號離散無記憶信源試對該信源編二進制赫夫曼碼。試對該信源編二進制赫夫曼碼。09. 013. 019. 023. 037. 06 . 00000000111111104. 005. 006. 007. 01 . 01 . 018. 04 . 01a2a3a4a5a6a7x8a1001011000001000101000100001100010001007a編碼過程編碼過程()2.55(/)H Xbit sym2.61K( )97.7%H xR。

10、率提高了可見,哈夫曼編碼的效則編碼效率若采用定長編碼,碼長7 .1285355. 2, 3KHuffman碼的編碼方法不是唯一的。碼的編碼方法不是唯一的。 首先,每次對縮減信源兩個最小的符號分配首先,每次對縮減信源兩個最小的符號分配“0”和和“1”碼元試任意的,所以可得到不同的碼字。只要碼元試任意的,所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性,即能得在各次縮減信源中保持碼元分配的一致性,即能得到可分離碼字。不同的碼元分配,得到的具體碼字到可分離碼字。不同的碼元分配,得到的具體碼字不同,但碼長,平均碼長都不變,所以沒有本質(zhì)區(qū)不同,但碼長,平均碼長都不變,所以沒有本質(zhì)區(qū)別。別。

11、 其次,若合并后的新符號的概率與其他符號的概率其次,若合并后的新符號的概率與其他符號的概率相等,從編碼的方法上來說,這幾個符號的次序可相等,從編碼的方法上來說,這幾個符號的次序可任意排列,編出的碼都是正確的,但得到的碼字不任意排列,編出的碼都是正確的,但得到的碼字不同。不同的編法得到的碼字長度也不盡相同。同。不同的編法得到的碼字長度也不盡相同。設(shè)有離散無記憶信源設(shè)有離散無記憶信源1 . 01 . 02 . 02 . 04 . 0)(54321xxxxxXPX用兩種不同的方法對其編二進制用兩種不同的方法對其編二進制huffmanhuffman碼碼方法一方法一方法二方法二信源符號信源符號ai概率概

12、率p(ai)碼字碼字Wi1碼長碼長Ki1碼字碼字Wi2碼長碼長Ki2a10.41 1002a20.2012102a30.20003112a40.1001040103a50.1001140113兩種不同的編碼方法得到的碼字和碼長的對比兩種不同的編碼方法得到的碼字和碼長的對比平均碼長和編碼效率平均碼長和編碼效率兩種編碼方法編出的碼字的碼長方差比較兩種編碼方法編出的碼字的碼長方差比較進行赫夫曼編碼時,為得到進行赫夫曼編碼時,為得到碼方差碼方差最小的最小的碼,應(yīng)使合并的信源符號位于縮減信源序碼,應(yīng)使合并的信源符號位于縮減信源序列列盡可能高的位置盡可能高的位置上,以減少再次合并的上,以減少再次合并的次數(shù)

13、,充分利用短碼。次數(shù),充分利用短碼。 游程序列游程 前面的幾種編碼方法主要時針對無記憶信源,對有前面的幾種編碼方法主要時針對無記憶信源,對有記憶信源,這些編碼方法的效率并不高,特別是對二記憶信源,這些編碼方法的效率并不高,特別是對二元相關(guān)信源,需要一些其它的方法。游程編碼就是這元相關(guān)信源,需要一些其它的方法。游程編碼就是這樣的方法,對相關(guān)信源的編碼更有效。樣的方法,對相關(guān)信源的編碼更有效。 指數(shù)字序列中連續(xù)出現(xiàn)相同符號的一段。在指數(shù)字序列中連續(xù)出現(xiàn)相同符號的一段。在二元信源中,連續(xù)的一段二元信源中,連續(xù)的一段00稱為一個稱為一個00游程,游程,00的個數(shù)稱為此游程的長度,同樣,也有的個數(shù)稱為此

14、游程的長度,同樣,也有11游程。游程。 用交替出現(xiàn)的用交替出現(xiàn)的00游程、游程、11游程的游程的長度,來表示任意二元序列而產(chǎn)生的一個新序列。它長度,來表示任意二元序列而產(chǎn)生的一個新序列。它和二元序列是一個一一對應(yīng)的變換。和二元序列是一個一一對應(yīng)的變換。二元序列:二元序列:000101110010001游程序列:游程序列:31132131二元序列二元序列赫夫赫夫曼編碼曼編碼 0:長度為1的“0”游程0000:長度為4的“0”游程 111:長度為3的“1”游程 長度為n的“1”游程11:1n多元序列也存在相應(yīng)的游程序列多元序列也存在相應(yīng)的游程序列 多元序列變換成游程序列再進行壓縮編多元序列變換成游

15、程序列再進行壓縮編碼沒有多大意義碼沒有多大意義 游游程編碼只適用于二元序列,對于多游游程編碼只適用于二元序列,對于多元信源,一般不能直接利用游程編碼元信源,一般不能直接利用游程編碼 因為游程變換是一一對應(yīng)的可逆變換,所以游程變換后,熵不變。組合編碼可獲得較高的編碼效率:游程編碼赫夫曼編碼“0”、“1”的概率分別為的概率分別為p0、p1長度長度i的的“0”游程概率:游程概率: 01001 iilp lpp長度長度j的的“1”游程概率:游程概率: 11110 jljp lpp00110 11iilpp lp11011 11jjlpp lp0p00010111001000131132131因為游程變

16、換是一一對應(yīng)的可逆變換,所以游程變換后,熵不變。游程編碼赫夫曼編碼組合編碼可獲得較高的編碼效率:010.6,0.4pp例例“0”游程長度信游程長度信源源二元序列:00010111001000011110011000101110001234()0.40.240.1440.0864LP L010203040.40.240.1440.0864llll000111100010011“1”游程長度信游程長度信源源111234()0.60.240.0960.0384LP L111213140.40.240.0960.0384llll010101101110011000101110010000111100110001011100,100,11000,0101111100001000100110,1111111010011100000111110010010011101信號序列碼序列冗余位冗余位信源序列中不攜帶信息的符號。多元信源序列:1211 12, , , ,mmmyyyx xxxx111000,000111,100,111,211121mmmxxxxx上面二元上面二元1表示信息位,表示信息位,0表示冗余位表示冗余位 冗余位序列游程編碼信息序

溫馨提示

  • 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. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論