信息论与编码 自学报告

1、信息论与编码课程自学报告题目：信息论与编码自学报告学号：姓名：任课教师：黄素娟联系方式:二零17年1月10日第一部分阐述“第四章信息率失真函数”主要内容1、基本概念1.1失真函数与平均失真度 平均失真度在离散情况下，信源X=al,a2,ar,其概率分布p(x) = p(al),p(a2),，p(ar)，信宿Y = bl,b2,bs。若已知试验信道的传递概率为p(bj/ai)时，则平均失真度为： 凡满足保真度准则一-平均失真度D?DO的试验信通称D失真许可的试验信道。失真函数假如某一信源X,输出样值为xi, xi?al,an，经过有失真的信源编码器，输出Y,样值为 yj, yj?bl,-bm。如

2、果xi = yj,则认为没有失真；如果xi?yj,那么就产生了失真。失真的大小， 用一个量来表示，即失真函数d(xi, yj),以衡量用yj代替xi所引起的失真程度。一般失真函数 定义为最常用的失真函数前三种失真函数适用于连续信源,后一种适用于离散信源。 ?1.2 信息率失真函数的定义互信息取决于信源分布和信道转移概率分布。当p(xi) 定时，互信息I是关于p(yj/xi)的U型凸 函数，存在极小值。在上述允许信道PD中，可以寻找一种信道pij,使给定的信源p(xi)经过此信 道传输后，互信息I(X； Y)达到最小。该最小的互信息就称为信息率失真函数R(D),即刁三匕；单位：bit/信源符号对

3、于离散无记忆信源，R(D)函数可写成p(ai), i = l, 2,，n?是信源符号概率分布；p(bj/ai), i = l, 2,，n, j = l, 2,，m?是转移概率分布； p(bj), j = l, 2,m?是接收端收到符号概率分布。信息率失真函数给出了熵压缩编码可能达到的最小熵率与失真的关系1.3 信息率失真函数的性质1、R(D)函数的定义域和值域R(D)的定义域为 允许失真度D的下限可以是零，这是不允许任何失真的情况。2、R(D)是关于平均失真度D的下凸函数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二元及等概率离散信源的信息率失真函数设二元信源计算率失真函数R(D)对于这种简单信源，可从D(S)解出S与D的显式表达式。二元等概率离散信源的率失真函数当上述二元信源呈等概率分布时，上面式子分别退化为3保真度准则下的信源编码定理 定理4.1(保真度准则下的信源编码定理,香农第三定理) 设R(D)为一离散无记忆信源的信息率失真函数，并且有有限的失真测度D。对于任意D ，*

5、 0以及任意长的码长k, 一定存在一种信源编码C,其码字个数为M 2kR(D)+e使编码后码的平均 失真度DD。定理的含义是：只要码长k足够长，总可以找到一种信源编码，使编码后的信息传输率略大于(直 至无限逼近)率失真函数R(D),而码的平均失真度不大于给定的允许失真度，即：D D 由于R(D)为给定D前提下信源编码可能达到的传信率的下限，所以香农第三定理说明了：达到此 下限的最佳信源编码是存在的。第二部分信源编码或信道编码典型案例的实现方案信源编码典型案例的实现方案-霍夫曼编码的 matlab 实现编码原理霍夫曼(Huffman)编码算法是满足前缀条件的平均二进制码长最短的编-源输出符号，而

6、将较 短的编码码字分配给较大概率的信源输出。算法是：在信源符号集合中，首先将两个最小概率的信 源输出合并为新的输出，其概率是两个相应输出符号概率之和。这一过程重复下去，直到只剩下一 个合并输出为止，这个最后的合并输出符号的概率为1。这样就得到了一张树图，从树根开始，将 编码符号1和0分配在同一节点的任意两分支上，这一分配过程重复直到树叶。从树根到树叶途经 支路上的编码最后就构成了一组异前置码，就是霍夫曼编码输出。编码步骤、码树形成过程：将信源概率按照从小到大顺序排序并建立相应的位置索引。然后按上述规则 进行信源合并，再对信源进行排序并建立新的位置索引，直到合并结束。在这一过程中每一次都把 排序

7、后的信源概率存入矩阵G中，位置索引存入矩阵Index中。这样，由排序之后的概率矩阵G 以及索引矩阵Index就可以恢复原概率矩阵P 了，从而保证了回溯过程能够进行下去。、码树回溯过程：在码树上分配编码码字并最终得到Huffman编码。从索引矩阵M的末行开始 回溯。在Index的末行2元素位置填入0和1。根据该行索引1位置指示，将索引1位置的编码(1)填入上一行的第一、第二元素位置， 并在它们之后分别添加0和1。将索引不为1的位置的编码值(0)填入上一行的相应位置(第3列)。以Index的倒数第二行开始向上，重复步骤(1)(3)，直到计算至Index的首行为止。程序代码%取得信源概率矩阵，并进行

8、合法性判断clear;P=input(请输入信源概率向量P=);N=length(P); forcomponent=1:1:N if(P(component)0.0001)error( 信源概率之和必须为 1);end%建立各概率符号的位置索引矩阵Index,利于编码后从树根进行回溯，从而得出对应的编码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中概率最小的两个元素合并，元素不足的地方补1end%

9、根据以上建立的Index矩阵，进行回溯，获取信源编码fori=l:N-lChar(i,:)=blanks(N*N);%初始化一个由空格符组成的字符矩阵N*N,用于存放编码 end%从码树的树根向树叶回溯，即从G矩阵的最后一行按与Index中的索引位置的对应关系向其第一 行进行编码Char(N-1,N)=0;%G中的NT行即最后一行第一个元素赋为0，存到Char中NT行的N列位置 Char(N-l,2*N)=1;%G中的NT行即最后一行第二个元素赋为1，存到Char中NT行的2*N列位 置%以下从G的倒数第二行开始向前编码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的编码码字填入到当前行的第一个编码位置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;%然后在当前行的第二个编码位置末尾填入1forj=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 中第一行索引将编码对应到 相应概率的信源符号上。fori=1:NResult(i,1:N)=Char(1,N*(find(Index(1,:)=i)-1)+1:find(Index(1,:)=i)*N);end%打印编码结果St ring二信源概率及