信息论与编码课程大作业二进制哈夫曼编码资料.docVIP

信息论与编码课程大作业 题 目： 二进制哈夫曼编码 学生姓名： 学 号： 2010020200 专业班级： 2010级电子信息班 2013年 5月 18日 PAGE PAGE 1 二进制哈夫曼编码 1、二进制哈夫曼编码的原理及步骤 1、1信源编码的计算 设有N个码元组成的离散、无记忆符号集，其中每个符号由一个二进制码字表示，信源符号个数n、信源的概率分布P={p(si)},i=1,…..,n。且各符号xi的以li个码元编码，在变长字编码时每个符号的平均码长为 ； 信源熵为： ； 唯一可译码的充要条件： ； 其中m为码符号个数，n为信源符号个数，Ki为各码字长度。 构造哈夫曼数示例如下图所示。 11 0.400.60 0.40 0.60 0.300.30 0.30 0.30 0.150.15 0.15 0.15 0.090.60 0.09 0.60 0.030.030.040.05 0.03 0.03 0.04 0.05 1、2 二元霍夫曼编码规则 （1）将信源符号依出现概率递减顺序排序。 （2）给两个概率最小的信源符号各分配一个码位“0”和“1”，将两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含（n-1）个信源符号的新信源。称为信源的第一次缩减信源，用s1 表示。 （3）将缩减信源 s1 的符号仍按概率从大到小顺序排列，重复步骤(2)，得到只含（n-2）个符号的缩减信源s2。 （4）重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号 的概率之和必为 1，然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。 1、3 二元哈夫曼编码流程图如下图所示。 开始 开始 等待数据输入 等待数据输入 判断输入的概 率是否小于零 判断输入的概 率是否小于零 是 结束 显示结果 计算码长 生成一个n - 1行n列的数组判断概率和是 否大于1 结束 显示结果 计算码长 生成一个n - 1行n列的数组 判断概率和是 否大于1 是 按照哈弗曼的编码规则进行编码 按照哈弗曼的编码规则进行编码 计算信源熵 计算编码效率 2、二元哈夫曼编码程序 p=input(please input a number:) %提示输入界面 n=length(p); for i=1:n if p(i)0 fprintf(\n The probabilities in huffman can not less than 0!\n); p=input(please input a number:) %如果输入的概率数组中有小于 0 的值， end end if abs(sum(p)-1)0 fprintf(\n The sum of the probabilities in huffman can more than 1!\n); p=input(please input a number:) %如果输入的概率数组总和大于 1，则重 end q=p; a=zeros(n-1,n); %生成一个 n-1 行 n 列的数组 for i=1:n-1 [q,l]=sort(q); %对概率数组q进行从小至大的排序，并且用l数组返回一个q排序前的顺序编号 a(i,:)=[l(1:n-i+1),zeros(1,i-1)]; %由数组 l 构建一个矩阵，该矩阵表明概率合并 q=[q(1)+q(2),q(3:n),1]; %将排序后的概率数组 q 的前两项，即概率最小的两 end for i=1:n-1 c(i,1:n*n)=blanks(n*n); end c(n-1,n)=0; %由于a矩阵的第n-1行的前两个元