信息论与编码课程设计报告
设计题目:统计信源熵、香农编码与费诺编码
专业班级:XXXXXXXXXXXX
姓名:XXXXXXXXXXXX
学号:XXXXXXXXXXXX
指导老师:XXXXXXXXXXXX
成绩:
时间:2015年3月31日
目录
一、设计任务与要求 (2)
二、设计思路 (2)
三、设计流程图 (5)
四、程序及结果 (7)
五、心得体会 (11)
六、参考文献 (12)
附录 (13)
一、 设计任务与要求
1. 统计信源熵
要求:统计任意文本文件中各字符(不区分大小写)数量,计算
字符概率,并计算信源熵。
2. 香农编码
要求:任意输入消息概率,利用香农编码方法进行编码,并计算
信源熵和编码效率。
3. 费诺编码
要求:任意输入消息概率,利用费诺编码方法进行编码,并计算
信源熵和编码效率。
二、 设计思路
1、统计信源熵:
统计信源熵就是对一篇英文文章中的i 种字符(包括标点符
号及空格,英文字母不区分大小写)统计其出现的次数count i (),
然后计算其出现的概率()p i ,最后由信源熵计算公式:
1()()log ()n
i i n H x p x p x ==-∑
算出信源熵()H x 。所以整体步骤就是先统计出文章中总的字符
数,然后统计每种字符的数目,直到算出所有种类的字符的个数,
进而算出每种字符的概率,再由信源熵计算公式计算出信源熵。
在这里我选择用Matlab 来计算信源熵,因为Matlab 中系统自带
了许多文件操作和字符串操作函数,其计算功能强大,所以计算
信源熵很是简单。
2、香农编码
信源编码模型:
信源编码就是从信源符号到码符号的一种映射f ,它把信源输出
的符号i a 变换成码元序列i x 。
1,2,...,,i i N f a i q x =→:
1:{,...,}q S s a a ∈ 信源 12{,...,}li i i i i X x x x = 码元
1{,...,}1,2,...,i q S a a i N ∈=
1,2,...,N i q =
1:{,...,}r X x x x ∈ 码符号
N 次扩展信源无失真编码器
凡是能载荷一定的信息量,且码字的平均长度最短,可分离
的变长码的码字集合都可以称为最佳码。为此必须将概率大的信
息符号编以短的码字,概率小的符号编以长的码字,使得平均码
字长度最短。能获得最佳码的编码方法主要有:香农(Shannon )、
费诺(Fano )、哈夫曼(Huffman )编码等。
香农第一定理:
离散无记忆信源为
1212......()()()......q q s s s S p s p s p s P ??
??=????????
熵()H S ,其N 次扩展为
1212......()()()......N q q S p p p P αααααα????=?????????
熵为()N H S ,码符号集为12(,,...,)r X x x x =。先对信源N S 进行编码,总
可以找到一种编码方法,构成唯一可译码,使S 中每个信源符号
所需的平均码长满足
()1()log log N L H S H S r N N r
+>≥ 且当N →∞时有()()log lim N r N L H S H S N r →∞== ,L 是平均码长1()N
q i i i L p αλ==∑,
i λ是i α对应的码字长度。
香农编码方法:
(1) 将信源消息符号按其出现的概率大小依次排列:12...n p p p ≥≥
(2)确定满足下列不等式整数码长i K 为
()()1i i i lb p K lb p -≤≤-+
(3)为了编成唯一可译码,计算第i 个消息的累加概率为
1
1()i i k k P p a -==∑
(4)将累加概率i P 变成二进制数。
(5)取i P 二进制数小数点后i K 位即为该消息符号的二进制码字。
3、费诺编码方法
(1)将信源消息符号按其出现的概率大小依次排列:12...n p p p ≥≥
(2)将依次排列的信源符号按概率值分为两大组,使两个组的
概率之和近似相同,并对各组赋予一个二进制码元“0”和“1”。
(3)将每一大组的信源符号再分为两组,使划分后的两个组的
概率之和近似相同,并对各组赋予一个二进制符号“0”和“1”。
(4)如此重复,直至每个组只剩下一个信源符号为止。
(5)信源符号所对应的码字即为费诺码。
三、 设计流程图
unm
由信源熵计算公式1()()log ()n
i i n H x p x p x ==-∑计算出信源熵
⑤
2、香农编码
输入概率矩阵
根据公式调用函数计算码长
3、费诺编码
开始
输入概率矩阵