信息论与编码课程大作业 题 目: 二进制哈夫曼编码 学生姓名: 学 号: ********** 专业班级: 2010 级电子信息班 2 0 1 3 年 5 月 1 8 日 1 二进制哈夫曼编码 1、二进制哈夫曼编码的原理及步骤 1、1 信源编码的计算 设有N 个码元组成的离散、无记忆符号集,其中每个符号由一个二进制码字表示,信源符号个数n、信源的概率分布P={p(si)},i=1,…..,n。且各符号xi的以li 个码元编码,在变长字编码时每个符号的平均码长为nilixipL1)( ; 信源熵为:)(lo g)()(1xipxipXHni ; 唯一可译码的充要条件:11niKim ; 其中m 为码符号个数,n 为信源符号个数,Ki 为各码字长度。 构造哈夫曼数示例如下图所示。 1、2 二元霍夫曼编码规则 (1)将信源符号依出现概率递减顺序排序。 (2)给两个概率最小的信源符号各分配一个码位“0”和“1”,将两个信源符号合并成一个新符号,并用这两个最小的概率之和作为新符号的概率,结0.60 0.15 0.09 0.30 1.000.60 0.03 0.30 0.15 0.40 0.05 0.04 0.03 2 果得到一个只包含(n-1)个信源符号的新信源。称为信源的第一次缩减信源,用s1 表示。 (3)将缩减信源 s1 的符号仍按概率从大到小顺序排列,重复步骤(2),得到只含(n-2)个符号的缩减信源s2。 (4)重复上述步骤,直至缩减信源只剩两个符号为止,此时所剩两个符号 的概率之和必为 1,然后从最后一级缩减信源开始,依编码路径向前返回,就得到各信源符号所对应的码字。 1、3 二元哈夫曼编码流程图如下图所示。 是 是 开始 等待数据输入 判 断 输 入 的概 率是否小于零 判断概率和是 否大于 1 生成一个n - 1 行 n 列的数组 按照哈弗曼的编码规则进行编码 计算码长 计算编码效率 计算信源熵 显示结果 结束 3 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); %生成一个 ...