GF(3) (4,2,3) Hamming Code.sagews

#----------------------------------------------------------------
# File name: Non-Binary_Hamming_Test_1.sage
# by Chong Zan Kai
# Email [email protected]
#
# To test the error-correction capability of GF(3) (4, 2, 3) Hamming Code.
#
# Public link: https://cloud.sagemath.com/projects/026994b5-e264-4071-a9e1-127c5595f170/files/GF(3)%20(4,2,3)%20Hamming%20Code.sagews
# Last modified on 31-Mar-2016.
#
print '#' + '-' * 50
print '# To test the error-correction capability of GF(3) (4, 2, 3) Hamming Code.'
print '#' + '-' * 50

#------------------------------------------------------------------------------
#
#------------------------------------------------------------------------------
print '#' + '-' * 50
print '# Demonstrate that G_mat and H_mat are dual codes.'
print '#' + '-' * 50

GFq = GF(3)

H_list = [
    [1, 1, 1, 0 ],
    [1, 2, 0, 1 ]]

H_mat = matrix(GFq, H_list)

G_list = [
    [1, 0, 2, 2 ],
    [0, 1, 2, 1 ]]
G_mat = matrix(GFq, G_list)

G_H_mat = G_mat * H_mat.T

print 'H_mat =\n', H_mat
print
print 'G_mat =\n', G_mat
print
print 'G_mat * H_mat.T =\n', G_H_mat
print

assert (G_H_mat == zero_matrix(GFq, 2, 2))

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



# Generate all possible errors.
error_vec_list = []
syndrome_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)


for error_vec in error_vec_list:
    syndrome_vec = error_vec * H_mat.T
    syndrome_vec_list.append(syndrome_vec)
    print 'For error_vec = %s, syndrome_vec = %s' % (error_vec, syndrome_vec)
print


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

k = 2
n = 4

#
print 'Randomize a message'
m_mat = random_matrix(GFq, 1, k)
print 'm_mat = %s' % m_mat
print

#
print 'Encoding message'
print 'G_mat = \n%s' % G_mat
print

x_mat = m_mat * G_mat
print 'x_mat = m_mat * G_mat'
print 'x_mat = %s' % x_mat
print

#
print 'Introduce error to the codeword'
error_mat = matrix(choice(error_vec_list))
print 'error_mat = %s' % error_mat
print

y_mat = x_mat + error_mat
print 'y_mat = x_mat + error_mat'
print 'y_mat = %s' % y_mat
print

#
print 'Syndrome decoding'
print 'H_mat = \n%s' % H_mat
print

s_mat = y_mat * H_mat.T
print 's_mat = y_mat * H_mat.T'
print 's_mat = %s' % s_mat
print

#
print 'Identifying the error vector.'
s_vec = vector(GFq, s_mat.list())
loc = syndrome_vec_list.index(s_vec)
corr_error_vec = error_vec_list[loc]
print 'The corresponding error vector is %s.' % corr_error_vec
print

#
print 'Correction to codeword.'
correct_x_mat = y_mat - matrix(corr_error_vec)
print 'Correct codeword is %s.' % correct_x_mat

print


#
correct_m_mat = x_mat.matrix_from_columns(range(k))
print 'Decoded messasge is %s.' % correct_m_mat
print

assert (correct_m_mat == m_mat)

#-------------------------------------------------- # To test the error-correction capability of GF(3) (4, 2, 3) Hamming Code. #-------------------------------------------------- #-------------------------------------------------- # Demonstrate that G_mat and H_mat are dual codes. #-------------------------------------------------- H_mat = [1 1 1 0] [1 2 0 1] G_mat = [1 0 2 2] [0 1 2 1] G_mat * H_mat.T = [0 0] [0 0] #-------------------------------------------------- # Show all the possible errors and their corresponding syndromes. #-------------------------------------------------- For error_vec = (1, 0, 0, 0), syndrome_vec = (1, 1) For error_vec = (0, 1, 0, 0), syndrome_vec = (1, 2) For error_vec = (0, 0, 1, 0), syndrome_vec = (1, 0) For error_vec = (0, 0, 0, 1), syndrome_vec = (0, 1) For error_vec = (2, 0, 0, 0), syndrome_vec = (2, 2) For error_vec = (0, 2, 0, 0), syndrome_vec = (2, 1) For error_vec = (0, 0, 2, 0), syndrome_vec = (2, 0) For error_vec = (0, 0, 0, 2), syndrome_vec = (0, 2) #-------------------------------------------------- # Encoding a message, introduce error bit and decode the codeword. #-------------------------------------------------- Randomize a message m_mat = [2 2] Encoding message G_mat = [1 0 2 2] [0 1 2 1] x_mat = m_mat * G_mat x_mat = [2 2 2 0] Introduce error to the codeword error_mat = [0 1 0 0] y_mat = x_mat + error_mat y_mat = [2 0 2 0] Syndrome decoding H_mat = [1 1 1 0] [1 2 0 1] s_mat = y_mat * H_mat.T s_mat = [1 2] Identifying the error vector. The corresponding error vector is (0, 1, 0, 0). Correction to codeword. Correct codeword is [2 2 2 0]. Decoded messasge is [2 2].