当前位置：首页 > news >正文

汉明码编码译码推演仿真（P124302169石雨婷）

news 2026/7/7 3:02:37

一、理论推导

1.1 汉明码基本概念

(7,4)汉明码是一种线性分组码，将4位信息位编码为7位码字，能纠正所有单比特错误，检测双比特错误（但不保证纠正）。

码长 n = 7
信息位 k = 4
校验位 r = n - k = 3
最小汉明距离 d_min = 3 → 纠错能力 t = ⌊(d_min-1)/2⌋ = 1

1.2 生成矩阵 G 的构造

标准形式的生成矩阵：G = [I₄ | P]

选择校验矩阵 H = [Pᵀ | I₃]，常用的 P 矩阵为：

P = [1 1 0]
[0 1 1]
[1 1 1]
[1 0 1]

因此：

text

G = [1 0 0 0 | 1 0 1] [0 1 0 0 | 1 1 0] [0 0 1 0 | 0 1 1] [0 0 0 1 | 1 1 1]

校验矩阵 H（3×7）：

text

H = [1 1 0 1 | 1 0 0] [0 1 1 1 | 0 1 0] [1 0 1 1 | 0 0 1]

1.3 编码过程

对于信息向量 u = (u₀,u₁,u₂,u₃)，码字 c = u·G = (u₀,u₁,u₂,u₃, p₀,p₁,p₂)

校验位计算：

2.4 查表纠错

s=[1,0,1]对应第6位错误，纠正第6位：0→1
纠错后 r' = [1, 0, 0, 1, 0, 1, 1] ← 注意这里我们故意演示查表

但实际正确的映射需要固定，为演示我们使用标准映射：我们查表发现 [1,0,1] 对应第6位，但第6位原本是校验位，翻转后恢复为正确码字 [1,0,1,1,0,1,0]

2.2 引入单比特错误（第2位翻转）

接收 r = [1, 0, 0, 1, 0, 1, 0]（原第2位由1变0）

2.3 计算校验子

s = H·rᵀ = [1, 0, 1]ᵀ (二进制)

p₀ = u₀ ⊕ u₁ ⊕ u₃
p₁ = u₀ ⊕ u₂ ⊕ u₃
p₂ = u₁ ⊕ u₂ ⊕ u
1.4 译码与纠错
接收向量 r = c ⊕ e（e为错误模式）
计算校验子：s = H·rᵀ (mod 2)
校验子与错误位置的对应关系（由H矩阵列向量决定）：
000 → 无错误
100 → 第0位错 (列0)
010 → 第1位错 (列1)
001 → 第2位错 (列2)
110 → 第3位错 (列3)
011 → 第4位错 (列4)
111 → 第5位错 (列5)
101 → 第6位错 (列6)
二、手工推演完整流程
取信息 u = [1, 0, 1, 1]
2.1 编码
p₀ = 1⊕0⊕1 = 0
p₁ = 1⊕1⊕1 = 1
p₂ = 0⊕1⊕1 = 0
码字 c = [1, 0, 1, 1, 0, 1, 0]

三、Python仿真实现

import numpy as np import matplotlib.pyplot as plt from itertools import product class Hamming74: def __init__(self): # 生成矩阵 G self.G = np.array([ [1, 0, 0, 0, 1, 0, 1], [0, 1, 0, 0, 1, 1, 0], [0, 0, 1, 0, 0, 1, 1], [0, 0, 0, 1, 1, 1, 1] ], dtype=int) # 校验矩阵 H self.H = np.array([ [1, 1, 0, 1, 1, 0, 0], [0, 1, 1, 1, 0, 1, 0], [1, 0, 1, 1, 0, 0, 1] ], dtype=int) # 校验子到错误位置的映射表 (二进制s -> 错误索引) self.syndrome_map = {} for i in range(7): col = self.H[:, i] key = tuple(col) self.syndrome_map[key] = i # 添加无错误情况 self.syndrome_map[(0,0,0)] = -1 def encode(self, u): """编码: 4位信息 -> 7位码字""" u = np.array(u, dtype=int) if len(u) != 4: raise ValueError("输入必须是4位信息") # 模2矩阵乘法 c = np.mod(np.dot(u, self.G), 2) return c def decode(self, r): """译码: 7位接收向量 -> 纠正后的4位信息""" r = np.array(r, dtype=int) if len(r) != 7: raise ValueError("输入必须是7位码字") # 计算校验子 s = np.mod(np.dot(self.H, r), 2) s_tuple = tuple(s) # 查表纠错 if s_tuple in self.syndrome_map: error_pos = self.syndrome_map[s_tuple] if error_pos != -1: # 翻转错误位 r[error_pos] ^= 1 corrected = True else: corrected = False else: # 双比特错误无法纠正，返回原样并标记 corrected = False # 提取信息位 (前4位) u_hat = r[:4] return u_hat, corrected, s def simulate_bsc(self, p_error, num_trials=10000): """BSC信道仿真""" errors = 0 undetected = 0 corrected_count = 0 for _ in range(num_trials): # 随机生成4位信息 u = np.random.randint(0, 2, 4) c = self.encode(u) # BSC信道传输 r = c.copy() # 每个比特以p_error概率翻转 flip_mask = np.random.random(7) < p_error r[flip_mask] ^= 1 # 译码 u_hat, corrected, s = self.decode(r) if np.any(u != u_hat): errors += 1 # 如果校验子全0但数据错了，说明发生了不可纠正的双比特错误 if np.all(s == 0): undetected += 1 if corrected: corrected_count += 1 ber = errors / (num_trials * 4) # 误比特率 correction_rate = corrected_count / num_trials undetected_rate = undetected / num_trials return ber, correction_rate, undetected_rate def test_hand_example(): """手工推演验证""" hamming = Hamming74() print("="*50) print("手工推演验证 (7,4)汉明码") print("="*50) # 信息 u = [1,0,1,1] u = np.array([1, 0, 1, 1]) print(f"信息位 u = {u}") # 编码 c = hamming.encode(u) print(f"编码码字 c = {c}") # 校验位计算验证 p0 = u[0] ^ u[1] ^ u[3] # 1⊕0⊕1 = 0 p1 = u[0] ^ u[2] ^ u[3] # 1⊕1⊕1 = 1 p2 = u[1] ^ u[2] ^ u[3] # 0⊕1⊕1 = 0 print(f"校验位 (p0,p1,p2) = ({p0},{p1},{p2}) ✓") # 引入单比特错误 (第2位翻转) r = c.copy() r[2] ^= 1 print(f"\n引入错误 (第2位翻转): r = {r}") # 译码 u_hat, corrected, s = hamming.decode(r) print(f"校验子 s = {s}") print(f"检测到错误? {corrected}") print(f"译码结果 u_hat = {u_hat}") print(f"原信息 u = {u}") print(f"译码正确? {np.all(u == u_hat)} ✓") return u, c, r, u_hat def test_random_data(): """随机多组数据验证""" hamming = Hamming74() num_tests = 100 print("\n" + "="*50) print(f"随机测试 {num_tests} 组数据 (无错误)") print("="*50) all_correct = True for i in range(num_tests): u = np.random.randint(0, 2, 4) c = hamming.encode(u) u_hat, _, _ = hamming.decode(c) if not np.all(u == u_hat): all_correct = False print(f"测试 {i}: 失败") break print(f"无错误情况下全部译码正确? {all_correct} ✓") def test_single_error_correction(): """单比特错误纠正测试""" hamming = Hamming74() print("\n" + "="*50) print("单比特错误纠正测试 (所有7个位置)") print("="*50) u = np.array([1, 0, 1, 1]) c = hamming.encode(u) for error_pos in range(7): r = c.copy() r[error_pos] ^= 1 u_hat, corrected, s = hamming.decode(r) s_tuple = tuple(s) detected_pos = hamming.syndrome_map.get(s_tuple, -1) print(f"错误位置 {error_pos}: 校验子 {s} -> 检测位置 {detected_pos}, " f"纠正成功? {np.all(u == u_hat)}") def plot_ber_curve(): """绘制BER曲线""" hamming = Hamming74() p_errors = np.logspace(-4, -0.5, 20) bers = [] correction_rates = [] undetected_rates = [] for p in p_errors: ber, corr_rate, undet_rate = hamming.simulate_bsc(p, num_trials=50000) bers.append(ber) correction_rates.append(corr_rate) undetected_rates.append(undet_rate) fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(14, 5)) # BER曲线 ax1.semilogx(p_errors, bers, 'b-', linewidth=2, label='(7,4)汉明码 BER') ax1.semilogx(p_errors, p_errors, 'r--', linewidth=1.5, label='无编码 BER (理论)') ax1.set_xlabel('信道交叉概率 p') ax1.set_ylabel('误比特率 (BER)') ax1.set_title('(7,4)汉明码 BSC信道 BER 曲线') ax1.grid(True, alpha=0.3) ax1.legend() ax1.set_xlim([1e-4, 0.5]) ax1.set_ylim([1e-5, 0.5]) # 纠错率与未检出率 ax2.semilogx(p_errors, correction_rates, 'g-', linewidth=2, label='纠正率') ax2.semilogx(p_errors, undetected_rates, 'r-', linewidth=2, label='未检出错误率') ax2.set_xlabel('信道交叉概率 p') ax2.set_ylabel('概率') ax2.set_title('纠错与未检出错误率') ax2.grid(True, alpha=0.3) ax2.legend() ax2.set_xlim([1e-4, 0.5]) plt.tight_layout() plt.savefig('hamming74_performance.png', dpi=150) plt.show() return p_errors, bers def main(): """主函数""" print("\n" + "="*50) print("(7,4)汉明码 编码译码推演与验证系统") print("="*50) # 1. 手工推演验证 test_hand_example() # 2. 随机数据验证 test_random_data() # 3. 单比特错误纠正测试 test_single_error_correction() # 4. BER性能仿真 print("\n" + "="*50) print("BSC信道性能仿真 (正在运行...)") print("="*50) p_errors, bers = plot_ber_curve() # 性能分析 print("\n性能分析:") print(f"当 p=0.01 时, BER ≈ {bers[np.argmin(np.abs(p_errors - 0.01))]:.6f}") print(f"当 p=0.1 时, BER ≈ {bers[np.argmin(np.abs(p_errors - 0.1))]:.6f}") print("\n理论分析: (7,4)汉明码码率 R = 4/7 ≈ 0.571") print("在 p 较小时，汉明码能有效纠正单比特错误，BER 显著低于无编码情况") print("当 p 增大时，双比特错误概率上升，纠错能力下降，BER 趋近于无编码") print("\n" + "="*50) print("验证完成!") print("="*50) if __name__ == "__main__": main()