信息论大作业

电子工程学院。班。号。

编码。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'];

信息论大作业

信息论作业

信息论编码作业

《信息论》全部作业详解

其他用户还读了