信息论与编码自学报告

1、信息论与编码课程自学报告题目:信息论与编码自学报告学号:姓名：任课教师：黄素娟联系方式零17年1月10日第一部分阐述“第四章 信息率失真函数”主要内容1、基本概念1.1失真函数与平均失真度平均失真度在离散情况下，信源X=a1,a2,ar,其概率分布p(x)=b1,b2,bs。若已知试验信道的传递s2 P (ai) p (bj/ ai)d (ai, bj)j=1凡满足保真度准则-平均失真度D 0 卫 Hyj最常用的失真函数占伕 7 =(耳一 4 订前三种失真函数适用于连续信源，后一种适用于离散信源。1.2信息率失真函数的定义互信息取决于信源分布和信道转移概率分布。 当P

2、(xi)定时， 互信息I是关于p(yj/xi)的U型凸函数，存在极小值。在上述允许信道PD中，可以寻找一种信 道pij,使给定的信源P(xi)经过此信道传输后，互信息I(X；Y)达到最小。该 最小的互信息就称为信息率失真函数R(D)，即肌单位：bit/信源符号对于离散无记忆信源，R(D)函数可写成p(a1),p(a2),p(ar)，信宿丫=概率为p(bj/ai)时，则平均失真度为：rD = Zp (ab )d (a,b) = SXYi =1均方失真=梱对失真=误码失真=吒- k. -jJOL1，JC I 丿(5)信息率失真函数给出了熵压缩编码可能达到的最小熵率与失真的关系1.3信息率失真函数的

3、性质1、R(D)函数的定义域和值域R(D)的定义域为-D- Dmax允许失真度2、R(D)是关于平均失真度D的下凸函数设为任意两个平均失真， -a-1，则有:RaD1+ (1- a)D2p aR(D1)+(1a)R(D2)区间上的连续和严格单调递减函数。离散信源的信息率失真函数2.1离散信源信息率失真函数的参量表达式n mP(ai),P(bj/ai)t-耳严1 i=1,2,i=1,j=1,2,，n2,n,皿)是信源符号概率分布；j=1,2,，m是转移概率分布; 是接收端收到符号概率分布。Dmin=送xp(X)myngyDmax呷吨p(曲咧D的下限可以是零，这是不允许任何失真的情况。P(bj/a

4、jrzi二3、R(D)是(Dmin，Dmax)I(X,Y)=2 2 p(ai)p(bj/ai)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(5)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二元及等概率离散信源的信息率失真函数设二元信源=H(p)-压缩的信息率。二元等概率离散信源的率失真函数(4.3.16)p(:)rx p失真矩阵为输入符号集输岀符号集=0, X2=0,y

5、2计算率失真函数RD)对于这种简单信源,D(S)aeSa+ eSa/XJXR(D)= Dln1可从D(S)解出S与D的显式表达式。SalnOfP(y1/x1)p(y1)p(yDLp2Dp(yot2DlnP-(1p(yp(y-p ) ln( 1 -P) + lnPCD(1-p I1一看上式右边第一项是信源熵, 第二项是因容忍一定失真而可能=0,R( 0)H(P)：=Dmax,RDmax)：=Dmax=otp.ln当上述二元信源呈等概率分布时，上面式子分别退化为11_D_a121 _Da12R(D) = In3保真度准则下的信源编码定理定理4.1 (保真度准则下的信源编码定理，香农第三定理)设R(

6、D)为一离散无记忆信源的信息率失真函数，并且有有限的失真测度 对于任意DX0，0，以及任意长的码长k，一定存在一种信源编码C,其码字 个数为M工2kR(D)使编码后码的平均失真度D 2Do所以香农第霍夫曼(Huffman)编码算法是满足前缀条件的平均二进制码长最短的编-源输出符号，而将较短的编码码字分配给较大概率的信源输出。算法是：在信源1的合并输出符号的概率为1o这样就得到了一张树图，从树根开始，将编码符号1和0分配在同一节点的任意两分支上，这一分配过程重复直到树叶。从 树根到树叶途经支路上的编码最后就构成了一组异前置码， 就是霍夫曼编码输出。2.编码步骤(1)、码树形成过程：将信源概率按照

7、从小到大顺序排序并建立相应的位置索引。 然后按上述规则进行信源合并， 再对信源进行排序并建立新的位置索引， 直到合 并结束。在这一过程中每一次都把排序后的信源概率存入矩阵G中，位置索引存入矩阵Index中。这样，由排序之后的概率矩阵G以及索引矩阵Index就可以 恢复原概率矩阵P了，从而保证了回溯过程能够进行下去。(2)、码树回溯过程：在码树上分配编码码字并最终得到Huffman编码。从索引矩阵M的末行开始回溯。(1)在Index的末行2元素位置填入0和1。(2)根据该行索引1位置指示， 将索引1位置的编码 (1)填入上一行的第一、第二元素位置，并在它们之后分别添加0和1。(3)将索引不为1的

8、位置的编码值(0)填入上一行的相应位置(第3列)。 以Index的倒数第二行开始向上，重复步骤(1)(3)，直到计算至Index的首行为止。3程序代码%取得信源概率矩阵,并进行合法性判断clear;P=input(请输入信源概率向量P=);N=length(P);for component=1:1:Nif(P(component)0.0001)error(信源概率之和必须为end%建立各概率符号的位置索引矩阵对应的编码Q=PIndex=zeros(N-1,N); %初始化fori=1:N-11);Index,利于编码后从树根进行回溯,从而得出IndexQ,L=sort(Q);Index(i,:

9、)=L(1:N-i+1),zeros(1,i-1);G(i,:)=Q;Q=Q(1)+Q(2),Q(3:N),1;方补1end %根据以上建立的Index矩阵，for i=1:N-1Char(i,:)=blanks(N*N);%存放编码end%从码树的树根向树叶回溯，即从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

10、=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的编码码字填入到当前行的第一个编码位置Char(N-i,N)=0; %然后在当前行的第一个编码位置末尾填入0Char(N-i,N+1:2*N-1)=Char(N-i,1:N-1); %将G后一行中索引为1的编码码字填入到当前行的第二个编码位置Char(N-i,2*N)=1; %然后在当前行的第二个编码位置末尾填入1for j=1:i-1%内循环作用：将Index后一行中索引不为1处的编

11、码按照左右顺序填入当前行 的第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);end end%Char中第一行的编码结果就是所需的Huffman编码输出，通过Index中第一 行索引将编码对应到相应概率的信源符号上。for i=1:NResult(i,1:N)=Char(1,N*(find(Index(1,:)=i)-1)+1:find(Index(1,:)=i)*N);%各Q中概率最小的两个元素合并，元素不足的地进行回溯，获取信源编码初始化一个由空格符组成的字符矩阵N*N,用于end%打印编码结果String=信源概率及其对应的Huffman编码如下; disp(String);disp(P);disp(Re