基于Python（PyQt5 ）实现的信息论与编码课程设计【100011581】

# 信息论与编码课程设计 # 一、设计要求 ## 1.1 必做题 对任意输入的字符串序列分别进行二元霍夫曼编码、fano编码、游程编码和算术编码，给出编码结果、编码效率；并实现相应的译码操作。 ## 1.2 提升题 对一幅BMP格式的灰度图像先进行二元霍夫曼编码和游程编码，并根据霍夫曼编码结果将游程编码变换成二进制序列。（象素用霍夫曼编码，游程用等长码）。 并设计相应的译码。 # 二、开发环境与工具 - 编辑工具：Visual Studio Code 编译工具：python 3.9.7 - 界面工具：PyQt5 designer - 用到的库：math; Pillow 8.4.0; PyQt5 5.15.4; # 三、设计原理 ## 3.1 Huffman编码原理： 哈夫曼编码的基本思想是以字符的使用频率作为权值构建一颗哈夫曼树,然后利用哈夫曼树对字符进行编码。构造的一棵哈夫曼树,是将要编码的字符作为叶子节点,将该字符在文件中的使用频率作为叶子节点的权值,以自底向上的方式,通过 n-1 次合并运算后构造出的树。其核心思想是让权值大的叶子离根最近。以二元霍夫曼编码为例题，下图为求解过程。  图 1 二元霍夫曼编码示例图说明：1、每次对缩减信源两个概率最小的符号分配“0”"和“1”是任意的，所以可得到不同的码字。2、缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。平均码长计算公式为： 𝐿̅ = ∑ 𝑝(𝑎𝑖 ) ∗ 𝑙𝑖 1）编码效率计算公式为 𝜂 = 𝐻(𝑆) /𝐿 2） 式中，𝑝(𝑎𝑖)为对应字符出现的概率， 为相应字符的码长，H(S)为信源的熵， 为编码效率。 ## 3.2 Fano编码原理 费诺编码属于统计匹配编码，但它一般不是最佳的编码方法。编码步骤为： 将信源消息(符号)按其出现的概率由大到小依次排列；(2)将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组分别赋予一个二进制码元“0”和“1”；(3)将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又分别赋予一个二进制符号“0”和“1”； (4)如此重复，直至每个组只剩下一个信源符号为止；(5)信源符号所对应的码字即为费诺码。费诺码考虑了信源的统计特性，使经常出现的信源符号能对应码长短的编码字。显然，费诺码仍然是一种相当好的编码方法。但是，这种编码方法不一定能使短码得到充分利用。尤其当信源符号较多，并有一些符号概率分布很接近时，分两大组的组合方法就很多。可能某种分配结果，会出现后面小组的“概率和”相差较远，因而使平均码长增加，所以费诺码不一定是最佳码。  图 2 二元Fano编码示例图 平均码长计算公式为： 𝐿̅ = ∑ 𝑝(𝑎𝑖 ) ∗ 𝑙（3）编码效率计算公式为 𝜂 = 𝐻(𝑆) /𝐿4） 式中，() 为对应字符出现的概率， 为相应字符的码长，H(S)为信源的熵， 为编码效率。 ## 3.3 游程编码原理 游程编码是相对简单的编码技术，主要思路是将一个相同值的连续串用一个代表值和串长来代替。例如，有一个字符串“aaabccddddd”，经过游程编码后可以用“3a1b2c5d”来表示。对图像编码来说，可以定义沿特定方向上具有相同灰度值的相邻像素为一轮，其延续长度称为延续的行程，简称为行程或游程。例如，若沿水平方向有一串 M 个像素具有相同的灰度 N，则行程编码后，只传递 2 个值 ,M) 就可以代替M个像素的M个灰度值N. ## 3.4 算数编码原理 计算信源符号序列的累积分布函数，使每组符号序列对应于累积分布函数上不同的区间，再在区间内取一点，将其二进制小数点后 l 位作为符号序列的码字。计算信源符号序列的累积分布函数，使每组符号序列对应于累积分布函数上 不同的区间，再在区间内取一点，将其二进制小数点后l位作为符号序列的码字. 假设有一段数据需要编码，统计里面所有的字符和出现的次数。将区间 [0,1) 连续划分成多个子区间，每个子区间代表一个上述字符， 区间的大小正比于这个字符在文中出现的概率 p。概率越大，则区间越大。所有的子区间加起来正好是 [0,1)。编码从一个初始区间 [0,1) 开始，设置:，不断读入原始数据的字符，找到这个字符所在的区间，比如 [ L, H )，更新。 设原字符串长度为lenstr,编码后的长度为lenstr2,累计概率为P 𝑃 = ∏ 𝑝i （5） 𝑙𝑒𝑛𝑠𝑡𝑟2 = ⌈log2 * 1/ 𝑃 ⌉ （6） 平均码长计算公式为： 𝐿̅ = 𝑙𝑒𝑛𝑠𝑡𝑟 /𝑙𝑒𝑛𝑠𝑡𝑟2 （7） 2 编码效率计算公式为 𝜂 = 𝐻(𝑆) /𝐿 (8）  ## 3.5 灰度图像 Huffman+游程编码原理 像素值用Huffman编码，连续出现的次数用游程编码，以下图为例：  初步思想为统计像素值和出现个数：（5，3）（3，1）（6，4）（6，2）（4，2） ，3）（3，1）。进一步，将像素值用哈夫曼编码，长度用等长游程编码。 # 四、系统功能描述及软件模块划分 由下图可见，有五个按钮，分别实现五个题目对应的功能，分别调用五个 python 文件来进行对应的编码。在文本框中输入被编码的字符串，点击不同的按钮，即可得到字符及其对应的编码，编码结果，译码结果和编码效率。Huffman 编码为Huffman.py，Fano编码为fano.py, 游程编码为run_length2.py, 算数编码为signal.py, 灰度图像编码为bmp_huffman.py，主界面源文件为main.ui 和UI_main.py, 主函数为main.py 负责将编码程序和界面程序统一管理。下图为软件主窗口图：  图 4 软件主窗口图以下为各个子文件的模块划分： ## 4.1 Huffman.py 模块的划分 | 函数名称 |函数输入 |函数输出 | |----|----|----| | Class node |Huffman 结点参数 |一个结点 | | get_text_count() |被编码的字符串 |字符和相应概率 | | create_nodes() |字符串的字符 |结点列表 | | create_huffman_tree() |结点列表 |Huffman 树和根结点 | | huffman_encoding() |字符频率和 Huffman 树 |每个结点被编成的字符串和平均码长 | | encode_str() |文本和结点列表 |被编码的字符串 | | decode_str() |被编码的字符串和结点列表 |解码后的字符串 | | get_H() |字符和相应的概率 |信源的熵 | 表 1 Huffman.py 模块的划分 ## 4.2 fano.py 模块的划分 | 函数名称 |函数输入 |函数输出 | |----|----|----| | Class node |fano 结点参数 |一个结点 | | get_text_count() |被编码的字符串 |字符和相应概率 | | create_nodes() |字符串的字符 |结点列表 | | fano_encode() |结点列表和字符相应概率 |每个结点被编成的字符串 | | encode_str() |文本和结点�