# Assignment08.py

user_9560538
python
23 days ago
6.0 kB
4
Indexable
Never
```# 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()```