3
$\begingroup$

A pretty well-known theorem regarding linear $(n,k,d)$ codes is that every $n-d+1$ coordinate positions contain an information set, but not all $n-d$ coordinate positions do. This is equivalent to a codeword always being able to handle $d-1$ erasures, but only sometimes more than that.

If any choice of $k$ coordinates is an information set, then the code is MDS. I've been searching pretty vigorously for results on the maximum number of information sets for a linear code but I've not found much. I'm guessing an exact answer is NP-complete, but even bounds are hard to find.

For a given linear $(n,k)$ code, the number of possible size $k$ subsets is $\binom{n}{k}$. I'd like to know how many of these can possibly be information sets.

References or reductions to equivalent problems would also be nice - notice that this problem is equivalent to finding the number of invertible $k \times k$ submatrices of a binary $k \times n$ matrix. This may be a well known problem in the CS community but my searches have turned up nothing...

Improve this question
$\endgroup$
3
  • $\begingroup$ Is this perhaps better suited for MathOverflow...? $\endgroup$
    – Benjamin Lindqvist
    Commented Mar 29, 2016 at 9:55
  • 1
    $\begingroup$ Some elementary related discussion. Probably you know all that - in particular the connection to the dual code. The probability for a random set of $k$ column vectors being linearly independent is known. That might give you a ball park figure? $\endgroup$
    – Jyrki Lahtonen
    Commented Mar 29, 2016 at 13:55
  • $\begingroup$ That's a nice link, but the problem is that I want a bound rather than an approximation. Maybe I could massage the problem statement so that I can use an approximation instead, but I'm not sure... $\endgroup$
    – Benjamin Lindqvist
    Commented Mar 29, 2016 at 14:14

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .