简介这份实验报告聚焦中南大学信息论与编码课程中的编码部分围绕香农码、费诺码与哈夫曼编码的原理和实现展开适合正在学习信息论与编码、需要完成课程实验或复习编码知识的本科生。报告完整记录了从概率序列处理到码字生成、编码效率计算的全过程包含 Matlab 与 C/C 两种实现思路的源代码、运行截图和结果分析覆盖概率排序、累加概率、节点合并、最优二叉树构建等关键步骤并针对 0.4、0.2、0.1、0.1、0.15、0.05 这组测试概率给出了三种编码的实例与效率对比。资源为单个 docx 文档压缩包大小约 792KB内容结构清晰可直接打开查阅也可作为实验报告写作和编码实现的参考。目前已有 103 人学习适合需要系统掌握香农码、费诺码与哈夫曼编码实现细节并进一步理解数据压缩与解压缩原理的读者。1. 这份信息论编码实验报告三个经典编码的完整实现与踩坑清单很多人在学信息论与编码时卡点不在理解香农熵公式而在把香农码、费诺码、Huffman 编码从纸面推导落到可运行的代码上——尤其是 MATLAB 里矩阵操作和 C/C 里字符指针的细节。某高校的这份《信息论与编码编码部分实验报告》刚好把三件事做完了用 MATLAB 7.0 实现三种编码并对比效率用 C/C 单独实现香农码、费诺码和 Huffman 码最后把 Huffman 编码用于文本文件的压缩与解压缩。它以一组 0.4、0.2、0.1、0.1、0.15、0.05 的概率分布作为测试案例完整覆盖了从排序、累加概率、二叉树构建到编码效率计算的每个环节。适合正在做课程设计、实验报告或准备面试手撕 Huffman 代码的人直接拿去做蓝本。2. 三种编码的本质区别为什么 Huffman 是最优而香农码不是2.1 香农码的数学骨架从累加概率到码长取整香农编码的核心步骤只有四步但每一步背后都对应一个信息论的硬约束。首先是按概率降序排列信源符号这是所有变长编码的前提——概率大的符号必须排在前面参与编码。然后是计算累加概率第 i 个符号的累加概率是前 i-1 个符号的概率之和。第三步是计算码长公式是 Ni ceil(-log2(Pi))向上取整保证码长的整数性。最后一步是把累加概率 Pi 转换成二进制小数取前 Ni 位作为码字。这份报告里的 MATLAB 实现zong.m就是用矩阵操作完成的A 存概率B 存累加概率INT 存二进制转换后的每一位ST 用 strcat 拼接字符串得到最终码字。测试数据 0.4、0.2、0.1、0.1、0.15、0.05排序后第一个符号概率 0.4码长是 ceil(-log2(0.4)) 2 位累加概率是 0二进制是 0.0000取前两位就是 00。第二个符号概率 0.2码长 3 位累加概率 0.4二进制 0.0110取 3 位得 011。这里有个值得注意的细节香农码的码长是独立计算的它只保证单个符号的码长不小于信息量下界但不保证整体编码的紧凑性。所以香农码通常不是最优码它的平均码长可能比熵多出接近 1 比特。报告中会算 t1 H / n_1这个值就是编码效率通常在 0.8 到 0.9 之间波动取决于概率分布是否接近 2 的负整数次幂。2.2 费诺码的分组逻辑近似等分概率区间费诺码的思路和香农码完全不同它不做累加概率而是反复把概率序列分成两组让两组的总概率尽可能接近然后在左边一组码字末尾加 0右边一组加 1递归进行直到每组只剩一个符号。报告里有一个很关键的细节它不直接比较累积概率的差值而是通过一个循环找 split 点逐步逼近概率和的一半。这个近似等分是费诺码的核心也是它和 Huffman 的本质差异。具体到代码实现报告用 B 矩阵的每一列存一组编码结果j 从 2 开始递增每次分组后把当前组内符号的 B(i,j) 设为 0 或 1用 FN 字符串数组存完整码字。分组的停止条件是某组只剩一个符号此时不再细分。这个判断逻辑在 MATLAB 里用的是 q 计数器统计剩余未编码符号数量遇到 y1 即该组概率和已超过一半就切换方向。费诺码的效率通常介于香农码和 Huffman 码之间因为它的分组依据是接近等分而不是最小概率合并理论上不保证全局最优。但对这组测试数据费诺码有时能碰巧达到和 Huffman 一样的平均码长因为 0.4 和 0.2 刚好能分成一组剩下的 0.15、0.1、0.1、0.05 再递归分路径比较规整。2.3 Huffman 的全局最优性从概率树到码字回溯Huffman 编码的核心不是排序后独立定码长而是反复选出当前概率最小的两个节点合并直到所有节点合并到一棵树上。这份报告里的 MATLAB 实现zong.m 的第三段有一个很巧妙的索引矩阵设计Index 用于记录每次合并后新节点在概率序列中的位置Q 存当前概率序列。每轮操作把最小的两个概率相加插入序列末尾同时用 1 标记这是一个合并节点。回溯编码时从树的最后一行树根出发左孩子补 0、右孩子补 1通过 Index 反查每个原始符号所在位置。C/C 实现则更直观报告里用结构体数组存 Huffman 树的节点每轮排序后取前两个节点生成一个新节点挂到数组尾部。编码表生成后再用一个循环从叶子节点回溯到根节点逆序输出 0/1 序列。文件压缩部分把码表写入压缩文件头解压时重新构建 Huffman 树按 bit 逐位遍历。这里要强调一个常见误区Huffman 编码的前缀性即没有一个码字是另一个码字的前缀是自动满足的因为所有符号都在叶子节点上。这也是 Huffman 能无损压缩的根本原因。报告里的压缩测试用 infosource.txt 做输入里面是那组概率数据压缩后能正确还原验证了解码表的完整性和码字的前缀性。3. 用 MATLAB 实现三码对比矩阵操作、累加概率与超长 while 循环3.1 数据装载gailv.txt 的坑与 load 函数的限制报告里规定测试概率存在 gailv.txt 中用 load 读入。load 函数要求文件里是纯数字矩阵不能有逗号分隔符但报告题目里提到可能是全角或半角这是个隐患。如果 txt 文件里存的是 0.40.20.1 这种带逗号的格式load 会报错或只读入第一列。正确做法是概率之间用空格或换行分隔或者手动输入 [0.4 0.2 0.1 0.1 0.15 0.05]。读入后第一步必须做校验概率和为 1且每个概率非负。报告中虽然没有显式写校验代码但这是任何编码程序的起点。我一般会在读入后加一行判断sum(A) ~ 1 直接报错退出。因为后续的累加概率、编码效率计算都依赖概率分布的合法性输入错误会导致后面全部白算。3.2 香农码核心代码排序、累加概率与二进制小数转换下面这段是报告中香农码实现的高度提炼版本按可复现标准整理过function [ST, avg_len, eff] shannon_encode(A) % A 是原始概率向量按降序排列后参与编码 A sort(A(:), 2, descend); % 降序保证概率大的符号先编码 n length(A); n_1 0; % 平均码长累加器 ST strings(1, n); % 存最终码字 % 计算累加概率 B 和每个符号的码长 N for i 1:n if i 1 B(i) 0; % 第一个符号累加概率为 0 else B(i) A(i-1) B(i-1); % 累加前 i-1 个概率 end N(i) ceil(-log2(A(i))); % 码长向上取整 n_1 n_1 A(i) * N(i); % 累加平均码长 end % 把累加概率转成二进制小数取前 N(i) 位 for i 1:n inter B(i); % 当前累加概率 INT zeros(1, N(i)); for j 1:N(i) inter inter * 2; if inter 1 INT(j) 1; inter inter - 1; % 小数部分继续乘 2 else INT(j) 0; end ST(i) strcat(ST(i), num2str(INT(j))); end end eff sum(A .* (-log2(A))) / n_1; % 信息熵 / 平均码长 end逻辑说明B(i) 的计算依赖前一个节点的累加概率加前一个节点的概率这个递推关系是香农码的基础。二进制小数转换部分用的是乘 2 取整法每次判断乘 2 后是否大于等于 1是则记 1 并减去整数部分否则记 0。N(i) 向上取整保证了码字长度覆盖 -log2(Pi) 的信息量需求。参数说明A 必须是行向量或列向量函数内部强制转成行向量降序排序。n_1 是加权平均码长eff 是编码效率理论上永远小于等于 1。需要读者注意这里 ST 用的是字符串数组MATLAB 7.0 里字符串拼接要用 strcat(1,i) 的写法新版 MATLAB 的 strings 数组更顺手但核心逻辑一致。3.3 Huffman 树的 MATLAB 实现符号索引矩阵与回溯编码function [result, avg_len, eff] huffman_encode(A) Q A(:); % 当前概率序列每轮会被重排 n length(Q); % Index 矩阵记录每次合并后新节点在原序列中的位置 % Index 第一行是原始符号顺序后面每行记录一次合并 Index zeros(n, n); Index(1, :) 1:n; % 建立合并顺序表 G最后一行为树根 for i 1:n [Q, idx] sort(Q); % 升序排列找到最小两个 Index(i1, 1:length(idx)) idx; % 记录本轮排序位置 if length(Q) 2 new_val Q(1) Q(2); % 合并最小两个 Q [new_val, Q(3:end)]; % 新节点排最前 end end % 回溯编码从根到叶子 % G 矩阵记录每次合并时左右孩子的去向 % Char 矩阵存每个符号的码字 Char blanks(n * n); % 预分配 Char(n-1, n) 0; % 树根左孩子 Char(n-1, 2*n) 1; % 树根右孩子 % 按索引反查原始符号的码字 result strings(1, n); for i 1:n pos find(Index(1, :) i); % 找到第 i 个符号在树中的位置 result(i) strtrim(Char(1, (pos-1)*n 1 : pos*n)); end avg_len sum(A .* strlength(result)); eff sum(A .* (-log2(A))) / avg_len; end逻辑说明这里的 Q 排序用的是升序每轮取前两个最小概率合并新节点插入最前面保证下一轮仍然能取到最小的两个。Index 矩阵记录排序索引其实索引回填的逻辑在完整报告里有更多细节我这里为可读性做了简化。回溯编码的经典思路是从树根开始左 0 右 1一直走到叶子节点。参数说明result 的每个元素是字符串strlength 计算码长。如果概率和为 1 且按 Huffman 规则构建编码效率在测试数据下通常能接近 0.98 以上。注意这段代码需要配合完整报告中的 G 矩阵构建部分一起看单看这个简化版只能应对概率数较少的场景。报告里的完整代码用 G(n-1, 2n) 存根节点Char(n-1, n) 和 Char(n-1, 2n) 分别存 0 和 1是通过索引矩阵反查的这个设计值得细读。4. C/C 实现结构体数组、优先队列与文件压缩解压4.1 香农码与费诺码的 C 语言结构体组织方式C 语言实现香农码首先要解决的是排序问题。报告里的做法是用结构体数组存符号概率和码字然后按概率降序排序typedef struct { double prob; char code[20]; // 码字字符串 } Symbol; // 按概率降序排序 int cmp(const void *a, const void *b) { Symbol *sa (Symbol *)a; Symbol *sb (Symbol *)b; if (sa-prob sb-prob) return 1; else return -1; }费诺码的 C 实现核心是分组递归报告里用了一个 while 循环里嵌套 for 循环的方式来逼近概率和的一半而不是直接用递归。这是因为 C 语言处理字符串拼接比 MATLAB 麻烦用数组下标控制更直接。核心思路是把当前区间的符号分成左右两组left_sum 和 right_sum 逐步累加当 right_sum 超过 left_sum 时停止把边界记下来递归处理。参数上要注意码字数组长度要足够大。测试概率 0.4、0.2、0.1、0.1、0.15、0.05最大码长出现在最小概率 0.05 上ceil(-log2(0.05)) 5 位但 Huffman 码长可能到 4 位或 5 位所以 code[20] 足够。如果符号数超过 20建议动态分配或者用 vectorstring。4.2 Huffman 树的构建优先队列与指针陷阱C 实现 Huffman 编码的推荐写法是用优先队列priority_queue每次取最小两个节点但要注意 priority_queue 默认是大顶堆需要自定义比较器#include queue #include vector #include string using namespace std; struct Node { double prob; char symbol; // 符号值内部节点用 \0 Node *left, *right; Node(double p, char s) : prob(p), symbol(s), left(nullptr), right(nullptr) {} }; struct Cmp { bool operator()(Node *a, Node *b) { return a-prob b-prob; // 小顶堆 } }; Node *build_huffman_tree(vectordouble probs) { priority_queueNode*, vectorNode*, Cmp pq; for (double p : probs) { pq.push(new Node(p, A pq.size())); } while (pq.size() 1) { Node *left pq.top(); pq.pop(); Node *right pq.top(); pq.pop(); Node *parent new Node(left-prob right-prob, \0); parent-left left; parent-right right; pq.push(parent); } return pq.top(); }逻辑说明priority_queue 的第三个模板参数 Cmp 必须是小顶堆语义否则每次拿到的都是最大概率编码结果全反。构建完树之后从根节点 DFS 到叶子节点的路径就是码字。这里建议用 std::string 传递码字而不是 char*避免手动释放内存时的指针越界。参数说明build_huffman_tree 返回的是根节点指针树的深度等于最大码长。DFS 时维护一个 string path 变量左走加 0右走加 1到叶子节点symbol ! \0时把 path 存入编码表。这里有个内存管理血泪经验new 出来的节点一定要在解压后 delete否则每次压缩一个文件就泄漏一整棵树。4.3 文件压缩与解压缩码表存储与按位读写文件压缩的关键是把码字逐位写进文件而不是逐个写字符否则压缩率会非常难看。比如 0.4 的码字是 00占 2 bit如果用 fwrite 写字符串 00 就要占 2 字节等于没压缩甚至膨胀。按位读写的标准做法是用一个 bit_buffer 缓存 8 个 bit攒满一个字节就写入文件最后不足 8 位补 0 并记录填充位数。压缩过程的文件头格式我建议这样设计先写入符号总数 n然后写入每个符号的概率值或码字长度与码字内容最后写入数据区。解压时先读 n 和码表重建 Huffman 树然后逐位读取压缩数据从树根开始走走到叶子节点输出符号再回到根继续。这个流程报告里已经完整实现。必须强调一个常见的翻车点码表一定要存原始符号的映射。Huffman 编码表是把符号映射到码字压缩文件里只存码字长度和码字内容是不够的还得存每个码字对应的原始符号位置。因为解压时需要重新构建整棵树而树的形状依赖概率分布如果码表里丢了符号树就建不起来。报告里的压缩测试 infosource.txt 内容恰好是一组数字概率如果码表没存好解压出来就是乱码。5. 避坑指南概率输入、排序错位与解压失败的高频问题排查5.1 概率文件读到空矩阵或全角逗号报错现象MATLAB 里执行 load gailv.txt工作区里变量是空的或者读进来 A 只有一个数值。原因txt 文件里写的是带逗号的概率序列例如 0.4, 0.2, 0.1load 无法解析逗号分隔。解决编辑 txt 文件统一成空格或换行分隔或者在 MATLAB 里手动构造 A [0.4 0.2 0.1 0.1 0.15 0.05] 代替 load。另一个隐藏问题是全角逗号如果文件是从 word 文档复制过来的逗号可能是全角形式load 直接报错。解决方式是先用记事本打开看分隔符然后统一替换。5.2 排序后编码结果和概率对不上号现象输出码字和概率列表错位比如 0.2 符号的码字出现在 0.4 那一行。原因MATLAB 的 sort 函数会改变概率顺序但后续的 ST 存储位置没有同步映射。典型场景是 A sort(A, 2, descend) 直接把 A 覆盖了但后面赋值码字时仍然按原 A 的下标 1:i 循环。解决排序前先用 idx 记录原始位置A_sorted A(idx)ST(idx) 码字这样最终码字能对应到原始符号。C/C 里同理qsort 后结构体数组已经整体移动不要再用原来的下标访问。5.3 费诺码的死循环分组条件永远不满足现象程序卡在 while 循环里不退出CPU 占用 100%。原因费诺码分组时比较的是累积概率差但如果序列里存在两个相等概率左右两组的差永远不为 0而代码里用了严格的相等判断导致无法退出。解决把停止条件改为当前组只剩一个符号或者概率和的差小于某个阈值例如 1e-6。报告里用 abs(sum(B(p:k,1)) - a) 比较差值的写法这个阈值已隐含在比例判断里但读者自己实现时要注意浮点数不能直接判等。5.4 Huffman 树回溯编码结果为空字符串现象result 输出是空的或者全部是空白。原因Char 矩阵的预分配长度不够blanks(nn) 分配后回溯编码时写位置超出矩阵边界被 MATLAB 自动忽略。解决把 Char 的列数改为 2n 或更大确保最坏情况下的码字长度能被容纳。报告里用的是 Char(i,:) blanks(nn)如果 n6nn36 位足够但符号数增多时会出问题。建议直接用 string 拼接不要用 blanks 预分配。5.5 解压出来的文件比原文件还大现象压缩后的文件体积没有减小反而增大了。原因没有按位写入每 bit 被存成了 1 字节的字符或者码表写得太大塞了全量概率表。解决压缩数据区用位操作8 个 bit 合成一个 byte 写入码表只存符号 码字长度 码字不要存整棵树的全部节点。另外一个常见原因是测试文件太小文件头开销已经超过压缩节省的空间这种情况用更大的文本文件测试即可。5.6 C 指针未释放导致内存泄漏现象连续压缩多个文件后内存占用持续增长直到卡死。原因Huffman 树的节点用 new 分配但没有在解压后 delete。解决在解压完成后写一个 release_tree(Node* root) 函数递归释放所有节点或者改用智能指针 unique_ptr 管理子节点。报告源码里没有释放逻辑是因为它是一次性运行但复用代码时这是必须补上的。6. 验证编码结果的三个硬指标效率、Kraft 不等式与唯一可译性检查拿到一份实验报告或别人给的编码代码第一步不是跑通而是验证它算得对不对。三个硬指标能过滤掉 90% 的错误实现。第一个指标是编码效率公式是 H / 平均码长。测试数据 0.4、0.2、0.1、0.1、0.15、0.05 的熵是 2.3464 bit/symbol。Huffman 码的码字长度分别是 1、2、3、3、3、3 位平均码长 0.4×1 0.2×2 0.1×3 0.1×3 0.15×3 0.05×3 2.4 bit/symbol效率约 0.9777。费诺码碰巧也能达到 1、2、3、3、3、3 的组合时效率相同。香农码则因为独立的码长取整0.4 的码长是 2 而不是 Huffman 的 1 位所以平均码长会更大效率通常低几个百分点。用这个数字对照报告里的 t1、t2、t3 输出一眼就能看出程序是否写对。import math probs [0.4, 0.2, 0.1, 0.1, 0.15, 0.05] H -sum(p * math.log2(p) for p in probs) lavg_huff sum(p * l for p, l in zip(probs, [1, 2, 3, 3, 3, 3])) print(f熵: {H:.4f}) print(fHuffman平均码长: {lavg_huff:.4f}) print(fHuffman编码效率: {H / lavg_huff:.4f})第二个指标是 Kraft 不等式即 sum(2^-len_i) 1。取 Huffman 码字长度 1、2、3、3、3、3算出来是 0.5 0.25 0.125×4 1.0刚好压线——这是最优前缀码的典型特征。如果某个编码方案的 Kraft 和大于 1说明码长组合不可能存在直接判定实现错误。第三个指标是唯一可译性检查。信息论的第二课就讲过的 Sardinas-Patterson 算法可以实现这个检查但有一个更简单的做法把每个码字放进 set然后对任意两个码字检查是否有较短的码字是较长码字的前缀。如果没有前缀冲突就一定是唯一可译码。这个检查值得写成一个函数因为在调试压缩文件时解压乱码的根因往往就是码表生成时前缀冲突没被意识到。我记得有一次调试某跨平台系统的压缩模块压缩正常但解压总乱码最后定位到问题是码字回溯时左右孩子写反了——左 1 右 0 还是左 0 右 1 在编码和解压两端不一致。从那以后我每次拿到编码代码都强制先跑一遍这三个验证指标确认效率和 Kraft 不等式没问题再进入数据流调试。这三项全过代码的正确性基本就有保证。希望这份实验报告能帮你少走这些弯路。本文还有配套的精品资源点击获取