1、信息论课程设计 第 1 页 信息论课程设计 课题名称课题名称：四元费诺编码 自适应算术编码 专业班级：专业班级： 任课教师任课教师: : 姓姓 名：名： 学学 号：号： 完成时间：完成时间：2012-12 信息论课程设计 第 2 页 四元费诺编码四元费诺编码 1.1.问题描述问题描述 费诺编码方法属于概率匹配编码。这种编码方法不是最佳的编码方法，但有 时也可得到最佳码的性能。设计一个程序对输入的一个字符串实现费诺编码。 2.2.基本要求基本要求 书本上大多讲解的二元的费诺编码，但是多元的费诺编码也能实现。请设计 程序用以对输入字符串实现 4 元费诺编码， 并且设计译码函数使满足根据编码的 结果
2、，输入任意的 4 进制数字串能够正确唯一的译码，最后计算编码效率。 3.3.二元费诺编码基本原理二元费诺编码基本原理 首先,将信源符号以概率递减的次序排列进来，将排列好的信源符号划分为 两大组，使第组的概率和近于相同,并各赋于一个二元码符号”0”和”1”.然后，将 每一大组的信源符号再分成两组，使同一组的两个小组的概率和近于相同，并又 分别赋予一个二元码符号。 依次下去， 直至每一个小组只剩下一个信源符号为止。 这样，信源符号所对应的码符号序列则为编得的码字。译码原理，按照编码的二 叉树从树根开始，按译码序列进行逐个的向其叶子结点走，直到找到相应的信源 符号为止。之后再把指示标记回调到树根，按
3、照同样的方式进行下一序列的译码 到序列结束。如果整个译码序列能够完整的译出则返回成功，否则则返回译码失 败。 编码方法：编码方法： 1.将信源消息符号按其出现的概率大小依次排列。 2.将依次排列的信源符号按概率值分为两大组， 使两个组的概率之和近似相 同，并对各组赋予一个二进制码元“0”和“1”。 3.将每一大组的信源符号再分为两组， 使划分后的两个组的概率之和近似相 同，并对各组赋予一个二进制符号“0”和“1”。 4.如此重复，直至每个组只剩下一个信源符号为止。 5.信源符号所对应的码字即为费诺码。 4.4.费诺编码特点费诺编码特点 信息论课程设计 第 3 页 费诺编码，它编码后的费诺码要比
4、香农码的平均码长小，消息传输速率达， 编码效率高，但它属于概率匹配编码它不是最佳的编码方法。 5.5.二元费诺编码思想二元费诺编码思想 费诺编码最困难的是根据信源概率对信源进行分组，本次借鉴了信息编码 与加密实践 （夏娜 蒋建国 丁志忠 编著）中的二元费诺编码的思想，设定一个 中间判断值old为每次分组总概率的一半大小， sum为每次相加的概率 和，每次相加后与该段的中间值差得绝对值与old比较，小于其值则分为一 组， 大于其值则为另一组。 递归调用这段程序， 直到每个分组只含一个信源结束。 6.6.四元费诺编码流程图四元费诺编码流程图 开始 输入字符窜 统计各个字符出现的频 率 按字符出现的概率大小 对符号进行排列 调用编码对函数进行编 码 输出编码结果 字符都已 编码完？ N Y 信息论课程设计 第 4 页 7.7.四元费诺编码思想与函数模块划分四元费诺编码思想与函数模块划分 四元费诺编码主要在二元费诺编码的基础上修改编码函数， 即二元费诺编码 每次递归分两组，四元费诺编码每次就要分为四组。具体修改方法如下： 参数
