Error correcting codes

Project meant for encoding messages such that they can be correctly decoded even after experiencing noise.
The theoretical basis for the project is described in Finite Fields and Error-Correcting Codes by Karl-Gustav Andersson.

The Code class

In order to encode or decode messages you need an object of type Code.

  class Code:
    def __init__(
                self, 
                generating_matrix: np.ndarray, 
                prime: int, 
                compute_coset_leader = True, 
                verbose = False
                ):

• generating_matrix: matrix to encode message. If in doubt, use the class Hamming_Code described later.
• prime: refers to the finite field in which all calculations are to be done.
• compute_coset_leader: set to False if there exists a file "data/coset_leader.json" which has correct coset leader information. Such a file is created when compute_coset_leader=True.

Sample code:

  G = np.array([
    [1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1],
    [0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
], dtype=int)

  code = Code(G, 2, verbose=True)

Encoding messages

Encoding is done with Code's methods encode_str() and encode_message().

  class Code:
    def encode_str(self, message_str: str) -> np.ndarray:
    def encode_message(self, message: np.ndarray) -> np.ndarray:

The method encode_str() takes a string as input and outputs a np.ndarray of encoded bits.

The method encode_message() takes a np.ndarray of bits as input and outputs a np.ndarray of encoded bits.

Decoding message

Decoding is done with Code's decode_to_str() and decode_message() methods.

  class Code:
    def decode_to_str(self, message: np.ndarray) -> str:
    def decode_message(self, message: np.ndarray) -> np.ndarray:

The method decode_to_str() takes a np.ndarray of bits and returns the decoded string, while decode_message() will take the same input and return the decoded bits.

So long as the number of errors in a chunk is less than or equal to (σ-1)/2, where σ is the seperation of the code, it will decode the chunk correctly.

Other attributes of a Code

• code.pack_density: can be seen as how relatively good a code is. Perfect codes (for example hamming codes) have pack_density=1.
• code.seperation: the seperation of the code. Seperation is 3 for all hamming codes.

Sample code

from code_class import Code
import numpy as np
  
G = np.array([
    [1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1],
    [0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
], dtype=int)

code = Code(G, 2)

input_string = input("Input: ")

encoded_message = code.encode_str(input_string)

noisy_encoded_message, noisy_string, nbr_noise = code.add_noise(encoded_message, 4)

decoded_string = code.decode_to_str(noisy_encoded_message)

print(f"Changed {nbr_noise} bits.")
print(f"Original Message: {input_string}")
print(f"Before decoding: {noisy_string}")
print(f"Decoded Message: {decoded_string}")

Sample output

Input: Hello World!
Changed 4 bits.
Original Message: Hello World!
Before decoding: Helmo`World!
Decoded Message: Hello World!

Hamming codes

To create perfect binary codes of seperation 3 one can use objects of type Hamming_Code.

  class Hamming_Code(Code):
    def __init__(
                self, 
                size: list[int, int], 
                compute_coset_leader = True, 
                verbose = False):

• size: the type of hamming code you wish to use. For a valid size = [m, n], the following must be true: 2^(n-m) - 1 = n.
• Valid sizes can be calculated by plugging in integer values of r in [2^r − 1, 2^r − r − 1]

Sample code

from code_class import Hamming_Code


hCode = Hamming_Code([11, 15])

input_string = input("Input: ")

encoded_message = hCode.encode_str(input_string)

noisy_encoded_message, noisy_string, nbr_noise = hCode.add_noise(encoded_message, 5)
print(f"Changed {nbr_noise} bits.")

decoded_string = hCode.decode_to_str(noisy_encoded_message)

print(f"Original Message: {input_string}")
print(f"Before decoding: {noisy_string}")
print(f"Decoded Message: {decoded_string}")