简介这份资源是中南大学信息论与编码课程编码部分的实验报告面向正在修读信息论与编码、数据压缩等课程的高校学生以及需要完成香农码、费诺码与Huffman编码实验的读者。资源包内共1个docx文档约792KB内容围绕三类经典编码的理论推导与编程实现展开正文涵盖实验目的与要求、各编码说明、源代码、运行结果截图及课程设计指导书等模块。报告具体涉及用MATLAB实现香农码、费诺码和Huffman编码的完整流程包括概率降序排列、累加概率计算、码字生成与编码效率分析同时给出用C/C实现香农码、Huffman码与费诺码的程序设计并延伸到利用Huffman编码完成文件的压缩与解压缩。文中的测试案例采用概率序列0.4、0.2、0.1、0.1、0.15、0.05可对照复现结果帮助读者理解前缀编码与最优二叉树的构造思路。目前已有102人学习下载适合作为实验报告撰写与代码调试的参考。1. 编码部分实验的核心是把定理跑成数据很多人做完信息论与编码的编码部分实验报告里只剩一张哈夫曼码表和一句“比等长编码更优”被追问“码长方差大会给译码端带来什么代价”就答不上来。编码实验真正要验证的是两条线信源编码这条线看平均码长 L 能压到离信源熵 H(X) 多近效率 H/L 是多少信道编码这条线看加入冗余后能在多大误码率下把错误纠回来(7,4) 汉明码为什么只能纠一位错多出来的 3 个校验位到底买到了什么。适合正在写实验报告、要复现哈夫曼码与汉明码、或者想把课程公式落成可复现脚本的人。下面按信源编码、信道编码、指标口径、排错四层展开每一步都给算法、参数和验证方式。2. 信源编码实验哈夫曼码、香农码与费诺码的码长对比2.1 先把信源熵和平均码长的计算口径定死编码部分实验最容易被扣分的地方不是算法而是口径不统一。熵用 bit 作单位就得用 log₂平均码长按 L Σ pᵢ·lᵢ 算编码效率 η H(X)/L冗余度是 1 − η。常见错误是熵用了自然对数、码长却按二进制位统计或者概率没有归一化就直接代公式结果效率算出大于 1一看就错。先把这两个函数固定下来后面三种码共用同一套输入对比才有意义。import math def entropy(p): p: 概率列表返回以 bit 为单位的信源熵 H(X) return -sum(pi * math.log2(pi) for pi in p if pi 0) def avg_len(p, lengths): 平均码长 L Σ p_i * l_i return sum(pi * li for pi, li in zip(p, lengths)) p [0.4, 0.2, 0.2, 0.1, 0.1] print(sum(p)) # 先确认等于 1.0否则熵和效率都不可信 print(entropy(p)) # 2.1219 bit这是压缩的理论下限逻辑说明entropy里跳过 pᵢ 0 的项避免 log₂0 抛异常avg_len只做加权求和不关心码字本身长什么样所以三种编码算法可以复用。参数上唯一要盯的是概率列表必须严格和为 1浮点求和可能得到 0.9999999工程上做一次p [x/sum(p) for x in p]归一化再喂进算法更稳妥。2.2 用优先队列构建哈夫曼树并生成码字哈夫曼编码的做法是每次取概率最小的两个节点合并直到只剩一个根。用 Python 的heapq要注意一点堆元素里必须塞一个单调递增的序号否则概率相同时会去比较字典对象而报TypeError。下面这个版本把码字直接挂在节点上合并时给左右子树的码字分别前置0和1省掉建树后再遍历的步骤。import heapq def huffman_codes(symbols, probs): # 堆元素 (概率, 序号, {符号: 码字})序号用于打破概率相同的比较 heap [(p, i, {s: }) for i, (s, p) in enumerate(zip(symbols, probs))] heapq.heapify(heap) while len(heap) 1: p1, _, t1 heapq.heappop(heap) # 最小 p2, _, t2 heapq.heappop(heap) # 次小 merged {s: 0 c for s, c in t1.items()} merged.update({s: 1 c for s, c in t2.items()}) heapq.heappush(heap, (p1 p2, len(heap), merged)) return heap[0][2] symbols [A, B, C, D, E] codes huffman_codes(symbols, p) lengths [len(codes[s]) for s in symbols] print(codes, avg_len(p, lengths)) # L 2.2 bit逻辑说明p1 p2是合并后的新概率len(heap)作为新序号保证唯一且递增。参数上真正影响结果的是“取最小还是取次小”这一对次序以及并列概率时谁先出堆——这两点都会改变具体码字但不会改变平均码长。所以报告里写码字时最好补一句“并列概率按符号字典序处理”否则换个人跑出来的码表和你不一样评审会怀疑结果。2.3 香农码与费诺码一个用累积概率一个用递归分组香农码的思路是给每个符号取码长 lᵢ ⌈−log₂pᵢ⌉再把累积概率 Fᵢ 的二进制小数截取前 lᵢ 位当码字。它能保证前缀条件成立Kraft 不等式取等号或严格小于代价是码长普遍偏长。费诺码走的是另一条路按概率降序排列后每次把序列切成两组让两组概率和尽可能接近上组前置0、下组前置1递归到底。import math from itertools import accumulate def shannon_codes(probs): order sorted(range(len(probs)), keylambda i: -probs[i]) cum list(accumulate([probs[i] for i in order])) codes {} for k, i in enumerate(order): l math.ceil(-math.log2(probs[i])) frac, bits cum[k] - probs[i], # 累积概率不含自身 for _ in range(l): # 二进制展开取前 l 位 frac * 2 bits str(int(frac)) frac - int(frac) codes[i] bits return codes def fano_codes(idx, probs, prefix): if len(idx) 1: return {idx[0]: prefix or 0} total, best, acc sum(probs[i] for i in idx), 0, 0 for k in range(len(idx) - 1): # 找概率和最接近一半的切点 acc probs[idx[k]] if abs(acc - total / 2) abs(best - total / 2): best acc cut k 1 left, right idx[:cut], idx[cut:] return {**fano_codes(left, probs, prefix 0), **fano_codes(right, probs, prefix 1)}逻辑说明cum[k] - probs[i]得到的是“排在当前符号之前的所有符号概率和”这是香农码定义里的 Fᵢ。费诺码里cut是把序列切成两组的位置切点搜索是 O(n²)符号数不多时够用真要做上百个符号的信源得换成动态规划版的最优分组。参数上两者都依赖“先按概率降序排序”这一步排序方式不同切分点就不同平均码长会有零点几 bit 的差异。2.4 三种码放同一张表里看差距把同一组概率喂给三种算法结果差异一眼能看出来。下面这组数据用的是课本常见的 5 符号信源H(X) 2.1219 bit符号概率哈夫曼码字码长香农码字码长费诺码字码长A0.400100201B0.20100301131003C0.20101310031013D0.101103110041103E0.101113111041113按这张表算下来哈夫曼和费诺的平均码长都是 2.2 bit效率 96.5%香农码平均码长 2.8 bit效率只有 75.8%等长编码需要 3 bit效率 70.7%。差距的来源是香农码强制 lᵢ ⌈−log₂pᵢ⌉对 p 0.4 这种“接近 0.5 但不等于 0.5”的概率会白白多花一位。报告里除了这张表还应该写上最小码长、最大码长和码长方差——方差直接关系到译码端的缓冲区设计是拿分点。3. 信道编码实验汉明码与循环码的编码译码链路3.1 (7,4) 汉明码的生成矩阵与校验矩阵怎么搭汉明码的核心是校验矩阵 H 的每一列都不为零且互不相同列数等于码长 n列向量的位宽 r 决定校验位数n 2ʳ − 1。取 r 3 就得到 (7,4) 码4 个信息位、3 个校验位、码率 4/7 ≈ 0.571。工程实现的通行做法是把 H 写成 [Pᵀ | I₃] 的系统形式对应的生成矩阵 G [I₄ | P]这样编出来的码字前 4 位就是原始信息抄读方便。import numpy as np G np.array([[1, 0, 0, 0, 1, 1, 0], [0, 1, 0, 0, 0, 1, 1], [0, 0, 1, 0, 1, 1, 1], [0, 0, 0, 1, 1, 0, 1]], dtypeint) H np.array([[1, 0, 1, 1, 1, 0, 0], [1, 1, 1, 0, 0, 1, 0], [0, 1, 1, 1, 0, 0, 1]], dtypeint) assert ((G H.T) % 2 0).all() # 校验G·Hᵀ 必须是全零矩阵 print(G.shape, H.shape) # (4, 7) (3, 7)逻辑说明(G H.T) % 2全零是系统码成立的必要条件写实验报告时把这行 assert 贴上去比空口说“矩阵构造正确”有说服力得多。参数上要注意dtypeint用默认浮点会引入舍入误差% 2之后可能出现 1.0000000002 这种值。另外 H 的列顺序决定了后面伴随式和错误位置的映射关系中途换顺序必然翻车。3.2 伴随式译码一位错的定位与纠错接收端拿到码字 r 后先算伴随式 s r·Hᵀ模 2。如果 s 是全零向量认为无误否则 s 就是一个 3 位二进制数等于 H 中某一列的值那一列的下标就是出错的位置。这个查表动作在软件里实现非常直接把 H 的列拼成字典即可。SYNDROME {tuple(H[:, i]): i for i in range(7)} # 列向量 - 位下标 def decode(r): r np.array(r, dtypeint).copy() s tuple((H r) % 2) if any(s): r[SYNDROME[s]] ^ 1 # 翻转出错位 return r cw (np.array([1, 0, 1, 1]) G) % 2 r cw.copy(); r[4] ^ 1 # 人为在第 4 位注入一位错 print(cw, r, decode(r)) # 译码结果应还原成 cw逻辑说明SYNDROME字典把 7 个列向量映射到 0~6 的位置下标查表就是 O(1)。参数上唯一要保证的是SYNDROME必须在同一个 H 上生成如果 H 换了列顺序而字典没重建就会把错误位翻到另一个位置上去表现为“越纠越错”。这也是实验里最常见的现象之一——误码率曲线在低信噪比段反而高于未编码系统。3.3 循环码 (7,4) 的生成多项式与模 2 除法循环码把码字看成 GF(2) 上的多项式编码本质是做多项式除法。以 g(x) x³ x 1二进制 1011为例系统编码的做法是先把信息多项式左移 n − k 3 位再对 g(x) 取余把余数拼回低位。整数位运算天然对应 GF(2) 多项式加减因为异或就是模 2 加法。def poly_mod(dividend, generator): GF(2) 多项式取模整数低位对应低次项 deg generator.bit_length() - 1 rem dividend while rem and rem.bit_length() - 1 deg: rem ^ generator (rem.bit_length() - 1 - deg) # 逐位消去最高次项 return rem def cyclic_encode(msg_bits, g0b1011, n_k3): m int(msg_bits, 2) n_k # 信息多项式左移 n-k 位 return format(m ^ poly_mod(m, g), 07b) for m in [0001, 1011, 1111]: print(m, -, cyclic_encode(m))逻辑说明poly_mod每轮把生成多项式左移到与当前余数最高次项对齐再异或消去循环到次数不够为止和手算长除法完全一致。参数n_k必须等于生成多项式的次数取值错了拼出来的码字位数就不对。循环码的好处是可用移位寄存器硬件实现软件里这段整型异或就是它的等价形式报告里如果配上移位寄存器的结构说明比只贴代码更有分量。3.4 在 BSC 上注入误码把纠错能力跑成曲线理论说汉明码最小距离 d_min 3能纠 1 位错能检出 2 位错所以误组率应该约等于“出现两位及以上错误”的概率。验证这件事只需要在二进制对称信道上跑蒙特卡洛。p 0.01 时(7,4) 码的误组率理论上约为 1 − 0.99⁷ − 7×0.01×0.99⁶ ≈ 2.0×10⁻³而同样 4 个信息位不编码直接传误组率是 1 − 0.99⁴ ≈ 3.9×10⁻²差了一个数量级。交叉概率 p未编码误组率(7,4) 汉明码误组率码率增益倍数0.0014.0×10⁻³2.1×10⁻⁵0.571约 1900.0103.9×10⁻²2.0×10⁻³0.571约 200.0501.9×10⁻¹4.5×10⁻²0.571约 4.2import numpy as np H np.array([[1, 0, 1, 1, 1, 0, 0], [1, 1, 1, 0, 0, 1, 0], [0, 1, 1, 1, 0, 0, 1]], dtypeint) G np.array([[1, 0, 0, 0, 1, 1, 0], [0, 1, 0, 0, 0, 1, 1], [0, 0, 1, 0, 1, 1, 1], [0, 0, 0, 1, 1, 0, 1]], dtypeint) SYNDROME {tuple(H[:, i]): i for i in range(7)} def run_bsc(p, trials200000, seed2024): rng np.random.default_rng(seed) msg rng.integers(0, 16, sizetrials) M (msg[:, None] np.arange(3, -1, -1)) 1 # 4 bit 信息矩阵 C (M G) % 2 # 编码成 7 bit E (rng.random((trials, 7)) p).astype(int) # BSC 误码图样 R (C E) % 2 # 接收码字 S (R H.T) % 2 # 伴随式 for i in range(trials): s tuple(S[i]) if s in SYNDROME: # 全零伴随式不动 R[i, SYNDROME[s]] ^ 1 return float((~np.all(R C, axis1)).mean()), float((R ! C).mean()) blk, bit run_bsc(0.01) print(f误组率{blk:.2e} 误比特率{bit:.2e}) # 误组率约 2.0e-03逻辑说明E是按 p 生成的独立误码图样S一次性把 20 万组伴随式全算出来只有纠错那一步用循环因为要按下标改R。返回两个指标误组率按“整块 7 位里还有错”统计误比特率按所有位的错误比例统计报告里两个都要给别只写一个。参数trials决定统计精度p 越小需要越多的试验次数p 0.001 时想稳定看到 10⁻⁵ 量级至少得跑 10⁶ 组。4. 实验数据与指标口径码率、编码效率、误码率怎么统一4.1 几个指标的定义别混用信源编码和信道编码的指标名字很像含义完全不同。信源侧的编码效率 η H(X)/L衡量的是压缩效果永远小于 1越接近 1 越好信道侧的码率 R k/n衡量的是冗余开销(7,4) 汉明码是 0.571它不是“效率”不能拿来和信源效率比大小。误码率也分两种误比特率 BER 按位统计误组率 BLER 或误帧率按块统计同一个系统下 BLER 通常比 BER 大一到两个数量级报告里必须写清用的是哪一个。指标定义(7,4) 汉明码取值常见误用信源熵 H(X)−Σpᵢlog₂pᵢ2.1219 bit用 ln 算平均码长 LΣpᵢlᵢ2.2 bit哈夫曼忘了乘概率信源编码效率 ηH(X)/L96.5%与码率混为一谈信道码率 Rk/n4/7 ≈ 0.571当成效率写进结论最小距离 d_min非零码字的最小重量3只算生成矩阵行重量纠错能力 t⌊(d_min−1)/2⌋1 位说成能纠 2 位4.2 参数设置表让结果可复现实验报告能不能被复现取决于参数写没写全。下面这张表是编码部分实验最常缺的几项直接照抄结构补上比在正文里大段描述“采用了较大规模的仿真”有用。参数建议取值说明信源符号数与分布5 符号0.4/0.2/0.2/0.1/0.1与教材例题一致便于对照理论值概率归一化强制 Σpᵢ 1浮点求和误差会导致熵偏小熵的对数底2单位 bit与码长单位一致信道模型BSC对称无记忆交叉概率 p 独立作用每一位p 的扫描范围10⁻³ ~ 10⁻¹ 对数等分画 BER 曲线的横轴单点试验次数p ≥ 0.01 用 10⁵p 0.01 用 10⁶相对误差控制在 5% 以内随机种子固定值如 2024保证同一次结果可复现译码方式硬判决伴随式译码与 (7,4) 汉明码匹配试验次数这一项可以用公式估误组率估计值的标准差约为 √(p̂(1−p̂)/N)N 10⁵、p̂ 2×10⁻³ 时相对标准差约 22%太糙N 10⁶ 时降到约 7%才够画曲线。这也是为什么报告里的低误码率点经常抖动得厉害——不是程序写错了是点数不够。4.3 把压缩率和误码率画成两张图两条实验线对应两张图信源侧画各符号码长柱状图加一条熵的水平线直观展示哪些符号的码长“超支”信道侧画 p-BER 对数曲线把未编码、汉明码两条线放一起中间的空间就是编码增益。画图时纵轴用对数坐标否则低误码率段全挤在轴线上看不出差别。import numpy as np, matplotlib.pyplot as plt p_list np.logspace(-3, -1, 9) # 10^-3 到 10^-1 对数等分 ber_unc 1 - (1 - p_list) ** 4 # 未编码 4 bit 的误组率 ber_hamming [run_bsc(p, trials200000)[0] for p in p_list] plt.figure(figsize(6, 4.5)) plt.semilogy(p_list, ber_unc, o-, label未编码 4 bit) plt.semilogy(p_list, ber_hamming, s-, label(7,4) 汉明码) plt.xlabel(BSC 交叉概率 p); plt.ylabel(误组率) plt.grid(True, whichboth, ls:); plt.legend() plt.tight_layout(); plt.savefig(ber_curve.png, dpi150)逻辑说明np.logspace(-3, -1, 9)生成 9 个对数等分点保证曲线在低误码率端也有足够采样semilogy把纵轴转成对数刻度。参数dpi150是投报告的最低要求100 的图插进 Word 打印后会糊。两张图建议分别命名为source_efficiency.png和ber_curve.png正文引用时直接按文件名对应评审翻起来不会找错。5. 编码实验最容易翻车的几个点与进阶验证5.1 五个高频错误逐条对照排查概率没归一化。输入是频数而不是频率时熵会算成负数码长看着正常但效率突破 1。开跑前固定加一行assert abs(sum(p) - 1) 1e-9。哈夫曼并列概率没约定。0.2/0.2 谁先出堆会得到两组不同的码字虽然平均码长相同但报告里的码表和别人对不上。在代码注释和报告里都写明“并列时按符号顺序处理”。校验矩阵列顺序与查表不一致。这是伴随式译码翻车的头号原因。修改 H 之后必须重建SYNDROME字典最好用一行断言锁定assert len({tuple(H[:, i]) for i in range(7)}) 7列向量必须互不相同且非零。用编码器的错误位统计代替接收端。误比特率必须在纠错之后再统计在纠错之前统计得到的是信道本身的误码率两者不能混着写进同一张表。低误码率点试验次数不足。前面算过10⁵ 次在 10⁻³ 量级上相对误差超过 20%曲线会出现“先降后升”的假象。5.2 用码字重量分布反推纠错能力报告里写“最小距离是 3”很常见但没说怎么来的。把 2ᵏ − 1 个非零码字全枚举出来算重量取最小值才是可验证的做法。k 4 时只有 15 个码字暴力枚举毫无压力这一点也顺带说明了为什么分组码的译码复杂度会随 k 指数增长。from itertools import product import numpy as np G np.array([[1, 0, 0, 0, 1, 1, 0], [0, 1, 0, 0, 0, 1, 1], [0, 0, 1, 0, 1, 1, 1], [0, 0, 0, 1, 1, 0, 1]], dtypeint) def weight_distribution(G): k G.shape[0] dist {} for bits in product([0, 1], repeatk): if not any(bits): continue # 排除全零码字 w int(((np.array(bits) G) % 2).sum()) dist[w] dist.get(w, 0) 1 return dist dist weight_distribution(G) print(dist, d_min , min(dist)) # {3: 7, 4: 7} d_min 3逻辑说明product([0,1], repeatk)枚举全部信息序列(bits G) % 2得到对应码字.sum()即汉明重量。输出只有重量为 3 和 4 的码字各 7 个最小距离是 3由 t ⌊(3−1)/2⌋ 1 得到纠错能力为 1 位。这组数同时验证了汉明码的一个重要性质它的重量分布是对称的重量接近 n 的码字数量与重量接近 0 的码字数量相等。用同一个函数换成循环码的生成矩阵把 g(x) 1011 对应的 4 个循环移位拼成矩阵得到的 d_min 也是 3说明 (7,4) 汉明码其实是循环码的一个特例。把两组重量分布并排放进报告比单独写“两者纠错能力相同”有说服力得多。本文还有配套的精品资源点击获取