二元Haffman编码.doc

河南师范大学计算机与信息工程学院信息论与编码实验报告学院：计算机与信息技术学院年级：2012级专业：通信工程学号：1208224048姓名：刘文会指导老师：刘艳芳内容：二元Haffman编码计算机与信息工程学院验证性实验报告专业：通信工程 年级/班级：12级通行工程班 20142015学年第一学期课程名称信息论与编码实验指导教师刘艳芳本组成员学号姓名学号：1208224048 姓名：刘文会实验地点计算机楼216机房实验时间2014.12.2项目名称二元Haffman编码实验类型验证性一、 实验目的1） 了解haffman编码的方法及详细步骤，知道二元haffman编码的实现过程。2） 能够用matlab编写出二元haffman编码。二、 实验仪器或设备装有matlab的计算机一台。三、 实验内容及步骤1） 霍夫曼（Huffman）编码算法是满足前缀条件的平均二进制码长最短的编-源输出符号，而将较短的编码码字分配给较大概率的信源输出。2） 编码方法：a. 先判断输入的概率是否满足概率空间。b. 将信源消息符号按其出现的概率大小依次排列，p1p2pqc. 取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，从而得到只包含q-1个符号的新信源S1。d. 对重排后的缩减信源S1重新以递减次序排序，两个概率最小符号重复步骤(2)的过程。e. 不断继续上述过程，直到最后两个符号配以0和1为止。f. 从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。注意：可先生成编码表 0.40.40.40.40.20.20.40.60.20.20.200.10.2000.1222编码表每列为缩减信源概率第一列为输入n个信源概率；第二列为第一次缩减后t=n-1个概率；第（n，2）元素放置合并元素在本列中位置；如果输入n个概率，则需要缩减n-1次后，剩下t=2两个概率；所以编码表可以定义为n行n-1列。3） 编码表生成后，从最后一列开始编码。首先最后一列两个元素分别编码为0和1；对其中某j列，其前t-2个元素编码为j+1列非合并概率移植过来。在编码表中从最后一列向前逐列编码，第j列前t-2个元素的编码直接复制第j+1列各 数的编码结果；而最后两个元素(将要合并的两项) 的编码是寻找在第j+1列合并后数值的编码结果，然后在这个码字的基础上分别增加0和1。第t-1元素和第t个元素为j+1列合并概率编码分别加0和加1。（合并概率的位置已经在本列最后一个元素中标出）四、 实验程序1） 判断函数是否满足概率空间的function函数gailv%满足概率空间的函数function x=gailv(P)b=(P=0);x=(sum(b)=length(P)&(sum(P)=1);2） 对输入的一组概率进行二元霍夫曼编码的函数Huffman%二元霍夫曼编码，（若合并后元素值和其它值重复，将其放在最高层）function ping_jun_ma_chang,H,xiao_lv,p,c=Huffman(p)x=gailv(p);%判断p是否满足概率空间if x=1 error(输入概率不满足概率空间);%如果输入的概率之和不为1则显示错误endn=length(p);p1=fliplr(sort(p);%将信源从大到小排序%biao=zeros(n,n-1);%建立一个n,n-1的零矩阵，表示霍夫曼编码表biao(:,1)=p1; %将排序后的概率空间赋值给表的第一列pp=biao(n,1)+biao(n-1,1);%第1列（原概率空间）的最后两个元素相加p1(n-1)=pp; %将排序后概率空间的第n-1个值替换成最后两个值的和p1(n)=0; %将第1列合并后空余的概率元素位置补0p1=fliplr(sort(p1);%将合并后的信源再从大到小排序%*下面的循环是生成编码表的第2至n-1列*t=n-1; %t表示编码表第2列的概率元素个数for j=2:n-1 %j表示编码表的第j列 biao(:,j)=p1;%将合并排序后的概率空间赋值给表的第j列 A=find(p1=pp); %寻找第j-1列后两项求和后的概率在第j列的位置,即第A行 biao(n,j)=A(1); %将每列的第n行数字都改为A，表示上一列合并后元素所在的位置 pp=(biao(t-1,j)+biao(t,j);%将第j列的最后两个元素相加 p1(t-1)=pp; p1(t)=0; %将第j+1列合并后空余的概率元素位置补0 p1=fliplr(sort(p1);%将信源从大到小排序 t=t-1; %t表示第j+1列概率元素的个数endbiao %输出霍夫曼编码表%*下面开始给编码表每一列后两个元素编码* %整体编程思路：在编码表中从最后一列向前逐列编码，第j列前t-2个元素的编码直接复制第j+1列各数的编码结果；而最后两个元素(将要合并的两项) %的编码是寻找在第j+1列合并后数值的编码结果，然后在这个码字的基础上分别增加0和1c=cell(1,n); %建立一个1,n的元胞数组,存放n个信源符号编码后的的码字序列c1=0; %将最后一列的第一个元素赋0c2=1; %将最后一列的第二个元素赋1c1=c; %c1作为码字的传递变量t=2+1; %此时t代表编码表倒数第2列的概率元素个数,是在最后一列的基础上多1for j=n-2:-1:1 %j表示编码表的第j列 %*先给前t-2个非合并元素编码* biao( biao(n,j+1),j+1)=10; %给j+1行的合并概率随便赋一个大于1的数 x=find(0biao(:,j+1)& biao(:,j+1) Huffman at 5输入概率不满足概率空间是不满足概率空间的，不允许编码。2） 当输入的值为p=0.2,0.1,0.2,0.1,0.4时，得出的结果如下：3） 当输入的p=0.2,0.4,0.1,0.3时，得出的结果如下图所示