1、信息論與編碼課程自學報告題 目：信息論與編碼自學報告學 號：姓 名：任課教師：黃素娟聯系方式：二零17年1月10日第一部分闡述“第四章 信息率失真函數”主要內容1、基本概念1.1 失真函數與平均失真度平均失真度在離散情況下，信源X=a1,a2, - ar,其概率分布p(x)= p(a1),p(a2),p(ar)，信宿 Y= b1,b2, bs。若已知試驗信道的傳遞概率為p(bj/ai)時，則平均失真度為：凡滿足保真度準則-平均失真度D ? D0的試驗信通稱D失真許可的試驗信道。失真函數假如某一信源X,輸出樣值為xi ,xi ?a1,an,經過有失真的信源編碼器， 輸出Y,樣值為yj , yj

2、?b1, bm。如果xi =yj ,則認為沒有失真；如果xi ? yj，那么就產生了失真。失真的大小，用一個量來表示，即失真函數d(xi ,yj), 以衡量用yj代替xi所引起的失真程度。一般失真函數定義為o xi = yj a a > 0 yj最常用的失真函數前三種失真函數適用于連續信源，后一種適用于離散信源。？1.2 信息率失真函數的定義互信息取決于信源分布和信道轉移概率分布。當 p(xi) 一定時，互信息I是關于 p(yj/xi) 的U型凸函數，存在極小值。在上述允許信道PD中，可以尋找一種信 道pij ,使給定的信源p(xi)經過此信道傳輸后，互信息I(X ； Y)達到最小。該最

3、小的互信息就稱為信息率失真函數R(D),即&3)=哽單位bit/信源符號對于離散無記憶信源，R(D)函數可寫成p(ai) , i=1, 2,，n?是信源符號概率分布;p(bj/ai) , i=1, 2,，n, j=1, 2,，m?是轉移概率分布;p(bj) , j=1, 2,m?是接收端收到符號概率分布。信息率失真函數給出了嫡壓縮編碼可能達到的最小嫡率與失真的關系1.3 信息率失真函數的性質1、R(D)函數的定義域和值域R(D)的定義域為允許失真度D的下限可以是零，這是不允許任何失真的情況。2、R(D)是關于平均失真度D的下凸函數設為任意兩個平均失真，0 * a - 1 ,則有：3、R

4、(D)是(Dmin,Dmax)區間上的連續和嚴格單調遞減函數離散信源的信息率失真函數2.1 離散信源信息率失真函數的參量表達式n mI (X,Y) -p(ai)p(bj /ai)10gi a j wP(bj /ai)p(bj/ai)- 0(2)p(ai)p(bj/ai)(m'、'p(bj /ai) = 1,(i -1,.,n) j 二n m:,匚 p(ai)p(bj/ai)d(ai,bj) = Di m j 4m力=I(X;Y) -p(bj/ai)-sDj2.2 二元及等概率離散信源的信息率失真函數設二元信源計算率失真函數RD) 對于這種簡單信源，可從 D(S)解出S與D的顯式

5、表達式。二元等概率離散信源的率失真函數當上述二元信源呈等概率分布時，上面式子分別退化為 3保真度準則下的信源編碼定理定理4.1 (保真度準則下的信源編碼定理，香農第三定理 )設R(D)為一離散無記憶信源的信息率失真函數，并且有有限的失真測度Do對于任意口至0,名A0,以及任意長的碼長k, 一定存在一種信源編碼C,其碼字k R( D) 個數為M之2以使編碼后碼的平均失真度D <D 0定理的含義是：只要碼長k足夠長，總可以找到一種信源編碼，使編碼后的信息 傳輸率略大于(直至無限逼近)率失真函數R(D),而碼的平均失真度不大于給定 的允許失真度，即：D m D由于R(D)為給定D前提下信源編碼

6、可能達到的傳信率的下限，所以香農第三定理說明了：達到此下限的最佳信源編碼是存在的。第二部分信源編碼或信道編碼典型案例的實現方案 信源編碼典型案例的實現方案-霍夫曼編碼的matlab實現 1.編碼原理霍夫曼(Huffman)編碼算法是滿足前綴條件的平均二進制碼長最短的編-源輸出符號，而將較短的編碼碼字分配給較大概率的信源輸出。算法是：在信源符號集合中，首先將兩個最小概率的信源輸出合并為新的輸出，具概率是兩個相應輸出符號概率之和。這一過程重復下去，直到只剩下一個合并輸出為止，這個 最后的合并輸出符號的概率為1。這樣就得到了一張樹圖，從樹根開始，將編碼 符號1和0分配在同一節點的任意兩分支上，這一分

7、配過程重復直到樹葉。從 樹根到樹葉途經支路上的編碼最后就構成了一組異前置碼，就是霍夫曼編碼輸出。2 .編碼步驟(1)、碼樹形成過程：將信源概率按照從小到大順序排序并建立相應的位置索引。 然后按上述規則進行信源合并，再對信源進行排序并建立新的位置索引，直到合 并結束。在這一過程中每一次都把排序后的信源概率存入矩陣G中，位置索引存入矩陣Index中。這樣，由排序之后的概率矩陣 G以及索引矩陣Index就可以 恢復原概率矩陣P了，從而保證了回溯過程能夠進行下去。(2)、碼樹回溯過程：在碼樹上分配編碼碼字并最終得到Huffman編碼。從索引矩陣M的末行開始回溯。(1)在Index的末行2元素位置填入0

8、和1。(2)根據該彳T索引1位置指示，將索引1位置的編碼(1')填入上一行的第 一、第二元素位置，并在它們之后分別添加0和1'。(3)將索引不為1'的位置的編碼值(0')填入上一行的相應位置(第3歹I) 以Index的倒數第二行開始向上，重復步驟(1)(3),直到計算至Index 的首行為止。3 .程序代碼%取得信源卞S率矩陣，并進行合法性判斷 clear;P=input('請輸入信源概率向量 P=');N=length(P);for component=1:1:Nif(P(component)<0)error(' 信源概率不能小于

9、0');endendif(sum(P)-1)>0.0001)error(' 信源概率之和必須為 1');end%建立各概率符號的位置索引矩陣Index, 利于編碼后從樹根進行回溯 , 從而得出對應的編碼 Q=PIndex=zeros(N-1,N); % 初始化 Indexfor i=1:N-1Q,L=sort(Q);Index(i,:)=L(1:N-i+1),zeros(1,i-1);G(i,:)=Q;Q=Q(1)+Q(2),Q(3:N),1;%等Q中概率最小的兩個元素合并，元素不足的地方補 1end%根據以上建立的Index 矩陣，進行回溯，獲取信源編碼for

10、i=1:N-1Char(i,:)=blanks(N*N);%初始化一個由空格符組成的字符矩陣N*N,用于存放編碼end%從碼樹的樹根向秋t葉回溯，即從G矩陣的最后一行按與Index中的索引位置的對應關系向其第一行進行編碼Char(N-1,N)='0'%G 中的 N-1 行即最后一行第一個元素賦為 0，存到 Char 中 N-1 行的 N 列位置Char(N-1,2*N)='1'%G 中的 N-1 行即最后一行第二個元素賦為 1，存到 Char 中N-1 行的 2*N 列位置%以下從G 的倒數第二行開始向前編碼for i=2:N-1Char(N-i,1:N-1)=

11、Char(N-i+1,N*(find(Index(N-i+1,:)=1) -(N-2):N*(find(Index(N-i+1,:)=1);% 將 Index 后一行中索引為 1 的編碼碼字填入到當前行的第一個編碼位置Char(N-i,N)='0' % 然后在當前行的第一個編碼位置末尾填入 '0'Char(N-i,N+1:2*N-1)=Char(N-i,1:N-1); % 將 G后一行中索引為 1 的編碼碼 字填入到當前行的第二個編碼位置Char(N-i,2*N)='1' % 然后在當前行的第二個編碼位置末尾填入 '1'for j

12、=1:i-1%內循環作用：將 Index 后一行中索引不為 1 處的編碼按照左右順序填入當前行的第 3 個位置開始的地方 , 最后計算到 Index 的首行為止Char(N-i,(j+1)*N+1:(j+2)*N)=Char(N-i+1,N*(find(Index(N-i+1,:)=j+1)-1 )+1:N*find(Index(N-i+1,:)=j+1);endend%Char 中第一行的編碼結果就是所需的 Huffman 編碼輸出，通過Index 中第一行索引將編碼對應到相應概率的信源符號上。for i=1:NResult(i,1:N)=Char(1,N*(find(Index(1,:)=i)-1)+1:find(Index(1,:)=i)*N);end% 打印編碼結果String=' 信源概率及其對應的 Huf