how to calculate minimum distance of a code minus a subcode

Question

I have a linear binary code $C$ with generators $(G_1,\cdots,G_a,G_{a+1},\cdots G_k)$.

$C$ has a subcode $C_a$ with generators $(G_1,\cdots,G_a)$.

I'd like to get the minimum weight of all codewords in $C$ that are not in $C_a$.

[Edit : minimum distance in original question changed to minimum weight]

Is there a way to get this without listing elements?

I'm tagging abelian groups and GAP since this can be viewed in a group setting too : I think this translates to looking at cosets of $C_a$ in $C$ and taking a representative (or "leader") of minimum weight.

An example for the Jyrki's answer : first 8 rows are for $C_a$ (so $r=2$)

[[1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
 [0,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,0,0,0],
 [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0],
 [1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1],
 [0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,1,0,1]]

$d_{min}(C)=4$ but $d_{min}(C-C_a)$ is known to be $6$ using other methods (brute force listing of elements). Note that this code is "degenerate" : it doesn't have unique columns (21 unique columns out of 27). The codes I tried that Jyrki's answer works for have unique columns.

Answer 1

A reminder: In general the question whether a linear code has non-zero words of Hamming weight below a given threshold is a difficult one. Alex Vardy proved it to be in one of those nasty complexity classes (NP-hard, NP-complete, ..., I don't know for sure). GAP/GUAVA can work with small codes easily enough, and the weight enumerators of some classes of codes with a rigid algebraic structure are known, but in general the outlook is grim.

---

The following observation can be done though. The result is that the minimum distance of $C\setminus C_a$ is equal to the minimum distance of one of the codes. The choice depends on the codimension that I denote by by $r=\dim C-\dim C_a$, so $r=k-a$.

• If $r=1$, then the complement $C\setminus C_a$ is just a single coset of $C_a$. As translation by a fixed vector is an isometry of the Hamming space, the distance distribution of $C\setminus C_a$ is identical to that of $C_a$. In particular, $d_{min}(C\setminus C_a)=d_{min}(C_a)$.
• If $r>1$, then $d_{min}(C\setminus C_a)=d_{min}(C)$. This can be shown as follows. Let $c\in C$ be a word of minimal (non-zero) Hamming weight $d_{min}(C)$. There are at least four cosets of $C_a$ in $C$. This means that there exists a coset $x+C_a\neq C_a$ such that the coset $c+x+C_a$ isn't equal to $C_a$ either. After all, translation by the word $c$ either permutes the cosets of $C_a$ in 2-cycles, or maps all the cosets to themselves (the latter case happens when $c\in C_a$). But both words $x,c+x\notin C_a$, and their distance is equal to the weight of $c$, that is, equal to $d_{min}(C)$. Obviously the minimum distance cannot be lower than that so we are done.