信息論編碼作業(yè)

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

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

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

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

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

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

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

8、160; 對應(yīng)的二進制數(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 費諾編碼（1）費諾編碼屬于概率匹配編碼，但它一般也不是最佳的編碼方法，只有當(dāng)信源的概率分布呈現(xiàn) 分布形式的條件下，才能達(dá)到最佳碼的性能。（2）費諾碼的編碼步驟如下：

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

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

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

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

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

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