1. This is very interesting to me. The Python part of the algorithm in SAGE is in coding/linear_codes.py. It is essentially a wrapper for a function written in GAP and C written by Steve Linton: http://modular.math.washington.edu/gap/Manuals/doc/htm/ref/CHAP023.htm#SSEC005.5
The function* AClosestVectorCombinationsMatFFEVecFFE *does all the work. As the name suggests, it returns a vector in a vector space over a finite field which is closest to a given vector but there are several parameters to play with which the documentaiton explains. It is what you might call a brute force algorithm. You can grep the GAP library (this is a "GAP kernel" function not a GUAVA function) to find where it is exactly if you want to read the C and GAP code for it. 2. I don't know C well enough but would like a modification to* AClosestVectorCombinationsMatFFEVecFFE* which returns all codewords of distance d to a given vector. (So that would be 2 modifications: (1) instead of "closest" vector, the Hamming distance should be a given integer d, (2) instead of just finding one, find all such codewords.) This modification might require using DistancesDistributionMatFFEVecFFE to determine the number of distance d codewords desired and then searching until the desired number of codewords is found. I don't even mind if your implementation requires inputing the number of codewords desired. (So the user would have to know the weight distribution of the code in advance.) 3. MAGMA's algorithm is faster and more sophisticated but you can't read the C code anywhere as far as I know. Some hints are in some talks by Markus Grassl http://iaks-www.ira.uka.de/home/grassl/ who I think writes most of their coding theory programs. I get the impression that it first dicides what kind of code it is (cyclic, for example), then puts the code in "standard form", then (if the code is long, ie n is large compared to k) it plays some tricks with the generator matrix. These tricks are described in his paper "Searching for good linear codes" which you can find it here: http://iaks-www.ira.uka.de/home/grassl/Academia/Algo-Gruppen-Codes-2003/ I actually thought of this trick before I read his paper but could not get a fast or elegant implementation working in GAP. I thnk he deserves a lot of credit for making it work so fast and writing such a nice description of the idea. ++++++++++++++++++++++++++++++++++++++++++++++++++++ Pere Urbón Bayes wrote: > Hello to every body, I know that this problem is NP ... but how about > the existing algorism? Is there any thing?. I mean this because one of > my interest in sage will be to provide our software with a lib that > could work eficiently with this problem. > > Regards, > > --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
