信息論基礎(chǔ):第四章 無失真信源編碼_第1頁
信息論基礎(chǔ):第四章 無失真信源編碼_第2頁
信息論基礎(chǔ):第四章 無失真信源編碼_第3頁
信息論基礎(chǔ):第四章 無失真信源編碼_第4頁
信息論基礎(chǔ):第四章 無失真信源編碼_第5頁
已閱讀5頁,還剩92頁未讀, 繼續(xù)免費閱讀

下載本文檔

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

文檔簡介

1、信息傳輸系統(tǒng) 消息消息第二章:信息量第三章信道與信道容量第四章:無失真信源編碼第四章 無失真信源編碼信源編碼的概念 信源編碼的模型等長編碼變長編碼香農(nóng)費諾艾利斯編碼霍夫曼編碼費諾編碼信源編碼的概念 要把信源的信息高速度、高質(zhì)量地通過信道傳送給信宿,一般要通過信源編碼和信道編碼來完成。 研究信源編碼:只考慮有效性,不考慮可靠性信源編碼的概念 信源編碼的作用 例: 信源發(fā)送符號為 是,否 信道中能夠傳輸?shù)姆枮?,1 符號變換:用信道能傳輸?shù)姆杹泶硇旁窗l(fā)出的消息,使信源適合于信道的傳輸。信源編碼的概念 例:電報: 1:母親患癌癥,情況危急,請速歸。 2:母病危速歸例: 信源發(fā)送符號為 是,否

2、方案1: 0,1 方案2: 000,111 有效傳輸(冗余度壓縮)減少信源的剩余度 在不失真的條件下,用盡可能少的符號來傳送信源信息,提高信息傳送率。信源編碼的概念 一般而言,編碼就是用數(shù)字形式表示消息的過程。編碼實質(zhì)上是對要處理的源數(shù)據(jù)按一定的規(guī)則進行變換。這些數(shù)學(xué)方法和變換策略的目的都是力圖用盡可能少的符號或位來表示較多、較長的符號及消息。 具體來說,信源編碼就是根據(jù)信源的統(tǒng)計特性,對信源發(fā)出的消息進行編碼。信源編碼的概念 對于離散信源,如果信源的統(tǒng)計特性已知,便可直接進行編碼。 對于連續(xù)信源,應(yīng)根據(jù)采樣定理將連續(xù)信號離散化。連續(xù)信號經(jīng)過采樣和量化就變成了離散信號。將離散信號按一定規(guī)律與一

3、組代碼相對應(yīng)就是編碼 。無失真信源編碼的基本概念 根據(jù)能否在解碼后完全準確的恢復(fù)出原始消息(信息熵是否變換),將信源編碼分為無失真信源編碼和率失真信源編碼.信源編碼模型設(shè)信源概率空間為對此信源進行二進制編碼。 編碼的過程就是建立 之間元素的對應(yīng)關(guān)系。 和編碼的定義 如果一種編碼方案 如果信源連續(xù)發(fā)送S1S2S3三個符號,則該信源編碼的輸出為000110編碼的定義 假定這樣的碼經(jīng)信道傳輸,在接收端收到以“0”“1”為符號的序列。如000110 如果一種編碼方案 將此序列進行譯碼,能唯一地恢復(fù)原來的消息序列。S1S1S1S3信源編碼模型 信源空間為: 編碼符號表為,用 的符號對消息 進行編碼。消息

4、 與由 的符號組成的符號序列相對應(yīng),用公式表示為信源編碼模型叫做對應(yīng)消息 的碼字。稱為碼元。 稱為 的字長。 無失真信源編碼的基本概念碼的分類二元碼:碼符號集為 ,所有碼字都是由0、1組成的二元符號序列。r進制碼元:碼元符號集為 , 所有碼字都是由0、1.r-1組成的r進制數(shù)字序列。信源符號碼1碼2S1000S2111S3102S4113碼的分類根據(jù)編碼后碼字的長度信源符號碼1碼2碼3碼4S1000001S21101110S310000100S41111111000碼的分類根據(jù)碼字的情況信源符號碼1碼2碼3碼4S1000001S20101110S310000100S41111111000根據(jù)譯

5、碼恢復(fù)出的序列的情況唯一可譯碼(UDC) 任意有限長的碼字序列,只能被唯一地分割成一個個的碼字,且任一碼字只與唯一一個信源符號對應(yīng),便稱為唯一可譯碼。又稱單義碼。 非唯一可譯碼碼的分類例:碼的分類例:要保證無失真編碼,必須采用唯一可譯碼。碼的分類信源符號碼1碼2S10000S20101S31000S41111001110等長非奇異碼一定是唯一可譯碼。根據(jù)碼字相互關(guān)聯(lián)的情況非續(xù)長碼 任意一個碼字都不是另一個碼字的續(xù)長,稱為非續(xù)長碼。換句話說,不能在任意一個碼字后邊,添上一些碼元構(gòu)成一個新的碼字。 因此,當非續(xù)長碼碼字的最后一個碼字出現(xiàn)時,譯碼器能立即判斷一個碼字已經(jīng)結(jié)束,可以立即譯碼,又稱即時碼

6、或立即碼。碼的分類續(xù)長碼碼的分類信源符號碼4碼5S101S20101S3011001S41110001結(jié)論: 非續(xù)長碼一定是單義碼,而單義碼卻不一定是非續(xù)長碼。 0011101011碼的分類非奇異碼、唯一可譯碼、非續(xù)長碼的關(guān)系樹圖法樹圖法:所有碼字用碼樹描述出來。碼樹是一棵倒置的樹,最上端是根節(jié)點,從根節(jié)點出發(fā)不斷向下伸出樹枝,分支與碼符號一一對應(yīng)。一個節(jié)點繼續(xù)分支,稱為中間節(jié)點;一個節(jié)點不再繼續(xù)分支,稱為終端節(jié)點。 將信源符號對應(yīng)的節(jié)點用實心圓表示,從根節(jié)點到這個節(jié)點經(jīng)過的分支對應(yīng)的碼符號序列就是碼字;沒有與信源符號對應(yīng)的節(jié)點用空心圓表示對于碼 和用碼樹表示如下:樹圖法編碼:用樹圖法構(gòu)造非續(xù)

7、長碼,只要將信源符號全部對應(yīng)于終端節(jié)點,而不是中間節(jié)點即可。這樣就可以保證任何一個碼字都不是其它碼字的前綴 解碼:按照碼符號的順序,從根節(jié)點依次查詢到終端節(jié)點,就得到對應(yīng)的信源符號。再從根節(jié)點對剩下的碼符號序列做相同的處理,直到處理完碼符號序列中所有的碼符號。非續(xù)長碼 -樹圖構(gòu)造例:給定編碼符號表X=0,1,碼字W=W1,W2,W3,W4,字長分別是n1=1,n2=2 ,n3=n4=3,求非續(xù)長碼。 非續(xù)長碼 -樹圖構(gòu)造非續(xù)長碼 -樹圖構(gòu)造非續(xù)長碼不是唯一的。全部終端節(jié)點都代表碼字,這種情況叫做用盡的非續(xù)長碼。單義碼存在定理 設(shè)信源S的符號集為 ,碼符號集 ,又設(shè)碼字為 ,其碼長分別為 。則存

8、在單義碼的必要條件是: 滿足Kraft不等式,即 其中,q是碼字的個數(shù),r是編碼符號表的碼元個數(shù),ni 是字長。若上式成立,就一定能構(gòu)造一個r進制的唯一可譯碼。例:給定編碼符號表X=0,1,碼字W=W1,W2,W3,W4 = 0,01,10,011,分別由1,2,2,3個碼元構(gòu)成的碼字單義碼存在定理按照不等式可知,q=4,r=2,n1=1,n2=2 ,n3=2 ,n4=3 ,代入Kraft不等式左邊得單義碼存在定理 如W改為為0,10,110,111, 即n1=1,n2=2 ,n3=3 ,n4=3 如W改為為0,01,110,011, 即n1=1,n2=2 ,n3=3 ,n4=3 單義碼存在定

9、理 碼字不滿足克拉夫特不等式,則肯定不是唯一可譯碼。碼字滿足克拉夫特不等式,并不一定是唯一可譯碼,只是說存在這樣的碼長條件的唯一可譯碼。 例: 接受為0110 0,10,110,111 0,01,110,011 等長編碼等長碼:各個碼字碼長都相等的碼 可以編碼成 有效性: 更好 可靠性: 更好,提供糾錯功能對于等長碼,如果是非奇異碼,那么一定是唯一可譯碼等長編碼 信源符號集有2個符號,可以用 編碼,碼長為1; 信源符號有4個,碼長為1就不行了,必須用碼長為2的等長碼 設(shè)信源符號集中有符號q個;用二元碼進行編碼,碼長為 ,能夠提供的最多碼字為 個,因此要滿足等長碼碼長不能無限制縮短。 用 準則編

10、解碼過程非常簡單,但是編碼效率非常低,有效性很差。主要原因是沒有考慮到信源符號間的相關(guān)性。等長編碼 如:英文電報由26個字母和6個標點符號組成,共32個信源符號。用2元等長碼編碼,傳輸一個字母或標點,用5個2元碼符號,而5個2元碼符號能夠傳輸?shù)淖畲笮畔⒘渴?bit。實際統(tǒng)計,每個英文字符包含信息量1.4bit 等長編碼N次擴展碼:擴展前,一個信源符號編碼成一個碼字。N次擴展碼,就是把N個信源符號組成的序列,變換成N個碼字組成的序列N次等長擴展碼 如信源符號集 碼字為2次擴展后信源符號集2次擴展碼為N次等長擴展碼 進行N次擴展,共有 個信源符號, 需要 , 平均到擴展前每一個信源符號, 這樣看來

11、并沒有提高編碼效率 考慮到相關(guān)性,不用對所有 個信源符號進行編碼,有些信源符號不可能出現(xiàn),有些出現(xiàn)的概率非常小。碼長自然減少了N次等長擴展碼 對信源擴展的次數(shù)越多,利用信源的相關(guān)性就越充分,編出來的碼長平均到每個信源符號上平均碼長就越短,編碼效率就越高 對信源做無限次擴展之后,能夠?qū)⒕幋a效率提高到一個極限的程度等長編碼定理 一個平穩(wěn)離散信源的信息熵為 ,若對長為N的信源符號序列進行等長編碼,N長符號對應(yīng)的碼長為 ,設(shè)碼符號集中有r個碼符號。 對于任意的 ,只要滿足 當N足夠大時,可以實現(xiàn)幾乎無失真的編碼。反之,則不可能實現(xiàn)無失真的編碼等長編碼定理 編碼效率:描述編碼的優(yōu)劣編碼后信息率每個信源符

12、號的信息熵 定義編碼效率為碼的冗余度(編碼后的新信源的冗余度)等長編碼例:離散無記憶信源(DMS)用碼元表X=0,1對U的單符號進行等長編碼必須用碼長為3的等長碼 要無失真的信息傳輸,必須滿足編碼后信息率每個信源符號的信息熵 定義編碼效率為碼的冗余度(編碼后的新信源的冗余度)等長編碼定理 等長信源編碼的意義:通過不斷的擴展信源進行等長編碼,可以不斷提高編碼效率,當擴展次數(shù)N很大的時候,能夠達到最大的編碼效率 編碼后平均每個信源符號對應(yīng)的碼符號序列所能攜帶的最大的信息量,一定要大于等于信源本身的信息量等長編碼的缺陷 會產(chǎn)生一定的誤差:因為把一些小概率的組合去掉,沒有進行編碼擴展維數(shù)太大:要達到比

13、較高的編碼效率,擴展信源的維數(shù)需要很大 例:信源的概率分布 ,要達到0.96的編碼效率,錯誤率控制在 以內(nèi),信源需要擴展4130萬次,擴展后信源符號數(shù)為 個 變長編碼-平均碼長 對于變長編碼,不要求每個碼字的碼長都很小,但卻要求整個碼字集合的平均碼長較小變長編碼-平均碼長 顯然,要是平均碼長短,除了要縮短每一個碼字的碼長外,還要合理的分配長短碼,使概率較大的信源符號使用較短的碼,概率較小的信源符號使用較長的碼對于某一信源,若有一個唯一可譯碼,其平均碼長小于其它任何唯一可譯碼的平均碼長,則稱此碼為緊致碼,或最佳碼變長信源編碼定理(香農(nóng)第一定理)平穩(wěn)信源信息熵為 ,對長為N的信源符號序列進行編碼,

14、編碼后的平均碼長為 ,碼符號有r個,那么要做到無失真編碼,平均碼長必須滿足另一方面,一定存在唯一可譯碼,其平均碼長滿足:即:變長編碼-變長信源編碼定理 香農(nóng)第一定理給出了無失真信源編碼的平均碼長所能達到的極限值,但是并不是所有的信源編碼方法都能夠達到這個極限值。為了衡量各種編碼到達極限狀況的程度,定義了編碼效率:相應(yīng)的碼的冗余度為:變長編碼-變長信源編碼定理【例】信源用0、1構(gòu)成即時碼等長編碼變長編碼-變長信源編碼定理對信源進行二次擴展,并變成編碼變長編碼-變長信源編碼定理香農(nóng)第一定理的意義:通過不斷的擴展信源進行變長編碼,可以不斷提高編碼效率,當擴展次數(shù)N很大的時候,能夠達到最大的編碼效率

15、編碼后平均每個信源符號對應(yīng)的碼符號序列所能攜帶的最大的信息量,一定要大于等于信源本身的信息量經(jīng)典編碼方法 霍夫曼(Huffman)編碼香農(nóng)(Shannon)編碼費諾(Fano)編碼 霍夫曼(Huffman)編碼 霍夫曼編碼是1952年由霍夫曼提出的一種編碼方法。這種編碼方法的主導(dǎo)思想是根據(jù)源數(shù)據(jù)符號發(fā)生的概率進行編碼。在源數(shù)據(jù)中出現(xiàn)概率越高的符號,相應(yīng)的碼長越短;出現(xiàn)概率越小的符號,其碼長越長,從而達到用盡可能少的碼符號表示源數(shù)據(jù)。理論表明,在數(shù)據(jù)壓縮中,霍夫曼編碼方法是接近壓縮比上限的一種較好的編碼方法?;舴蚵℉uffman)編碼 霍夫曼編碼及其變種,在壓縮編碼領(lǐng)域中應(yīng)用的非常廣泛。數(shù)字圖

16、像 JPEG運動圖像 MPEG2、H.261、H.263 通信編碼 Modem ADSL (1)將n個信源U的各個符號ui按概率分布p(ui)以遞減次序排列起來。 霍夫曼(Huffman)編碼 編碼方法 (2)將兩個概率最小的信源符號合并成一個新符號,新符號的值為兩個信源符號值的和,從而得到只包含n1個符號的新信源,稱為U信源的縮減信源U1。 (3)把縮減信源U1的符號仍按概率以遞減次序排列,然后將其中兩個概率最小的符號合并成一個符號,這樣又形成了n2個符號的縮減信源U2。 霍夫曼(Huffman)編碼 (4)依次繼續(xù)下去,直至信源最后只剩下個符號為止。 (5)將每次合并的兩個信源符號分別用0

17、和1碼符號表示。 (6)從最后一級縮減信源開始,向前返回,就得出各信源符號所對應(yīng)的碼符號序列,即得各信源符號對應(yīng)的碼字。 霍夫曼(Huffman)編碼霍夫曼編碼例1編成2元霍夫曼碼,求編碼效率霍夫曼編碼例1霍夫曼編碼例1霍夫曼編碼例1霍夫曼編碼例1消息概率編碼碼長S10.4002S20.2102S30.2112S40.10103S50.10113例:離散無記憶信源: 對應(yīng)的霍夫曼編碼如圖所示: 霍夫曼編碼-課堂作業(yè)消息概率編碼碼長U10.501U20.25102U30.1251103U40.1251113霍夫曼編碼-課堂作業(yè)霍夫曼編碼對于同一個信源,霍夫曼編碼的方式有很多種:左分支編0、右分支

18、編1;左分支編1、右分支編0;左右分支混編編出來的平均碼長都一樣霍夫曼編碼 合并后的新信源符號與其它信源符號概率相同時,合并后的符號插入到什么位置,編出來的碼也是不一樣的:例1中是將新信源符號插入到最前面例2將新信源符號插入到最后面霍夫曼編碼例2編成2元霍夫曼碼,求編碼效率霍夫曼編碼例2霍夫曼編碼例2霍夫曼編碼例2霍夫曼編碼例2消息概率編碼碼長S10.411S20.2012S30.20003S40.100104S50.100114霍夫曼編碼兩種編碼方式的編碼效率相等。第一種方法只有兩種碼長:2、3;第二種方法有4種碼長14第一種方法方差比較小,更接近于等長碼,更簡單,更容易實現(xiàn)霍夫曼編碼擴展到

19、r元霍夫曼編碼,只要每次取r個最小概率的信源符號即可編成3元霍夫曼碼,求編碼效率霍夫曼編碼例3霍夫曼編碼例3霍夫曼編碼例3消息概率編碼碼長S10.411S20.221S30.2002S40.1012S50.1022霍夫曼編碼解碼 霍夫曼編碼的所有碼字都在碼樹的終端節(jié)點上,所以霍夫曼碼是即時碼。 因此霍夫曼碼的解碼可以使用即時碼的解碼方法。從碼樹的根節(jié)點開始,按碼符號對應(yīng)的分支逐步向下,直到找到一個終端節(jié)點。再從根節(jié)點開始對剩下的碼符號序列做相同的處理,直到處理完所有的碼符號?;舴蚵幋a解碼 解碼100101100011霍夫曼編碼解碼 優(yōu)點就是編碼效率很好,是最佳編碼缺點是容錯性能非常差,只要有

20、1位出現(xiàn)了錯誤,將可能導(dǎo)致后面的解碼全部錯誤或翻譯不出來費諾編碼霍夫曼編碼在構(gòu)造碼樹的時候,是從下層節(jié)點開始,逐級向上直到根節(jié)點的;而費諾編碼正好相反,是由根節(jié)點出發(fā),直到終端節(jié)點。費諾編碼的思想就是使編碼后的碼集盡可能的等概率分布。費諾碼不是最佳編碼方法,但是有時候也能編出最佳碼。費諾編碼 將信源符號按概率大小遞減排列,按照概率之和分為大致相等的r組(2組),分別編以0、1r-1(0、1),再分別對r個(2個)組做相同的處理,直到每個組只有一個信源符號為止。例:求2元費諾碼及編碼效率費諾編碼費諾編碼消息概率編碼碼長S10.32002S20.22012S30.18102S40.161103S50.0811104S60.0411114課堂練習(xí)離散無記憶

溫馨提示

  • 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)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論