2024-03-13--ReedSolomon-class.ipynb

Kernel: SageMath 10.2

class ReedSolomon:
    def __init__(self,q,k):
        self.q = q
        self.F = GF(q)

        self.k = k
        self.t = floor((q-k)/2)  # we should be able to correct this many errors!
        
        self.V = VectorSpace(self.F,self.q)

        self.R = self.F['T']
        self.T = self.R.0  
        
    def vectorize(self,f):
        if f.degree() < self.k:
            return self.V([ f(a) for a in self.F ])
        else:
            print("error")

    def decode(self,v):
        q = self.q
        k = self.k
        
        M1 = floor((1/2)*(q-k))
        M2 = k + ceil((1/2)*(q-k)) - 1

        # the elements of the field F
        elts = [ a for a in self.F ]    
        
        def mkRow(i):
            return [ elts[i]^j for j in range(M2+1) ] + [-elts[i]^j * v[i] for j in range(M1+1) ]

        M = MatrixSpace(self.F,q,q+1).matrix([ mkRow(i) for i in range(q) ])

        # get a vector in the null space of V.
        coeffs = M.right_kernel().basis()[0]

        T = self.T

        # use the vector in the null space of V to build polynomials g and h
        g = sum([ coeffs[j] * T^j      for j in range(M2+1) ])
        h = sum([ coeffs[M2+1+j] * T^j for j in range(M1+1) ])

        # our solution is the quotient f = g/h
        # h divides g, so we "coerce" the ratio g/h to be element of self.R -- i.e. a polynomial
        # and not just a rational function of self.T
        f = self.R(g/h)

        # return the vector corresponding to f - this the decoded vector.
        return self.vectorize(f)


    def random_field_element(self):
        elts = [ a for a in self.F ]
        return choice(elts)

    def random_poly(self):
        # return a random polynomial of degree < k

        T = self.T
        return sum([ self.random_field_element()*T^j for j in range(self.k) ])

    def random_error(self):
        q = self.q
        k = self.k
        t = self.t
                    
        # choose t random indices
        ll = [ choice(range(q)) for _ in range(t) ]

        # return a random error vector, according to the indices in ll
        return self.V([ self.random_field_element() if j in ll else 0 for j in range(q) ])


    def display_result(self,res):
        print("sent/received/error: \n")
        M = MatrixSpace(self.F,3,self.q).matrix([ res['sent'], res['received'], res['error'] ])
        print(M)
        print(f"\ndecoded correctly? {res['passed']}") 

    
    def test(self):
        f = self.random_poly()
        v = self.vectorize(f)
        e = self.random_error()
        return { "sent": v,
                 "poly": f,
                 "received": v + e,
                 "error": e,
                 "passed": v == self.decode(v+e)
               }
    

    def run_tests(self,m):
        print(f"Reed Solomon code with q = {self.q} and k = {self.k}")
        print(f"Can correct t = {self.t} errors.")
        print(f"test decoding of {m} random vectors in C each with <={self.t} random errors\n")
        test_results = [ self.test() for _ in range(m) ]
        
        all_passed = all([ res['passed'] for res in test_results ])
        print(f"all passed? {all_passed}")
        print("------\n")
        
        for res in test_results:
            self.display_result(res)
            print("-----\n")

rs = ReedSolomon(19,5)
rs.run_tests(10)

Reed Solomon code with q = 19 and k = 5
Can correct t = 7 errors.
test decoding of 10 random vectors in C each with <=7 random errors

all passed? True
------

sent/received/error: 

[10  1  6 13 12 14 13  5  7  0  5  7 12  9  8  2  5 14  9]
[ 3  1  6 13 12  3 13  5  7  0  5  4 14  7  8  2  5 12  9]
[12  0  0  0  0  8  0  0  0  0  0 16  2 17  0  0  0 17  0]

decoded correctly? True
-----

sent/received/error: 

[ 1 17  9 13 14  3 15 15 12  2  6 13 18  3 13  4 14 11  7]
[13 17  9 13 14  3 15 15 12  2 17 13 18  9  2  4 11 11  5]
[12  0  0  0  0  0  0  0  0  0 11  0  0  6  8  0 16  0 17]

decoded correctly? True
-----

sent/received/error: 

[ 5  0 13 16  5  0  7 18 11  7 13  3 13  8 15  9  8 16  4]
[ 5  1 13 16  5  0  7 10 11  7 13  3  9  8  3  9  8  1 14]
[ 0  1  0  0  0  0  0 11  0  0  0  0 15  0  7  0  0  4 10]

decoded correctly? True
-----

sent/received/error: 

[ 3  9  5  4 17 15  5 11 17  5 12 16 12 12  7  5 12 13 10]
[ 3 14 10  4 17 15 14 11 17  5 12 16 12 12  7  5  5 13  1]
[ 0  5  5  0  0  0  9  0  0  0  0  0  0  0  0  0 12  0 10]

decoded correctly? True
-----

sent/received/error: 

[18 15  1 11 11 12 13  1  8 16 14 17  9  0  7 16  1  0  1]
[18 15 10 11 12 12 13  1  8 18 17 17  9  0  7 16 17 10  1]
[ 0  0  9  0  1  0  0  0  0  2  3  0  0  0  0  0 16 10  0]

decoded correctly? True
-----

sent/received/error: 

[ 2  7  7 14  3  7  3  7 17 13 14  2 17  5  8 12  4 10  0]
[ 2  7  7 14  3  7 17  7  7 13 14 18 17  6  8 13  4 10  0]
[ 0  0  0  0  0  0 14  0  9  0  0 16  0  1  0  1  0  0  0]

decoded correctly? True
-----

sent/received/error: 

[ 4  3  3 13 15  2 16 15  6  7  9 14 16  1  4 14 12  9  8]
[ 9  3  3 13 15  2 16 15  6  6  9 14 16  1  4  9 12  9  8]
[ 5  0  0  0  0  0  0  0  0 18  0  0  0  0  0 14  0  0  0]

decoded correctly? True
-----

sent/received/error: 

[14 17  1 11  1  5  4  2  7 12 14 14 17 13 15  2 14  0  8]
[11 17  9 11  1  7  4  8 15 12 14 14 17 13 15  2 14 14  8]
[16  0  8  0  0  2  0  6  8  0  0  0  0  0  0  0  0 14  0]

decoded correctly? True
-----

sent/received/error: 

[ 6  3 13 10 15  1  7  5 14  5 15 14  0 18  8 14 13 10  0]
[ 6 13 13 11 15  1  7  5 14  9 15 11  0 18  1  4 13 14  0]
[ 0 10  0  1  0  0  0  0  0  4  0 16  0  0 12  9  0  4  0]

decoded correctly? True
-----

sent/received/error: 

[15  0 14 15  7  2  1 13 17  0 14  5  3  8  9  3 14 17 14]
[15  0 13 15  7  2 12 13  7  0 11 18 12  8 17  3 14 17 14]
[ 0  0 18  0  0  0 11  0  9  0 16 13  9  0  8  0  0  0  0]

decoded correctly? True
-----