Hamming(7,4)

main.py

#!/usr/bin/env python3

"""
Hamming(7,4) is a linear error-correcting code that encodes four bits of data
into seven bits by adding three parity bits.

The minimal Hamming distance between any two correct codewords is 3, and
received words can be correctly decoded if they are at a distance of at most one
from the codeword that was transmitted by the sender.

G, the generator matrix, is a matrix whose rows form a basis for a linear code.
The codewords w are all of the linear combinations of the rows of this matrix.
G has format k × n where k is the number of information bits and n is the length
of a codeword. In the case of Hamming(7, 4), G has format 4 × 7.

In the table below, Gt is the rapresentation of the diagram:
https://upload.wikimedia.org/wikipedia/commons/b/b0/Hamming%287%2C4%29.svg
And is the transposed of G, having format 7 × 4:

    | Gt  | d1  | d2  | d3  | d4  |
    |:---:|:---:|:---:|:---:|:---:|
    | p1  |  1  |  1  |  0  |  1  |
    | p2  |  1  |  0  |  1  |  1  |
    | d1  |  1  |  0  |  0  |  0  |
    | p3  |  0  |  1  |  1  |  1  |
    | d2  |  0  |  1  |  0  |  0  |
    | d3  |  0  |  0  |  1  |  0  |
    | d4  |  0  |  0  |  0  |  1  |

Given an input vector s of format 1 × 4, the codeword is defined as:

    w = sG

w has format 1 × 7.
"""


import random


Gt = [
    # p1 covers d1, d2, d4
    [1, 1, 0, 1],
    # p2 covers d1, d3, d4
    [1, 0, 1, 1],
    # d1
    [1, 0, 0, 0],
    # p3 covers d2, d3, d4
    [0, 1, 1, 1],
    # d2
    [0, 1, 0, 0],
    # d3
    [0, 0, 1, 0],
    # d4
    [0, 0, 0, 1]]

# Transpose from Gt
G = list(zip(*Gt))

def matrix_prod(A, B):
    """
    Return the product of two matrices.
    See also: https://stackoverflow.com/questions/10508021/matrix-multiplication-in-python
    """
    A_rows = len(A)
    A_cols = len(A[0])
    B_rows = len(B)
    B_cols = len(B[0])

    # Check compatibility
    if A_cols != B_rows:
        raise ValueError('Matrices not compatible for mutiplication')
    
    # Create result matrix, initially zero filled
    C = [[0] * B_cols] * A_rows
    
    # C[i][j] is the sum of A[i][cols] * B[rows][j]
    # C has A_rows rows and B_cols columns
    for i in range(A_rows):
        for j in range(B_cols):
            for x in range(A_cols): # Same as B_rows
                C[i][j] += A[i][x] * B[x][j]

    return C


def info(*args):
    """Helper method to format logs"""
    print('{:43s}: {}'.format(*args))


def main():

    # Random input data, 4 bits
    data = random.getrandbits(4)
    info('Generate 4 bits random integer', data)

    # Convert to binary
    # e.g. 10 -> '0b1010'
    bin_data = bin(data)
    # Remove leading '0b'
    bin_data = bin_data[2:]
    # Don't forget to zero pad
    bin_data = bin_data.zfill(4)
    info('Integer as binary', bin_data)

    # Convert to array of length 4
    s = [int(x) for x in bin_data]

    # Convert to matrix of format 1 × 4
    s = [ s ]
    info('Integer as matrix of format 1 × 4', s)

    # Calculate codeword (has format 1 × 7)
    w = matrix_prod(s, G)

    # Extract first (and only) row from matrix
    w = w[0]

    # Calculate modulo 2 of each element
    w = [i % 2 for i in w]
    info('Codeword', w)


if __name__ == '__main__':
    main()