Hamming Code

from math import log2
from random import randrange

# Function 1 ---> 2^r >= m + r + 1
def find_r(m):
    r = 0
    while 2**r - r < m + 1:
        r = r + 1
    return r

# Function 2 - Decimal to binary
def dec_to_bin(decimal):
    # decimal = INTEGER
    if decimal == 0:
        return [0]
    else:
        digits = list()
        LEN = int(log2(decimal)) + 1
        for exp in range(LEN-1, -1, -1):
            value = 2 ** exp
            if decimal >= value:
                digits.append(1)
                decimal -= value
            else:
                digits.append(0)
        return digits


# Function 3 - Binary to decimal
def bin_to_dec(binary):
    # binary = LIST
    SUM = 0
    LEN = len(binary)
    for index in range(LEN):
        SUM += binary[index] * (2**(LEN-1-index))
    return SUM


# Function 4 - Padding with zeros
def pad_zeros(binary, LEN):
    LEN1 = int(log2(LEN)) + 1
    LEN2 = len(binary)
    binary2 = [0 for i in range(LEN1 - LEN2)]
    binary = binary2 + binary
    return binary


# Function 5 - Binary representation of indeces
def bin_representation(LEN):
    # If LEN = 11, I will create a list with all the binary representations of numbers
    # between 11 and 1 (inclusively)
    indeces_binary = list()
    for i in range(LEN, 0, -1):
        binary = dec_to_bin(i)
        indeces_binary.append(pad_zeros(binary, LEN))
    return indeces_binary



# Function 6 - Write the codeword without redundant bits
def write_codeword_no_redundant(data, m, r, LEN):
    # I will symbolize redundant with the number '-1'
    codeword_no_redundant = list()
    counter = 0
    for i in range(LEN, 0, -1):
        if log2(i) == int(log2(i)):
            codeword_no_redundant.append(-1)
        else:
            codeword_no_redundant.append(data[counter])
            counter += 1
    return codeword_no_redundant



# Function 7 - Parity bits
def determine_parity(codeword_no_redundant, m, r, LEN, indeces_binary):
    # There will be 'r' parity bits in the word
    # print()
    par_bits = list()
    for par_exp in range(r):
        # print("par_exp = ", par_exp)
        # r = 4, par_exp = (0, 1, 2, 3)
        # Assuming r = 2, check the 2nd position (index 1) from binary representation of indeces
        pos_check = r - 1 - par_exp
        # I will check how many 1's are there in positions with index pos_check
        SUM = 0
        for i in range(len(indeces_binary)):
            index_binary = indeces_binary[i]
            if index_binary[pos_check] == 1:
                # print(bin_to_dec(index_binary))
                value = codeword_no_redundant[i]
                # print("Value = ", value)
                if value != -1:
                    SUM += value
        # SUM IS OK by now
        # print("SUM = ", SUM)
        par_bit = SUM % 2
        par_bits.append(par_bit)
        # print()
    # Now, I have to flip my list with parity bits
    par_bits.reverse()
    return par_bits



# Function 8 - Fill with parity bits
def fill_with_parity(codeword_no_redundant, par_bits):
    counter = 0
    for i in range(len(codeword_no_redundant)):
        if codeword_no_redundant[i] == -1:
            codeword_no_redundant[i] = par_bits[counter]
            counter += 1
    return codeword_no_redundant



# MAIN FUNCTI0N
# 1. Initialization of parameters
# m = data bit length, r = num of redundant bits
low = 7
high = 7
m = randrange(low, high + 1)
data = [randrange(2) for i in range(m)]
r = find_r(m)
LEN = m + r         # Codeword length

# 2. Codeword without redundant
print()
print("    Data = ", data)
codeword_no_redundant = write_codeword_no_redundant(data, m, r, LEN)
print("Codeword = ", codeword_no_redundant)

# 3. Determine the missing positions of a codeword = message + redundant
indeces_binary = bin_representation(LEN)
par_bits = determine_parity(codeword_no_redundant, m, r, LEN, indeces_binary)
print("Par_bits = ", par_bits)

# 4. Fill the gaps (-1) in codeword with this list
codeword = fill_with_parity(codeword_no_redundant, par_bits)
print("Codeword = ", codeword_no_redundant)