每日算法 — 使用java实现汉明距离：纠错码与海明编码

一、背景介绍

1.1 汉明距离是什么

汉明距离（Hamming Distance）是衡量两个等长字符串在对应位置上不同字符的个数。简单来说，就是将一个字符串变换成另一个字符串所需要替换的字符个数。

例如：
– “karolin” 和 “kathrin” 的汉明距离是 3（第3、4、6位不同）
– 1011101 和 1001001 的汉明距离是 2
– 2173896 和 2233796 的汉明距离是 3

汉明距离由美国数学家理查德·卫斯里·汉明（Richard Wesley Hamming）于1950年在论文《错误检测与错误纠正码》中提出，是信息论和编码理论中的基础概念。

1.2 海明编码是什么

海明编码（Hamming Code）是一种利用奇偶校验位来检测和纠正数据传输中单个比特错误的线性纠错码。它通过在数据位中插入校验位，使得接收方能够检测并纠正单个比特的翻转错误。

海明编码广泛应用于：
– 内存（DRAM）错误纠正
– 卫星通信
– 数据存储系统
– 条形码扫描

二、核心算法原理

2.1 汉明距离计算

对于两个等长的二进制串，汉明距离的计算非常直观：
1. 逐位比较两个二进制串
2. 统计对应位置上值不同的位数
3. 不同的位数就是汉明距离

数学表示：d(x, y) = Σ(xi XOR yi)

2.2 海明编码原理

海明编码的核心思想是在数据位之间插入多个校验位，每个校验位负责检测特定位置的数据位：

校验位位置规则：校验位放在 2 的幂次位置上（第1、2、4、8、16…位）

校验位计算：
– 第1个校验位（位置1）：负责所有位置编号二进制末位为1的位（1, 3, 5, 7, 9, 11…）
– 第2个校验位（位置2）：负责所有位置编号二进制第二位为1的位（2, 3, 6, 7, 10, 11…）
– 第3个校验位（位置4）：负责所有位置编号二进制第三位为1的位（4-7, 12-15…）
– 以此类推

错误检测：接收方重新计算所有校验位，如果结果与接收到的校验位不同，将错误校验位的位置编号相加，得到的就是错误位的位置。

三、完整Java实现

/**
 * 汉明距离与海明编码实现
 * 包含汉明距离计算、海明编码、错误检测与纠正
 */
public class HammingCode {

    // ==========================================
    // 第一部分：汉明距离计算
    // ==========================================

    /**
     * 计算两个二进制字符串的汉明距离
     * @param s1 二进制字符串1
     * @param s2 二进制字符串2
     * @return 汉明距离
     */
    public static int hammingDistance(String s1, String s2) {
        if (s1.length() != s2.length()) {
            throw new IllegalArgumentException("两个字符串长度必须相等");
        }
        int distance = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                distance++;
            }
        }
        return distance;
    }

    /**
     * 计算两个整数的汉明距离（按二进制位比较）
     * @param x 整数x
     * @param y 整数y
     * @return 汉明距离
     */
    public static int hammingDistance(int x, int y) {
        // 异或操作：相同位为0，不同位为1
        int xor = x ^ y;
        int distance = 0;
        // 统计异或结果中1的个数
        while (xor != 0) {
            distance += xor & 1; // 取最低位
            xor = xor >>> 1;     // 无符号右移
        }
        return distance;
    }

    /**
     * 使用Brian Kernighan算法优化的汉明距离计算
     * 时间复杂度：O(k)，k为不同位的数量
     */
    public static int hammingDistanceOptimized(int x, int y) {
        int xor = x ^ y;
        int distance = 0;
        while (xor != 0) {
            xor &= (xor - 1); // 清除最低位的1
            distance++;
        }
        return distance;
    }

    // ==========================================
    // 第二部分：海明编码实现
    // ==========================================

    /**
     * 计算需要的校验位数量
     * 公式：2^r >= m + r + 1，其中m是数据位数，r是校验位数
     * @param dataLength 数据位长度
     * @return 校验位数量
     */
    public static int calculateParityBits(int dataLength) {
        int r = 0;
        while (Math.pow(2, r) < dataLength + r + 1) {
            r++;
        }
        return r;
    }

    /**
     * 对数据进行海明编码
     * @param data 原始数据二进制字符串（如 "1011"）
     * @return 编码后的二进制字符串（包含校验位）
     */
    public static String encode(String data) {
        int m = data.length();
        int r = calculateParityBits(m);
        int totalLength = m + r;

        // 创建编码数组，索引从1开始（方便计算）
        int[] code = new int[totalLength + 1];

        // 第一步：将数据位放入非2的幂次位置
        int dataIndex = 0;
        for (int i = 1; i <= totalLength; i++) {
            if (isPowerOfTwo(i)) {
                // 校验位位置，先留空
                code[i] = 0;
            } else {
                // 数据位位置
                code[i] = data.charAt(dataIndex) - '0';
                dataIndex++;
            }
        }

        // 第二步：计算每个校验位的值（偶校验）
        for (int i = 0; i < r; i++) {
            int parityPos = (int) Math.pow(2, i); // 校验位位置
            int parity = 0;

            // 遍历所有该校验位负责的位置
            for (int j = parityPos; j <= totalLength; j++) {
                // 检查j的二进制第i位是否为1
                if (((j >> i) & 1) == 1) {
                    parity ^= code[j]; // 异或（偶校验）
                }
            }
            code[parityPos] = parity;
        }

        // 转换为字符串输出
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= totalLength; i++) {
            sb.append(code[i]);
        }
        return sb.toString();
    }

    /**
     * 检测并纠正海明编码中的错误
     * @param received 接收到的编码字符串
     * @return 纠错后的结果对象（包含是否出错、错误位置、纠正后数据）
     */
    public static HammingResult decode(String received) {
        int totalLength = received.length();
        int[] code = new int[totalLength + 1];

        for (int i = 1; i <= totalLength; i++) {
            code[i] = received.charAt(i - 1) - '0';
        }

        // 计算校验位，找出错误位置
        int errorPos = 0;
        int r = 0;
        while (Math.pow(2, r) <= totalLength) {
            r++;
        }

        for (int i = 0; i < r; i++) {
            int parityPos = (int) Math.pow(2, i);
            int parity = 0;

            for (int j = parityPos; j <= totalLength; j++) {
                if (((j >> i) & 1) == 1) {
                    parity ^= code[j];
                }
            }

            // 如果校验结果不为0，说明该组有错误
            if (parity != 0) {
                errorPos += parityPos;
            }
        }

        HammingResult result = new HammingResult();
        result.originalCode = received;
        result.hasError = (errorPos != 0);
        result.errorPosition = errorPos;

        // 如果有错误，纠正该位
        if (result.hasError && errorPos <= totalLength) {
            code[errorPos] = 1 - code[errorPos]; // 翻转该位
            result.corrected = true;
        }

        // 提取数据位（去掉校验位）
        StringBuilder dataSb = new StringBuilder();
        for (int i = 1; i <= totalLength; i++) {
            if (!isPowerOfTwo(i)) {
                dataSb.append(code[i]);
            }
        }
        result.data = dataSb.toString();

        // 重建纠正后的完整编码
        StringBuilder codeSb = new StringBuilder();
        for (int i = 1; i <= totalLength; i++) {
            codeSb.append(code[i]);
        }
        result.correctedCode = codeSb.toString();

        return result;
    }

    /**
     * 判断一个数是否是2的幂
     */
    private static boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }

    // ==========================================
    // 结果类
    // ==========================================

    /**
     * 海明解码结果类
     */
    static class HammingResult {
        String originalCode;   // 原始接收到的编码
        String correctedCode;  // 纠正后的编码
        String data;           // 提取的数据
        boolean hasError;      // 是否检测到错误
        boolean corrected;     // 是否已纠正
        int errorPosition;     // 错误位置（0表示无错误）

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("=== 海明解码结果 ===\n");
            sb.append("原始编码: ").append(originalCode).append("\n");
            if (hasError) {
                sb.append("检测到错误！错误位置: 第").append(errorPosition).append("位\n");
                sb.append("纠正后编码: ").append(correctedCode).append("\n");
            } else {
                sb.append("未检测到错误\n");
            }
            sb.append("提取数据: ").append(data);
            return sb.toString();
        }
    }

    // ==========================================
    // 第三部分：应用示例
    // ==========================================

    /**
     * 模拟数据传输：发送 -> 引入错误 -> 接收并纠正
     */
    public static void simulateTransmission(String data, int errorPos) {
        System.out.println("========================================");
        System.out.println("模拟数据传输");
        System.out.println("========================================");
        System.out.println("原始数据: " + data);

        // 编码
        String encoded = encode(data);
        System.out.println("海明编码: " + encoded);
        System.out.println("编码长度: " + encoded.length() + " 位 (数据位: " + data.length() + ", 校验位: " + calculateParityBits(data.length()) + ")");

        // 引入错误（翻转指定位置的位）
        char[] chars = encoded.toCharArray();
        if (errorPos >= 0 && errorPos < chars.length) {
            chars[errorPos] = (chars[errorPos] == '0') ? '1' : '0';
            System.out.println("引入错误: 第 " + (errorPos + 1) + " 位翻转");
        }
        String received = new String(chars);
        System.out.println("接收到的: " + received);

        // 解码并纠错
        HammingResult result = decode(received);
        System.out.println(result);
        System.out.println();
    }

    // ==========================================
    // 主方法：演示
    // ==========================================

    public static void main(String[] args) {
        System.out.println("╔══════════════════════════════════════╗");
        System.out.println("║      汉明距离与海明编码演示          ║");
        System.out.println("╚══════════════════════════════════════╝\n");

        // --- 第一部分：汉明距离演示 ---
        System.out.println("【一、汉明距离计算】");
        System.out.println("----------------------------");

        String s1 = "101101";
        String s2 = "110111";
        System.out.println("字符串1: " + s1);
        System.out.println("字符串2: " + s2);
        System.out.println("汉明距离: " + hammingDistance(s1, s2));
        System.out.println();

        int x = 25;  // 11001
        int y = 18;  // 10010
        System.out.println("整数 x = " + x + " (二进制: " + Integer.toBinaryString(x) + ")");
        System.out.println("整数 y = " + y + " (二进制: " + Integer.toBinaryString(y) + ")");
        System.out.println("汉明距离: " + hammingDistance(x, y));
        System.out.println("优化算法: " + hammingDistanceOptimized(x, y));
        System.out.println();

        // --- 第二部分：海明编码演示 ---
        System.out.println("【二、海明编码与纠错】");
        System.out.println("----------------------------");

        // 测试1：无错误传输
        simulateTransmission("1011", -1);

        // 测试2：第3位出错
        simulateTransmission("1011", 2);

        // 测试3：第5位出错
        simulateTransmission("1011001", 4);

        // 测试4：更长的数据
        simulateTransmission("11010110", 7);

        // --- 第三部分：汉明距离应用 ---
        System.out.println("【三、汉明距离应用：最近邻搜索】");
        System.out.println("----------------------------");

        String[] codes = {"0000", "0011", "0101", "0110", "1001", "1010", "1100", "1111"};
        String query = "0001";
        System.out.println("查询码: " + query);
        System.out.println("在编码库中查找最近邻:");

        int minDist = Integer.MAX_VALUE;
        String nearest = "";
        for (String code : codes) {
            int dist = hammingDistance(query, code);
            System.out.println("  " + code + " - 距离: " + dist);
            if (dist < minDist) {
                minDist = dist;
                nearest = code;
            }
        }
        System.out.println("最近邻: " + nearest + " (距离 = " + minDist + ")");
    }
}

四、复杂度分析

4.1 汉明距离计算

4.2 海明编码

4.3 海明编码的纠错能力

• 检测能力：可以检测最多2个比特错误
• 纠正能力：可以纠正1个比特错误
• 编码效率：数据位越多，校验位占比越低，效率越高

五、应用拓展

5.1 扩展海明码（SECDED）

标准海明码只能纠正单个错误，扩展海明码（Single Error Correction, Double Error Detection）增加一个全局奇偶校验位，可以：
– 纠正单个比特错误
– 检测双比特错误（但无法纠正）

5.2 实际应用场景

1. 内存ECC：服务器内存使用ECC（Error-Correcting Code）技术，基于海明码原理防止内存位翻转
2. QR码：二维码使用Reed-Solomon编码（海明码的推广）实现容错
3. DNA测序：使用汉明距离衡量基因序列差异
4. 图像相似度：感知哈希算法（pHash）使用汉明距离比较图像相似度

5.3 相关编码对比