电子工程学院。班。号。
编码。1. huffman 编码原理:
将信源符号按概率从大到小的顺序排列,令p(x1)≥ p(x2)≥…p(xn)
给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”,将这两个信源符号合并成一个新符号,并用这两个最小的概率之和作为新符号的概率,结果得到一个只包含(n-1)个信源符号的新信源。称为信源的第一次缩减信源,用s1表示。
将缩减信源s1的符号仍按概率从大到小顺序排列,重复步骤2,得到只含(n-2)个符号的缩减信源s2。
重复上述步骤,直至缩减信源只剩两个符号为止,此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始,依编码路径向前返回,就得到各信源符号所对应的码字。
2. 霍夫曼编码优缺点:
1) 编出来的码都是异字头码,保证了码的唯一可译性。
2) 由于编码长度可变。因此译码时间较长,使得霍夫曼编码的压缩与还原相当费时。
3) 编码长度不统一,硬件实现有难度。
4) 对不同信号源的编码效率不同,当信号源的符号概率为2的负幂次方时,达到100%的编码效率;若信号源符号的概率相等,则编码效率最低。
5) 由于0与1的指定是任意的,故由上述过程编出的最佳码不是唯一的,但其平均码长是一样的,故不影响编码效率与数据压缩性能。
3.编码流程:
读入一幅图像的灰度值;
1. 将矩阵的不同数统计在数组c的第一列中;
2. 将相同的数占站整个数组总数的比例统计在数组p中;
3. 找到最小的概率,相加直到等于1,把最小概率的序号存在tree第一列中,次小放在第二列,和放在p像素比例之后;
4. c数组第一维表示值,第二维表示**数值大小,第三维表示**的位数;
5. 把概率小的值为1标识,概率大的值为0标识;
6. 计算信源的熵 ;
7. 计算平均码长 ;
8. 计算编码效率';
9. 计算冗余度。
源程序:p=input('请输入数据:')
n=length(p);
for i=1:n
if p(i)<0
fprintf(' 提示:概率值不能小于0!');
p=input('请重新输入数据:')
endend
if abs(sum(p))>1
fprintf(' 哈弗曼码中概率总和不能大于1!');
p=input('请重新输入数据:')
endq=p;
a=zeros(n-1,n); 生成一个n-1 行n 列的数组。
for i=1:n-1
[q,l]=sort(q);
a(i,:)l(1:n-i+1),zeros(1,i-1)];
q=[q(1)+q(2),q(3:n),1];
endfor i=1:n-1
c(i,1:n*n)=blanks(n*n);
endc(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(a(n-i+1,:)1))-n-2):n*(find(a(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(a(n-i+1,:)j+1)-1)+1:n*find(a(n-i+1,:)j+1));
endend完成huffman 码字的分配。
for i=1:n
h(i,1:n)=c(1,n*(find(a(1,:)i)-1)+1:find(a(1,:)i)*n);
ll(i)=length(find(abs(h(i,:)32));计算每一个huffman 编码的长度。
endl=sum(p.*ll计算平均码长。
fprintf(' huffman编码结果为:');h
fprintf(' 编码的平均码长为:');l
hh=sum(p.*(log2(p)))计算信源熵。
fprintf(' 信源熵为:hh
fprintf(' 编码效率为:t=hh/l
%计算编码效率。
运行结果为:
请输入数据:[0.1,0.1,0.1,0.2,0.1,0.1,0.2,0.1]
huffman编码结果为:h =
编码的平均码长为:l =
信源熵为:hh =
编码效率为:t =
编码:fano码:
费诺编码属于概率匹配编码,但它不是最佳的编码方法。不过有时也可以得到紧致码的性能。信源符号以概率递减的次序排列进来,将排列好的信源符号划分为两大组,使第组的概率和近于相同,并各赋于一个二元码符号”0”和”1”.
然后,将每一大组的信源符号再分成两组,使同一组的两个小组的概率和近于相同,并又分别赋予一个二元码符号。依次下去,直至每一个小组只剩下一个信源符号为止。这样,信源符号所对应的码符号序列则为编得的码字。
费诺码编码的一般步骤如下:
1)将信源消息符号按其出现的概率大小依次排列排列:。
2)将依次排列的信源符号按概率值分为两大组,使两个组的概率之和近似相同,并且对各组赋予一个二进制码元“0”和“1”。
3)将每一大组的信源符号再分成两组,使划分后的两个组的概率之和近似相同,并且对各组赋予一个二进制符号“0”和“1”。以上两部分在程序中。
4)如此重复,直到每个组只剩下一个信源符号为止。在程序中本部分采用递归思想。
信源符号所对应的码字即为费诺编码。
费诺编码特点。
费诺编码,它编码后的费诺码要比香农码的平均码长小,消息传输速率达,编码效率高,但它属于概率匹配编码它不是最佳的编码方法。
源程序:a=input('input the a:')
a=fliplr(sort(a));降序排列。
m,n]=size(a);
for i=1:n
encoding(i,1)=a(i);%生成b的第1列。
end生成b第2列的元素。
a=sum(encoding(:,1))/2;
for k=1:n-1
if abs(sum(encoding(1:k,1))-a)<=abs(sum(encoding(1:k+1,1))-a)
break;
endend
for i=1:n%生成b第2列的元素。
if i<=k
encoding(i,2)=0;
elseencoding(i,2)=1;
endend
生成第一次编码的结果。
code=encoding(:,2)';
code=sym(code);
生成第3列及以后几列的各元素。
j=3;while (j~=0)
p=1;while(p<=n)
x=encoding(p,j-1);
for q=p:n
if x==-1
break;
elseif encoding(q,j-1)==x
y=1;continue;
elsey=0;
break;
endend
endif y==1
q=q+1;
endif q==p|q-p==1
encoding(p,j)=-1;
elseif q-p==2
encoding(p,j)=0;
code(p)=[char(code(p)),0'];
encoding(q-1,j)=1;
code(q-1)=[char(code(q-1)),1'];
elsea=sum(encoding(p:q-1,1))/2;
for k=p:q-2
if abs(sum(encoding(p:k,1))-a)<=abs(sum(encoding(p:k+1,1))-a);
break;
endend
for i=p:q-1
if i<=k
encoding(i,j)=0;
code(i)=[char(code(i)),0'];
elseencoding(i,j)=1;
code(i)=[char(code(i)),1'];
信息论作业
b.2 唯一可译码判决准则。1.实验目的。1 进一步熟悉唯一可译码判决准则 2 掌握c语言字符串处理程序的设计和调试技术。2.实验要求。1 已知 信源符号个数,码字集合c。2 输入 任意的一个码。码字个数和每个具体的码字在运行时从键盘输入。3 输出 判决 是唯一可译码 不是唯一可译码 4 源程序格式...
信息论编码作业
信息论编码。一 信息论的认识。1.消息是信息的载荷者。信息是抽象的,消息是具体的。要研究信息,还得从研究消息入手。2.由于信源发送什么消息预先是不可知的,只能用概率空间来描述信源。3.单符号信源 输出是单个符号 的消息。离散信源。连续信源。4.平稳随机序列信源 信源输出的消息由一系列符号序列所组成,...
《信息论》全部作业详解
第2章信源熵。2.1 试问 制 八进制脉冲所含信息量是二进制脉冲的多少倍?答 2倍,3倍。2.2 一副充分洗乱了的牌 含52张牌 试问。1 任一特定排列所给出的信息量是多少?2 若从中抽取13张牌,所给出的点数都不相同,能得到多少信息量?解 1 2 任取13张,各点数不同的概率为,信息量 9.479...