Python functions for Hamming encoding and decoding, as used in CSSE3010 Prac 4 and Project 1. Manchester encoding is also included as a reference.

hamming.py

# List of syndrome positions. SYNDROME_CHECK[pos] will give the
# bit in the provided encoded byte that needs to be fixed
# Note: bit order used is 7 6 5 4 3 2 1 0
SYNDROME_CHECK = [-1, 6, 5, 0, 4, 1, 2, 3]


def extract_bit(byte, pos):
    return (byte >> pos) & 0x01


def hamming_encode_nibble(data):
    """
    Encode a nibble using Hamming encoding.
    Nibble is provided in form 0b0000DDDD == 0 0 0 0 D3 D2 D1 D0
    Encoded byte is in form P H2 H1 H0 D3 D2 D1 D0
    """
    d = [0, 0, 0, 0]
    d[0] = extract_bit(data, 0)
    d[1] = extract_bit(data, 1)
    d[2] = extract_bit(data, 2)
    d[3] = extract_bit(data, 3)

    # Calculate hamming bits
    h = [0, 0, 0]
    h[0] = (d[1] + d[2] + d[3]) % 2
    h[1] = (d[0] + d[2] + d[3]) % 2
    h[2] = (d[0] + d[1] + d[3]) % 2

    # Calculate parity bit, using even parity
    p = d[0] ^ d[1] ^ d[2] ^ d[3] ^ h[0] ^ h[1] ^ h[2]

    # Encode byte
    encoded = (data & 0x0f)
    encoded |= (p << 7) | (h[2] << 6) | (h[1] << 5) | (h[0] << 4)

    return encoded


def hamming_decode_byte(byte):
    """
    Decode a single hamming encoded byte, and return a decoded nibble.
    Input is in form P H2 H1 H0 D3 D2 D1 D0
    Decoded nibble is in form 0b0000DDDD == 0 0 0 0 D3 D2 D1 D0
    """
    error = 0
    corrected = 0

    # Calculate syndrome
    s = [0, 0, 0]

    # D1 + D2 + D3 + H0
    s[0] = (extract_bit(byte, 1) + extract_bit(byte, 2) +
            extract_bit(byte, 3) + extract_bit(byte, 4)) % 2

    # D0 + D2 + D3 + H1
    s[1] = (extract_bit(byte, 0) + extract_bit(byte, 2) +
            extract_bit(byte, 3) + extract_bit(byte, 5)) % 2

    # D0 + D1 + D3 + H2
    s[2] = (extract_bit(byte, 0) + extract_bit(byte, 1) +
            extract_bit(byte, 3) + extract_bit(byte, 6)) % 2

    syndrome = (s[0] << 2) | (s[1] << 1) | s[2]

    if syndrome:
        # Syndrome is not 0, so correct and log the error
        error += 1
        print 'bad syndrome', byte, syndrome, s
        byte ^= (1 << SYNDROME_CHECK[syndrome])
        print 'new byte', byte
        corrected += 1

    # Check parity
    p = 0
    for i in range(0, 7):
        p ^= extract_bit(byte, i)

    if p != extract_bit(byte, 7):
        print 'parity', p, extract_bit(byte, 0)
        # Parity bit is wrong, so log error
        error += 1
        if not syndrome:
            # Parity is wrong and syndrome is fine, so corrected parity bit
            corrected += 1
            print 'syn'

    return ((byte & 0x0f), error, corrected)


def manchester_encode(byte):
    """
    Encode a byte using Manchester encoding. Returns an array of bits.
    Adds two start bits (1, 1) and one stop bit (0) to the array.
    """
    # Add start bits (encoded 1, 1)
    manchester_encoded = [0, 1, 0, 1]

    # Encode byte
    for i in range(7, -1, -1):
        if extract_bit(byte, i):
            manchester_encoded.append(0)
            manchester_encoded.append(1)
        else:
            manchester_encoded.append(1)
            manchester_encoded.append(0)

    # Add stop bit (encoded 0)
    manchester_encoded.append(1)
    manchester_encoded.append(0)

    return manchester_encoded


def manchester_decode(manchester_array):
    """
    Decode a Manchester array to a single data byte.
    """
    decoded = 0
    for i in range(0, 8):
        bit = 7 - i
        # Use the second value of each encoded bit, as that is the bit value
        # eg. 1 is encoded to [0, 1], so retrieve the second bit (1)
        decoded |= manchester_array[4 + (i * 2) + 1] << (bit)

    return decoded