1、無失真信源編碼 無失真信源編碼 信源編碼的定義 指定能夠滿足信道特性（適合于信道傳輸）的符號序列（碼序列），指定能夠滿足信道特性（適合于信道傳輸）的符號序列（碼序列），來代表信源輸出的消息。來代表信源輸出的消息。 完成編碼功能的器件成為編碼器。完成編碼功能的器件成為編碼器。,X)(2121niLiLxxxXXXXX信源編碼器信源編碼器)(21kjkYYYYY)/(ijxyp碼元（信道基本符號集合）碼元（信道基本符號集合）碼長碼長,21mjyyyY碼組碼組第1頁/共26頁信源編碼器的性能指標(biāo) 信源編碼速率R的定義：平均傳輸一個信源符號所需要的碼字的最大信息量。 信源編碼效率：RXH)(LmKR2

2、log1log)(loglog)(log)(22221mxpkmxpikkxpkiiiiniii條消息編成的碼長。表示第其中：第2頁/共26頁信源編碼器的性能指標(biāo) 要使信源編碼器的效率高，需減小編碼速率，即減少平均碼長。 信息率越小越好，最小能小到多少才能做到無失真譯碼呢？ 這些問題就是最佳變長信源編碼定理的研究范疇。第3頁/共26頁信源編碼 5.1 離散信源編碼 5.2 連續(xù)信源編碼 5.3 相關(guān)信源編碼 5.4 變換編碼第4頁/共26頁5.15.1 信源最佳變長編碼一、最佳變長編碼定理：若信源有n條消息，第i條消息出現(xiàn)的概率為pi，且p1=p2=pn，且第i條消息對應(yīng)的碼長為ki，并有k1

3、=k2=k進(jìn)制編碼） （1）將pi從大至小排列（2）將概率分為2組（k組），使每組概 率盡可能相等或接近（3）給每組分配一位碼元（4）將各分組按照相同原則繼續(xù)劃分，重復(fù)（2） （3），直到概率不可分為止。（5）從左至右依次讀出碼元形成碼字。第14頁/共26頁例：對上例的信源進(jìn)行二進(jìn)制費(fèi)諾編碼，并求編碼速率和效率。第15頁/共26頁費(fèi)諾編碼的性能指標(biāo)的計(jì)算： 平均碼長： 編碼速率： 編碼效率： 比較：費(fèi)諾碼有較高的編碼效率，適合每次分組概率都很接近的信源 61/45. 2iiikpk符號碼元45. 26112loglog22ikpLmKRii%91.9845. 242. 2)(RXH第16頁/共

4、26頁Huffman哈夫曼編碼方法（二進(jìn)制 ） 1、將pi從大至小排列 2、將概率最小的兩個消息編成0和1，并求其概率和 3、將新求得的概率和與其他剩余消息，重新降序排列 4、重復(fù)2和3，直到和為1 5、從右至左依次讀出碼元形成碼字。 第17頁/共26頁例題 要求：對該信源進(jìn)行二進(jìn)制哈夫曼編碼，求每條消息對應(yīng)的二進(jìn)制碼組，并計(jì)算平均碼長和編碼效率。05.01.015.02.025.025.0)(654321xxxxxxXPX第18頁/共26頁10.5510.150.30解：消息編碼編碼碼長碼長112002012100310104101146x2x3x4x5x0.250.250.20.150.1

5、00.05010010.45101結(jié)束1x第19頁/共26頁Huffman編碼的性能指標(biāo)的計(jì)算：u平均碼長：u編碼速率：u編碼效率： 61/45. 2iiikpk消息碼元符號/45. 212loglog22bitKLmKR%91.9845. 242. 2)(RXH第20頁/共26頁思考：1、三進(jìn)制Huffman編碼如何編？2、K進(jìn)制呢？第21頁/共26頁離散無記憶信源變長編碼小結(jié)定長變長定長變長，kku提高編碼效率u哈夫曼編碼集合不唯一，但平均碼長和編碼效率不變哈夫曼編碼集合不唯一，但平均碼長和編碼效率不變 第22頁/共26頁 變長編碼的缺點(diǎn)： 需要大量緩沖設(shè)備來存儲這些變長碼，再以恒定的速率

6、進(jìn)行傳送。需要大量緩沖設(shè)備來存儲這些變長碼，再以恒定的速率進(jìn)行傳送。 容易引起誤碼擴(kuò)散容易引起誤碼擴(kuò)散第23頁/共26頁離散有記憶信源的變長編碼離散有記憶信源的變長編碼 二元平穩(wěn)相關(guān)信源：采用游程編碼。 適用于連適用于連0 0或連或連1 1較多的序列。較多的序列。 游程：數(shù)字序列中連續(xù)出現(xiàn)相同符號的一段。游程：數(shù)字序列中連續(xù)出現(xiàn)相同符號的一段。 例：000101110010001。求其游程編碼。 設(shè)二元游程總是從設(shè)二元游程總是從0 0開始，則游程編碼序列為開始，則游程編碼序列為3113213131132131 且由游程序列很容易恢復(fù)原始二元信源序列。且由游程序列很容易恢復(fù)原始二元信源序列。 可見游程變換是一一對應(yīng)的可逆變換。可見游程變換是一一對應(yīng)的可逆變換。 游程變換減弱了原序列符號之間的相關(guān)性，并把二元序列變成多元序列，提高了通信效率和