简介这份文档是中南大学「信息论与编码」课程编码部分实验的完整报告面向正在修读该课程、需要完成香农码、费诺码与Huffman编码实验的本科生也可作为自学者理解变长前缀编码的参考范例。报告围绕三种经典信源编码展开先用MATLAB实现香农码与费诺码的概率排序、累加概率计算、码字生成及编码效率求解再用C/C构造Huffman树、生成编码表并完成文本文件的压缩与解压缩附有原理说明、源代码与运行结果截图还包含以0.4、0.2、0.1、0.1、0.15、0.05为测试案例的完整演算过程、课程设计指导书以及三种编码效率的对比图示。资源包共1个docx文件约792KB结构清晰便于直接查阅与复用代码。目前已有102人学习适合需要参考实验思路、核对代码实现或准备课程设计的同学。1. 编码实验报告里最容易翻车的是那句「结果如图」实验课上把哈夫曼树画得整整齐齐汉明码的校验矩阵背得滚瓜烂熟卷积码的网格图也能默画出来交上去的报告却被一句「你这个平均码长 2.57 是怎么算出来的」问住。问题往往不在信息论本身而在实验记录和代码之间断了链条概率表是手抄的码表是手算的误码率曲线是按课本公式反推着描出来的。中南大学信息论与编码课程的编码实验部分通常就压在这三块上——信源编码的码长与效率、线性分组码的编码与纠错、卷积码的维特比译码与误码率测量。这一篇按这三块往下走每一块给出能直接抄进脚本的函数、能写进报告的数值表、以及参数改错时该盯哪一行。适合正在赶这份报告的人也适合想把编码理论重新用代码过一遍的工程师。2. 信源编码实验从信源熵到哈夫曼码长的可复现计算信源编码这一段的报告本质是让「熵」这个抽象量变成一个具体的比特数再拿它去比对你的码字平均长度。很多人写实验报告时把熵算成 2.51平均码长算成 2.57却没有解释这两个数为什么必须放在一起看。效率 ηH/L 就是那个把两者拴住的比值。2.1 把信源熵和编码效率写成两个可以复用的函数信息论课上的公式 H(X)−Σ pᵢ log₂ pᵢ落到 numpy 里只有两行但零概率符号必须提前剔掉否则 log₂(0) 会返回 −inf 把整个求和污染掉。这是新手脚本里最常见的第一个坑。import numpy as np def entropy(p): p: 一维概率向量返回以 bit 为单位的信源熵 p np.asarray(p, dtypefloat) p p[p 0] # 0*log0 约定为 0直接剔除 return float(-(p * np.log2(p)).sum()) def evaluate(p, code_len): code_len: 与 p 顺序一致的码长列表返回 (熵, 平均码长, 编码效率) p np.asarray(p, dtypefloat) H entropy(p) L float((p * np.asarray(code_len, dtypefloat)).sum()) return H, L, H / L这里的p 0是必需的过滤条件evaluate返回的第三个值 η 只可能落在 (0, 1] 区间内。如果算出大于 1 的效率几乎一定是概率向量和码长列表的顺序错位了——比如把排过序的码长配给了没排序的概率这是报告里最隐蔽也最致命的一类错误因为数字看着「挺合理」。提示概率向量建议直接从命令行或配置文件读入不要硬编码在函数体里。这样改信源分布时不用动代码也方便在报告附录里附上完整的输入。2.2 哈夫曼编码的最小实现与三个必须处理的边界哈夫曼算法本身不复杂每次取概率最小的两个节点合并左支添 0、右支添 1直到只剩一个根节点。真正的麻烦在于工程细节——Python 3 的堆没法直接比较两个列表权重相同时会抛异常只有一个符号时会出现空码字码字本身不唯一但码长在给定合并顺序下是确定的。import heapq def huffman_code(freq): freq: {符号: 概率或频数}返回 {符号: 码字} # 堆元素: [权重, 序号, [[符号, 码字], ...]] # 序号用于权重相同时的稳定排序避免 Python3 比较列表报错 heap [[w, i, [[s, ]]] for i, (s, w) in enumerate(freq.items())] heapq.heapify(heap) if len(heap) 1: # 退化情形只有一个符号 return {heap[0][2][0][0]: 0} while len(heap) 1: lo heapq.heappop(heap) # 概率较小的一支走 0 hi heapq.heappop(heap) # 概率较大的一支走 1 for pair in lo[2]: pair[1] 0 pair[1] # 向上归并时在最高位补分支号 for pair in hi[2]: pair[1] 1 pair[1] heapq.heappush(heap, [lo[0] hi[0], lo[1], lo[2] hi[2]]) return dict(heap[0][2])heap里为什么要塞一个i因为 Python 3 在元组比较时遇到相等权重会继续比较第三个元素而列表之间不支持大小比较会直接抛 TypeError。pair[1] 0 pair[1]是在最高位补码保证先合并的层最后被添加得到的码字从左到右就是根到叶的路径。拿一个偏斜的七符号信源实测freq {A:0.35,B:0.20,C:0.15,D:0.10,E:0.08,F:0.07,G:0.05}按上面的堆序跑出来的结果是符号概率哈夫曼码字码长码长 × 概率A0.351120.70B0.200120.40C0.1511130.45D0.1000130.30E0.0800030.24F0.07110140.28G0.05110040.20合计平均码长 L2.57 bit信源熵 H2.5134 bit编码效率 η0.9780。报告里真正该写的是这三个数而不是那七个码字——码字随权重平局的处理方式变化码长不会。顺带用 Kraft 不等式做一次自检Σ2^(−lᵢ) 2×2⁻² 3×2⁻³ 2×2⁻⁴ 1.0恰好取等说明这是一套紧致码没有任何冗余余量。2.3 香农-费诺码与哈夫曼码的码长对比怎么做才严谨香农-费诺码按概率降序排列后反复寻找使两组概率之和最接近的切分点切点左边添 0、右边添 1。实现上用一个栈代替递归代码短且不用调递归深度。def shannon_fano(freq): freq: {符号: 概率}返回 {符号: 码字} items sorted(freq.items(), keylambda kv: -kv[1]) # 概率降序 code {s: for s, _ in items} stack [items] while stack: seq stack.pop() if len(seq) 1: continue prefix [0] for _, w in seq: prefix.append(prefix[-1] w) # 找切点 i使左边 i 个符号的概率和尽量接近总和的一半 cut min(range(1, len(seq)), keylambda i: abs(prefix[-1] - 2 * prefix[i])) for s, _ in seq[:cut]: code[s] 0 for s, _ in seq[cut:]: code[s] 1 stack.append(seq[:cut]) stack.append(seq[cut:]) return code把同一份freq分别喂给两个函数再用evaluate算效率是这一节唯一值得做的对比实验。需要提醒的是在小字母表上两者平均码长经常完全相等比如上面那个七符号信源香农-费诺码长分布是 2、2、3、3、3、4、4平均码长同样是 2.57。这不是代码写错了而是这两种算法在小规模、分布不算极端的信源上确实常常重合。差异要到符号数二三十个、尾部概率压得极低时才明显。所以报告里如果写了「哈夫曼优于香农-费诺」最好附上具体分布和具体差值否则这句话站不住脚。2.4 用扩展信源验证效率随分组长度上升单个符号编码时效率卡在 0.978 上不去原因是每个码字至少要占 1 bit而低概率符号本身信息量不到 1 bit。把 N 个符号捆成一个「超符号」再编码效率会随 N 上升逼近 1这是实验里很值得补的一组数据。from itertools import product def block_source(freq, n): 把 n 个独立符号合成一个超符号返回新的频数字典 syms list(freq) out {} for combo in product(syms, repeatn): p 1.0 for s in combo: p * freq[s] out[.join(combo)] p return out base {A: 0.35, B: 0.20, C: 0.15, D: 0.10, E: 0.08, F: 0.07, G: 0.05} for n in (1, 2, 3): blk block_source(base, n) code huffman_code(blk) H, L, eta evaluate(list(blk.values()), [len(code[s]) for s in blk]) print(fN{n} 符号数{len(blk):3d} 熵{H:.4f} L{L:.4f} eta{eta:.4f})product(syms, repeatn)会生成 7ⁿ 个组合N3 时已经有 343 个符号堆操作量仍然很小。注意打印出来的 H 是 N 倍单符号熵L 也是 N 倍量级只有 η 是可比的。N2 时效率通常能到 0.99 以上N3 更接近 1。这条曲线是报告里最能说明「为什么工程上要用分组编码」的一页图比单纯罗列码表有说服力得多。3. 信道编码实验汉明码的生成矩阵、伴随式与纠错验证从信源编码转到信道编码问题的性质变了前面关心的是「用多少比特表示信源」这里关心的是「加上多少冗余比特能把传错的比特找回来」。线性分组码的实验最容易做成照抄矩阵的形式主义其实只要把 G 和 H 的构造逻辑、伴随式查表、注错验证这三步走通报告就有内容了。3.1 (7,4) 汉明码的生成矩阵与校验矩阵怎么摆系统形式的 (7,4) 汉明码生成矩阵写成 G[I₄|P]校验矩阵写成 H[Pᵀ|I₃]两者满足 H·Gᵀ0模 2。P 的具体取值不唯一但一旦选定编码和译码必须用同一套。下面这组是教材里最常用的import numpy as np # 系统形式 G [I4 | P] G np.array([ [1, 0, 0, 0, 1, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 1, 0, 0, 1, 1], [0, 0, 0, 1, 1, 1, 1], ], dtypeint) # H [P^T | I3]每一列是 1~7 的二进制表示 H np.array([ [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 1, 0, 1, 0], [0, 1, 1, 1, 0, 0, 1], ], dtypeint) assert not ((H G.T) % 2).any(), H·G^T 必须为全零矩阵最后那行断言值得保留在脚本里它是本实验最省事的自检只要你手改过 P 里任何一个元素忘了同步改 H这行立刻报错。H 的七列按顺序是 (1,1,0)、(1,0,1)、(0,1,1)、(1,1,1)、(1,0,0)、(0,1,0)、(0,0,1)恰好是 1 到 7 的二进制这不是巧合而是汉明码能被伴随式直接定位错误位置的根本原因。3.2 用 GF(2) 矩阵乘法完成编码编码过程就是把四位信息向量右乘 G再对 2 取模。矩阵乘法在 GF(2) 上的唯一区别是每次乘加后都要模 2numpy 里就是加一个% 2。def hamming_encode(msg_bits): msg_bits: 长度 4 的 0/1 列表返回长度 7 的码字 m np.asarray(msg_bits, dtypeint).reshape(-1, 4) return (m G) % 2 def hamming_decode(rx): rx: 长度 7 的接收向量返回 (信息位, 是否纠正) r np.asarray(rx, dtypeint) s (H r) % 2 # 伴随式 if not s.any(): return r[:4].tolist(), 0 # 无错 for i in range(7): # 伴随式等于 H 的某一列 if np.array_equal(s, H[:, i]): e np.zeros(7, dtypeint) e[i] 1 # 该位置发生了单比特翻转 return ((r e) % 2)[:4].tolist(), 1 return r[:4].tolist(), -1 # 落到表外属于不可纠正的错误hamming_encode里用reshape(-1, 4)是为了支持一次编码整个信息块实验里要处理几百上千组数据时能省掉循环。hamming_decode先用s.any()判断伴随式是否全零这是无错路径速度最快有错时再遍历七列比对代价可以忽略。3.3 伴随式与错误位置的对应关系表译码的本质是一张查表把 3 bit 的伴随式映射到 7 个可能的错误位置。这张表写进报告比画网格图直观得多伴随式 H·rᵀ对应错误位是否在纠错能力内000无错—110第 1 位是101第 2 位是011第 3 位是111第 4 位是100第 5 位是010第 6 位是001第 7 位是七个非零伴随式刚好被七个单比特错误位置占满一位不剩。这既是汉明码效率高的原因也是它无法区分单比特错和双比特错的根本原因——下面一节直接用穷举把这个结论跑出来。3.4 注错实验单比特纠正与双比特检出的真实边界报告里光写「汉明码能纠一位错」太薄得把 16 个信息字 × 7 个错误位置全部穷举一遍再把 21 种双比特错误也跑一遍用数据说明边界在哪。from itertools import combinations def inject_and_decode(bits, positions): 在指定位置翻转比特后译码返回还原出的信息位 r list(bits) for p in positions: r[p] ^ 1 return hamming_decode(r) ok1 total1 ok2 total2 0 for m in product([0, 1], repeat4): cw hamming_encode(m)[0].tolist() for p in range(7): # 全部单比特错误 total1 1 if inject_and_decode(cw, [p])[0] list(m): ok1 1 for a, b in combinations(range(7), 2): # 全部双比特错误 total2 1 if hamming_decode([cw[i] ^ (i in (a, b)) for i in range(7)])[0] list(m): ok2 1 print(f单比特错误: {ok1}/{total1} 纠正成功) print(f双比特错误: {ok2}/{total2} 纠正成功)跑出来会看到单比特错误 112/112 全部纠正双比特错误 0/336 全部失败而且失败的方式很隐蔽——译码器不会报错它会安静地把收到向量「纠正」成另一个合法码字输出一段看似正常的信息位。这就是为什么报告里不能只写纠错能力还得写「双比特错误会被误纠」。如果实验要求同时具备纠 1 检 2 的能力需要给 (7,4) 汉明码加一位全校验位构成 (8,4) 扩展汉明码代价是码率从 4/7 掉到 4/8这笔账在报告里值得单独算一次。4. 卷积码与维特比译码参数怎么设、误码率曲线怎么跑卷积码实验和分组码完全不是一种做法。分组码是「一块信息加一块冗余」卷积码是「每个信息比特持续影响后面若干拍输出」因此译码必须考虑整条序列而维特比译码就是在这张网格图上找一条累计度量最小的路径。这块实验最容易出错的地方是状态定义和回溯一旦状态编号约定和编码端不一致译码结果会是完全随机的。4.1 (2,1,3) 卷积码的状态定义与编码实现约定约束长度 K3记忆单元 2 个状态数 2²4生成多项式 g₁111、g₂101表示两路输出的抽头位置。状态用整数 s 表示bit(K−2) 是最近一次输入bit0 是最早的输入新状态由(b (K-2)) | (s 1)得到。def conv_encode(bits, g1(1, 1, 1), g2(1, 0, 1), K3): 一次输出 2 bit返回长度为 2*len(bits) 的码字序列 state 0 out [] for b in bits: reg [(state (K - 2 - i)) 1 for i in range(K - 1)] reg [b] reg # 最新输入放在最前 out.append(sum(a * x for a, x in zip(g1, reg)) % 2) out.append(sum(a * x for a, x in zip(g2, reg)) % 2) state ((b (K - 2)) | (state 1)) ((1 (K - 1)) - 1) return outreg的长度是 K第一位是新输入后面是历史状态。sum(...) % 2是 GF(2) 上的异或累加。生成多项式的系数顺序务必和状态位序一致g1(1,1,1) 表示新输入、上一拍、上两拍都参与第一路输出。顺序反了编码仍能跑但和课本上的网格图对不上后面译码必错。4.2 维特比译码的度量更新与回溯维特比的核心是每个时刻对四个状态各保留一条最优路径用汉明距离作为分支度量累加后取最小。def viterbi(rx, g1(1, 1, 1), g2(1, 0, 1), K3): rx: 接收到的硬判决序列0/1返回译码后的信息比特 n_states 1 (K - 1) INF float(inf) cost [INF] * n_states cost[0] 0 paths [[] for _ in range(n_states)] for t in range(0, len(rx), 2): pair rx[t:t 2] nxt [INF] * n_states npath [[] for _ in range(n_states)] for s in range(n_states): if cost[s] INF: continue for b in (0, 1): reg [b] [(s (K - 2 - i)) 1 for i in range(K - 1)] o1 sum(a * x for a, x in zip(g1, reg)) % 2 o2 sum(a * x for a, x in zip(g2, reg)) % 2 d (o1 ^ pair[0]) (o2 ^ pair[1]) # 硬判决汉明距离 ns ((b (K - 2)) | (s 1)) if cost[s] d nxt[ns]: nxt[ns] cost[s] d npath[ns] paths[s] [b] # 记录幸存路径 cost, paths nxt, npath best min(range(n_states), keylambda s: cost[s]) return paths[best]初始只有状态 0 的代价为 0其余为无穷大这对应「编码器从零状态出发」的约定。每个时刻对每个状态试两条输入分支代价小的留下来。硬判决用汉明距离软判决把d换成欧氏距离平方即可同一份代码改一行就能切换。收尾时取代价最小的状态回溯末尾不足 K−1 位可以直接截掉这是最常见也最省事的收尾方式。4.3 误码率曲线的测量点怎么设测误码率要固定每个信噪比点发送的比特数否则低信噪比处的曲线会抖得没法看。经验值是每个点至少累计 100 个错误转换到发送量上Eb/N0 为 6 dB 时通常需要几十万比特0 dB 时几万比特就够。Eb/N0 (dB)未编码 BPSK 理论 BER(2,1,3) 硬判决维特比参考 BER07.9e-24.5e-215.6e-22.5e-223.7e-21.2e-232.3e-25.0e-341.2e-21.8e-356.0e-35.5e-462.4e-31.4e-4表里的数值只给量级参考用来判断你自己跑出来的曲线是否离谱。判断标准有三条曲线必须单调下降同一信噪比下编码后的 BER 必须低于未编码两条曲线的间距在 BER 为 1e-3 附近大约 1.5 到 2 dB这就是硬判决维特比相对未编码的编码增益。如果算出的间距超过 4 dB先检查是不是把未编码那一支的信噪比换算搞错了——卷积码每 2 bit 输出对应 1 bit 信息码率 1/2Eb/N0 和 Es/N0 之间差 3 dB这个换算漏掉是高频错误。4.4 回溯深度与判决方式这两个参数怎么调回溯深度是影响译码结果最直接的参数。理论值取 5K 已经足够K3 时就是 15 步。把回溯深度从 5 调到 20误码率几乎没有变化调到 2 以下误码率会明显恶化因为路径还没收敛就被截断了。报告里可以用一组对比数据说明这一点三五个点就够。判决方式的影响更大。硬判决丢弃了接收信号的幅度信息软判决保留它同样约束长度下能多拿约 2 dB 的增益。改动量很小把接收序列从 0/1 换成带符号的浮点数分支度量从异或改成平方差其余逻辑不动。如果实验报告需要体现「同一编码、不同译码」的对比这是性价比最高的一组实验。5. 编码实验的进阶用法把三组实验收敛成一份能自证的报告三块内容各自跑通不难难的是让报告里的每个数字都能被重新算出来。做法是把信源编码、汉明码、卷积码三组实验收进一个入口脚本用命令行参数控制信源分布、随机种子和信噪比范围输出结构化结果而不是控制台打印。5.1 一个入口脚本跑完全部实验import argparse, json, pathlib import numpy as np def main(): ap argparse.ArgumentParser() ap.add_argument(--src, default0.35,0.2,0.15,0.1,0.08,0.07,0.05, help信源概率逗号分隔) ap.add_argument(--seed, typeint, default20240501, help随机种子写进报告附录保证可复现) ap.add_argument(--ebn0, default0:1:6, help起始:步长:结束单位 dB) ap.add_argument(--bits, typeint, default200000, help每个信噪比点的比特数) ap.add_argument(--out, defaultreport) args ap.parse_args() rng np.random.default_rng(args.seed) # 统一随机源 probs [float(x) for x in args.src.split(,)] result {seed: args.seed, entropy: entropy(probs)} outdir pathlib.Path(args.out) outdir.mkdir(exist_okTrue) (outdir / result.json).write_text( json.dumps(result, ensure_asciiFalse, indent2), encodingutf-8) if __name__ __main__: main()三个关键点所有随机过程共用rng一个实例避免不同函数的随机序列互相干扰--seed直接写进输出文件报告附录里附上这一行别人就能跑出和你一模一样的数据噪声和错误位置不要用时间戳做种子否则曲线每次都不一样实验结论就没法复现。5.2 报告里必须给出的三类交叉校验数值能不能站住脚取决于有没有独立于主流程的校验手段。下面三类校验每次实验都值得跑校验项表达式通过标准不通过说明什么正交性校验H·Gᵀ mod 2全零矩阵P 和 Pᵀ 不同步矩阵抄错了Kraft 校验Σ2^(−lᵢ)≤ 1紧致码取等码字不满足前缀条件树构造有环曲线收敛校验BER 随 Eb/N0 单调严格单调下降样本量不足或信噪比换算错误第三类校验要养成看数字的习惯不能只靠眼睛看图。把每个信噪比点的错误数和总比特数一起打印出来如果 6 dB 点只累计到 3 个错误那条曲线末端的可信度基本为零需要在报告里注明或加大发送量。5.3 一个让报告立住的小技巧把错误位置打出来最后一招是最省事的杀手锏在注错和信道仿真时把每次发生错误的位置连同校验子一起写进日志文件。汉明码实验里做二十组就够。这样当老师质疑「你怎么确定这次纠的是第一位」时可以直接翻到对应的那一行——校验子是 110翻转位置是 0输出信息位和原始信息位一致。卷积码同理把每个信噪比点实际发生的错误比特数和译码后的错误比特数分别记录误码率不再是一个孤零零的数字而是一条可以逐点追溯的记录链。本文还有配套的精品资源点击获取