Re: [sage-devel] Minimum distance of a Hamming code

52 views
Skip to first unread message

Dima Pasechnik

unread,
May 24, 2015, 12:05:35 PM5/24/15
to sage-...@googlegroups.com, sage-codi...@googlegroups.com


On Saturday, 23 May 2015 22:36:10 UTC+1, vdelecroix wrote:
On 23/05/15 12:53, Dima Pasechnik wrote:
 > please review #18480 that fixes the corner case

Thanks for the fix Dima.

>> For  r > 5  it seems to hang interminably, while back in
>> November/December I could do  r = 7  in a few seconds, and
 >> do  r = 10  without waiting too long.

this sounds very weird that minimum distance of a code of length 127 and dimension 120 (this is for r=7) can be done in few seconds 
using the quite brute force algorithm, that would call GAP's AClosestVectorCombinationsMatFFEVecFFECoords
that chases all the linear combinations of i vectors, for i = 1..122 (in this case).

Probably the GAP part was buggy before and didn't return the correct results in general
(I vaguely recall there were reports of this code in GAP being buggy)

Dima

David Joyner

unread,
May 24, 2015, 1:38:45 PM5/24/15
to sage-codi...@googlegroups.com, sage-devel
On Sun, May 24, 2015 at 12:05 PM, Dima Pasechnik <dim...@gmail.com> wrote:
>
>
> On Saturday, 23 May 2015 22:36:10 UTC+1, vdelecroix wrote:
>>
>> On 23/05/15 12:53, Dima Pasechnik wrote:
>> > please review #18480 that fixes the corner case
>>
>> Thanks for the fix Dima.
>>
>> >> For r > 5 it seems to hang interminably, while back in
>> >> November/December I could do r = 7 in a few seconds, and
>> >> do r = 10 without waiting too long.
>
>
> this sounds very weird that minimum distance of a code of length 127 and
> dimension 120 (this is for r=7) can be done in few seconds
> using the quite brute force algorithm, that would call GAP's
> AClosestVectorCombinationsMatFFEVecFFECoords
> (see http://gap-system.org/Manuals/doc/ref/chap23.html#X82E5987E81487D18 for
> the description)
> that chases all the linear combinations of i vectors, for i = 1..122 (in
> this case).
>

Once you show that d!=1 and d!=2 (which can be done rather quickly in
the binary case), all GAP needs to do is find 1 codeword of weight 3
in the kernel of the check matrix H. It doesn't seem that weird to me
that such a vector can be found quickly.


> Probably the GAP part was buggy before and didn't return the correct results
> in general
> (I vaguely recall there were reports of this code in GAP being buggy)
>
> Dima
>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-coding-theory" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-coding-the...@googlegroups.com.
> To post to this group, send email to sage-codi...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sage-coding-theory/ae42acec-45b7-4c6f-b818-2e07c4b342c4%40googlegroups.com.
>
> For more options, visit https://groups.google.com/d/optout.

Vincent Delecroix

unread,
May 24, 2015, 1:59:15 PM5/24/15
to sage-codi...@googlegroups.com
On 24/05/15 19:38, David Joyner wrote:
> On Sun, May 24, 2015 at 12:05 PM, Dima Pasechnik <dim...@gmail.com> wrote:
>>
>>
>> On Saturday, 23 May 2015 22:36:10 UTC+1, vdelecroix wrote:
>>>
>>> On 23/05/15 12:53, Dima Pasechnik wrote:
>>> > please review #18480 that fixes the corner case
>>>
>>> Thanks for the fix Dima.
>>>
>>>>> For r > 5 it seems to hang interminably, while back in
>>>>> November/December I could do r = 7 in a few seconds, and
>>> >> do r = 10 without waiting too long.
>>
>>
>> this sounds very weird that minimum distance of a code of length 127 and
>> dimension 120 (this is for r=7) can be done in few seconds
>> using the quite brute force algorithm, that would call GAP's
>> AClosestVectorCombinationsMatFFEVecFFECoords
>> (see http://gap-system.org/Manuals/doc/ref/chap23.html#X82E5987E81487D18 for
>> the description)
>> that chases all the linear combinations of i vectors, for i = 1..122 (in
>> this case).
>>
>
> Once you show that d!=1 and d!=2 (which can be done rather quickly in
> the binary case), all GAP needs to do is find 1 codeword of weight 3
> in the kernel of the check matrix H. It doesn't seem that weird to me
> that such a vector can be found quickly.

There is perhaps an algorithmic answer, but the problem is not there.
In the current situation, Sage has an extra argument to initialize the
minimum distance (curious but it is there). Since #18099, this argument
is used to initialize the attribute _minimum_distance but then this
attribute is completely ignored (since minimum_distance is now a
cached_method and does not rely anymore on the attribute).

So let me first say that before #18099, Sage was *not* computing the
minimum distance. It only returned an integer that was stored as an
attribute! So the timing used to be few micro seconds rather than few
seconds.

I did the review of #18099, so I might take a blame for that. I do not
know what the authors of #18099 intend to do because they talked about
refactoring the different code families.

I would feel more confortable with the method minimum_distance having an
argument force (which default to False). The behavior would be that with
force=True, the computation is always done. What do you think?

Vincent

PS: @DavidJoyner Showing that d != 1 is easy in any case since you just
have to check that your subspace is disjoint from the lines generated by
the basis. But what for d != 2? I am very curious about that! In the
binary case, you can just check explicitely that the vectors with two
entries do not belong to the subspaces. That was what you thought about?

David Joyner

unread,
May 24, 2015, 2:02:45 PM5/24/15
to sage-codi...@googlegroups.com
On Sun, May 24, 2015 at 1:59 PM, Vincent Delecroix
<20100.d...@gmail.com> wrote:
> On 24/05/15 19:38, David Joyner wrote:

...

>>
>> Once you show that d!=1 and d!=2 (which can be done rather quickly in
>> the binary case), all GAP needs to do is find 1 codeword of weight 3
>> in the kernel of the check matrix H. It doesn't seem that weird to me
>> that such a vector can be found quickly.
>

...

>
> Vincent
>
> PS: @DavidJoyner Showing that d != 1 is easy in any case since you just have
> to check that your subspace is disjoint from the lines generated by the
> basis. But what for d != 2? I am very curious about that! In the binary
> case, you can just check explicitely that the vectors with two entries do
> not belong to the subspaces. That was what you thought about?

Not exactly. In the binary case, d=2 iff 2 columns of H are equal.
That can be checked quickly.

>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-coding-theory" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-coding-the...@googlegroups.com.
> To post to this group, send email to sage-codi...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sage-coding-theory/55621170.2090901%40gmail.com.

Johan S. R. Nielsen

unread,
May 24, 2015, 2:13:35 PM5/24/15
to sage-codi...@googlegroups.com
On Sunday, May 24, 2015 at 7:59:15 PM UTC+2, Vincent Delecroix wrote:
I would feel more confortable with the method minimum_distance having an
argument force (which default to False). The behavior would be that with
force=True, the computation is always done. What do you think?

-1
I think that the minimum_distance argument to LinearCode was a mistake from the beginning. The much more scalable solution is to make different families sub-classes of (what is now) AbstractLinearCode, and these will then override whatever generic stuff for this family. For instance the minimum distance of a Hamming code.

We already have the code for this and the beginning of it is already in Sage. We even have a specialised class for Hamming codes (which know their minimum distance). Soon, we will also propose to remove the minimum_distance argument again (with proper deprecation).

But we are missing reviewers: see http://trac.sagemath.org/ticket/18376

Best,
Johan

Dima Pasechnik

unread,
May 24, 2015, 2:21:33 PM5/24/15
to sage-codi...@googlegroups.com
Well, you could have posted about this ticket here, and/or cc
potential reviewers on the ticket.

Dima

>
> Best,
> Johan
>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-coding-theory" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-coding-the...@googlegroups.com.
> To post to this group, send email to sage-codi...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sage-coding-theory/8b4a1e6b-4598-41ab-8f0b-9d9a2163535f%40googlegroups.com.

Johan S. R. Nielsen

unread,
May 24, 2015, 3:29:22 PM5/24/15
to sage-codi...@googlegroups.com

Well, you could have posted about this ticket here, and/or cc
potential reviewers on the ticket.

We are not yet quite sure who potential interested reviewers could be. We'll gladly Cc you another time, if you are?

You're also right: We would probably have posted here on sage-coding-theory in any case quite soon if the ticket stayed unreviewed.

(I keep saying "we" since most of the work is carried out by David Lucas)

Best,
Johan

P Purkayastha

unread,
May 24, 2015, 7:45:13 PM5/24/15
to sage-codi...@googlegroups.com


On May 25, 2015 1:59 AM, "Vincent Delecroix" <20100.d...@gmail.com> wrote:
.


> In the current situation, Sage has an extra argument to initialize the minimum distance (curious but it is there). Since #18099, this argument is used to initialize the attribute _minimum_distance but then this attribute is completely ignored (since minimum_distance is now a cached_method and does not rely anymore on the attribute).
>
> So let me first say that before #18099, Sage was *not* computing the minimum distance. It only returned an integer that was stored as an attribute! So the timing used to be few micro seconds rather than few seconds.

This was introduced by me in #13090. I was working with lot of simulations of communication systems using modifications of well known linear codes and the first stumbling block was the very long time computing the minimum distance took.

Irrespective of how the linear codes are  implemented,  it would be immensely helpful if some basic stuff is fast. In my usage of linear codes I had come across the following issues:

* getting minimum distance of well known codes was very slow

* iterating through all codewords was very slow

* getting the n-th codeword in some sense of "n-th" was very slow

* decoding of codes was very slow. I am glad that the linear codes are becoming individual classes. That's how I handled decoding in my own work.

@lucas Please feel free to post in this group if you want feedback. I wasn't really free the past few months but I have a bit more time at hand now and will go through the tickets when I can.

Cheers,
   basu.

david.luca...@gmail.com

unread,
May 25, 2015, 6:07:00 AM5/25/15
to sage-codi...@googlegroups.com
Hello Sage-coding-theory users,

The main issue with the original coding theory structure is that everything is considered as a "generic" linear code. For instance, when one creates a specific code family (like Hamming codes, or Reed-Solomon codes), the program silently computes a generator matrix for this code, and then calls LinearCode with this generator matrix as an argument.

So, all the specific structure was lost, and of course only generic algorithms can be used on codes, which implies slowness in computations that should not be too slow.

As Johan said, we are trying to create a new structure, relying heavily on objects to allow more scalability and flexibility. Our main objective here is to write every code family as an object, in order to be able to use specific (which are often faster) algorithms for "daily basis" computations, like decoding. For instance, with this new structure, one will be able to decode Reed-Solomon codes using Berlekamp-Welch algorithm instead of using generic (and much slower) syndrome decoding algorithm. And it will solve this minimum_distance speed computation problem too, as every code family will get its own, fitted, method to compute it.

We posted a proposition for a new structure on encoding in #18376. After that, we also have a structure to handle decoding. Once all this work will be into Sage, we will be able to focus on code families, rewrite them as classes and thus get faster algorithms for these. And we of course want to enhance implementation of several methods for "generic" linear codes with that new structure.


> @lucas Please feel free to post in this group if you want feedback. I wasn't really free the past few months but I have a bit more time at hand now and will go through the tickets when I can.

Thanks a lot, I'll definitely do that! We really want to enhance the library in a way that will be useful for every user, whatever their field of interest (combinatorics, decoding...) so feedback will be really useful to be sure that what we are doing here is good for every people using coding theory in Sage.

Best,

David Lucas
Reply all
Reply to author
Forward
0 new messages