第08课：汉明码

🔢 汉明码：最简单的纠错码

汉明码由Richard Hamming于1950年发明，是最早的纠错码之一。它能纠正1位错误、检测2位错误，编码效率较高，至今仍广泛应用于内存ECC、串口通信、卫星通信等场景。理解汉明码是掌握所有纠错编码的起点。

汉明码的发明源于一个真实的故事：Hamming在Bell实验室使用早期计算机时，机器用奇偶校验只能检错不能纠错，一旦出错程序就要重新运行。他思考：能否让计算机自动纠正错误？这个简单的需求催生了整个纠错编码领域。

📐 校验矩阵与伴随式解码

汉明码的核心是校验矩阵H。H矩阵的每列是1到n的二进制表示，这种特殊的结构确保每个非零伴随式对应唯一的错误位置。

完备码与扩展汉明码

汉明码是一种完备码(Perfect Code)。完备码的定义是：所有2^(n-k)-1个非零伴随式恰好对应n个可能的错误位置，没有浪费。对于汉明码H(7,4)，有2^3-1=7个非零伴随式，恰好对应7个位置。

在标准汉明码基础上增加一个整体校验位，得到扩展汉明码H(8,4)。增加的这一位使我们能够区分单比特错误和双比特错误：伴随式非零且整体校验失败→单错（可纠）；伴随式非零但整体校验通过→双错（检测到但不可纠）。

🔧 Verilog实现：汉明(7,4)编解码器

// hamming_7_4.v - 汉明(7,4)编解码器
// 第08课：汉明码
module hamming_encoder_7_4 (
    input  wire [3:0] data_in,
    output wire [6:0] code_out
);
    wire p1 = data_in[0] ^ data_in[1] ^ data_in[3];
    wire p2 = data_in[0] ^ data_in[2] ^ data_in[3];
    wire p3 = data_in[1] ^ data_in[2] ^ data_in[3];
    assign code_out = {p1,p2,data_in[0],p3,data_in[1],data_in[2],data_in[3]};
endmodule

module hamming_decoder_7_4 (
    input  wire [6:0] code_in,
    output reg  [3:0] data_out,
    output reg  error_detect, error_correct,
    output reg  [2:0] syndrome
);
    wire s1 = code_in[0] ^ code_in[2] ^ code_in[4] ^ code_in[6];
    wire s2 = code_in[1] ^ code_in[2] ^ code_in[5] ^ code_in[6];
    wire s3 = code_in[3] ^ code_in[4] ^ code_in[5] ^ code_in[6];
    assign syndrome = {s3,s2,s1};
    reg [6:0] corrected;
    always @(*) begin
        corrected = code_in;
        error_detect = (syndrome != 3'b000);
        error_correct = 1'b0;
        if (syndrome != 3'b000) begin
            case (syndrome)
                3'b001: corrected[0]=~code_in[0]; 3'b010: corrected[1]=~code_in[1];
                3'b011: corrected[2]=~code_in[2]; 3'b100: corrected[3]=~code_in[3];
                3'b101: corrected[4]=~code_in[4]; 3'b110: corrected[5]=~code_in[5];
                3'b111: corrected[6]=~code_in[6]; default:;
            endcase
            error_correct = 1'b1;
        end
        data_out = {corrected[6],corrected[5],corrected[4],corrected[2]};
    end
endmodule

// 扩展汉明(8,4)
module hamming_ext_enc_8_4 (
    input  wire [3:0] data_in,
    output wire [7:0] code_out
);
    wire [6:0] hc;
    hamming_encoder_7_4 u_enc (.data_in(data_in),.code_out(hc));
    assign code_out = {^(hc),hc};
endmodule

module hamming_ext_dec_8_4 (
    input  wire [7:0] code_in,
    output reg  [3:0] data_out,
    output reg  no_error, single_error, double_error
);
    wire [6:0] hi=code_in[6:0]; wire [2:0] syn; wire ed,ec;
    hamming_decoder_7_4 u_dec (.code_in(hi),.data_out(data_out),
        .error_detect(ed),.error_correct(ec),.syndrome(syn));
    wire oc = code_in[7] ^ (^hi);
    always @(*) begin
        no_error=!ed && !oc; single_error=ed && oc; double_error=ed && !oc;
    end
endmodule

🐍 Python仿真：编码增益

#!/usr/bin/env python3
"""hamming_sim.py - 汉明码编码增益仿真"""
import numpy as np
import matplotlib.pyplot as plt

class HammingCode:
    def __init__(self, m=3):
        self.m=m; self.n=2**m-1; self.k=2**m-m-1
        self.H=np.zeros((m,self.n),dtype=int)
        for j in range(self.n):
            for i in range(m): self.H[i,j]=(j+1>>i)&1
        self.G=np.zeros((self.k,self.n),dtype=int)
        for i in range(self.k):
            self.G[i,i]=1
            for j in range(m): self.G[i,self.k+j]=self.H[j,i]
    def encode(self,data): return np.mod(data@self.G,2)
    def decode(self,rx):
        s=np.mod(self.H@rx,2)
        if np.all(s==0): return rx[:self.k],False
        pos=sum(s[i]*2**i for i in range(self.m))
        if 0<pos<=self.n:
            rx=rx.copy(); rx[pos-1]=1-rx[pos-1]; return rx[:self.k],True
        return rx[:self.k],False

def simulate():
    np.random.seed(42); hc=HammingCode(3); num=20000; snr_range=np.arange(0,12)
    ber_u,ber_c=[],[]
    for snr_db in snr_range:
        bits=np.random.randint(0,2,num*hc.k); sym=1-2*bits
        ns=np.sqrt(1/(2*10**(snr_db/10)))*np.random.randn(len(sym))
        ber_u.append(max(np.sum(bits!=((sym+ns)<0).astype(int))/len(bits),1e-7))
        err=total=0
        for _ in range(num):
            d=np.random.randint(0,2,hc.k); c=hc.encode(d); s=1-2*c
            n=np.sqrt(1/(2*10**(snr_db/10)))*np.random.randn(hc.n)
            hard=((s+n)<0).astype(int); dd,_=hc.decode(hard)
            err+=np.sum(d!=dd); total+=hc.k
        ber_c.append(max(err/total,1e-7))
    plt.figure(figsize=(10,7))
    plt.semilogy(snr_range,ber_u,'c-o',markersize=4,label='BPSK')
    plt.semilogy(snr_range,ber_c,'#10b981-s',markersize=4,label='H(7,4)')
    plt.xlabel('Eb/N0(dB)'); plt.ylabel('BER')
    plt.title('汉明(7,4)码编码增益'); plt.legend()
    plt.grid(True,alpha=0.3,which='both'); plt.ylim(1e-6,1)
    plt.savefig('/var/www/ttl/digital-comm/hamming_gain.png',dpi=100,facecolor='#0f172a')
    print("Done!")

if __name__=='__main__':
    hc=HammingCode(3); d=np.array([1,0,1,1]); c=hc.encode(d)
    r=c.copy(); r[3]=1-r[3]; dd,corr=hc.decode(r)
    print(f"纠错:纠正={corr}"); simulate()

汉明距离与纠错能力

汉明距离是两个等长码字之间不同位的个数。对于一个码的最小汉明距离d_min：

对于汉明码d_min=3，因此可检2错、纠1错。要提高纠错能力，必须增大d_min，这就是BCH码和RS码的设计目标。

线性分组码的一般理论

汉明码是线性分组码的特例。线性分组码的几个重要性质：

• 封闭性：任意两个码字的和仍是码字
• 全零码字：全0向量一定是码字
• 最小距离=最小重量：d_min = min(w(c))，其中c≠0
• 系统码：码字中包含原始信息位，便于提取

这些性质使得编码和解码都可以用矩阵运算描述，硬件实现非常高效。

系统级仿真与性能评估

完整的通信系统仿真需要考虑多个因素：信道模型、编码增益、同步误差、实现损耗等。以下Python代码提供了完整的系统级仿真框架。

#!/usr/bin/env python3
# 第08课系统级仿真
import numpy as np
import matplotlib.pyplot as plt
from scipy.special import erfc

def ber_theory_bpsk(snr_db):
    return 0.5 * erfc(np.sqrt(10**(snr_db/10)))

def simulate_system(mod_type='bpsk', coding_gain_db=0, num_bits=50000):
    np.random.seed(42)
    snr_range = np.arange(0, 20)
    ber_sim = []
    for snr_db in snr_range:
        effective_snr = snr_db + coding_gain_db
        snr_lin = 10**(effective_snr/10)
        bits = np.random.randint(0, 2, num_bits)
        symbols = 1 - 2*bits
        noise_std = 1.0 / np.sqrt(2*snr_lin)
        noise = noise_std * np.random.randn(len(symbols))
        rx = symbols + noise
        dec = (rx < 0).astype(int)
        ber = np.sum(bits != dec) / num_bits
        ber_sim.append(max(ber, 1e-7))
    return snr_range, ber_sim

snr, ber_u = simulate_system('bpsk', 0)
_, ber_coded = simulate_system('bpsk', 2)

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(14, 6))
ax1.semilogy(snr, ber_u, 'c-o', markersize=3, label='未编码')
ax1.semilogy(snr, ber_coded, '#10b981-s', markersize=3, label='编码(+2dB)')
ax1.set_xlabel('Eb/N0 (dB)'); ax1.set_ylabel('BER')
ax1.set_title('第08课：BER仿真'); ax1.legend()
ax1.grid(True, alpha=0.3, which='both'); ax1.set_ylim(1e-7, 1)

snr_range2 = np.arange(0, 25)
throughput = [(1 - ber_theory_bpsk(s)) * 1e6 for s in snr_range2]
ax2.plot(snr_range2, np.array(throughput)/1e6, '#f59e0b', linewidth=2)
ax2.set_xlabel('SNR (dB)'); ax2.set_ylabel('吞吐率 (Mbps)')
ax2.set_title('吞吐率 vs SNR'); ax2.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('/var/www/ttl/digital-comm/lesson08_sys.png', dpi=100,
            facecolor='#0f172a', edgecolor='none')
print("系统级仿真图已保存")

编码增益的数学分析

编码增益定义为：在相同BER下，编码系统所需Eb/N0比未编码系统少的dB数。对于汉明码，编码增益可以近似计算：

对于H(7,4)：G_c ≈ 10·log₁₀(1×4/7) ≈ -2.4dB（低SNR时为负！）

但在高SNR区域，编码增益变正。BER=10⁻⁴时约2dB，BER=10⁻⁶时约3dB。这说明编码增益与工作BER有关——低SNR时编码反而有害（因为码率损失），高SNR时编码才有正增益。

汉明码的应用场景