Advertisement
makispaiktis

Hamming Code

May 6th, 2022 (edited)
1,149
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 4.11 KB | None | 0 0
  1. from math import log2
  2. from random import randrange
  3.  
  4. # Function 1 ---> 2^r >= m + r + 1
  5. def find_r(m):
  6.     r = 0
  7.     while 2**r - r < m + 1:
  8.         r = r + 1
  9.     return r
  10.  
  11. # Function 2 - Decimal to binary
  12. def dec_to_bin(decimal):
  13.     # decimal = INTEGER
  14.     if decimal == 0:
  15.         return [0]
  16.     else:
  17.         digits = list()
  18.         LEN = int(log2(decimal)) + 1
  19.         for exp in range(LEN-1, -1, -1):
  20.             value = 2 ** exp
  21.             if decimal >= value:
  22.                 digits.append(1)
  23.                 decimal -= value
  24.             else:
  25.                 digits.append(0)
  26.         return digits
  27.  
  28.  
  29. # Function 3 - Binary to decimal
  30. def bin_to_dec(binary):
  31.     # binary = LIST
  32.     SUM = 0
  33.     LEN = len(binary)
  34.     for index in range(LEN):
  35.         SUM += binary[index] * (2**(LEN-1-index))
  36.     return SUM
  37.  
  38.  
  39. # Function 4 - Padding with zeros
  40. def pad_zeros(binary, LEN):
  41.     LEN1 = int(log2(LEN)) + 1
  42.     LEN2 = len(binary)
  43.     binary2 = [0 for i in range(LEN1 - LEN2)]
  44.     binary = binary2 + binary
  45.     return binary
  46.  
  47.  
  48. # Function 5 - Binary representation of indeces
  49. def bin_representation(LEN):
  50.     # If LEN = 11, I will create a list with all the binary representations of numbers
  51.     # between 11 and 1 (inclusively)
  52.     indeces_binary = list()
  53.     for i in range(LEN, 0, -1):
  54.         binary = dec_to_bin(i)
  55.         indeces_binary.append(pad_zeros(binary, LEN))
  56.     return indeces_binary
  57.  
  58.  
  59.  
  60. # Function 6 - Write the codeword without redundant bits
  61. def write_codeword_no_redundant(data, m, r, LEN):
  62.     # I will symbolize redundant with the number '-1'
  63.     codeword_no_redundant = list()
  64.     counter = 0
  65.     for i in range(LEN, 0, -1):
  66.         if log2(i) == int(log2(i)):
  67.             codeword_no_redundant.append(-1)
  68.         else:
  69.             codeword_no_redundant.append(data[counter])
  70.             counter += 1
  71.     return codeword_no_redundant
  72.  
  73.  
  74.  
  75. # Function 7 - Parity bits
  76. def determine_parity(codeword_no_redundant, m, r, LEN, indeces_binary):
  77.     # There will be 'r' parity bits in the word
  78.     # print()
  79.     par_bits = list()
  80.     for par_exp in range(r):
  81.         # print("par_exp = ", par_exp)
  82.         # r = 4, par_exp = (0, 1, 2, 3)
  83.         # Assuming r = 2, check the 2nd position (index 1) from binary representation of indeces
  84.         pos_check = r - 1 - par_exp
  85.         # I will check how many 1's are there in positions with index pos_check
  86.         SUM = 0
  87.         for i in range(len(indeces_binary)):
  88.             index_binary = indeces_binary[i]
  89.             if index_binary[pos_check] == 1:
  90.                 # print(bin_to_dec(index_binary))
  91.                 value = codeword_no_redundant[i]
  92.                 # print("Value = ", value)
  93.                 if value != -1:
  94.                     SUM += value
  95.         # SUM IS OK by now
  96.         # print("SUM = ", SUM)
  97.         par_bit = SUM % 2
  98.         par_bits.append(par_bit)
  99.         # print()
  100.     # Now, I have to flip my list with parity bits
  101.     par_bits.reverse()
  102.     return par_bits
  103.  
  104.  
  105.  
  106. # Function 8 - Fill with parity bits
  107. def fill_with_parity(codeword_no_redundant, par_bits):
  108.     counter = 0
  109.     for i in range(len(codeword_no_redundant)):
  110.         if codeword_no_redundant[i] == -1:
  111.             codeword_no_redundant[i] = par_bits[counter]
  112.             counter += 1
  113.     return codeword_no_redundant
  114.  
  115.  
  116.  
  117. # MAIN FUNCTI0N
  118. # 1. Initialization of parameters
  119. # m = data bit length, r = num of redundant bits
  120. low = 7
  121. high = 7
  122. m = randrange(low, high + 1)
  123. data = [randrange(2) for i in range(m)]
  124. r = find_r(m)
  125. LEN = m + r         # Codeword length
  126.  
  127. # 2. Codeword without redundant
  128. print()
  129. print("    Data = ", data)
  130. codeword_no_redundant = write_codeword_no_redundant(data, m, r, LEN)
  131. print("Codeword = ", codeword_no_redundant)
  132.  
  133. # 3. Determine the missing positions of a codeword = message + redundant
  134. indeces_binary = bin_representation(LEN)
  135. par_bits = determine_parity(codeword_no_redundant, m, r, LEN, indeces_binary)
  136. print("Par_bits = ", par_bits)
  137.  
  138. # 4. Fill the gaps (-1) in codeword with this list
  139. codeword = fill_with_parity(codeword_no_redundant, par_bits)
  140. print("Codeword = ", codeword_no_redundant)
  141.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement