hamming_code.py

import math

def _int_to_bits(n, num_bits):
    """Converts an integer to a list of bits (MSB first)."""
    return [(n >> i) & 1 for i in range(num_bits - 1, -1, -1)]

def _bits_to_int(bits):
    """Converts a list of bits (MSB first) to an integer."""
    return sum(bit << (len(bits) - 1 - i) for i, bit in enumerate(bits))

def encode_hamming_7_4_single(data_bits: list[int]) -> list[int]:
    """
    Encodes a 4-bit data block into a 7-bit Hamming(7,4) codeword.
    data_bits: A list of 4 bits [d1, d2, d3, d4].
    Returns: A list of 7 bits [p1, p2, d1, p3, d2, d3, d4].
    """
    if len(data_bits) != 4:
        raise ValueError("Hamming(7,4) encode_single requires 4 data bits.")

    d1, d2, d3, d4 = data_bits

    p1 = (d1 + d2 + d4) % 2
    p2 = (d1 + d3 + d4) % 2
    p3 = (d2 + d3 + d4) % 2

    return [p1, p2, d1, p3, d2, d3, d4]

def decode_hamming_7_4_single(encoded_bits: list[int]) -> tuple[list[int], bool, bool]:
    """
    Decodes a 7-bit Hamming(7,4) codeword and attempts to correct a single error.
    encoded_bits: A list of 7 bits [p1, p2, d1, p3, d2, d3, d4].
    Returns: Tuple of (data_bits: list[4 bits], error_detected: bool, error_corrected: bool).
             If uncorrectable (e.g. >1 error), error_detected will be true, error_corrected false.
    """
    if len(encoded_bits) != 7:
        raise ValueError("Hamming(7,4) decode_single requires 7 encoded bits.")

    p1, p2, d1, p3, d2, d3, d4 = encoded_bits

    s1 = (p1 + d1 + d2 + d4) % 2
    s2 = (p2 + d1 + d3 + d4) % 2
    s3 = (p3 + d2 + d3 + d4) % 2

    syndrome = s3 * 4 + s2 * 2 + s1 * 1  

    error_detected = syndrome != 0
    error_corrected = False

    corrected_bits = list(encoded_bits)

    if error_detected:
        if 0 < syndrome <= 7:
            corrected_bits[syndrome - 1] = 1 - corrected_bits[syndrome - 1] 
            
            np1, np2, nd1, np3, nd2, nd3, nd4 = corrected_bits
            ns1 = (np1 + nd1 + nd2 + nd4) % 2
            ns2 = (np2 + nd1 + nd3 + nd4) % 2
            ns3 = (np3 + nd2 + nd3 + nd4) % 2
            if (ns3 * 4 + ns2 * 2 + ns1 * 1) == 0:
                error_corrected = True
            else: 
                error_corrected = False 
        else:
            error_corrected = False 

    final_d1 = corrected_bits[2]
    final_d2 = corrected_bits[4]
    final_d3 = corrected_bits[5]
    final_d4 = corrected_bits[6]
    
    return [final_d1, final_d2, final_d3, final_d4], error_detected, error_corrected


def encode_bytes_with_hamming(data_bytes: bytes) -> list[int]:
    """
    Encodes a stream of bytes using Hamming(7,4).
    Each byte (8 bits) is split into two 4-bit chunks.
    Pads the last byte with zero bits if necessary to form 4-bit chunks.
    """
    all_encoded_bits = []
    data_bits_buffer = []

    for byte_val in data_bytes:
        data_bits_buffer.extend(_int_to_bits(byte_val, 8))
        
        while len(data_bits_buffer) >= 4:
            chunk_to_encode = data_bits_buffer[:4]
            data_bits_buffer = data_bits_buffer[4:]
            all_encoded_bits.extend(encode_hamming_7_4_single(chunk_to_encode))
            
    if data_bits_buffer: 
        pass 

    return all_encoded_bits

def decode_bits_with_hamming(encoded_bits: list[int], num_original_data_bytes: int) -> tuple[bytes, bool]:
    """
    Decodes a stream of Hamming(7,4) encoded bits back into bytes.
    encoded_bits: list of bits, length must be a multiple of 7.
    num_original_data_bytes: The exact number of original data bytes expected.
    Returns: (decoded_bytes, any_uncorrectable_error_occurred: bool)
    """
    if len(encoded_bits) % 7 != 0:
        raise ValueError("Length of encoded_bits for Hamming(7,4) decoding must be a multiple of 7.")

    decoded_data_bits = []
    any_uncorrectable_error = False
    
    num_encoded_chunks = len(encoded_bits) // 7

    for i in range(num_encoded_chunks):
        chunk_to_decode = encoded_bits[i*7 : (i+1)*7]
        data_segment, detected, corrected = decode_hamming_7_4_single(chunk_to_decode)
        
        if detected and not corrected:
            any_uncorrectable_error = True
            
        decoded_data_bits.extend(data_segment)

    num_expected_data_bits = num_original_data_bytes * 8
    
    actual_decoded_data_bits = decoded_data_bits[:num_expected_data_bits]

    output_bytes = bytearray()
    for i in range(0, len(actual_decoded_data_bits), 8):
        byte_bits = actual_decoded_data_bits[i : i+8]
        if len(byte_bits) < 8: 
            pass
        if len(byte_bits) == 8 : 
             output_bytes.append(_bits_to_int(byte_bits))
        elif byte_bits : 
            pass


    return bytes(output_bytes), any_uncorrectable_error