算法之Hamming码

紫风

发布于 2025-10-14 15:09:33

900

代码可运行

运行总次数：0

代码可运行

一、Hamming码的本质与核心思想

Hamming码是一种经典的纠错编码技术，由Richard Hamming于20世纪中期提出，旨在通过添加冗余位检测并纠正数据传输中的单比特错误。其核心思想是通过数学奇偶校验和位位置编码实现错误定位与修复24。

1. 编码规则 4

冗余位位置：校验位位于2的幂次方位置（如1、2、4、8等）。
奇偶校验：每个校验位负责覆盖特定数据位的奇偶性（偶校验或奇校验）。
错误定位：通过校验位的组合结果（称为校验子）唯一确定错误位置。

例如，对于4位数据1011，需插入3个冗余位（位置1、2、4），最终形成7位编码1011010，其中每个校验位覆盖不同组合的数据位。

二、Java实现示例

1. 编码实现

public class HammingCode {
    // 生成Hamming码
    public static int[] encode(int[] data) {
        int m = data.length;
        int r = 0;
        while ((1 << r) < m + r + 1) r++; // 计算冗余位数
        
        int[] code = new int[m + r];
        int j = 0;
        // 填充数据位
        for (int i = 0; i < code.length; i++) {
            if (!isPowerOfTwo(i + 1)) { // 非校验位填充数据
                code[i] = data[j++];
            }
        }
        // 计算校验位
        for (int i = 0; i < r; i++) {
            int pos = (1 << i) - 1; // 校验位位置
            for (int k = pos; k < code.length; k += (pos + 1) * 2) {
                for (int l = k; l < Math.min(k + pos + 1, code.length); l++) {
                    code[pos] ^= code[l]; // 异或计算奇偶性
                }
            }
        }
        return code;
    }

    private static boolean isPowerOfTwo(int x) {
        return (x & (x - 1)) == 0;
    }
}

2. 解码与纠错

public static int[] decode(int[] received) {
    int r = 0;
    while ((1 << r) < received.length) r++;
    int errorPos = 0;
    
    // 计算校验子
    for (int i = 0; i < r; i++) {
        int parity = 0;
        int pos = (1 << i) - 1;
        for (int j = pos; j < received.length; j += (pos + 1) * 2) {
            for (int k = j; k < Math.min(j + pos + 1, received.length); k++) {
                parity ^= received[k];
            }
        }
        if (parity != 0) errorPos += pos + 1; // 定位错误位
    }
    
    if (errorPos != 0) received[errorPos - 1] ^= 1; // 纠正错误
    return extractData(received);
}

三、性能分析

指标	数值	说明
时间复杂度	O(n log n)	冗余位计算需遍历数据位和校验位 8
空间复杂度	O(n + log n)	存储原始数据及冗余位 4
纠错能力	单比特错误检测与纠正	无法处理多比特错误 10