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

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

2、果xi = yj,則認(rèn)為沒有失真；如果xi?yj,那么就產(chǎn)生了失真。失真的大小， 用一個(gè)量來表示，即失真函數(shù)d(xi, yj),以衡量用yj代替xi所引起的失真程度。一般失真函數(shù) 定義為最常用的失真函數(shù)前三種失真函數(shù)適用于連續(xù)信源,后一種適用于離散信源。 ?1.2 信息率失真函數(shù)的定義互信息取決于信源分布和信道轉(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/信源符號(hào)對(duì)

3、于離散無記憶信源，R(D)函數(shù)可寫成p(ai), i = l, 2,，n?是信源符號(hào)概率分布；p(bj/ai), i = l, 2,，n, j = l, 2,，m?是轉(zhuǎn)移概率分布； p(bj), j = l, 2,m?是接收端收到符號(hào)概率分布。信息率失真函數(shù)給出了熵壓縮編碼可能達(dá)到的最小熵率與失真的關(guān)系1.3 信息率失真函數(shù)的性質(zhì)1、R(D)函數(shù)的定義域和值域R(D)的定義域?yàn)?允許失真度D的下限可以是零，這是不允許任何失真的情況。2、R(D)是關(guān)于平均失真度D的下凸函數(shù)0 a 0蘭 p(b=/a ) = 1,(i-1,.,n) HYPERLINK l bookmark0 o Current

4、Document jIj 1(2)j=1j(1)血 p (a ) p (b / a )d (a , b ) = D/ i i ji=1 j=1(4)O = I(X; Y)卩蘭 p(b / a ) sD (5)ij ij=12.2二元及等概率離散信源的信息率失真函數(shù)設(shè)二元信源計(jì)算率失真函數(shù)R(D)對(duì)于這種簡單信源，可從D(S)解出S與D的顯式表達(dá)式。二元等概率離散信源的率失真函數(shù)當(dāng)上述二元信源呈等概率分布時(shí)，上面式子分別退化為3保真度準(zhǔn)則下的信源編碼定理 定理4.1(保真度準(zhǔn)則下的信源編碼定理,香農(nóng)第三定理) 設(shè)R(D)為一離散無記憶信源的信息率失真函數(shù)，并且有有限的失真測(cè)度D。對(duì)于任意D ，*

5、 0以及任意長的碼長k, 一定存在一種信源編碼C,其碼字個(gè)數(shù)為M 2kR(D)+e使編碼后碼的平均 失真度DD。定理的含義是：只要碼長k足夠長，總可以找到一種信源編碼，使編碼后的信息傳輸率略大于(直 至無限逼近)率失真函數(shù)R(D),而碼的平均失真度不大于給定的允許失真度，即：D D 由于R(D)為給定D前提下信源編碼可能達(dá)到的傳信率的下限，所以香農(nóng)第三定理說明了：達(dá)到此 下限的最佳信源編碼是存在的。第二部分信源編碼或信道編碼典型案例的實(shí)現(xiàn)方案信源編碼典型案例的實(shí)現(xiàn)方案-霍夫曼編碼的 matlab 實(shí)現(xiàn)編碼原理霍夫曼(Huffman)編碼算法是滿足前綴條件的平均二進(jìn)制碼長最短的編-源輸出符號(hào)，而

6、將較 短的編碼碼字分配給較大概率的信源輸出。算法是：在信源符號(hào)集合中，首先將兩個(gè)最小概率的信 源輸出合并為新的輸出，其概率是兩個(gè)相應(yīng)輸出符號(hào)概率之和。這一過程重復(fù)下去，直到只剩下一 個(gè)合并輸出為止，這個(gè)最后的合并輸出符號(hào)的概率為1。這樣就得到了一張樹圖，從樹根開始，將 編碼符號(hào)1和0分配在同一節(jié)點(diǎn)的任意兩分支上，這一分配過程重復(fù)直到樹葉。從樹根到樹葉途經(jīng) 支路上的編碼最后就構(gòu)成了一組異前置碼，就是霍夫曼編碼輸出。編碼步驟、碼樹形成過程：將信源概率按照從小到大順序排序并建立相應(yīng)的位置索引。然后按上述規(guī)則 進(jìn)行信源合并，再對(duì)信源進(jìn)行排序并建立新的位置索引，直到合并結(jié)束。在這一過程中每一次都把 排序

7、后的信源概率存入矩陣G中，位置索引存入矩陣Index中。這樣，由排序之后的概率矩陣G 以及索引矩陣Index就可以恢復(fù)原概率矩陣P 了，從而保證了回溯過程能夠進(jìn)行下去。、碼樹回溯過程：在碼樹上分配編碼碼字并最終得到Huffman編碼。從索引矩陣M的末行開始 回溯。在Index的末行2元素位置填入0和1。根據(jù)該行索引1位置指示，將索引1位置的編碼(1)填入上一行的第一、第二元素位置， 并在它們之后分別添加0和1。將索引不為1的位置的編碼值(0)填入上一行的相應(yīng)位置(第3列)。以Index的倒數(shù)第二行開始向上，重復(fù)步驟(1)(3)，直到計(jì)算至Index的首行為止。程序代碼%取得信源概率矩陣，并進(jìn)行

8、合法性判斷clear;P=input(請(qǐng)輸入信源概率向量P=);N=length(P); forcomponent=1:1:N if(P(component)0.0001)error( 信源概率之和必須為 1);end%建立各概率符號(hào)的位置索引矩陣Index,利于編碼后從樹根進(jìn)行回溯，從而得出對(duì)應(yīng)的編碼Q=PIndex二zeros(NT,N);%初始化 Index fori=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中概率最小的兩個(gè)元素合并，元素不足的地方補(bǔ)1end%

9、根據(jù)以上建立的Index矩陣，進(jìn)行回溯，獲取信源編碼fori=l:N-lChar(i,:)=blanks(N*N);%初始化一個(gè)由空格符組成的字符矩陣N*N,用于存放編碼 end%從碼樹的樹根向樹葉回溯，即從G矩陣的最后一行按與Index中的索引位置的對(duì)應(yīng)關(guān)系向其第一 行進(jìn)行編碼Char(N-1,N)=0;%G中的NT行即最后一行第一個(gè)元素賦為0，存到Char中NT行的N列位置 Char(N-l,2*N)=1;%G中的NT行即最后一行第二個(gè)元素賦為1，存到Char中NT行的2*N列位 置%以下從G的倒數(shù)第二行開始向前編碼fori=2:N-1Char(N-i,1:N-1)=Char(N-i+1,

10、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è)編碼位置末尾填入0Char(N-i,N+1:2*N-1)=Char(N-i,1:N-1);%將G后一行中索引為1的編碼碼字填入到當(dāng)前行的第二 個(gè)編碼位置Char(N-i,2 *N)=1;%然后在當(dāng)前行的第二個(gè)編碼位置末尾填入1forj=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);endend%Char 中第一行的編碼結(jié)果就是所需的 Huffman 編碼輸出，通過 Index 中第一行索引將編碼對(duì)應(yīng)到 相應(yīng)概率的信源符號(hào)上。fori=1:NResult(i,1:N)=Char(1,N*(find(Index(1,:)=i)-1)+1:find(Index(1,:)=i)*N);end%打印編碼結(jié)果St ring二信源概率及