编码方式如下:
首先将信源消息符号按其出现的概率大小依次从大到小排列,为了编成唯一可译码,计算第i个消息的累加概率P=∑p(a),并将累加概率Pi变换成二进制数。
最后去Pi二进制数的小数点后Ki位提取出,即为给出符号的二进制码字。
由此可见香农编码法冗余度稍大,实用性不强,但他是依据编码定理而来,因此具有重要的理论意义。
1.2费诺编码方法
费诺编码属于概率匹配编码,但不是最佳的编码方法。
在编N进制码时首先将信源消息符号按其出现的概率依次由小到大排列开来,并将排列好的信源符号按概率值分N大组,使N组的概率之和近似相同,并对各组赋予一个N进制码元0、1……N-1。
之后再针对每一大组内的信源符号做如上的处理,即再分为概率和相同的N组,赋予N进制码元。
如此重复,直至每组只剩下一个信源符号为止。
此时每个信源符号所对应的码字即为费诺码。
针对同一信源,费诺码要比香农码的平均码长小,消息传输速率大,编码效率高。
1.3哈夫曼编码方法
编码方法:
也是先将信源符号按其出现的概率大小依次排列,并取概率最小的字母分别配以0和1两个码元(先0后1或者先1后0,以后赋值顺序固定),再将这两个概率想家作为一个新字母的概率,与未分配的二进制符号的字母重新排队。
并不断重复这一过程,直到最后两个符号配以0和1为止。
最后从最后一级开始,向前返回得到各个信源符号所对应的码元序列,即为相应的码字。
哈夫曼编码方式得到的码并非唯一的。
在对信源缩减时,两个概率最小的符号合并后的概率与其他信源符号的概率相同时,这两者在缩减信源中的排序将会导致不同码字,但不同的排序将影响码字的长度,一般将合并的概率放在上面,这样可获得较小的码方差。
哈夫曼码的平均码长最小,消息传输效率最大,编码效率最高。
鉴于以上编码的特点与我所掌握的知识下面我将着重介绍费诺编码。
2.费诺编码的描述
费诺编码是一种信源编码.
信源编码分为无失真信源编码和限失真信源编码。
一般称无失真信源编码为第一机械定理;限失真信源编码定理称为第三极限定理。
由于信源符号之间存在分布不均匀和相关性,使得信源存在冗余度,信源编码的主要任务就是减少冗余,提高编码效率。
具体说,就是针对信源输出符号序列的统计特性,寻找一定的方法把信源输出符号序列变换为最短码字序列的方法。
信源编码的基本途径有两个:
使编码中各个符号出现的概率尽可能地相等,即概率均匀化。
信源编码的基础是信息论中的两个编码定理:
无失真编码定理和限失真编码定理。
其中无失真编码定理是可逆编码的基础。
可逆是指当信源符号转换成代码后,可从代码无失真地恢复信源符号。
当已知信源符号的概率特性时,可计算它的符号熵,这表示每个信源符号所载有的信息量。
编码定理不但证明了必定存在一种编码方法,可使代码的平均长度可任意接近但不低于符号熵,而且还阐明达到这目标的途径,就是使概率与码长匹配。
无失真编码或可逆编码只适用于离散信源。
对于连续信源,编成代码后就无法无失真地恢复原来的连续值,因为后者的取值可有无限多个。
此时只能根据率失真编码定理在失真受限制的情况下进行限失真编码。
信源编码定理出现后,编码方法就趋于合理化。
凡是能载荷一定的信息量,且码字的平均长度最短,可分离的变长码的码字集合称为最佳变长码。
能获得最佳码的编码方法主要有:
香农码(Shannon)、费诺(Fano)、哈夫曼(Huffman)编码等。
3.费诺编码步骤
1.将信源消息符号按其出现的概率大小依次排列:
P1>=P2>=…>=Pn。
2.依次排列的信源符号按概率值分为两大组,使两个组的概率之和近似相同,并对各组赋予一个二进制码元“0”和“1”。
3.使划分后的两个组的概率之和近似相同,并对各组赋予一个二进制符号“0”和“1”。
4.如此重复,直至每个组只剩下一个信源符号为止。
5.信源符号所对应的码字即为费诺码。
4.费诺编码特点
费诺编码,它编码后的费诺码要比香农码的平均码长小,消息传输速率大,编码效率高,但它属于概率匹配编码它不是最佳的编码方法[1]。
费诺编码方法属于概率匹配编码,具有如下特点:
1、概率大,则分解次数小;概率小则分解次数多。
这符合最佳码原则。
2、码字集合是唯一的。
3、分解完了,码字出来了,码长也有了,即先有码字后有码长。
因此,费诺编码方法又称为子集分解法。
2.2设计步骤
1.费诺编码过程框图
图1费诺码编码过程图
2.费诺编码过程表
消息符号Xi
各个符号概率P(Xi)
第一次分组
第二次分组
第三次分组
第四次分组
二元码字
码长
X1
0.19
0
0
00
2
X2
0.18
1
0
010
3
X3
0.17
1
011
3
X4
0.16
1
0
10
2
X5
0.13
1
0
110
3
X6
0.10
1
0
1110
4
X7
0.06
1
1111
5
X
0.01
11111
5
表1费诺码编码过程表
3.计算平均码长、编码效率、冗余度。
4.冗余度
在数据传输中,由于衰减或干扰会使数据代码发生突变,此时就要提高数据代码的抗干扰能力.这必须在原二进制代码长度的基础上增加几位二进制代码的长度,使相应数据具有一定的冗余度,也称做富裕度.
简单地说,所谓冗余度,就是从安全角度考虑多余的一个量,这个量就是为了保障仪器、设备或某项工作在非正常情况下也能正常运转。
目前大多现代产品和工程设计中都应用了冗余度这个思想和理论。
在许多医疗单位中药品存量不足,卫生材料存量不够,一遇突发事件,就会造成缺货,造成涨价风波,影响社会安定。
在我们的医院中,由于各项费用都与经济效益挂钩,医疗设备等卫生装备冗余度很不够,基本上只能按平时的正常运转设置,甚至有的都没达到。
一遇突发事件,这点装备就显得严重不足。
冗余度,通俗的讲就是数据的重复度。
在一个数据集合中重复的数据称为数据冗余
第3章费诺编码的MATLAB实现
3.1MATLAB简介
Matlab是MathWorks公司于1982年推出的一套高性能的数值计算和可视化软件。
它集数值分析、矩阵运算、信号处理和图形显示于一体,构成了一个方便、界面良好的用户环境。
它还包括了Toolbox(工具箱)的各类问题的求解工具,可用来求解特定学科的问题。
其特点是:
[16,17,18]
(1)可扩展性:
Matlab最重要的特点是易于扩展,它允许用户自行建立指定功能的M文件。
对于一个从事特定领域的工程师来说,不仅可利用Matlab所提供的函数及基本工具箱函数,还可方便地构造出专用的函数。
从而大大扩展了其应用范围。
当前支持Matlab的商用Toolbox(工具箱)有数百种之多。
而由个人开发的Toolbox则不可计数。
(2)易学易用性:
Matlab不需要用户有高深的数学知识和程序设计能力,不需要用户深刻了解算法及编程技巧。
(3)高效性:
Matlab语句功能十分强大,一条语句可完成十分复杂的任务。
如fft语句可完成对指定数据的快速傅里叶变换,这相当于上百条C语言语句的功能。
它大大加快了工程技术人员从事软件开发的效率。
据MathWorks公司声称,Matlab软件中所包含的Matlab源代码相当于70万行C代码。
3.2MATLAB广泛应用
由于Matlab具有如此之多的特点,在欧美高等院校,Matlab已成为应用于线性代数、自动控制理论、数理统计、数字信号处理、时间序列分析、动态系统仿真等高级课程的基本教学工具:
在研究单位、工业部门,Matlab也被广泛用于研究和解决各种工程问题。
当前在全世界有超过40万工程师和科学家使用它来分析和解决问题[14]。
Matlab作为科学计算软件,主要适用于矩阵运算和信息处理领域的分析设计,它使用方便、输入简捷,运算高效、内容丰富,并且有大量的函数库可提供使用,与Basic,C和Fortran相比,用Matlab编写程序,其问题的提出和解决只需要以数学方式表达和描述,不需要大量繁琐的编程过程。
利用Matlab软件并通过计算机仿真光学空间滤波实验过程的新方法,其特点是:
既可以随意改变所设计滤波器的参量,又可以对输入图像进行振幅、相位或复合滤波,并且可实现傅里叶变换频谱中相位信息的提取、存储和利用,因而能够完成一般光学实验中往往难以实现的某些操作.并分别给出了网格滤波、低通、高通及相位滤波等仿真实验结果。
这种仿真实验给光学滤波器的设计和图象处理带来很大方便,同时也为相关器件的设计提供了一条新的途径。
3.3MATLAB软件系统构成
MATLAB软件主要包括主包、Simulink和工具箱三大部分组成。
下图为MATLAB界面:
3.4MATLAB语言
MATLAB可以认为是一种解释性语言,可以直接在MATLAB命令窗口键入命令,也可以在编辑器内编写应用程序,这样MATLAB软件对命令或程序中各条语句进行翻译,然后在MATLAB环境下对它进行处理,最后返回运算结果。
MATLAB语言的基本语句结构为:
变量名列表=表达式
其中等号左边的变量名列表为MATLAB语句的返回值,等号右边是表达式的定义,它可以是MATLAB允许的矩阵运算,也可以使函数调用。
等号右边的表达式可以由分号结束,也可以由逗号或回车结束,但他们的含义是不同的,如果用分号结束,则左边的变量结果将不在屏幕上显示出来,否则将把结果全部显示出来。
MATLAB语言和C语言有所不同,在调用函数式MATLAB允许一次返回多个结果,这时等号左边是用[]括起来的变量列表。
3.4MATLAB编程
费诺编码也是一种常见的信源编码方法。
信源符号以概率递减的次序排列进来,将排列好的信源符号划分为两大组,使第组的概率和近于相同,并各赋于一个二元码符号”0”和”1”.然后,将每一大组的信源符号再分成两组,使同一组的两个小组的概率和近于相同,并又分别赋予一个二元码符号.依次下去,直至每一个小组只剩下一个信源符号为止.这样,信源符号所对应的码符号序列则为编得的码字。
根据其原理所得到的MATLAB程序如下:
clc;
clear;
A=[0.19,0.18,0.17,0.16,0.13,0.10,0.06,0.01];
A=fliplr(sort(A));%降序排列
[m,n]=size(A);
fori=1:
n
B(i,1)=A(i);%生成B的第1列
end
%生成B第2列的元素
a=sum(B(:
1))/2;
fork=1:
n-1
ifabs(sum(B(1:
k,1))-a)<=abs(sum(B(1:
k+1,1))-a)
break;
end
end
fori=1:
n%生成B第2列的元素
ifi<=k
B(i,2)=0;
else
B(i,2)=1;
end
end
%生成第一次编码的结果
END=B(:
2)';
END=sym(END);
%生成第3列及以后几列的各元素
j=3;
while(j~=0)
p=1;
while(p<=n)
x=B(p,j-1);
forq=p:
n
ifx==-1
break;
else
ifB(q,j-1)==x
y=1;
continue;
else
y=0;
break;
end
end
end
ify==1
q=q+1;
end
ifq==p|q-p==1
B(p,j)=-1;
else
ifq-p==2
B(p,j)=0;
END(p)=[char(END(p)),'0'];
B(q-1,j)=1;
END(q-1)=[char(END(q-1)),'1'];
else
a=sum(B(p:
q-1,1))/2;
fork=p:
q-2
ifabs(sum(B(p:
k,1))-a)<=abs(sum(B(p:
k+1,1))-a);
break;
end
end
fori=p:
q-1
ifi<=k
B(i,j)=0;
END(i)=[char(END(i)),'0'];
else
B(i,j)=1;
END(i)=[char(END(i)),'1'];
end
end
end
end
p=q;
end
C=B(:
j);
D=find(C==-1);
[e,f]=size(D);
ife==n
j=0;
else
j=j+1;
end
end
B
A
END
fori=1:
n
[u,v]=size(char(END(i)));
L(i)=v;
end
avlen=sum(L.*A)
encodef=2.61/avlen
3.5运行结果及分析
图3运行结果图
第4章总结
本学期的课程设计结束了,通过本次设计的经历我认识到了许多专业知识上的不足之处,对于老师课堂上的理论知识进一步的进行了巩固,在以后的学习中还应该继续努力。
仿真时,我学习巩固了仿真软件MATLAB,学习到了仿真软件的一些作用。
和Mathematica、Maple并称为三大数学软件。
它在数学类科技应用软件中在数值计算方面首屈一指。
MATLAB可以进行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程序等,主要应用于工程计算、控制设计、信号处理与通讯、图像处理、信号检测、金融建模设计与分析等领域。
MATLAB的基本数据单位是矩阵,它的指令表达式与数学、工程中常用的形式十分相似,故用MATLAB来解算问题要比用其他的仿真软件等语言完成相同的事情简捷得多,并且应用它也吸收了像Maple等软件的优点,使它成为一个强大的数学软件。
可以说MATLAB就是我们设计的好帮手。
通过这次课程设计,我们又掌握了许多新知识,学习巩固了MATLAB软件.同时也巩固了专业知识,为以后学习打下了好的基础,每次的课程设计我们都应该认真完成它。
它对我们以后的学习和工作都有着很大的帮助,我们学习了以后工作可能用得到的东西,学习了新的东西。
参考文献
[1]·曹雪虹,张宗橙·信息论与编码·清华大学出版社·2009.2·
[2]·樊昌信,曹丽娜·通信原理·国防工业出版社·2006.9.·
[3]·严蔚敏,吴伟民·数据结构·清华大学出版社·2007.·
[4]·谭浩强·C程序设计·清华大学出版社·2005.·
[5]·徐利民,舒君,谢优忠·基于MATLAB的信号与系统实验教程·清华大学出版社·2010.2·
[6]·周炯磐·信息论基础·人民邮电出版社·1983.·
[7]·周炯磐,丁晓明·信源编码原理·人民邮电出版社·1999.·
[8]·周荫清信·息理论基础·北京航空航天大学出版社·1993.·
[9]·吴伯修,祝宗泰,钱霖君·信息论与编码·东南大学出版社·1991.·
[10]·阙喜戎·信息安全原理及应用·清华大学出版社·2003.·