信息論與編碼自學報告

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

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

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

4、(D)是(Dmin,Dmax)區(qū)間上的連續(xù)和嚴格單調(diào)遞減函數(shù)離散信源的信息率失真函數(shù)2.1 離散信源信息率失真函數(shù)的參量表達式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 二元及等概率離散信源的信息率失真函數(shù)設(shè)二元信源計算率失真函數(shù)RD) 對于這種簡單信源，可從 D(S)解出S與D的顯式

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

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

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

8、和1。(2)根據(jù)該彳T索引1位置指示，將索引1位置的編碼(1')填入上一行的第 一、第二元素位置，并在它們之后分別添加0和1'。(3)將索引不為1'的位置的編碼值(0')填入上一行的相應位置(第3歹I) 以Index的倒數(shù)第二行開始向上，重復步驟(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%根據(jù)以上建立的Index 矩陣，進行回溯，獲取信源編碼for

10、i=1:N-1Char(i,:)=blanks(N*N);%初始化一個由空格符組成的字符矩陣N*N,用于存放編碼end%從碼樹的樹根向秋t葉回溯，即從G矩陣的最后一行按與Index中的索引位置的對應關(guān)系向其第一行進行編碼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 的倒數(shù)第二行開始向前編碼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%內(nèi)循環(huán)作用：將 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 中第一行的編碼結(jié)果就是所需的 Huffman 編碼輸出，通過Index 中第一行索引將編碼對應到相應概率的信源符號上。for i=1:NResult(i,1:N)=Char(1,N*(find(Index(1,:)=i)-1)+1:find(Index(1,:)=i)*N);end% 打印編碼結(jié)果String=' 信源概率及其對應的 Huf