Assignment08.py

# CSCI 355 Web Technology
#Summer 2024
#Assignment 8:   “Error Detection and Correction”


#ACK - Class



from random import random, randint

# [1] Define a function random_bits(n, p = 0.5) that computes a random bit string of length n. The additional, optional parameter p specifies the probability of generating a 1, defaulted to 0.5

def random_bits(n, p = 0.5):
    return ''.join(['1' if random() < p else '0' for _ in range(n)])

# [2] Define functions that implement each of the four error-detection algorithms:
#
# ed_parity_1d
# ed_parity_2d
# ed_checksum
# ed_crc

def ed_parity_1d(bits, odd = True):
    print("ED Parity 1D")
    print(f"Bits: {bits}")
    print(f"Odd: {odd}")
    # Return 1 if the number of 1s is odd, otherwise return 0
    return '1' if (bits.count('1') % 2 == 0) == odd else '0'

def ed_parity_2d(bits,n_r, n_c, odd = True):
    print("ED Parity 2D")
    print(f"Bits: {bits}")
    print(f"n_r: {n_r}")
    print(f"n_c: {n_c}")
    print(f"Odd: {odd}")
    n = len(bits)
    if n != n_r * n_c:
        raise ValueError(f"Length of bits ({n}) must be equal to n_r * n_c ({n_r * n_c})")
    # Create a 2D list of bits
    matrix = [bits[i:i+n_c] for i in range(0, n, n_c)]
    # Calculate the parity bits for each row
    row_parities = [ed_parity_1d(row, odd) for row in matrix]
    col_parities = [ed_parity_1d(''.join([matrix[i][j] for i in range(n_r)]), odd) for j in range(n_c)]

    print("Matrix: ", matrix)
    print("Row Parities: ", row_parities)
    print("Column Parities: ", col_parities)

    return row_parities, col_parities



def ed_checksum(bits):
    print("ED Checksum")
    print(f"Bits: {bits}")
    n = len(bits)
    if n % 2 != 0:
        raise ValueError("Length of bits must be even")
    bit_chunks = bits[:n//2], bits[n//2:]
    res = ""
    c = 0
    for i in range(n//2 - 1, -1 , -1):
        s = int(bit_chunks[0][i]) + int(bit_chunks[1][i]) + c
        c = 1 if s > 1 else 0
        s = s % 2
        res = str(s) + res
    ones_complement = "".join(['1' if bit == '0' else '0' for bit in res])

    print(f"Bit Chunks: {bit_chunks}")
    print(f"Result: {res}")
    print(f"Ones Complement: {ones_complement}")


def xor(a, b):
    # initialize result
    result = []

    # Traverse all bits, if bits are
    # same, then XOR is 0, else 1
    for i in range(1, len(b)):
        if a[i] == b[i]:
            result.append('0')
        else:
            result.append('1')

    return ''.join(result)


# Performs Modulo-2 division
def mod2div(dividend, divisor):
    # Number of bits to be XORed at a time.
    pick = len(divisor)

    # Slicing the dividend to appropriate
    # length for particular step
    tmp = dividend[0: pick]

    while pick < len(dividend):

        if tmp[0] == '1':

            # replace the dividend by the result
            # of XOR and pull 1 bit down
            tmp = xor(divisor, tmp) + dividend[pick]

        else:  # If leftmost bit is '0'
            # If the leftmost bit of the dividend (or the
            # part used in each step) is 0, the step cannot
            # use the regular divisor; we need to use an
            # all-0s divisor.
            tmp = xor('0' * pick, tmp) + dividend[pick]

            # increment pick to move further
        pick += 1

    # For the last n bits, we have to carry it out
    # normally as increased value of pick will cause
    # Index Out of Bounds.
    if tmp[0] == '1':
        tmp = xor(divisor, tmp)
    else:
        tmp = xor('0' * pick, tmp)

    checkword = tmp
    return checkword


# Function used at the sender side to encode
# data by appending remainder of modular division
# at the end of data.


def ed_crc(data, key):
    print("ED CRC")
    print(f"Data: {data}")
    print(f"Key: {key}")

    l_key = len(key)

    # Appends n-1 zeroes at end of data
    appended_data = data + '0' * (l_key - 1)
    print("Appended Data : ", appended_data)
    remainder = mod2div(appended_data, key)

    # Append remainder in the original data
    codeword = data + remainder
    print("Remainder : ", remainder)
    print("Encoded Data (Data + Remainder) : ",
          codeword)


def flip_bits(bits, k):
    for i in range(k):
        index = randint(0, len(bits) - 1)
        bits = bits[:index] + ('1' if bits[index] == '0' else '0') + bits[index + 1:]
    return bits

def compare_parities(row_parities, col_parities, row_parities2, col_parities2):
    print("Comparing Parities")
    print(f"Row Parities: {row_parities}")
    print(f"Column Parities: {col_parities}")
    print(f"Row Parities 2: {row_parities2}")
    print(f"Column Parities 2: {col_parities2}")
    row_diff = [i for i in range(len(row_parities)) if row_parities[i] != row_parities2[i]]
    col_diff = [i for i in range(len(col_parities)) if col_parities[i] != col_parities2[i]]
    print(f"Row Differences: {row_diff}")
    print(f"Column Differences: {col_diff}")

    index_err = row_diff[0] * len(col_parities) + col_diff[0]

    print(f"Error Found at Index: {index_err}")

    return index_err

def main():
    rand_bits = random_bits(16, 0.8)
    row_parities, col_parities = ed_parity_2d(rand_bits, 4, 4, True)
    rand_bits2 = flip_bits(rand_bits, 1)
    row_parities2, col_parities2 = ed_parity_2d(rand_bits2, 4, 4, True)
    index_err = compare_parities(row_parities, col_parities, row_parities2, col_parities2)
    rand_bits3 = rand_bits2[:index_err] + ('1' if rand_bits2[index_err] == '0' else '0') + rand_bits2[index_err + 1:]

    print(f"Random Bits Before: {rand_bits}")
    print(f"Random Bits After: {rand_bits2}")
    print(f"Random Bits After Fix: {rand_bits3}")

    # ed_checksum(rand_bits)

    # Driver code
    data = "100100"
    key = "1101"
    ed_crc(data, key)

    bits = "11111"
    ed = ed_parity_1d(bits, True)
    print(ed)

if __name__ == "__main__":
    main()