4.5信源編碼的基本方法1信源編碼的基本方法5/9/2024一.信源編碼的基本方法

1.信源編碼的目的：提高傳輸效率

（1）去除信息中的冗余度，使傳輸的符號盡可能都是獨立的，沒有多余的成分(如語音、圖像信號壓縮)；（2）使傳輸的符號所含的信息最大化。例如，通過編碼使符號以等概分布的形式出現，使每個符號可能攜帶的信息量達到最大；（3）采用不等長編碼，讓出現概率大的符號用較短的碼元序列表示，對概率小的符號用較長的碼元序列；

(4)在允許一定失真的條件下，如何實現高效率的編碼。2信源編碼的基本方法5/9/20242.離散無記憶信源(DMS:DiscreteMemorylessSource）離散無記憶信源的輸出序列：

各個符號間彼此獨立其中反之，若輸出的各符號間有一定的相關性，則其為一種

有記憶的信源。有記憶的信源，經過處理后，有可能變為一種無記憶的信源。如有記憶的信源，經過理想的、完全去除冗余的壓縮編碼后產生的輸出。3信源編碼的基本方法5/9/2024

若將信源輸出的符號按每J個為一組進行編碼，則任意的第m個分組可以表示為

編碼輸出其中為輸出的碼元集。接收端的譯碼輸出4信源編碼的基本方法5/9/2024

待編碼碼組

編碼輸出碼組(碼字)5信源編碼的基本方法5/9/2024定義4.5.1

若對信源的每個不同的符號或不同的符號序列，編碼后產生的碼字不同的，則稱該碼為唯一可譯碼。

若待編碼的符號序列的不同組合個數為碼字集中不同的碼字個數

唯一可譯碼的條件6信源編碼的基本方法5/9/2024定義4.5.2編碼表示一個信源符號所需的平均信息量的定義為編碼速率

。

碼字長度為常數的編碼稱為等長編碼，發之稱為不等長編碼。

等長編碼的編碼速率不等長編碼的編碼速率

其中為不等長編碼的平均碼長。7信源編碼的基本方法5/9/2024

定義4.5.3信源的熵與編碼速率的比值定義為編碼效率

要保證編碼沒有信息丟失，要求8信源編碼的基本方法5/9/20243.

霍夫曼(Huffman)編碼霍夫曼編碼是一種異字頭不等長編碼，其基本思想是：對出現概率大的符號或符號組用位數較少的碼字表示；對出現概率小的符號或符號組用位數較多的碼字表示。由此可提高編碼效率。

霍夫曼編碼：

定理4.5.17

霍夫曼編碼一種最佳的不等長編碼?；舴蚵幋a的應用條件：信源的分布(統計)特性已知。記信源符號集為：編碼輸出符號集為：9信源編碼的基本方法5/9/2024霍夫曼編碼的步驟：(1)將L個信源符號按概率大小，以遞減次序，從上到下排成一列；(2)對處于最下面的概率最小的D個信源符號，一一對應地分別賦予碼字元素Z1、Z2、…、ZD，把這D個概率最小的信源符號相應的概率相加，所得的值用一個虛擬的符號代表，與余下的L-D個符號組成含有(L-D)+1=L-(D-1)個符號的第一次縮減信源S(1)；(3)對縮減信源S(1)仍按其概率大小以遞減次序從上到下排列，按照步驟(2)的方法處理，得到一個含有[(L-D)+1]-D+1=L-2(D-1)個符號的第二次縮減信源S(2)；(4)按照上述的方法，依次繼續下去，每次縮減所減少的符號數是D-1個；只要縮減后的信源Si符號的個數大于D，縮減就繼續進行；(5)當進行第k次縮減后信源S(k)符號個數剛好等于D，即有

則對最后這D個符號分別賦予碼字元素Z1、Z2、…、ZD；10信源編碼的基本方法5/9/2024霍夫曼編碼的步驟：(6)從最后賦予的碼符號開始，沿著每一信源符號在各次縮減過程中得到的碼字元素進行路線前向返回，達至每一信源符號，按前后次序，把返回路途中所遇到的碼元素排成序列，這個序列，就是相應信源符號對應的碼字；(7)若進行k次縮減后，當進行第k次縮減后信源S(k)符號個數不等于D，即有則中止縮減，增加個概率為0的虛假信源符號重新編碼，使在k次編碼后一定有。11信源編碼的基本方法5/9/2024示例：已知信源符號集編碼輸出的碼字符號集為解：已知：嘗試需要增加虛假符號數為

新構建的信源滿足：12信源編碼的基本方法5/9/2024改造后的符號概率場為:

編碼過程如下13信源編碼的基本方法5/9/2024

平均碼字長度：14信源編碼的基本方法5/9/2024示例(續)：如果不加入虛假符號，直接進行編碼，則有平均碼字長度15信源編碼的基本方法5/9/2024

碼字長度的均勻性和方差在同樣的平均碼字長度的情況下，碼字長度越均勻，對傳輸越有利。

定義4.5.16

碼字長度的方差其中

編碼過程的排序過程不同會影響碼長的方差。16信源編碼的基本方法5/9/2024

碼字長度的均勻性和方差示例：信源的符號空間為編碼輸出碼字集編碼方式1將局部概率和置于相同概率的最低位置17信源編碼的基本方法5/9/2024示例：編碼方式1

平均碼長：

方差：18信源編碼的基本方法5/9/2024編碼方式2將局部概率和置于相同概率的最高位置

平均碼長：

方差：19信源編碼的基本方法5/9/2024

可見

雖然平均碼長一樣，但編碼方法2使得輸出的碼長更為均勻。在編碼過程中，當對縮減信源概率重新排列時，應使合并得到的局部概率和，盡量使其處于最高位置；使得合并元素重復編碼的次數減少，有利于降低碼字長度的方差。

20信源編碼的基本方法5/9/20244.6率失真理論21信源編碼的基本方法5/9/2024一.實際系統中的權衡問題實際系統中通常需要考慮性能與經濟性之間的權衡問題；可采用以某些不可察覺或可察覺但不影響應用的信號失真代價，來換取所需的傳輸速率、存儲空間、運算復雜度和系統實現成本的降低；電話系統采樣8kHz采樣，8比特量化；數字音響系統采樣44kHz采樣，16或24比特量化；

22信源編碼的基本方法5/9/20241.失真的概念

失真是指用某種尺度衡量的理想信源樣值與“變換”后的樣值間的差異。

這里所謂的“變換”，可以是某種有損的編碼，或者是經傳輸后受到劣化的信號。

失真函數：對由符號變為符號產生失真造成的影響，可根據不同的情況定義一個非負函數來描述，該函數就稱為失真函數。失真函數的取值通常反映失真產生的代價。23信源編碼的基本方法5/9/2024失真函數的示例：

24信源編碼的基本方法5/9/20242.率失真理論研究的問題

率失真理論研究的是限定失真條件下信源的編碼和信息傳輸問題的方法。分析在允許一定失真的條件下，要重構信源的符號，至少應獲得多少信源的信息量；

25信源編碼的基本方法5/9/2024(1)率失真理論在通信系統中應用時的參數

輸入信號集：輸出信號集：對離散無記憶信道，有失真函數：其中為輸入符號；為輸出符號26信源編碼的基本方法5/9/2024(2).平均失真度失真函數矩陣與轉移概率矩陣對應，可定義相應的失真度矩陣：

定義4.6.1平均失真度定義為

平均失真度是從統計意義上來說每個符號失真的平均值。27信源編碼的基本方法5/9/2024在通信系統中，失真通常在信道中產生，平均失真度與信道的關系可由轉移概率的函數來描述。給定信源的統計特性

和失真函數的定義平均失真度由信道轉移概率決定28信源編碼的基本方法5/9/2024平均失真度與信道轉移概率的關系

示例已知信源統計特性信道轉移概率矩陣

當失真測度采用漢明失真函數時，平均失真度為29信源編碼的基本方法5/9/2024(3).率失真函數

回顧平均互信息定義定理4.6.2給定信源的統計特性平均互信息量是信道轉移概率的∪型凸函數。

定理成立的主要依據：對數函數的

型凸函數特性；概率的基本關系式：30信源編碼的基本方法5/9/2024

定義4.6.3

給定信源統計特性給定失真度準則

率失真函數定義為其中

轉移概率矩陣集

定理4.6.2保證了率失真函數的存在。

31信源編碼的基本方法5/9/2024(4).率失真函數的物理意義：如果將符號通過信道傳輸看作某種變換過程，為了以小于等于DC

的失真度恢復信源的輸出，平均每個信源符號需要得到的最小信息量。若將率失真函數看作D的函數，顯然有如下的關系32信源編碼的基本方法5/9/2024當沒有失真時():

當失真達到最大時()：33信源編碼的基本方法5/9/2024

率失真函數的定義域

參見上頁圖，，但并非所有的取值都有意義。

一般地

使的最小平均失真度

34信源編碼的基本方法5/9/2024

率失真函數的主要性質：

(1)(定理4.6.3)率失真函數是D的

型凸函數。

作為D的函數存在最小值。(2)(定理4.6.4)率失真函數是D的單調遞減函數。允許的失真越大，所需的互信息量越小。

(3)(定理4.6.5)是D的連續函數。

35信源編碼的基本方法5/9/2024

示例：已知等概分布的信源信源的熵為：采用漢明失真函數漢明失真測度的失真矩陣為：36信源編碼的基本方法5/9/2024

示例：若轉移概率矩陣為即有37信源編碼的基本方法5/9/2024

則平均失真度為:隨機變量Y

的分布為因為轉移概率矩陣的元素非0即1，因此有38信源編碼的基本方法5/9/2024平均互信息量為:即若允許平均互失真度為可只發送信源的前面n個符號，后面的