信息论与编码自学报告

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