信息论与编码

信息论与编码信息论与编码 实验报告实验报告 学生姓名 李俊 班号 116111 25 班 号 20111003660 指导教师 黄鹰 中国地质大学 武汉 信息工程学院中国地质大学 武汉 信息工程学院 2013 年年 7 月月 实验1 Huffman 编码 Huffman 编码原理 将信源符号按概率从大到小的顺序排列 令 p x1 p x2 p xn 给两个概率最小的信源符号p xn 1 和p xn 各分配一个码位 0 和 1 将这两个信源符号 合并成一个新符号 并用这两个最小的概率之和作为新符号的概率 结果得到一个只包含 n 1 个信源符号的新信源 称为信源的第一次缩减信源 用S1表示 将缩减信源S1的符号仍按概率从大到小顺序排列 重复步骤2 得到只含 n 2 个符号的 缩减信源S2 重复上述步骤 直至缩减信源只剩两个符号为止 此时所剩两个符号的概率之和必为1 然后从最后一级缩减信源开始 依编码路径向前返回 就得到各 信源符号所对应的码字 Huffman 树的编码步骤 步骤1 将各个符号及其出现频率分别作为不同的小二叉树 目前每棵树只有根节点 步骤2 在步骤1中得到的树林里找出频率值最小的两棵树 将他们分别作为左 右子树连 成一棵大一些的二叉树 该二叉树的频率值设为两棵子树频率值 之和 步骤3 对上面得到的树林重复步骤2的做法 直到所有符号都连入树中为止 数据结构定义 typedef struct unsigned long weight int parent lchild rchild HTNode HuffmanTree typedef char HuffmanCode 指向存放数组指针的数组即二维数组 包含的函数 1 void Select HuffmanTree float p q p q 1 0 for i 1 i n i if HT i parent 0 s2 i else p HT i weight s1 i if s2 s1 指针s1存放权值较小的节点 i s1 s1 s2 s2 i void CreateHuffmanTree HuffmanTree int s1 s2 HuffmanTree t if n 1 return m 2 n 1 HT HuffmanTree malloc m 1 sizeof HTNode for t HT i 1 iweight w t parent 0 t lchild 0 t rchild 0 for iweight 0 t parent 0 t lchild 0 t rchild 0 for i n 1 i m i Select HT i 1 HT s1 parent i HT s2 parent i HT i lchild s1 HT i rchild s2 HT i weight HT s1 weight HT s2 weight void HuffmanCoding HuffmanTree HT HuffmanCode char cd HC HuffmanCode malloc n 1 sizeof char cd char malloc n sizeof char cd n 1 0 编码结束符 for i 1 i n i start n 1 编码结束位置 for p i q HT i parent q 0 p q q HT q parent 从叶节点到根节点 逆向求编码 if HT q lchild p start cd start 0 左孩子编码为 0 else start cd start 1 左孩子编码为 1 HC i char malloc n start sizeof char strcpy HC i 将编码从cd复制到HC中 free cd void OutputHuffCode HuffmanCode HC char ch float w int n printf huffman编 码 为a o n for int i 1 i n i printf c t f t ch i 1 w i 1 puts HC i printf n 结果显示 学习心得 本次实验 熟悉了课堂上的信源编码的一种 即 huffman 编码 加深了对知识的理解 通过编程简单实现了编码 但是我的程序存在一些缺陷 即在我的程序中需要手工输入信 源符号的概率 我觉得可以输入一串字符串 统计每个字符出现的概率 这样更加方便 另外从HT 1 n 中选出权值最小的两个节点可以通过最小堆来实现 效率更高一些 附录 文件 huffman h ifndef HUFFMANCODE H define HUFFMANCODE H include include include typedef struct float weight int parent lchild rchild HTNode HuffmanTree typedef char HuffmanCode void Select HuffmanTree float p q p q 1 0 for i 1 i n i if HT i parent 0 s2 i else p HT i weight s1 i if s2 s1 i s1 s1 s2 s2 i void CreateHuffmanTree HuffmanTree int s1 s2 HuffmanTree t if n 1 return m 2 n 1 HT HuffmanTree malloc m 1 sizeof HTNode for t HT i 1 iweight w t parent 0 t lchild 0 t rchild 0 for iweight 0 t parent 0 t lchild 0 t rchild 0 for i n 1 i m i Select HT i 1 HT s1 parent i HT s2 parent i HT i lchild s1 HT i rchild s2 HT i weight HT s1 weight HT s2 weight void HuffmanCoding HuffmanTree HT HuffmanCode char cd HC HuffmanCode malloc n 1 sizeof char cd char malloc n sizeof char cd n 1 0 for i 1 i n i start n 1 for p i q HT i parent q 0 p q q HT q parent if HT q lchild p start cd start 0 else start cd start 1 HC i char malloc n start sizeof char strcpy HC i free cd void OutputHuffCode HuffmanCode HC char ch float w int n printf huffman编 码 为a o n for int i 1 i n i printf c t f t ch i 1 w i 1 puts HC i printf n endif main 函数 int tmain int argc TCHAR argv HuffmanTree HT HuffmanCode HC int n i float sum 0 char ch float w cout n w float malloc n sizeof float ch char malloc n sizeof char cout 请 输 入 字 符 和 每 个 字 符 发 生 的 概 率 o endl for i 0 i ch i w i sum w i cout 剩 余 概 率 为a 1 0 sum endl for i 0 i n i CreateHuffmanTree HT w n HuffmanCoding HT HC n OutputHuffCode HC ch w n free w free ch return 0 实验 2 CRC 校验码编码实验 本实验中 是对 7 4 循环码的编码 实验原理 CRC 校验的基本思想是利用线性编码理论 在发送端根据要传送的 k 位二进制码序 列 以一定的规则产生一个校验用的监督码 CRC 码 r 位 并附在信息后边 构成一个 新的二进制码序列数共 k r 位 最后发送出去 在接收端 则根据信息码和 CRC 码之 间所遵循的规则进行检验 以确定传送中是否出错 数据结构 定义生成多项式为g x x 3 x 2 1 因此采用数组 int a 4 1 1 0 1 来表示该多项 式 主要函数 void code int a1 int b1 int c 7 int i j for i 0 i 7 i 把所有的信息位左移三位 if i 4 c i b1 i else c i 0 for i 0 i 4 i for j 0 j 4 j c i j c i j a1 j for i 0 i 7 i if i 4 c i b1 i cout c i 实验结果 实习体会 通过这个实验 我熟悉了按位计算 CRC 码 但是我的算法不具有普遍性和通用性 针 对是特点情况 另外我在网上还看到了其他几种方式来计算 CRC 码 如按字节计算 CRC 码 按半字节计算 CRC 码 但是按字节计算 CRC 码需要很大的空间 按位计算 CRC 码需 要较长的时间 而按半字节计算 CRC 码就均衡了上面的两种方式 代码附录 include using namespace std void code int a1 int b1 int c 7 int i j for i 0 i 7 i 把所有的信息位左移三位 if i 4 c i b1 i else c i 0 for i 0 i 4 i for j 0 j 4 j c i j c i