第五章信源編碼編碼定義及定長編碼

第五章信源編碼編碼定義及定長編碼第1頁，共52頁?；仡櫍簽槭裁催M行信源編碼？理論上，信源傳送信息所需要的信息率：極限熵H∞（X）或信息率失真函數R（D）.極限熵H∞（X）：多符號離散平穩(wěn)信源實際上就是原始信源在不斷地發(fā)出符號，隨著信源之間的依賴關系（即信源的相關性）變多，信源的實際熵越小（第二章P32-33證明），越趨于H∞（X）。所以H∞（X）是離散平穩(wěn)有記憶信源平均每發(fā)一個符號提供的信息量的最小值。第2頁，共52頁。信息率失真函數R（D）：從允許一定失真的條件下，我們去尋找可以用較小的信息率來傳送信息，即去掉某些不必要的成分，這時得到的信息率的最小值是R（D）。由此可見，極限熵H∞（X）或信息率失真函數R（D）是理論上傳送信息的最小值。而實際上，信源發(fā)出消息時包含了多余信息，即存在冗余度，冗余度體現了信源輸出信號的信息攜帶效率。第3頁，共52頁。冗余度定義：衡量信源發(fā)出消息時包含了多余信息的物理量來源：1.信源符號的相關性。相關程度越大，信源的實際上越小，越趨向于H∞（X）。2.信源符號分布的不均勻性。等概率分布時信源熵最大，不均勻分布時，信源熵減小。當各符號之間不存在依賴關系且為等概率分布時，信源實際熵趨于最大熵H0（X）

第4頁，共52頁。下面，以英文為例，計算文字信源的冗余度：首先給出英文字母（含空檔）出現概率如下：第5頁，共52頁。下面，首先求得獨立等概率情況，即其次，計算獨立不等概率情況，再次，若僅考慮字母有一維相關性，求H2最后，利用統(tǒng)計推斷方法求出，由于采用的逼近的方法和所取的樣本的不同，推算值也有不同，這里采用Shannon的推斷值。第6頁，共52頁。采用等概率下傳送方式，計算得這樣，可以計算出R=0.71。這一結論說明，英文信源，從理論上看71％是多余成分。直觀地說100頁英文書，理論上看僅有29頁是有效的，其余71頁是多余的。正是由于這一多余量的存在，才有可能對英文信源進行壓縮編碼。消息的冗余，特別是大量的冗余，為我們提高通信效率，壓縮信號容量提供了基礎。為了提高傳輸效率，對大量冗余進行壓縮，即信源編碼。第7頁，共52頁。信源編碼信源編碼是以提高通信的有效性為目的編碼。采用的一般方法是壓縮每個信源符號的平均比特數。同樣多的信息用較少的信息率來傳送，使單位時間內傳送的平均信息量增加，從而提高通信的有效性。信源編碼的目的就是要減少冗余，提高編碼效率。第8頁，共52頁。信源編碼的基本途徑（即消除冗余度來源的途徑）有兩個：使序列中的各個符號盡可能地互相獨立，即解除相關性；使編碼中各個符號出現的概率盡可能地相等，即概率均勻化。第9頁，共52頁。

根據能否在解碼后完全準確的恢復出原始消息（可逆）分為：

無失真信源編碼限失真信源編碼無失真編碼只適用于離散信源；對于連續(xù)信源，只能在失真受限制的情況下進行限失真編碼。前者主要用于文字、數據信源的壓縮;后者主要用于圖像、語音信源的壓縮。第10頁，共52頁。一般地：由于這些定理都要求符號數很大（參考極限熵H∞（X）序列長趨向于∞）才能使它的值接近所規(guī)定的值，因而這些定理被稱為極限定理。1.無失真信源編碼定理稱為第一極限定理；2.信道編碼定理(包括離散和連續(xù)信道)稱為第二極限定理；3.限失真信源編碼定理稱為第三極限定理。這些定理的完善化，是香農信息論的主要內容。第11頁，共52頁。編碼定理不但證明了必然存在一種編碼方法，使代碼的平均長度可任意接近但不能低于符號熵，而且還闡明了達到這目標的途徑，就是使概率與碼長匹配。例如之后學習的變長編碼，使出現概率小的信源符號用短碼編，出現概率大的用長的碼編，這樣就可以使平均每個信源符號的輸出符號降低。以哈夫曼編碼為例：第12頁，共52頁。哈夫曼編碼的編碼結果可以看出，信源出現符號小的a7編碼長度是4位，信源出現符號小的a1編碼長度是2位，平均碼長計算得2.72碼元/符號，輸出符號碼長減小。第13頁，共52頁。信源編碼（主要內容）信源編碼定理信源編碼基本概念定長信源編碼變長信源編碼信源編碼方法離散信源編碼連續(xù)信源編碼相關信源編碼變換編碼第14頁，共52頁。5.1編碼的定義分組碼定義：將信源消息分成若干組，即符號序列Xi=[xi1,xi2,...,xiL],序列中的每一個符號取自于符號集A，xil屬于{a1，

a2，···，

ai，···，

an}，而每個符號序列Xi依照固定的碼表映射成一個碼字Yi，這樣的碼稱為分組碼，有時也叫塊碼。分組碼百科定義：它把信源待發(fā)的信息序列按固定的κ位一組劃分成消息組,再將每一消息組獨立變換成長為n(n＞κ)的二進制數字組,稱為碼字。如果消息組的數目為M(顯然M≤2κ),由此所獲得的M個碼字的全體便稱為碼長為n、信息數目為M的分組碼,記為【n，M】。

第15頁，共52頁。只有分組碼才有對應的碼表，而非分組碼中不存在碼表。編碼定義：二元信道（基本符號0,1）中，若將信源X通過這樣的二元信道傳輸，就必須把信源符號ai變換成有1.0符號組成的碼符號序列，這個過程就是信源編碼。編碼的廣泛定義：編碼是信息從一種形式或格式轉換為另一種形式的過程也稱為計算機編程語言的代碼簡稱編碼。用預先規(guī)定的方法將文字、數字或其它對象編成數碼，或將信息、數據轉換成規(guī)定的電脈沖信號。我們之后介紹的是二元信道中的編碼。第16頁，共52頁。信源編碼器－示意圖信源符號集X＝[a1,a2,…an]：代表信源發(fā)出的消息，共有n個信源符號。碼表（碼符號集）碼符號集中的元素稱為碼元或者碼符號，適合信道傳輸。碼字集合Y=[W1,W2,…Wn]：與信源符號一一對應，碼字由碼符號序列組成。第17頁，共52頁。一個簡單的編碼實例【例】對學生的成績等級進行編碼，分為優(yōu)、良、中、差4個等級。信源符號集X＝[a1,a2,…an]={優(yōu)、良、中、差}用二元碼，碼符號集合為{0,1}碼字集合為Y=[W1,W2,…Wn]={00,01,10,11}編碼過程：00代表優(yōu)，01代表良，10代表中，11代表差。每一個碼字都是2個碼符號組成的序列。第18頁，共52頁。第19頁，共52頁。(1)奇異碼與非奇異碼書中定義：若信源符號和碼字是一一對應的，則該碼是非奇異碼；反之，是奇異碼。這個定義可以理解為數學意義上的映射，每一個符號均可以在碼字集合中找到唯一對應的碼。華中科技大學書中定義：若一種碼中的所有碼字都互不相同，則稱此分組碼為非奇異碼，否則稱為奇異碼?？梢钥闯?，表中碼1是奇異碼，有兩個11碼。其他是非奇異碼第20頁，共52頁。（2）唯一可譯碼書中定義：任意有限長序列，只能被分割成一個個的碼字，便可以稱為唯一可譯碼。例如給定一個信源,編碼后的碼字有{0,，10，11}，就是說信源只能變出這三種碼字。任意給定一個序列100111000，按照分割成信源定義的三種碼字可以分成10,0,11,10,0,0唯一一種方式。任何其他分割法都會產生信源不能發(fā)出的碼字。這種碼字就是唯一可譯碼碼1是奇異碼，必定不能唯一可譯，因為如果分到11碼，就不確定是信源發(fā)的a2還是a4碼2也不是唯一可譯碼，看碼2的碼字特點，若是序列中有一段碼是00，我們即可以分成00對應a3，也可以分成0,0對應發(fā)兩次a1.碼3是唯一可譯碼。因為分解時只要遇到1就看后面有幾個0，確定唯一譯碼第21頁，共52頁。（3）非即時碼和即時碼書中定義：如果接受端收到一個完整的碼字后，不能立即譯碼，還需要等下一個碼字開始接受后才能判斷是否可以譯碼，這樣的碼叫做非即時碼。一個唯一可譯碼成為即時碼的充要條件是其中任何一個碼字都不是其它碼字的前綴（前綴問題）這里是建立在唯一可譯碼基礎上的，表中碼3碼4是唯一可譯碼。碼3，接到0后不能確定到某個碼，碼4只要接到1就確認是哪個碼了。第22頁，共52頁。第23頁，共52頁。第24頁，共52頁。(1)哪些是唯一可譯碼（2）哪些是即時碼（3）計算平均碼長和編碼效率第25頁，共52頁。樹圖法對于m進制樹圖，有樹根、樹枝和節(jié)點。樹圖最頂部的節(jié)點稱為樹根；每一個分支稱為樹枝；樹枝的盡頭稱為節(jié)點，每個節(jié)點生出的樹枝數目等于碼符號數m；從樹根到終端節(jié)點各樹枝代表的碼符號順次連接，就得到了編碼碼字。第26頁，共52頁。m＝2的二進制樹圖第27頁，共52頁。整樹與非整樹考慮一個樹有r階節(jié)點整樹：碼樹的各個分支都延伸到最后一級端點，此時，將共有mr個碼字；非整樹：碼樹中存在分支，沒有延伸到最后一級端點，此時，將少于mr個碼字。第28頁，共52頁。整樹圖例第29頁，共52頁。非整樹圖例第30頁，共52頁。即時碼的構造－樹圖法編碼：用樹圖法構造即時碼，只要將信源符號全部對應于終端節(jié)點，而不是中間節(jié)點即可。這樣就可以保證任何一個碼字都不是其它碼字的前綴解碼：按照碼符號的順序，從根節(jié)點依次查詢到終端節(jié)點，就得到對應的信源符號。再從根節(jié)點對剩下的碼符號序列做相同的處理，直到處理完碼符號序列中所有的碼符號對應表中的碼4分析第31頁，共52頁。唯一可譯碼存在的充要條件克勞夫特不等式：m是進制數，n是信源符號數1.唯一可譯碼必定滿足不等式2.滿足不等式的碼存在唯一可譯碼，但不一定是唯一可譯碼此定理只證明存在性第32頁，共52頁。例題p88第33頁，共52頁。無失真信源編碼－概念無失真信源編碼：要求精確地復現信源的輸出保證信源的全部信息無損的送給信宿研究方法：只考慮有效性，不考慮可靠性將信道編解碼看成一個無噪無損信道第34頁，共52頁。輸入序列X長度L，每一位n種可能。編碼后Y的長度是KL，每一位m種可能。北京郵電大學周炯槃的書中解釋無失真條件：無失真：nL≤mK(每個消息序列有對應的編碼碼組)

信源輸出有效：nL

大于等于mK（編碼輸出的碼組數小于信源消息序列總數）信源編碼輸入輸出X＝[X1,X2,…XL]Y＝[Y1,Y2,…YKL]第35頁，共52頁。由無失真條件可得：第36頁，共52頁。編碼的目的：希望傳送Y時所需的信息率（信息率是通過接收到的信息可獲得的發(fā)送信息的信息量,即互信息。單位:bit/符號）最小。序列Y的最大信息量是K·logm(序列長乘以每個符號的最大信息熵)所以送一個信源符號x需要的平均信息率為：

信息率最小就是找到一種編碼方式使最小。第37頁，共52頁。5.2.1定長編碼定理定義：各個碼字碼長都相等的碼定長碼中每個碼字長度相等，所以只要定長碼是非奇異碼，則必為唯一可譯碼第38頁，共52頁。第39頁，共52頁。唯一可譯定長碼的存在條件對一個簡單信源X進行定長編碼，信源X存在唯一可譯定長碼的條件是：

n≤mK其中，n是信源X的符號個數，m是信道基本碼符號數，K是定長碼的碼長。此為華中科技大學書中給出的定理。第40頁，共52頁。英文電報有32個符號，即n＝32，26個英文字母加上6個標點符號采用二元碼時，則m＝2。對信源X的逐個符號xi,i＝1,2,…,32進行二元編碼，則32≤2K這就是說，每個英文電報符號至少要用5位二元符號進行編碼才能得到唯一可譯碼第41頁，共52頁。定長信源編碼定理（香農第一等長編碼公式）定理內容：由L個符號組成的，每個符號的熵為HL（X）的無記憶平穩(wěn)信源符號X＝[X1,X2,…XL]，編碼K個符號Y＝[Y1,Y2,…YKL]（每個符號m種可能）對任意ε>0,δ>0，只要滿足則當L足夠大時，必可使譯碼差錯小于δ。反之，若則當L足夠大時，可以實現幾乎無失真編碼，譯碼錯誤概率趨于1，幾乎必定出錯。第42頁，共52頁。定長信源編碼定理的意義：信源經過定長編碼后，所能攜帶的信息量，一定要大于信源所攜帶的平均信息量(熵)。若是小于，肯定不能無失真若是等于，是臨界狀態(tài)。可能失真，也可能不失真。第43頁，共52頁。例如某信源有8種符號，L=1，信源序列熵=log8=3bit/符號。說明可以用3bit的信息屢進行無失真編碼。采用二進制，{0,1}，等概時lb8=3bit/符號（這是等概信源的）若信源非等概，p(ai)={0.4,0.18,0.1,0.1,0.07,0.06,0.05,0.04},則

H(X)=2.55bit/符號的信息率在二進制中可以表示22.55=5.856種碼字，還有部分符號沒有編碼，當出現沒編碼的符號只能用其他符號代替，這就是失真。當L足夠大時，有些符號的發(fā)生概率變得很小，差錯率就變得很小。第44頁，共52頁。典型序列及非典型序列的說明引入信源的不等概統(tǒng)計特性后，無需將信源所有符號序列編碼，僅對大概率典型序列編碼，小的不編碼（會失真），下面介紹北京郵電大學周炯槃書中的對典型序列及非典型序列的說明：當L足夠大時，根據大數定理，其中一些序列的集合會以趨向概率1出現，如果每一個序列等概率出現，這個概率為2-LH（X）（這個計算是先確定等概率的信息上是log2-LH（X）這個計算=LH(X),就是是平均每個序列的信息量，L長序列，序列中每個符號信息量是H(X)。）所以證明這個集合就是典型序列集合，共有2LH（X）個典型序列，只需要對這些序列編碼即可。這一概念對應本書中的互補集合。第45頁，共52頁。L增大時，典型序列數目增多，小概率事件概率更小。根據切比雪夫不等式式中，為信源序列的自信息方差，為一正數。當和均為定值時，P可以小于任一正數。信源序列長度L必滿足可以看出，L無窮大時，誤碼概率趨向于0.第46頁，共52頁。信源編碼效率對于等長編碼，

編碼效率一定是小于或等于1的數。對同一信源來說，若碼的平均碼長越短，信息傳輸率就越高，這時也越接近1。所以編碼效率可以用來衡量各種編碼方法在有效性方面的優(yōu)劣。

第47頁，共52頁。上面介紹到了，L無限長時，實際編碼長變小，越接近最小可能碼長?？聪旅娴睦樱涸O離散無記憶信源概率空間為信源熵為對信源符號采用定長二元編碼，要求編碼效率為若取L=1，則可以算出：即每個符號用2.83bit進行定長二元編碼，共有7.11種可能性，按7種算，有一個符號沒有對應的碼字，取概率最小的a8，差錯仍0.04，太大。第48頁，共52頁。試想信源發(fā)送的L很大時，可以用編碼效率的公式計算：信源序列的自信息方差為若要求譯碼錯誤概率則可見，一定