《信息论基础》实验指导书

0 目目 录录 实验一 英文半字节压缩编码技术 1 实验二 Huffman 编码 5 实验三 重复码编译码方法 11 1 实验一实验一 英文半字节压缩编码技术英文半字节压缩编码技术 一 实验目的 1 理解信源编码的作用和目的 掌握数据压缩的基本思想 2 掌握数据压缩中常用的比特流操作办法 3 掌握英文半字节压缩编码技术 二 实验内容 通过 C 语言编程 实现对一般英文文本文件的半字节压缩编码与译码程 序 并观察编码 译码结果以及压缩效果 三 实验原理 对于一个通信系统来说 信息传输的有效性 可靠性 安全性和认证性 是人们的主要目标 其中 信息传输的有效性指的是尽可能的使用较短的时 间和较少的设备等资源来传送尽可能多的信息 而这一目的主要是通过信源 编码这个环节来实现的 虽然有许许多多不同的信源编码方法 但总的说来 信源编码主要是通 过减少或消除信源的剩余度来提高传输效率的 而且 有时人们为了追求更 高的传输效率 在满足实际需求的情况下 还允许在编译码过程中存在一定 程度的失真 这就是所谓的有损压缩 当然 针对不同的应用要求 可以选 择不同的压缩编码办法 为了方便理解和实现 针对一般的英文文本 可以 设计一种半字节压缩编码方法来实现数据的压缩 一 有损处理 在一般英文文本中 除了大 小写英文字母外 还有多种不同的标点符 号 为了达到在不影响文章大意的前提下 尽可能的减少需编码的符号数 以提高信息传输效率的目的 可采取这样的处理方法 1 所有的英文字母不区分大 小写 如 将所有的大写英文字母变成小 写字母 2 保留标点符号 和 2 3 将 和 变为 其他符号全部变成 这样 原来的英文文本就变成了一个新的文本 该文本全部由 26 个英 文字母和 以及 这 31 种符号组成 而且 文章 的大意并没有发生大的变化 可以认为这种失真是在允许的失真范围之内的 当然 为了简化操作 上面的第一步也可省略 虽然这样会使输出文件 中既有大写字符 又有小写字符 但只需在后面的编码操作时将大 小写等 同处理 则同样达到了不区分大小写的目的 二 数据压缩 在计算机中 文本文件中的每个符号都是由 8 位的 ASCII 码所构成 共 有 256 种取值的可能 既然经过上述有损处理后文件中只存在 31 种不同的符 号 所以在压缩编码过程中只需对 31 种符号进行编码 就可以大大压缩文本 文件的数据量 考虑到各字母以及符号出现的概率 并考虑码字的可分离性 可以采取以下的编码方法来进行数据的压缩 1 对于概率最大的 15 个符号分别编以 0000 1110 的码字 符号码字符号码字符号码字符号码字 空格0000e0100l1000s1100 a0001f0101n1001t1101 c0010h0110o1010u1110 d0011i0111r1011 2 对于其余的 16 个符号分别编以 1111 0000 1111 1111 的码字 符号码字符号码字符号码字符号码字 1111 0000b1111 0100m1111 1000w1111 1100 1111 0001g1111 0101p1111 1001x1111 1101 1111 0010j1111 0110q1111 1010y1111 1110 1111 0011k1111 0111v1111 1011z1111 1111 这样 一些最经常出现的符号从原来的 8bit 变为 4bit 达到了数据压缩 的目的 3 从表中可以看出 后 16 个符号的码字中前 4 比特均为 1111 因此可 先向编码文件输出前 4 比特 然后再输出后 4 比特 这样的好处是 不论是 前 15 种符号还是后 16 种符号 都可执行同一种输出操作 输出 4 比特 只 是对于后 16 种符号是连续执行两次而已 三 译码 译码过程是编码的逆过程 解码后得到由这 31 种符号所组成的文本文件 由于后 16 个符号的码字中前 4 比特均为 1111 因此可设计译码过程 为 每次读取 4bit 若不为 1111 则根据此次读取的 4bit 译为相应的前 15 个符号之一 若为 1111 则再次读取 4bit 并根据后 4bit 译为相应的 后 16 个符号之一 这样 不论是前 15 种符号还是后 16 种符号的译码 都可 执行同一种读取操作 读取 4 比特 只是对于后 16 种符号是连续执行两次 而已 四 半字节操作 在计算机中 所有对数据的操作 不论是数据的存储还是对文件的读写 都是以字节 8bit 为基本单位的 而我们的编码与解码都是以半个字节 4bti 为单位的 因此需要运用位操作来进行数据的控制 1 编码过程中 执行的操作是每次输出 4 比特 由于每次向输出文件的 写入是以字节 8bit 为单位的 因此可定义一个缓存变量来存储每次输出 的 4 比特数据 只有当缓存中的有效数据凑足 8bit 1 字节 时才执行一次 向输出文件的写入操作 这里需要注意的是 如果待编码文件中所有符号的码长之和不是 8 的整 数倍时 就会出现缓存中剩余 4 比特有效数据不能输出 因为不能凑够满字 节 的情况 这时可以在后面补 4 比特 0000 即为空格 使其能够输出 到输出文件中 2 译码过程中 执行的操作是每次读取 4bit 由于每次向输入文件的读 取是以字节 8bit 为单位的 故需将每次读取的 8bit 1 字节 存入缓存 然后使用位操作依次读取其前后各 4 比特 四 实验步骤 1 编写有损处理程序 在不影响文章大意的基础上对英文文本文件进行 4 有损处理 减少需编码的符号数 产生待编码文件 2 编写半字节编码程序 对待编码文件进行半字节压缩编码 并计算压 缩比 观察压缩效果 3 编写半字节解码程序 对压缩后的文件进行解码 并与压缩前的文件 进行比较 五 实验环境 1 计算机 2 Visual C 编程环境 六 实验报告要求 1 格式与内容应符合实验报告标准 2 对程序设计的思路以及具体设计步骤应详细说明 并附上相应的程序 流程图 3 对程序设计中发生的问题以及解决的办法要加以叙述与总结 4 附上所设计的程序清单 并对关键部分进行说明 5 实验二实验二 Huffman 编码编码 一 实验目的 1 熟练掌握 Huffman 编码过程 2 掌握 C 语言递归程序的设计和调试技术 3 掌握 C 语言中的动态分配内存技术 二 试验内容 根据输入的信源符号数及相应的概率分布 使用 C 语言编写 Huffman 编 码程序 从而输出每个信源符号所对应的码字 三 实验原理 在众多的无失真信道编码技术中 Huffman 编码是一种有效的获得最佳 码的编码技术 它能够充分利用短码 大幅度降低码字的平均码长 从而获 得较高的编码效率 在保证码字的可分离性的同时 有效的提高了通信系统 的有效性 也正是由于 Huffman 编码技术的优越性 目前在有关信源编码的 许多领域中 Huffman 编码作为一项基本技术 得到了极为广泛的应用 一 Huffman 编码方法 由于目前数字通信中一般都使用二进制符号 因此二进制的 Huffman 编 码技术最为普遍 其编码步骤如下 1 将信源符号按概率从大到小进行排列 2 给两个概率最小的信源符号各分配一个码元 0 和 1 然后将这 两个信源符号合并成一个新符号 并用这两个最小的概率之和作为新符号的 概率 结果得到一个只有 n 1 个信源符号的新信源 假设原来所需编码的 符号数为 n 称为信源的第一次缩减信源 S1 3 将缩减信源 S1的符号仍按概率从大到小的顺序进行排列 重复步骤 2 得到只含 n 2 个符号的缩减信源 S2 4 重复上述步骤 直至缩减信源只剩两个符号为止 此时所剩两个符号 的概率之和必为 1 将这两个符号各分配一个码元 0 和 1 后 从最后 6 一级缩减信源开始 依编码路径向前返回 就得到各信源符号所对应的 Huffman 码字 二 方差最小的 Huffman 码字 缩减信源时 若合并后的新符号概率与其他符号的概率相等 从编码方 法上来讲 这几个符号的次序可任意排列 编出的码字都是正确的 但不同 的编法得到的码字不同 码字长度也不尽相同 从而码长的方差也会不同 若码长的方差较小 则意味着码长变化较小 各个码长都比较接近于平均码 长 这样对于信息传输的实现 特别是对传输有实时性要求的时候 会带来 很大的便利 因此也就更好一些 为了得到方差最小的 Huffman 码字 在对缩减信源按概率从大到小重新 排列时 应使合并后的新符号尽可能地排在靠前的位置 这样可使合并后的 新符号重复编码次数减少 使短码得到充分利用 降低码长的方差 三 递归算法实现 Huffman 编码 由于在 Huffman 编码过程中 每次都是对减少一个符号数的缩减信源进 行同样的操作 排序与合并 且最终的码字是按照编码路径逆序返回而得 到 因此可利用递归的思想实现 Huffman 的编码程序 假设对 n 个符号 概率为 pi的信源进行 Huffman 编码 则递归实现算法 的主要思想可简单描述为 procedure Huffman n pi if n 2 then 对两个符号各分配一个码元 0 和 1 else 降序排序 合并符号 并得到新的概率分布 pi Huffman n 1 pi 对被合并的两个符号各分配一个码元 0 和 1 end procedure 四 动态分配内存 由于本程序设计要求根据所输入的信源符号数与概率分布进行 Huffman 编码 在输入之前并不确定所要编码的信源符号数 而且编得的码字长度也 7 不能确定 因此对各符号以及相应码字的存储使用固定长度的数组显然不太 合适 而在 C 语言中使用动态分配内存技术则可以根据需要灵活分配存储空 间 从而有效的解决这个问题 C 语言中常用的动态内存管理函数有以下四 个 1 函数 malloc 这是给指针动态分配内存的通用函数 它的原型是 void malloc size t nbytes 其中 nbytes 是我们想要给指针分配的内存字节数 这个函数返回一个 void 类型的指针 因此我们需要用类型转换 type cast 来把它转换成目标指针 所需要的数据类型 例如 char ronny ronny char malloc 10 这个例子将一个指向 10 个字节可用空间的指针赋给 ronny 当我们想给一组除 char 以外的类型 不是 1 字节长度的 的数值分配内 存的时候 我们需要用元素数乘以每个元素的长度来确定所需内存的大小 int bobby bobby int malloc 5 sizeof int 这一小段代码将一个指向可存储 5 个 int 型整数的内存块的指针赋给 bobby 它的实际长度可能是 2 4 或更多字节数 取决于程序是在什么操作 系统下被编译的 2 函数 calloc calloc 与 malloc 在操作上非常相似 他们主要的区别是在原型上 void calloc size t nelements size t size 可见它接收 2 个参数而不是 1 个 这两个参数相乘被用来计算所需内存 块的总长度 通常第一个参数 nelements 是元素的个数 第二个参数 size 被用来表示每个元素的长度 例如 我们可以像下面这样用 calloc 定义 bobby int bobby bobby int calloc 5 sizeof int malloc 和 calloc 的另一点不同在于 calloc 会将所有的元素初始化为 0 8 而 malloc 只管分配内存 并不能对所得的内存进行初始化 所以得到的一片 新内存中 其值将是随机的 3 函数 realloc 它被用来改变已经被分配给一个指针的内存的长度 其原型为 void realloc void pointer size t size 参数 pointer 用来传递一个已经被分配内存的指针或一个空指针 而参 数 size 用来指明新的内存长度 这个函数给指针分配 size 字节的内存 这个函数可能需要改变内存块的地址以便能够分配足够的内存来满足新 的长度要求 在这种情况下 指针当前所指的内存中的数据内容将会被拷贝 到新的地址中 以保证现存数据不会丢失 然后返回新的指针地址 如果新 的内存尺寸不能够被满足 函数将会返回一个空指针 但原来参数中的指针 pointer 及其内容保持不变 4 函数 free 这个函数用来释放被前面 malloc calloc 或 realloc 所分配的内存块 void free void pointer 注意 注意 如果忘记释放动态分配地内存 程序就会在结束时出现内存泄漏 的问题 五 程序设计问题 1 数据存储 根据实验要求 我们要根据输入的信源符号数及相应的概率分布输出每 个信源符号所对应的码字 因此需要定义一个记录信源符号序号的数组 一 个记录相应符号概率的数组 一个记录各符号码字的二维数组 且各数组的 长度应根据输入的信源符号数决定 2 排序 从 Huffman 算法流程来看 第一次排序和对缩减信源的排序略有不同 对缩减信源的排序是在基本有序的情况下进行排序的 也就是说 除了合并 符号以外 其他的符号已经是降序排列的 因此只需将合并的符号插入到相 应的位置即可 而且为了得到方差最小的 Huffman 码字 应使合并后的新符 号尽可能地排在靠前的位置 对于第一次排序则没有这样的条件与要求 也 正是为此 我们可以在上述的递归算法中将这两种排序分开 9 主程序 第一次排序 procedure Huffman n pi if n 2 then 对两个符号各分配一个码元 0 和 1 else 合并符号 并得到新的概率分布 pi 缩减信源的排序 Huffman n 1 pi 对被合并的两个符号各分配一个码元 0 和 1 end procedure 由于对信源符号的描述有三个数组 序号 概率以及码字 因此排序中 的每次改变都需对这三个数组同时进行相应的变动 3 递归编码 在递归算法中 每次递归都需要对参与合并的两个符号分配码元 由于 对信源符号的描述由数组完成 因此在逐级返回时只是返回指向数组的指针 而其中元素的值不能返回 为了在每次返回上一级递归时找到这两个符号 则需要在每次递归时记录下这两个符号的序号 以便返回时能正确的对这两 个符号分配码元 四 实验步骤 1 使用 C 语言编写 Huffman 编码程序 2 输入几种信源的符号数及其概率 将程序输出的码字与手动计算的码 字进行比较 验证程序的正确性 五 实验环境 1 计算机 2 Visual C 编程环境 六 实验报告要求 10 1 格式与内容应符合实验报告标准 2 对程序设计的思路以及具体设计步骤应详细说明 并附上相应的程序 流程图 3 对程序设计中发生的问题以及解决的办法要加以叙述与总结 4 附上所设计的程序清单 并对关键部分进行说明 11 实验三实验三 重复码编译码方法重复码编译码方法 一 实验目的 1 理解信道编码的作用和目的 2 巩固 实验一 中的比特流操作办法 3 掌握重复码的编解码技术 二 实验内容 通过 C 语言编程 实现对数据文件的 3 1 二元重复码编码与译码程 序 并对编码 译码结果进行观察与比较 三 实验原理 一般的通信信道中总是不可避免的存在噪声或者干扰 因此在信息传输 的过程中也就必然会造成信息的损失 或者说 信源符号在有噪信道中的传 输过程中会产生失真 为了降低这种信息损失 就需要我们在信源符号输入 到信道之前 对其进行有效的信道编码 信道编码是通信系统中的一个重要环节 目的就是为了降低传输过程中 错误发生的概率 从而提高通信系统的可靠性 信道编码的基本思想是附加 冗余信息 增加信源的剩余度 这样在接收端就可以利用相关性进行检错或 者纠错 根据有噪信道编码定理 附加冗余位可以降低信息传输率 使错误 概率减小 当信息传输率小于信道容量时 理论上就可以使译码错误概率任 意小 从而几乎无失真的进行信息传送 当然 同样是增加信源剩余度 不 同的编码方法 其检 纠错能力也不同 目前 人们对信道编码的研究有很 多 大概可分为线性分组码 循环码 卷积码等等 一 重复码 重复编码是一种简单的信道编码方法 其实质就是将每个要发送的符号 重复发送 或者说是将原来的每一个信源符号编成多个相同的码元符号 其 值与原来的符号取值相同 比如 3 1 二元重复码 其编码方法就是将原来 二进制序列中的每一个 0 编成 000 将每一个 1 编成 111 因此 12 我们可以设计以下简单的编码流程 1 读取待编码文件的一个比特 2 重复 3 次向输出文件中写入一个相同的比特 3 重复执行上面两步 直到待编码文件的所有数据全部编码完毕 所谓的译码规则就是指接收符号与发送符号之间的映射关系 不同的译 码规则会造成不同的平均错误概率 所以人们一般都根据最小错误概率准则 来确定译码规则 对于二元对称信道来说 一般总认为出错概率是小于等于 0 5 的 所以对于二元重复码 最小错误概率准则与择多译码规则是一致的 也就是说 译码时根据码字中 0 1 的数目选择数目多的进行译码 比如 3 1 二元重复码的译码 可以将接收到的 000 001 010 和 100 译为 0 将接收到的 011 101 110 和 111 译为 1 这样 每个码字对于传输