a bug in computing minimum distance, coding theory

For anyone who is familiar with coding theory, we build codes as a subspace of the vector space F_q^n from generating matrices, with all linear combinations of rows of this matrix. For any generating matrix defined over a Finite Field, SAGE has spesific attributes "C =LinearCode(G)" which constructs the code from generating matrix and "C.minimum_distance()" which computes the minimum distance of the code. However, there is probably a bug or something which I couldn't find out.

For example see this:

This code is a [7,3] linear code over the field GF(4,"a"), which has min. distance 3,(as computed with MAGMA), but SAGE computes its min. distance as 5, which is above upper bound!

This is the SAGE input-output:

K = GF(4,"a"); a = K.gen(); G = Matrix([[a, a + 1, 1, a + 1, 1, 0, 0], [0, a, a + 1, 1, a + 1, 1, 0], [0, 0, a, a + 1, 1, a + 1, 1], [a + 1, 0, 1, 0, a + 1, 1, a + 1], [a, a + 1, a + 1, 0, 0, a + 1, 1], [a + 1, a, a, 1, 0, 0, a + 1], [a, a + 1, 1, a + 1, 1, 0, 0]]); C=LinearCode(G); C; C.minimum_distance();


gives the output:

︡"Linear code of length 7, dimension 3 over Finite Field in a of size 2^2"   "5"


However for the same conditions MAGMA says this:

︡> G6 := LinearCode <F,7|[[a, a + 1, 1, a + 1, 1, 0, 0], [0, a, a + 1, 1, a + 1, 1, 0], [0, 0, a, a + 1, 1, a + 1, 1], [a + 1, 0, 1, 0, a + 1, 1, a + 1], [a, a + 1, a + 1, 0, 0, a + 1, 1], [a + 1, a, a, 1, 0, 0, a + 1], [a, a + 1, 1, a + 1, 1, 0, 0]]>; G6;


[7, 3, 3] Linear Code over GF(2^2)

I don't understand where SAGE fails.. Do you have any idea?

edit retag close merge delete

Sort by » oldest newest most voted

Hello,

The problem comes from the fact that your matrix does not have full rank (indeed it has rank 3 and 7 rows). If you use a full rank matrix then you are done

sage: C1 = LinearCode(G)
sage: C2 = LinearCode(G[:3])
sage: C1 == C2
True
sage: C1.minimum_distance()
5
sage: C2.minimum_distance()
3


I opened a the trac ticket #17452 for that problem. It will be modified in the next stable release. Thanks for your report!

If you want to contribute to Sage, do not hesitate to open a trac account and participate in the resolution of this problem.

Vincent

more

Thank you, Until it is okay, I use this command rather than above and it works but it is not handy at all;

C=LinearCode(G.row_space().basis_matrix())

( 2014-12-24 09:19:04 +0100 )edit

The ticket has been merged... it will be corrected in the next release! And I agree that it is not handy at all right now.

( 2015-01-05 23:41:00 +0100 )edit

Since you now have 15 karma points, you can upvote @vdelecroix answer, and even accept it as the best ever !

( 2015-02-07 22:47:48 +0100 )edit

Thanks @vdelecroix for all the help. It seems fixed in the upcoming release..

( 2015-02-24 06:46:28 +0100 )edit