信息論與編碼自學(xué)報(bào)告

1、信息論與編碼課程自學(xué)報(bào)告題目:信息論與編碼自學(xué)報(bào)告學(xué)號:姓名：任課教師：黃素娟聯(lián)系方式零17年1月10日第一部分闡述“第四章 信息率失真函數(shù)”主要內(nèi)容1、基本概念1.1失真函數(shù)與平均失真度平均失真度p(a1),p(a2),p(ar)，信宿 丫=概率為p(bj/ai)時(shí)，則平均失真度為：rD = Z p (ab )d (a,b) = SXYi =1在離散情況下，信源X = a1,a2,ar,其概率分布p(x)= b1,b2,bs。若已知試驗(yàn)信道的傳遞s2 P (ai ) p (b j / ai )d (ai , b j )j=1凡滿足保真度準(zhǔn)則-平均失真度D <

2、D0的試驗(yàn)信通稱D失真許可的試驗(yàn)信道。 失真函數(shù)假如某一信源X，輸出樣值為xi，xi鞏a1,an，經(jīng)過有失真的信源編碼 器，輸出丫，樣值為yj，yj鬥b1,bm。如果xi = yj，則認(rèn)為沒有失真；如果 xi呵，那么就產(chǎn)生了失真。失真的大小，用一個(gè)量來表示，即失真函數(shù)d(xi， yj)，以衡量用yj代替xi所引起的失真程度。一般失真函數(shù)定義為 哦 > 0 衛(wèi)H yj最常用的失真函數(shù)均方失真=占伕7» =(耳一 4訂梱對失真=誤碼失真=吒- k. -jJOl1，JC I 丿卑它前三種失真函數(shù)適用于連續(xù)信源，后一種適用于離散信源。1.2信息率失真函數(shù)的定義互信息取決于信源分布和信道

3、轉(zhuǎn)移概率分布。當(dāng) P(xi) 定時(shí)，互信息I是關(guān)于 p(yj/xi) 的U型凸函數(shù)，存在極小值。在上述允許信道PD中，可以尋找一種信 道pij ,使給定的信源P(xi)經(jīng)過此信道傳輸后，互信息I(X ； Y)達(dá)到最小。該 最小的互信息就稱為信息率失真函數(shù) R(D)，即肌單位：bit/信源符號對于離散無記憶信源，R(D)函數(shù)可寫成P(ai),P(bj/ai)P(bj),t -耳嚴(yán)1 i = 1, 2,i = 1, j = 1, 2,，n2,n,皿)是信源符號概率分布；j = 1, 2,，m 是轉(zhuǎn)移概率分布; 是接收端收到符號概率分布。信息率失真函數(shù)給出了熵壓縮編碼可能達(dá)到的最小熵率與失真的關(guān)系1

4、.3信息率失真函數(shù)的性質(zhì)1、R(D)函數(shù)的定義域和值域R(D)的定義域?yàn)?D - DmaxDmin =送xp(X)myngy"Dmax 呷噸 p(曲咧(5)3、R(D)是(Dmin，Dmax )D的下限可以是零，這是不允許任何失真的情況。允許失真度2、R(D)是關(guān)于平均失真度D的下凸函數(shù)設(shè)為任意兩個(gè)平均失真，° - a - 1，則有:RaD1 + (1- a)D2p aR(D1)+ (1 a)R(D2)區(qū)間上的連續(xù)和嚴(yán)格單調(diào)遞減函數(shù)。離散信源的信息率失真函數(shù)2.1離散信源信息率失真函數(shù)的參量表達(dá)式 P(bj/ajrzi 二n mI(X,Y)=2 2 p(ai)p(bj/ai

5、)logi zt j ziP(bj/ai)工 0n m送送 p(aj p(bj/ai)d(ai,bj) =Di# j#m= I(X;丫)-氣2 p(bj/aJ-sDp(4.3.16)D(s)=S Z p(ai)p(bj九d(ai,bj)expsd©,©)i jnR(s) =sD(s) + 2 p(ai) log 幾i(4.3.17)i丄2.2二元及等概率離散信源的信息率失真函數(shù)設(shè)二元信源p(:)rx p失真矩陣為輸入符號集輸岀符號集=0, X 2=0, y 2計(jì)算率失真函數(shù)RD)對于這種簡單信源,D( S )aeSa+ e Sa/XJXR(D)= Dln1可從 D(S)解出

6、S與D的顯式表達(dá)式。SalnOfP( y 1 / x 1)p( y 1)p( yDLp2Dp( yot2DlnP -(1p(yp( y-p ) ln( 1 -P ) + lnpcD(1-p I1 一看=H( p)-上式右邊第一項(xiàng)是信源熵,第二項(xiàng)是因容忍一定失真而可能壓縮的信息率。=0,R( 0)H( P)：=Dmax ,R Dmax)：=Dmax=otp.ln二元等概率離散信源的率失真函數(shù)當(dāng)上述二元信源呈等概率分布時(shí)，上面式子分別退化為1Dmax=min Dj = D? = - a= 212)a1_Da121 _D>2a12p(yi / xi)p(yi / X2)p(y2 / xi)Q

7、-加p 紅汽廠 DG -烏)gQ -耳1 -2D) DO -D -必衛(wèi)進(jìn)_ - 2 _2D-!i1 -paDaD-=p(y1 / X2) a-T)=p(y1 / x1)p(y2 / xj R( D) = In3保真度準(zhǔn)則下的信源編碼定理Do定理4.1 (保真度準(zhǔn)則下的信源編碼定理，香農(nóng)第三定理)設(shè)R(D)為一離散無記憶信源的信息率失真函數(shù)，并且有有限的失真測度 對于任意dX0，£>0，以及任意長的碼長k，一定存在一種信源編碼C,其碼字 個(gè)數(shù)為M工2kR(D)使編碼后碼的平均失真度D < D o定理的含義是：只要碼長k足夠長，總可以找到一種信源編碼，使編碼后的信息 傳輸率略

8、大于(直至無限逼近)率失真函數(shù)R(D)，而碼的平均失真度不大于給定 的允許失真度，即：D-D所以香農(nóng)第由于R(D)為給定D前提下信源編碼可能達(dá)到的傳信率的下限, 三定理說明了：達(dá)到此下限的最佳信源編碼是存在的。第二部分信源編碼或信道編碼典型案例的實(shí)現(xiàn)方案信源編碼典型案例的實(shí)現(xiàn)方案-霍夫曼編碼的matlab實(shí)現(xiàn)霍夫曼(Huffman)編碼算法是滿足前綴條件的平均二進(jìn)制碼長最短的編-源輸出符號，而將較短的編碼碼字分配給較大概率的信源輸出。算法是：在信源1.編碼原理口號，符號集合中，首先將兩個(gè)最小概率的信源輸出合并為新的輸出， 其概率是兩個(gè)相應(yīng)輸出符號概率之和。這一過程重復(fù)下去，直到只剩下一個(gè)合并輸

9、出為止，這個(gè) 最后的合并輸出符號的概率為1o這樣就得到了一張樹圖，從樹根開始，將編碼符號 1 和 0 分配在同一節(jié)點(diǎn)的任意兩分支上，這一分配過程重復(fù)直到樹葉。從 樹根到樹葉途經(jīng)支路上的編碼最后就構(gòu)成了一組異前置碼， 就是霍夫曼編碼輸出。 2. 編碼步驟(1) 、碼樹形成過程：將信源概率按照從小到大順序排序并建立相應(yīng)的位置索引。 然后按上述規(guī)則進(jìn)行信源合并， 再對信源進(jìn)行排序并建立新的位置索引， 直到合 并結(jié)束。在這一過程中每一次都把排序后的信源概率存入矩陣G中，位置索引存入矩陣 Index 中。這樣，由排序之后的概率矩陣 G 以及索引矩陣 Index 就可以 恢復(fù)原概率矩陣 P 了，從而保證了

10、回溯過程能夠進(jìn)行下去。( 2)、碼樹回溯過程：在碼樹上分配編碼碼字并最終得到Huffman 編碼。從索引矩陣 M 的末行開始回溯。(1) 在Index的末行2元素位置填入0和1。(2) 根據(jù)該行索引 1 位置指示， 將索引 1 位置的編碼 (1')填入上一行的第一、第二元素位置，并在它們之后分別添加0'和1'。(3) 將索引不為1'的位置的編碼值(0')填入上一行的相應(yīng)位置(第3 列)。 以Index的倒數(shù)第二行開始向上，重復(fù)步驟(1)(3)，直到計(jì)算至Index 的首行為止。3程序代碼%取得信源概率矩陣 , 并進(jìn)行合法性判斷clear;P=input(

11、' 請輸入信源概率向量 P=');N=length(P);for component=1:1:Nif(P(component)<0)error(' 信源概率不能小于 0');endendif(sum(P)-1)>0.0001)error(' 信源概率之和必須為 end%建立各概率符號的位置索引矩陣對應(yīng)的編碼Q=PIndex=zeros(N-1,N); % 初始化 for i=1:N-11');Index, 利于編碼后從樹根進(jìn)行回溯 , 從而得出IndexQ,L=sort(Q);Index(i,:)=L(1:N-i+1),zeros(1

12、,i-1);G(i,:)=Q;%各Q中概率最小的兩個(gè)元素合并，元素不足的地進(jìn)行回溯，獲取信源編碼Q=Q(1)+Q(2),Q(3:N),1; 方補(bǔ) 1 end %根據(jù)以上建立的 Index 矩陣， for i=1:N-1初始化一個(gè)由空格符組成的字符矩陣N*N,用于Char(i,:)=blanks(N*N);%存放編碼end%從碼樹的樹根向樹葉回溯，即從G矩陣的最后一行按與Index中的索引位置的對應(yīng)關(guān)系向其第一行進(jìn)行編碼Char(N-1,N)='0'%G 中的N-1行即最后一行第一個(gè)元素賦為 0,存到Char中N-1 行的 N 列位置Char(N-1,2*N)='1

13、9;%G 中的N-1行即最后一行第二個(gè)元素賦為1,存到Char中N-1 行的 2*N 列位置%以下從G的倒數(shù)第二行開始向前編碼for i=2:N-1Char(N-i,1:N-1)=Char(N-i+1,N*(find(Index(N-i+1,:)=1) -(N-2):N*(find(Index(N-i+1,:)=1);% 將 Index 后一行中索引為 1 的編碼碼字填入到當(dāng)前行的第一個(gè)編碼位置Char(N-i,N)='0' % 然后在當(dāng)前行的第一個(gè)編碼位置末尾填入 '0'Char(N-i,N+1:2*N-1)=Char(N-i,1:N-1); % 將 G后一行

14、中索引為 1 的編碼碼字填入到當(dāng)前行的第二個(gè)編碼位置Char(N-i,2*N)='1' % 然后在當(dāng)前行的第二個(gè)編碼位置末尾填入 '1'for j=1:i-1%內(nèi)循環(huán)作用：將 Index 后一行中索引不為 1 處的編碼按照左右順序填入當(dāng)前行 的第 3個(gè)位置開始的地方 ,最后計(jì)算到 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);end end%Char中第一行的編碼結(jié)果就是所需的 Huffman編碼輸出，通過Index中第一 行索引將編碼對應(yīng)到相應(yīng)概率的信源符號上。for i=1:NResult(i,1:N)=Char(1,N*(find(Index(1,:)=i)-1)+1:find(Index(1,:)=i)*N);end% 打印編碼結(jié)果String=' 信源概率及其對應(yīng)的 Huffman 編碼如下 &