扩展汉明码编码器实现故障求助：疑parity计算方法出错

问题描述 #

看完3Blue1Brown的汉明码相关视频后，我尝试实现一个扩展汉明码编码器，但部分输入无法得到预期输出。例如输入0x38c时，预期输出为0x71d4，实际得到0x70ce；但输入0x1、0x400时输出正确。已测试copy_bits等基础函数均正常，推测问题出在compute_parity方法中。

我的逻辑是：对置位的比特索引进行异或后，翻转对应parity位使异或结果为0，再设置全局奇偶位保证偶校验，但实际结果不符合预期。

原代码 #

import math

def get_bitstring(n, bit_length) -> str:
    return format(n, f'0{bit_length}b')

def get_bit(n: int, bit_index: int) -> int:
    return (n >> bit_index) & 1

def set_bit(n: int, bit_index: int, value: int) -> int:
    mask = 1 << bit_index
    n &= ~mask
    if value:
        n |= mask
    return n

def get_on_bits(bits, bit_length):
    # Global parity has index 0, so subtract the index from block_size - 1
    return [bit_length - i - 1 for i, bit in enumerate(bits) if bit]

class HammingCode:
    def __init__(self, bits_per_block: int) -> None:
        self.raw_message: int = 0
        self.encoded_message: int = 0
        self.bits_per_block: int = bits_per_block
        self.parity_bits_per_block: int = int(math.log2(self.bits_per_block)) + 1
        self.data_bits_per_block: int = self.bits_per_block - self.parity_bits_per_block

    def encode(self, message: bytes | bytearray) -> int:
        self.raw_message = int.from_bytes(message, 'big')
        self.copy_bits()
        self.compute_parity()
        return self.encoded_message

    def copy_bits(self) -> int:
        self.encoded_message = 0
        bits_used = 0
        # Copies bits into encoded message
        for i in range(self.bits_per_block):
            if not self.is_parity_bit(i):
                bit_value = get_bit(self.raw_message, bits_used)
                self.encoded_message = set_bit(self.encoded_message, i, bit_value)
                bits_used += 1
        assert(bits_used == self.data_bits_per_block)
        return self.encoded_message

    def compute_parity(self):
        from functools import reduce
        bits = [int(bit) for bit in self.get_bitstring()]
        parity = reduce(lambda x, y: x ^ y, get_on_bits(bits, self.bits_per_block))
        for i in range(1, self.parity_bits_per_block):
            parity_index = 1 << i
            if parity & parity_index != 0:
                bit_value = 0 if get_bit(self.encoded_message, parity_index) else 1
                self.encoded_message = set_bit(self.encoded_message, i + 1, bit_value)
        bits = [int(bit) for bit in self.get_bitstring()]
        parity = len(get_on_bits(bits, self.bits_per_block))
        self.encoded_message = set_bit(self.encoded_message, 0, 1 if parity & 1 == 1 else 0)
        return self.encoded_message

    def is_parity_bit(self, bit_index: int) -> int:
        assert(bit_index < self.bits_per_block)
        return (bit_index & (bit_index - 1)) == 0

    def get_bitstring(self) -> str:
        return get_bitstring(self.encoded_message, self.bits_per_block)

bytes = b'\x03\x8c'
input = int.from_bytes(bytes)
print(f"Running with {hex(input)} {get_bitstring(input, 16)}")
h = HammingCode(16)
n = h.encode(bytes)
print(f"Encoded message: {get_bitstring(int.from_bytes(bytes), h.data_bits_per_block)} => {get_bitstring(n, h.bits_per_block)}")
print(f"Encoded block in hex is {hex(n)}")

问题定位 #

• 奇偶位索引混淆：compute_parity循环中用i+1作为奇偶位设置索引，完全错误。16位扩展汉明码的汉明校验位索引应为1、2、4、8，全局奇偶位为0，你的逻辑没有对应正确的索引。
• 校验组计算错误：你试图用所有置位索引的异或结果直接翻转位，而没有针对每个奇偶位单独计算其负责的校验组的奇偶性。汉明码的每个校验位只负责二进制索引中对应位为1的所有位，需要单独计算每组的异或和。
• 全局奇偶位计算逻辑错误：你用置位的数量来判断奇偶，这在存在奇数个1时正确，但如果用异或会更直接，且之前的汉明校验位设置错误会导致这一步的输入本身就不对。

修复方案 #

修改compute_parity方法，针对每个汉明校验位单独计算校验组的奇偶，再设置全局奇偶位：

def compute_parity(self):
    # 处理汉明校验位（索引1、2、4、8），保证每组偶校验
    for parity_pos in [1, 2, 4, 8]:
        parity_sum = 0
        for bit_pos in range(self.bits_per_block):
            # 校验位负责所有二进制索引中包含当前校验位对应位的位置（含自身）
            if (bit_pos & parity_pos) != 0:
                parity_sum ^= get_bit(self.encoded_message, bit_pos)
        # 设置校验位，使组内异或和为0（偶校验）
        self.encoded_message = set_bit(self.encoded_message, parity_pos, parity_sum)
    
    # 处理全局奇偶位（索引0），保证整个块的偶校验
    total_parity = 0
    for bit_pos in range(self.bits_per_block):
        total_parity ^= get_bit(self.encoded_message, bit_pos)
    # 全局奇偶位设置为总异或结果，确保整体偶校验
    self.encoded_message = set_bit(self.encoded_message, 0, total_parity)
    return self.encoded_message

修复说明 #

1. 逐个校验组计算：针对每个汉明校验位（1、2、4、8），遍历所有位，计算该组内所有位的异或和，设置校验位值使组内异或和为0（偶校验）。
2. 全局奇偶位修正：计算整个块的所有位的异或和，设置索引0的位，确保整个16位块的总奇偶为偶数。
3. 索引逻辑修正：直接使用正确的校验位索引，避免之前的索引混淆问题。

测试输入0x38c时，修复后的编码器将输出预期的0x71d4。

内容的提问来源于stack exchange，提问作者Philippe Gorley