László Párkányi
5bf5bfec5d
refactor(framing): re-name hamming codec to 7,4 to reflect algorithm used
97 lines
3.9 KiB
Python
97 lines
3.9 KiB
Python
import numpy as np
|
|
import numpy.typing as npt
|
|
|
|
GEN_MATRIX = np.asarray([(1, 1, 1, 0, 0, 0, 0),
|
|
(1, 0, 0, 1, 1, 0, 0),
|
|
(0, 1, 0, 1, 0, 1, 0),
|
|
(1, 1, 0, 1, 0, 0, 1),
|
|
])
|
|
PARITY_MATRIX = np.asarray([(0, 0, 0, 1, 1, 1, 1),
|
|
(0, 1, 1, 0, 0, 1, 1),
|
|
(1, 0, 1, 0, 1, 0, 1),
|
|
])
|
|
DECODER_MATRIX = np.asarray([(0, 0, 1, 0, 0, 0, 0,),
|
|
(0, 0, 0, 0, 1, 0, 0,),
|
|
(0, 0, 0, 0, 0, 1, 0,),
|
|
(0, 0, 0, 0, 0, 0, 1,),
|
|
])
|
|
|
|
|
|
def number_to_list(number: int, N: int) -> npt.NDArray:
|
|
"""Return the last N bits of a number as an MSB-first array"""
|
|
return np.array([(number >> (N-1-i)) % 2 for i in range(0, N)],dtype=int)
|
|
|
|
|
|
def list_to_number(array: npt.NDArray, N: int) -> int:
|
|
"""Reconstruct a number from the first N elements of an MSB-first array"""
|
|
output = 0
|
|
for i in range(0, N):
|
|
output += array[i] << (N-1-i)
|
|
return output
|
|
|
|
|
|
def encode_nibble(data: int) -> int:
|
|
"""Encode the lower 4 bits of data as hamming(7,4)"""
|
|
data_asarr = number_to_list(data, 4)
|
|
output_asarr = (data_asarr @ GEN_MATRIX) % 2
|
|
return list_to_number(output_asarr, 7)
|
|
|
|
|
|
def hamming_7_4_encode(data: list[int]) -> list[int]:
|
|
"""Encode a list of ints using Hamming(7,4)
|
|
The returned list is twice as long as the list in the argument"""
|
|
data_encoded = []
|
|
for element in data:
|
|
data_encoded += [encode_nibble(element >> 4),
|
|
encode_nibble(element % 16)]
|
|
return data_encoded
|
|
|
|
|
|
def decode_nibble(data: int) -> int:
|
|
"""decode a single nibble using the parity check matrix of Hamming(7,4).
|
|
This should correct 2 errors maximum."""
|
|
data_asarr = number_to_list(data, 7)
|
|
syndrome = (PARITY_MATRIX @ data_asarr) % 2
|
|
error = list_to_number(syndrome, 3)
|
|
if error == 0:
|
|
data_decoded = (DECODER_MATRIX @ data_asarr) % 2
|
|
return list_to_number(data_decoded, 4)
|
|
data_asarr[error - 1] ^= 1
|
|
data_decoded = (DECODER_MATRIX @ data_asarr) % 2
|
|
return list_to_number(data_decoded, 4)
|
|
|
|
|
|
def hamming_7_4_decode(data: list[int]) -> list[int]:
|
|
"""Decode a list of ints using Hamming(7,4)
|
|
The returned list is half as long as the list in the argument"""
|
|
return [(decode_nibble(data[i]) << 4) + (decode_nibble(data[i + 1])) for i in range(0, len(data), 2)]
|
|
|
|
|
|
if __name__ == "__main__":
|
|
msg = 'TEST DE HA5PLS'
|
|
data_in = [byte for byte in bytearray(msg.encode())]
|
|
data_encoded = hamming_7_4_encode(data_in)
|
|
print(f"Data sent: {msg}")
|
|
|
|
data_corrupted_1bit = [data ^ (1 << (idx % 7))
|
|
for idx, data in enumerate(data_encoded)]
|
|
# print(f"Corrupt data with 1-bit errors: {data_corrupted_1bit}")
|
|
data_corrected_1bit = hamming_7_4_decode(data_corrupted_1bit)
|
|
data_corrected_1bit_str = [int.to_bytes(int(i), 1, "big").decode(
|
|
encoding="utf-8", errors="ignore") for i in data_corrected_1bit]
|
|
print(f"Recovered data from 1-bit errors: {data_corrected_1bit_str}")
|
|
|
|
data_corrupted_2bit = [data ^ (5 << (idx % 7))
|
|
for idx, data in enumerate(data_encoded)]
|
|
# print(f"Corrupt data with 2-bit errors: {data_corrupted_2bit}")
|
|
data_corrected_2bit = hamming_7_4_decode(data_corrupted_2bit)
|
|
data_corrected_2bit_str = [int.to_bytes(int(i), 1, "big").decode(
|
|
encoding="utf-8", errors="ignore") for i in data_corrected_2bit]
|
|
print(f"Recovered data from 2-bit errors: {data_corrected_2bit_str}")
|
|
|
|
# print(f"Corrupt data with 3-bit errors: {data_corrupted_3bit}")
|
|
data_corrected_noerr = hamming_7_4_decode(data_encoded)
|
|
data_corrected_noerr_str = [int.to_bytes(int(i), 1, "big").decode(
|
|
encoding="utf-8", errors="ignore") for i in data_corrected_noerr]
|
|
print(f"Recovered data from no errors: {data_corrected_noerr_str}")
|