I think its related to the problem of computing the smallest weight basis of a matroid.
As i worked with low density parity check codes, computing the sparsest generator matrix of a linear code is an open problem and until now an algorithm for this propose is not introduced.
Assuming you are only interested in algorithms with feasible complexity :-) I hazard a guess that this is very difficult. A related problem of proving that a code has a word with weight below a given bound is proven to be in some nasty NP-category. I have this vague recollection that someone (Alex Vardy?) proved that another related problem of minimizing the trellis of a linear block code is similarly nasty, but I may be wrong about that.
Hi Jyrki, there is a greedy algorithm that solves the problem. The preprocessing is exponential as it requires ordering all codeword by increasing Hamming weight. This is the analogy with matroids I mentioned. Now is there something smarter, faster?
Hi Patrick, this is also known as the null space problem. You are right in that the preprocessing is exponential in the parameters. There has been work done by Coleman and Pothen, "The Null Space Problem I. Complexity" and "The Null Space Problem I. Algorithms".
I think this is a fundamental question. Clearly one should solve it for codes of dimension 2, then dimension 3, and so on.
As already mention, the problem is at least as hard as finding the minimum weight of the code. Hence one could use a general algorithm for computing the minimum weight that at the same time collects the words of minimum weight. If those don't span the code, one has to go to the next weight and so on.
This is related to the strategy used form some implementation of Leon's algorithm to compute the automorphism group of a linear code. As in intermediate step, Leon considers the action on words of constant weight, and if they don't span the code, a lot of backtracking is needed. I recall that early implementations of the Leon's algorithm in MAGMA faced that problem. So later a check was added whether the words of given weight span the code.
i think that the first condition of given sparsest generator matrix should be clear up.For this reason you should given rank of a matroid M that for a given base B of M we have card(B) is at most equal to r.
i put in a proposal to see my summary second paper.i hope be beneficial to you.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms