Ask Your Question
1

a bug in computing minimum distance, coding theory

asked 2014-10-16 12:14:26 -0500

algebraicallyclosed gravatar image

updated 2017-01-08 05:06:26 -0500

FrédéricC gravatar image

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 flag offensive close merge delete

1 answer

Sort by » oldest newest most voted
0

answered 2014-12-06 16:25:41 -0500

updated 2014-12-06 17:36:09 -0500

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

edit flag offensive delete link more

Comments

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())
algebraicallyclosed gravatar imagealgebraicallyclosed ( 2014-12-24 02:19:04 -0500 )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.

vdelecroix gravatar imagevdelecroix ( 2015-01-05 16:41:00 -0500 )edit

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

tmonteil gravatar imagetmonteil ( 2015-02-07 15:47:48 -0500 )edit

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

algebraicallyclosed gravatar imagealgebraicallyclosed ( 2015-02-23 23:46:28 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2014-10-16 12:14:26 -0500

Seen: 155 times

Last updated: Dec 06 '14