信息论课程设计报告

信息论课程设计报告信息论课程设计报告 香农编码香农编码 1 问题描述 为了使得平均编码长度为最小 必须将概率大的信息符号编以短的码字 概率小的符 号编以长的码字 香农第一定理指出 可选择每个码字的长度满足关系式 log p si li log p si 1 按不等式选择的码长所构成的码称为香农码 其编码步骤为 1 将信源发出的 n 个消息符号按其概率的递减次序依次排列 2 按下式计算第 i 个消息的二进制代码组的码长 并取整 3 为了编成唯一可译码 首先计算第 i 个消息的累加概率 4 将累加概率Pi 为小数 变成二进制数 5 去除小数点 并根据码长li 取小数点后li 位数作为第i个消息的码字 要求 对给定的信源符号集合 按香农编码的思想对其进行编码 使经常出现的信源符号对应 较短的码字 使信源的平均码长缩短 从而实现了对信源的压缩 2 需求分析 2 1 解决的问题 对于给定的信源符号集合 能够以任意进制运用香农编码的思想对信源符号集进行编码 根据用户的要求 对给定的任意一个信源符号的集合 设计一个程序显示编码结果 2 2 程序的功能 由用户任意设置各信源符号及对应的概率 并规定编码进制数 得出编码结果显示出来 2 3 输入输出 以人机对话的方式让用户输入信源符号集中信源符号的个数及各信源符号的概率 以及 编码进制数 运用香农编码得出编码结果并输到屏幕上 3 概要设计 3 1 数据结构的设计 运用四个数组 k 用来存各信源符号的概率 a 用来按从大到小顺序存放信源符号概率 b 用来存累积概率 c 用来存各信源符号的码长 3 2 算法的设计 1 本设计最主要的一个模块 运用 code 函数将信源符号集中的各信源符号编码并将 结果存放在一个二维数组中 2 主程序的流程图如下 输入信源符号的个 数及编码进制数 输入各信源符号的概率 将信源符号的概率按从 大到小排序 并计算出 各信源符号对应的码长 结束 开始 对各信源符号进行 编码并输出 3 函数调用关系图 main code 4 函数接口规格说明 char code int n int m float b int c 根据各信源符号的概率及编码码长用 m 进制对 n 个信源符号进行编码 并将编码结果用二维数组指针返回给主调函数 4 详细设计 编码函数 code 先根据信源符号个数动态申请二维数组 d 的空间 用来存放编码结果 然后从第一个信 源符号开始编码 将累计概率转化为 m 进制 并取其小数点后码长位数作为该信源符号的 编码结果 重复该操作直到第 n 个信源符号编码完毕 被调用的函数 main code 5 测试结果 5 1 测试输入 7 2 0 20 0 18 0 19 0 17 0 10 0 01 0 15 测试目的 测试用二进制编码时 经常出现的信源符号是否对应较短码长 编码结果是 否正确 正确输出 000 011 100 001 1111110 1110 101 实际输出 与正确输出一样 当前状态 通过 以下为截屏 5 2 测试输入 7 3 0 20 0 18 0 19 0 17 0 10 0 01 0 15 测试目的 测试用其它进制编码时 经常出现的信源符号是否对应较短码长 编码结果 是否正确 并与二进制编码进行比较 正确输出 00 10 01 12 220 22220 20 实际输出 与正确输出一样 当前状态 通过 以下为截屏 6 分析与探讨 1 主要问题 调试过程中 遇到的主要问题是用二维数组存放各信源符号的编码结果时 每个信源符 号对应码长不同 需要动态申请不同大小的空间 2 算法的时间空间复杂度分析 本程序中主要函数的时间空间复杂度如下 char code 设最大码长为 k 则时间复杂度为 O n k 空间复杂度为 O n k 3 该算法可以实现根据用户要求对任意信源符号集以任意进制用香农编码进行编码 4 香农编码特点 有系统的 惟一的编码方法 编出的码为唯一可译码 但在很多情况下编码效率不是很 高 由于累加概率总是进一取整 香农编码方法不一定是最佳的 由于第一个消息符号的 累加概率总是为 0 故它对应码字总是 0 00 000 0 0 的式样 码字集合是唯一的 且为即时码 先有码长再有码字 对于一些信源 编码效率不高 冗余度稍大 因此其 实用性受到较大限制 附录 源程序清单 include include include using namespace std bool cmp float a float b return a b char code int n int m float b int c char d int i j d char malloc n sizeof char for i 0 i n i d i char malloc c i sizeof char for i 0 i n i for j 0 j 1 d i j int b i 0 b i int b i else d i j 0 return d int main int m n i j s float a b k int c k 用来存各信源符号的概率 a 用来按从大到小顺序存放信源符号概率 b 用来存累积概率 c 用来存码长 char d 存放编码结果 cout 请输入信源符号的个数及编码进制数 n m a float malloc n sizeof float b float malloc n sizeof float k float malloc n sizeof float c int malloc n sizeof int cout 请输入各信源符号的概率 endl for i 0 i k i a i k i sort a a n cmp for i 0 i n i if i 0 b i 0 else b i b i 1 a i 1 c i log 1 a i log m if c i log 1 a i log m c i 1 d code n m b c cout 各信源符号的码字为 endl for i 0 i n i for s 0 s n s if k i a s break for j 0 j c s j cout d s j cout endl return 0 惟一可译码的判别惟一可译码的判别 1 问题描述 若码的任意一串有限长的码符号序列只能被惟一的译成所对应的信源符号序列 则此 码称为惟一可译码 或单义可译码 若某码组C对应码长不满足克拉夫特不等式 则一定不是惟一可译码 但若码长满足 克拉夫特不等式 则不一定是惟一可译码 因此 不能用克拉夫特不等式来判断码 C 是否 是惟一可译码 根据惟一可译码的定义 可得惟一可译码的判断方法 将码C中所有可能的尾随后缀组成一个集合 F 当且仅当集合 F 中没有包含任一码字 便可判断此码 C 为唯一可译变长码 设C为码字集合 按以下步骤构造此码的尾随后缀集合F 1 考查C中所有的码字 若Wi是Wj的前缀 则将相应的后缀作为一个尾随后缀放入 集合F0中 2 考查C和Fi两个集合 若Wj C是Wi Fi的前缀或Wi Fi 是Wj C的前缀 则 将相应的后缀作为尾随后缀码放入集合Fi 1中 3 F Fi即为码C的尾随后缀集合 4 若F中出现了C中的元素 则算法终止 返回假 C不是唯一可译码 否则若F中 没有出现新的元素 则返回真 要求 对于任意给定的码字集合 按惟一可译码的判别方法 判断该码字集合是否为惟一可译 码 2 需求分析 2 1 解决的问题 对于用户任意输入的信源符号码字集合 能够判断出该码字集合是否为惟一可译码 2 2 程序的功能 由用户任意设置各信源符号码字集合 判断该码字集合是否为惟一可译码并显示在屏幕 上 2 3 输入输出 用户输入信源符号的个数及各信源符号的码字 输出该码字集合是否为惟一可译码 3 概要设计 3 1 模板的设计 运用类模板 vector 定义保存字符串对象的 vector 用来存各码字序列 3 2 算法的设计 1 本算法设计主要有三个模块 运用 Prefix 函数 判断一个码字是否是另一个码字的前缀 运用 Pushpost 函数 向后缀集合中插入不重复的后缀 运用 weiyi 函数判断一个码字集合是否是惟一可译码 2 主程序的流程图如下 输入信源符号个数 及各信源符号码字 判断该码字集合是否为唯 一可译码 是惟一可译码 继续 结束 输出不是惟 一可译码 输出是惟一可 译码 开始 3 函数调用关系图 main weiyi weiyi Pushpost Prefix 4 函数接口规格说明 int Prefix char a const char b 判断码字 a 是否为码字 b 的前缀 若是返回 0 不是返回 1 两码字相同返回 2 给调用函数 void Pushpost s typedef vector s int Prefix char a const char b 判断码字 a 是否为码字 b 的前缀 若是返回 0 不是返回 1 两码字相同返回 2 int n if strlen a strlen b return 1 n memcmp a b sizeof char strlen a if n 0 if n 0 return 2 return 1 void Pushpost si a size i if strcmp b a i 0 return a push back b int weiyi s char s1 s2 int i j newpost n for i 0 i m size i s1 m at i for j 0 j m size j if i j continue s2 m at j if Prefix s1 s2 0 Pushpost Postfix s2 strlen s1 if Postfix size 0 return 0 newpost Postfix size do n Postfix size for i 0 i m size i s1 m at i for j n newpost j n j s2 Postfix at j if Prefix s1 s2 2 return 1 if Prefix s1 s2 0 Pushpost Postfix s2 strlen s1 if Prefix s2 s1 0 Pushpost Postfix s1 strlen s2 newpost Postfix size n while newpost 0 Postfix clear return 0 int main s Code int Num int i Continue 1 while Continue 1 cout Num cout 请依次输入各信源符号码字 endl for i 0 i strBuffer char pTemp new char strBuffe