信息论与编码实验.doc

信息论与编码实验一种信源编码。设有离散无记忆信源X,P(X)二进制费诺编码为：1.将信源符号按概率从大到小的顺序排列2.将信源分成两组按两组概率之差为最小分3.上面一组编码为0，下面一组编码为1，一直分到一组只有一个信源为止4.将一个信源分组得到的0和1全部连接起来，组成该信源的码字，信源即得到自己的费诺编码该程序采用费诺编码算法，通过调用函数递归实现。调用用f1函数将输入变量赋初值，f1函数完成第一次分组后，并对字符数组x（存放码字）第一列赋值得到第一个分界点d，再用f1,f2函数相互调用和自身调用分别实现第一分界点以上和以下的符号再次分组并赋值给字符数组x;因为f1,f2函数分别每次，实现分界点以上和以下寻找下一个分界点所采用的算法不同，两个函数相互调用；本程序的难点是字符数组x如何存放码字，程序采用每次调用增加存放码字数组x的列数r，在寻得分界点后即赋值,可是最后程序输出只有第一列的值，原来变量x每次的值被冲了，采用global全局变量解决了上问题，不过采用global全局变量定义x后，x的类型需要转换为char最关键的是程序开头必须用clear all把global定义的变量归零，不然global定义的变量中存放的还是上次所存的值.clc;clear all;N=input(N=);%输入信源符号的个数s=0;l=0;H=0;for i=1:N fprintf(第%d个,i); p(i)=input(p=);%输入信源符号概率分布矢量,p(i)1 if p(i)=0 error(不符合概率分布) end s=s+p(i) H=H+(- p(i)*log2(p(i);%计算信源信息熵endif (s=1.000001)error(不符合概率分布)endtic;for i=1:N-1 %按概率分布大小对信源排序 for j=i+1:N if p(i)p(j) m=p(j);p(j)=p(i);p(i)=m; end endendx=f1(1,N,p,1);for i=1:N %计算平均码长 L(i)=length(find(x(i,:); l=l+p(i)*L(i);endn=H/l; %计算编码效率fprintf(按概率降序排列的码字:n);disp(x) %显示按概率降序排列的码字fprintf(平均码长:n);disp(l)% 显示平均码长fprintf(编码效率:n);disp(n) %显示编码效率fprintf(计算耗时time= %fn,toc);%函数f1存放于f1.mfunction x=f1(i,j,p,r)global x;x=char(x);if(j=i) return;else q=0;for t=i:j %对于区间i,j自上而下求累加概率值 q=p(t)+q;y(t)=q; endfor t=i:j%把所有自上而下的累加概率值与该区间总概率值减该累加概率值之差取绝对值存在一数组v(t)=abs(y(t)-(q-y(t); endfor t=i:j if(v(t)=min(v) %求该数组中最小的一个值来确定分界点位置 for k=i:t %赋值码字 x(k,r)=0; end for k=(t+1):j x(k,r)=1; end d=t; f1(i,d,p,r+1); %递归调用及相互调用 f2(d+1,j,p,r+1); f1(d+1,j,p,r+1); f2(i,d,p,r+1); else endend endreturn;%函数f2存放于f2.mfunction x=f2(i,j,p,r)global x;x=char(x);if(j=i) return;else q=0;for t=i:j %对于区间i,j自上而下求累加概率值 q=p(t)+q;y(t-i+1)=q; endfor t=1:j-(i-1)%把所有自上而下的累加概率值与该区间总概率值减该累加概率值之差取绝对值存在一数组v(t)=abs(y(t)-(q-y(t); endfor t=1:j-(i-1) if(v(t)=min(v) %求该数组中最小的一个值来确定分界点位置 d=t+i-1; for k=i:d %赋值码字 x(k,r)=0; end for k=(d+1):j x(k,r)=1; end f2(d+1,j,p,r+1);%递归调用及相互调用 f1(i,d,p,r+1); f2(i,d,p,r+1); f1(d+1,j,p,r+1); else endend endreturn;运行结果：N=6第1个p=0.32s = 0.3200第2个p=0.22s = 0.5400第3个p=0.04s = 0.5800第4个p=0.08s = 0.6600第5个p=0.16s = 0.8200第6个p=0.18s = 1按概率降序排列的码字:00 01 10 110 11101111平均码长: 2.4000编码效率: 0.9801计算耗时time= 0.094000信道容量的迭代算法：clc;clear all;N = input(输入信源符号X的个数N=); M = input(输出信源符号Y的个数M=); p_yx=zeros(N,M); %程序设计需要信道矩阵初始化为零fprintf(输入信道矩阵概率n)for i=1:N for j=1:M p_yx(i,j)=input(p_yx=);%输入信道矩阵概率 if p_yx(i)0 error(不符合概率分布) end endendfor i=1:N %各行概率累加求和 s(i)=0; for j=1:M s(i)=s(i)+p_yx(i,j); endendfor i=1:N %判断是否符合概率分布if (s(i)=1.000001) error(不符合概率分布)endendb=input(输入迭代精度：);%输入迭代精度for i=1:N p(i)=1.0/N; %取初始概率为均匀分布endfor j=1:M %计算q(j) q(j)=0; for i=1:N q(j)=q(j)+p(i)*p_yx(i,j); endend for i=1:N %计算a(i) d(i)=0; for j=1:M if(p_yx(i,j)=0) d(i)=d(i)+0; else d(i)=d(i)+p_yx(i,j)*log(p_yx(i,j)/q(j); end end a(i)=exp(d(i);endu=0;for i=1:N %计算u u=u+p(i)*a(i);endIL=log2(u); %计算ILIU=log2(max(a);%计算IUn=1;while(IU-IL)=b) %迭代计算 for i=1:N p(i)=p(i)*a(i)/u; %重新赋值p(i) end for j=1:M %计算q(j) q(j)=0; for i=1:N q(j)=q(j)+p(i)*p_yx(i,j); end end for i=1:N %计算a(i) d(i)=0; for j=1:M if(p_yx(i,j)=0) d(i)=d(i)+0; else d(i)=d(i)+p_yx(i,j)*log(p_yx(i,j)/q(j); end end a(i)=exp(d(i); end u=0; for i=1:N %计算u u=u+p(i)*a(i); end IL=log2(u); %计算IL IU=log2(max(a);%计算IU n=n+1;endfprintf(信道矩阵为：n);disp(p_yx);fprintf(迭代次数n=%dn,n);fprintf(信道容量C=%f比特/符号,IL);运行结果：输入信源符号X的个数N=2输出信源符号Y的个数M=4输入信道矩阵概率p_yx=0.5p_yx=0.25p_yx=0.125p_yx=0.125p_yx=0.25p_yx=0.5p_yx=0.125p_yx=0.125输入迭代精度：0.0001信道矩阵为： 0.5000 0.2500 0.1250 0.1250 0.2500 0.5000 0.1250 0.1250迭代次数n=1信道容量C=0.061278比特/符号Humff编码function h,l=huffman(p) if (length(find(p10e-10) error(Not a prob.vector,component do not add to 1) end n=length(p); q=p; m=zeros(n-1,n); for i=1:n-1 q,l=sort(q); m(i,:)=l(1:n-i+1),zeros(1,i-1); q=q(1)+q(2),q(3:n),1; end for i=1:n-1 c(i,:)=blanks(n*n); end c(n-1,n)=0; c(n-1,2*n)=1; for i=2:n-1 c(n-i,1:n-1)=c(n-i+1,n*(find(m(n-i+1,:)=1). -(n-2):n*(find(m(n-i+1,:)=1); c(n-i,n)=0; c(n-i,n+1:2*n-1)=c(n-i,1:n-1); c(n-i,2*n)=1; for j=1:i-1 c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,. n*(find(m(n-i+1,:)=j+1)-1)+1:n*find(m(n-i+1,:)=j+1); end end for i=1:n h(i,1:n)=c(1,n*(find(m(1,:)=i)-1)+1:find(m(1,:)=i)*n); ll(i)=length(find(abs(h(i,:)=32); end l=sum(p.*ll); h,l=huffman(p),输入为一维行矩阵p，p为各符号的