简介：这份实验报告聚焦中南大学信息论与编码课程中的编码部分，围绕香农码、费诺码与哈夫曼编码的原理和实现展开，适合正在学习信息论与编码、需要完成课程实验或复习编码知识的本科生。报告完整记录了从概率序列处理到码字生成、编码效率计算的全过程，包含 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 计数器统计剩余未编码符号数量，遇到 y==1 即该组概率和已超过一半就切换方向。
费诺码的效率通常介于香农码和 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.4，0.2，0.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(i+1, 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，建议动态分配或者用 vector<string>。
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(vector<double> probs) { priority_queue<Node*, vector<Node*>, 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 写字符串 '0''0' 就要占 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.1，load 无法解析逗号分隔。解决：编辑 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)，如果 n=6，nn=36 位足够，但符号数增多时会出问题。建议直接用 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(f"Huffman平均码长: {lavg_huff:.4f}") print(f"Huffman编码效率: {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 不等式没问题再进入数据流调试。这三项全过，代码的正确性基本就有保证。希望这份实验报告能帮你少走这些弯路。
本文还有配套的精品资源，点击获取
