GF(2) (3,1) Cyclic Code.sagews

#
# File name: GF(2) (3,1) Cyclic Code.sagews
# by Chong Zan Kai
# Email [email protected]
#
# To construct a GF(2) (3, 1) Cyclic Code.
#
# Last edit on 1-Apr-2016
# Public link: https://cloud.sagemath.com/projects/026994b5-e264-4071-a9e1-127c5595f170/files/GF(2)%20(3,1)%20Cyclic%20Code.sagews
#

#------------------------------------------------------------------------------
# Useful Functions
#------------------------------------------------------------------------------

def vec_to_poly(input_vec):
    '''
    Convert a vector into polynomial.
    Example:
        vec = vector(GF(2), [1,0,1])
        vec_to_poly(vec)
        >> D^2 + 1
    '''
    poly_list = [val * D^num for num, val in enumerate(input_vec)]
    poly = sum(poly_list)
    return poly


def poly_to_vec(poly, length, GFq):
    '''
    To convert a polynomial to a vector.
    e.g. 1+D+D^3 to [1 1 0 1 0 0] (say the dimension is  6).
    Example:
        D = PolynomialRing(GF(2), 'D').gen()
        p = D^2 + 1
        poly_to_vec(p, 4, GF(2))
        >> (1, 1, 0, 0)
    '''
    x_list = poly.coefficients()
    x_list += [0] * (length - len(x_list))
    return vector(GFq, x_list)


def generate_error_vec_list(GFq, length):
    # Generate all possible errors.
    error_vec_list = []

    for q in GFq.list()[1:]:
        for i in range(4):
            error_vec = zero_vector(GFq, 4)
            error_vec[i] = q
            error_vec_list.append(error_vec)
    return error_vec_list

def generate_error_vec_list(GFq, length):
    """
    Generate a list of all possible error vectors.
    Example:
        generate_error_vec_list(GF(3), 3)
        >> [(1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1), (2, 0, 0, 0), (0, 2, 0, 0), (0, 0, 2, 0), (0, 0, 0, 2)]
    """
    # Generate all possible errors.
    error_vec_list = []

    for q in GFq.list()[1:]:
        for i in range(4):
            error_vec = zero_vector(GFq, 4)
            error_vec[i] = q
            error_vec_list.append(error_vec)
    return error_vec_list

#------------------------------------------------------------------------------
#
#------------------------------------------------------------------------------
print '#' + '-' * 50
print '# To construct a GF(2) (3, 1) Cyclic Code.'
print '#' + '-' * 50

GFq = GF(2)
k = 1
n = 3
#
# Construct the polynomial
#
D = PolynomialRing(GFq, 'D').gen()
print 'The factor of D^3 + 1 is %s.' % (D^3 + 1).factor()
print

g_D = 1 + D + D^2
print 'We the generator as g(D) = %s' % g_D
print




#------------------------------------------------------------------------------
#
#------------------------------------------------------------------------------
print '#' + '-' * 50
print '# Show all the possible errors and their corresponding syndromes.'
print '#' + '-' * 50



# Generate all possible errors in polynomial.
error_vec_list = generate_error_vec_list(GFq, n)

error_D_list = [vec_to_poly(vec) for vec in error_vec_list]

syndrome_D_list = []

for error_D in error_D_list:
    syndrome_D = error_D % g_D
    syndrome_D_list.append(syndrome_D)
    print 'error_D = %5s, syndrome_D = %s' % (error_D, syndrome_D)


#------------------------------------------------------------------------------
#
#------------------------------------------------------------------------------
print '#' + '-' * 50
print '# Encoding a message, introduce error bit and decode the codeword.'
print '#' + '-' * 50


#
print 'Randomize a message'
m_vec = random_vector(GFq, k)
m_D = vec_to_poly(m_vec)
print 'Message polynomial is %s' % m_D
print


#
print 'Encoding the message into codeword.'
t1_D = m_D * D**(n-k)
b_D = t1_D % g_D
x_D = t1_D + b_D

print 'The codeword polynomial is %s.' % x_D
print

print 'Introduce error.'
e_D = choice(error_D_list)
print 'Error polynomial is %s.' % e_D


print 'Receiver receives codeword.'
y_D = x_D + e_D
print 'Received codeword polynomial is %s.' % y_D
print

print 'Decoding based on syndrome'
s_D = y_D % g_D
loc = syndrome_D_list.index(s_D)
guess_error_D = error_D_list[loc]
print 'Syndome polynomial is %s, which corresponding to error polynomial %s.' % (s_D, guess_error_D)
print

print 'Making correction to received codeword polynomial.'
correct_y_D = y_D - guess_error_D
print 'Correct codeword polynomial is %s.' % correct_y_D
print

assert (correct_y_D == x_D)

#-------------------------------------------------- # To construct a GF(2) (3, 1) Cyclic Code. #-------------------------------------------------- The factor of D^3 + 1 is (D + 1) * (D^2 + D + 1). We the generator as g(D) = D^2 + D + 1 #-------------------------------------------------- # Show all the possible errors and their corresponding syndromes. #-------------------------------------------------- error_D = 1, syndrome_D = 1 error_D = D, syndrome_D = D error_D = D^2, syndrome_D = D + 1 error_D = D^3, syndrome_D = 1 #-------------------------------------------------- # Encoding a message, introduce error bit and decode the codeword. #-------------------------------------------------- Randomize a message Message polynomial is 0 Encoding the message into codeword. The codeword polynomial is 0. Introduce error. Error polynomial is D. Receiver receives codeword. Received codeword polynomial is D. Decoding based on syndrome Syndome polynomial is D, which corresponding to error polynomial D. Making correction to received codeword polynomial. Correct codeword polynomial is 0.