信息論編碼作業(yè)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上信息論編碼一信息論的認(rèn)識(shí)1.消息是信息的載荷者。信息是抽象的，消息是具體的。要研究信息，還得從研究消息入手。2.由于信源發(fā)送什么消息預(yù)先是不可知的，只能用概率空間來(lái)描述信源3.單符號(hào)信源：輸出是單個(gè)符號(hào)（代碼）的消息n 離散信源n 連續(xù)信源4.平穩(wěn)隨機(jī)序列信源：信源輸出的消息由一系列符號(hào)序列所組成，可用N維隨機(jī)矢量 X(X1,X2,XN)描述，且隨機(jī)矢量X 的各維概率分布都與時(shí)間起點(diǎn)無(wú)關(guān)-平穩(wěn)！n 離散平穩(wěn)信源n 連續(xù)平穩(wěn)信源n 無(wú)記憶（獨(dú)立）離散平穩(wěn)信源n 有記憶信源n m階馬爾可夫信源5.隨機(jī)波形信源l 信息是信息論中最基本、最重要的概念，既抽象又復(fù)雜l 信息在日

2、常生活中被認(rèn)為是“消息”、“知識(shí)”、“情報(bào)”等 l “信息”不同于消息（在現(xiàn)代信息論形成之前，信息一直被看作是通信中消息的同義詞，沒(méi)有嚴(yán)格的數(shù)學(xué)含義），消息是表現(xiàn)形式，信息是實(shí)質(zhì)；l “信息”不同于情報(bào)，情報(bào)的含義比“信息”窄的多，一般只限于特殊的領(lǐng)域，是一類特殊的信息；l 信息不同于信號(hào)，信號(hào)是承載消息的物理量；l 信息不同于知識(shí)，知識(shí)是人們根據(jù)某種目的,從自然界收集得來(lái)的數(shù)據(jù)中整理、概括、提取得到的有價(jià)值的信息，是一種高層次的信息。 6.互信息量 I(xi ; yj)：收到消息yj 后獲得關(guān)于xi的信息量即：互信息量表示先驗(yàn)的不確定性減去尚存的不確定性，這就是收信者獲得的信息量對(duì)于無(wú)干擾信

3、道，I(xi ; yj) = I(xi)；二我們學(xué)到了1.離散信源熵和互信息 定義具有概率為p（xi）的符號(hào)xi的自信息量為 I(xi)=-logp（xi）信源輸出的整體特征用平均自信息量，表示本身的特征用信源熵。2.信道與信道容量信道分類：根據(jù)用戶數(shù)量可分為單用戶信道和多用戶信道 根據(jù)信道輸入端和輸出端的關(guān)系可分為無(wú)反饋信道和反饋信道。 根據(jù)信道參數(shù)與時(shí)間的關(guān)系可分為固定參數(shù)信道和時(shí)變參數(shù)信道。 根據(jù)信道中所受噪聲種類的不同，可分為隨即差錯(cuò)信道和突發(fā)差錯(cuò)信道。 根據(jù)輸入輸出的特點(diǎn)可分為離散信道、連續(xù)信道、半離散半連續(xù)信道、波形信道等。3.信源編碼 編碼碼樹(shù)（1） r進(jìn)制碼樹(shù)對(duì)應(yīng)r進(jìn)制編碼（2

4、） 碼序列為樹(shù)根到每個(gè)終端結(jié)點(diǎn)的樹(shù)枝的序號(hào)（3） n級(jí)終端節(jié)點(diǎn)對(duì)應(yīng)一個(gè)碼字最多有n個(gè)碼字符號(hào)（4） q個(gè)終端節(jié)點(diǎn)對(duì)應(yīng)q個(gè)不同碼字一.編碼器模型 由于信源編碼可以不考慮抗干擾問(wèn)題，所以它的數(shù)學(xué)模型比較簡(jiǎn)單。下圖為一個(gè)編碼器模型:4.碼樹(shù) 形狀：倒立樹(shù) 概念：樹(shù)枝：碼樹(shù)上的線段 結(jié)點(diǎn)：樹(shù)枝的兩端點(diǎn) 樹(shù)根 N級(jí)結(jié)點(diǎn) R進(jìn)制碼樹(shù) 終端節(jié)點(diǎn)5.編碼（1）變長(zhǎng)碼 若一組碼中碼字的碼長(zhǎng)各不相同（即碼字長(zhǎng)度 不等），則稱為變長(zhǎng)碼 . 如表中“編碼1”為等長(zhǎng)碼，“編碼2”為變長(zhǎng)碼。信源符號(hào)si符號(hào)出現(xiàn)概率p(si)編碼1編碼2s1p(s1)000s2p (s2)0101s3p (s3)10001s4p (s4)

5、11101（2）分組碼 若每個(gè)信源符號(hào)按照固定的碼表映射成一個(gè)碼字，則稱為分組碼。否則就是非分組碼. 如果采用分組編碼方法，需要分組碼具有某些屬性，以保證在接收端能夠迅速而準(zhǔn)確地將接收到的碼譯成與信源符號(hào)對(duì)應(yīng)的消息。下面討論分組碼的一些直觀屬性。（3）非奇異碼和奇異碼 若一組碼中所有碼字都不相同(即所有信源符號(hào)映射到不同的碼符號(hào)序列)，則稱為非奇異碼。反之，則為奇異碼。如表中的“編碼2”是奇異碼，其他碼是非奇異碼。（4）惟一可譯碼 若任意一串有限長(zhǎng)的碼符號(hào)序列只能被惟一地譯成所對(duì)應(yīng)的信源符號(hào)序列，則此碼稱為惟一可譯碼（或稱單義可譯碼）。否則就稱為非惟一可譯碼或非單義可譯碼。 若要使某一碼為惟一

6、可譯碼，則對(duì)于任意給定的有限長(zhǎng)的碼符號(hào)序列，只能被惟一地分割成一個(gè)個(gè)的碼字。（5）綜上所述，可將碼作所示的分類：6.碼樹(shù)如下圖 樹(shù)根èç碼字起點(diǎn)； 樹(shù)枝數(shù)èç碼的進(jìn)制數(shù)； 節(jié)點(diǎn)èç碼字或碼字的一部分； 終端節(jié)點(diǎn)èç碼字； 階數(shù)èç碼長(zhǎng)； 非整樹(shù)èç變長(zhǎng)碼； 整樹(shù)èç等長(zhǎng)碼。 變長(zhǎng)碼往往在碼長(zhǎng)的平均值不很大時(shí)，就可編出效率很高而且無(wú)失真的碼，其平均碼長(zhǎng)受香農(nóng)第一定理所限定，即： 若對(duì)信源離散無(wú)記憶信源S的N次擴(kuò)展信源 進(jìn)行編碼，則總可以找到一種編碼方法，構(gòu)成

7、惟一可譯碼，使信源S中每個(gè)信源符號(hào)所需的平均碼長(zhǎng)滿足：7.編碼分類： 香濃編碼（1） 香農(nóng)第一定理指出，可選擇每個(gè)碼字的長(zhǎng)度滿足關(guān)系式： 或：（2） é x ù 表示不小于 x 的整數(shù)。按不等式選擇的碼長(zhǎng)所構(gòu)成的碼稱香農(nóng)碼。香農(nóng)碼滿足克拉夫特不等式，所以一定存在對(duì)應(yīng)碼字的長(zhǎng)度的惟一可譯碼。（3）香農(nóng)碼的編碼步驟如下： 【1】將個(gè)信源符號(hào)按概率遞減的方式進(jìn)行排列： 【2】按香農(nóng)不等式計(jì)算出每個(gè)信源符號(hào)的碼長(zhǎng) ； 【3】為了編成惟一可譯碼，計(jì)算第i個(gè)信源符號(hào)的累加概率 【4】將累加概率 用二進(jìn)制數(shù)表示。 【5】取 對(duì)應(yīng)二進(jìn)制數(shù)的小數(shù)點(diǎn)后位構(gòu)成該信源符號(hào)的二進(jìn)制碼字。信源符號(hào)&#

8、160; 對(duì)應(yīng)的二進(jìn)制數(shù)  碼字 0.2000.0002.343000 0.190.20.00112.413001 0.180.390.01102.483011 0.170.570.10012.563100 0.150.740.10112.743101 0.100.890.11103.3441110 0.010.990.6.667 費(fèi)諾編碼（1）費(fèi)諾編碼屬于概率匹配編碼，但它一般也不是最佳的編碼方法，只有當(dāng)信源的概率分布呈現(xiàn) 分布形式的條件下，才能達(dá)到最佳碼的性能。（2）費(fèi)諾碼的編碼步驟如下：

9、【1】信源符號(hào)以概率遞減的次序排列起來(lái)； 【2】將排列好的信源符號(hào)按概率值劃分成兩大組，使每組的概率之和接近于相等，并對(duì)每組各賦予一個(gè)二元碼符號(hào)“0”和“1”； 【3】將每一大組的信源符號(hào)再分成兩組，使劃分后的兩個(gè)組的概率之和接近于相等，再分別賦予一個(gè)二元碼符號(hào)； 【4】依次下去，直至每個(gè)小組只剩一個(gè)信源符號(hào)為止；【5】信源符號(hào)所對(duì)應(yīng)的碼字即為費(fèi)諾碼。（3）例:將下列消息按二元費(fèi)諾碼方法進(jìn)行編碼。 解:其編碼過(guò)程如下頁(yè)： 碼的性能分析： 此信源的熵 (比特符號(hào))， 而碼的平均長(zhǎng)度 (二元碼符號(hào)符號(hào)) 顯然，該碼是緊致碼，編碼效率： 該碼之所以能達(dá)到最佳，是因?yàn)樾旁捶?hào)的概率分布正好滿足式，否則

10、，在一般情況下是無(wú)法達(dá)到編碼效率等于“1”的。 （4）費(fèi)諾碼具有如下的性質(zhì)： 費(fèi)諾碼的編碼方法實(shí)際上是一種構(gòu)造碼樹(shù)的方法，所以費(fèi)諾碼是即時(shí)碼。 費(fèi)諾碼考慮了信源的統(tǒng)計(jì)特性，使概率大的信源符號(hào)能對(duì)應(yīng)碼長(zhǎng)較短的碼字，從而有效地提高了編碼效率。 費(fèi)諾碼不一定是最佳碼。因?yàn)橘M(fèi)諾碼編碼方法不一定能使短碼得到充分利用:當(dāng)信源符號(hào)較多時(shí)，若有一些符號(hào)概率分布很接近時(shí)，分兩大組的組合方法就會(huì)很多?？赡苣撤N分大組的結(jié)果，會(huì)使后面小組的“概率和”相差較遠(yuǎn)，從而使平均碼長(zhǎng)增加。 r 元費(fèi)諾碼 前面討論的費(fèi)諾碼是二元費(fèi)諾碼，對(duì)r元費(fèi)諾碼，與二元費(fèi)諾碼編碼方法相同，只是每次分組時(shí)應(yīng)將符號(hào)分成概率分布接近的r個(gè)組。 19

11、52年，霍夫曼（Huffman）提出了一種構(gòu)造最佳碼的方法，這是一種最佳的逐個(gè)符號(hào)的編碼方法，一般就稱作霍夫曼碼。 設(shè)信源 ，其對(duì)應(yīng)的概率分布為 ，則對(duì)二元霍夫曼碼而言，其編碼步驟如下： 1）將q個(gè)信源符號(hào)按概率遞減的方式排列起來(lái)； 2）用“0”、“1”碼符號(hào)分別表示概率最小的兩個(gè)信源符號(hào)，并將這兩個(gè)概率最小的信源符號(hào)合并成一個(gè)新的符號(hào)，從而得到只包含q-1個(gè)符號(hào)的新信源，稱之為S信源的S1縮減信源； 3）將縮減信源中的符號(hào)仍按概率大小以遞減次序排列，再將其最后兩個(gè)概率最小的符號(hào)合并成一個(gè)符號(hào)，并分別用“0”、“1”碼符號(hào)表示，這樣又形成了由q-2個(gè)符號(hào)構(gòu)成的縮減信源S2； 4）依次繼續(xù)下去，

12、直到縮減信源只剩下兩個(gè)符號(hào)為止，將這最后兩個(gè)符號(hào)分別用“0”、“1”碼符號(hào)表示； 5）從最后一級(jí)縮減信源開(kāi)始，向前返回，沿信源縮減方向的反方向取出所編的碼元，得出各信源符號(hào)所對(duì)應(yīng)的碼符號(hào)序列，即為對(duì)應(yīng)信源符號(hào)的碼字。 :對(duì)離散無(wú)記憶信源 哈弗曼編碼 （1） 進(jìn)行霍夫曼編碼。 解:編碼過(guò)程如表所示： 【1】將信源符號(hào)按概率大小由大至小排序。 【2】從概率最小的兩個(gè)信源符號(hào)和開(kāi)始編碼，并按一定的規(guī)則賦予碼符號(hào)，如下面的信源符號(hào)（小概率）為“1”，上面的信源符號(hào)（大概率）為“0”。若兩支路概率相等，仍為下面的信源符號(hào)為“1” 上面的信源符號(hào)為“0”。 【3】將已編碼兩個(gè)信源符號(hào)概率合并，重新排隊(duì)，編

13、碼。 【4】重復(fù)步驟3）直至合并概率等于“1.0”為止。 【5】從概率等于“1.0”端沿合并路線逆行至對(duì)應(yīng)消息編碼.（2）按霍夫曼碼的編碼方法，可知這種碼有如下特征： 它是一種分組碼：各個(gè)信源符號(hào)都被映射成一組固定次序的碼符號(hào)； 它是一種惟一可解的碼：任何碼符號(hào)序列只能以一種方式譯碼； 它是一種即時(shí)碼：由于代表信源符號(hào)的節(jié)點(diǎn)都是終端節(jié)點(diǎn)，因此其編碼不可能是其它終端節(jié)點(diǎn)對(duì)應(yīng)的編碼的前綴，霍夫曼編碼所得的碼字一定是即時(shí)碼。所以一串碼符號(hào)中的每個(gè)碼字都可不考慮其后的符號(hào)直接解碼出來(lái)。（3）霍夫曼碼的譯碼：對(duì)接收到的霍夫曼碼序列可通過(guò)從左到右檢查各個(gè)符號(hào)進(jìn)行譯碼。三總結(jié)1.信息通過(guò)信道傳輸?shù)叫潘薜倪^(guò)程

14、即為通信。要做到既不失真又快速地通信，需要解決兩個(gè)問(wèn)題： 在不失真或允許一定失真條件下，如何提高信息傳輸速度-這是本章要討論的信源編碼問(wèn)題. 在信道受到干擾的情況下，如何增加信號(hào)的抗干擾能力，同時(shí)又使得信息傳輸率最大-這是下章要討論的信道編碼問(wèn)題.2.一般來(lái)說(shuō)，抗干擾能與信息傳輸率二者相互矛盾。然而編碼定理已從理論上證明，至少存在某種最佳的編碼能夠解決上述矛盾，做到既可靠又有效地傳輸信息。3.信源雖然多種多樣，但無(wú)論是哪種類型的信源，信源符號(hào)之間總存在相關(guān)性和分布的不均勻性，使得信源存在冗余度。信源編碼的目的就是要減少冗余，提高編碼效率。4.許多信號(hào)變換方法都可用于變換編碼。需要注意的是數(shù)據(jù)的壓縮并不是在變換步驟取得的，而是在量化變換系數(shù)時(shí)取得的，因?yàn)樵趯?shí)際編碼時(shí)，對(duì)應(yīng)于方差很小的分量，往往可以不傳送，從而使數(shù)據(jù)得到壓縮。對(duì)某一個(gè)給定的編碼應(yīng)用，如何選擇