number of errors in a binary code

Question

To transmit the eight possible stages of three binary symbols, a code appends three further symbols: if the message is ABC, the code transmits ABC(A+B)(A+C)(B+C). How many errors can it detect and correct?

My first step should be to find the minimum distance, but is there a systematic way to find this? Or do I just try everything?

Answer 1

This is a linear code with the generator matrix

$$ G = \begin{pmatrix} 1&0&0 & 1&1&0\\ 0&1&0 & 1&0&1\\ 0&0&1 & 0&1&1\\ \end{pmatrix} $$

For linear codes, the minimum distance between two distinct codewords is equal to the minimum nonzero weight of a codeword. Since your code only has $2^3$ codewords, you can just write them out (i.e., compute $xG$ for each $x \in \mathbb{Z}_2^3$).

In this related question; azimut describes a quicker algorithm.

---

By the way, if you're just interested in computing the minimum distance (but not how), Sage has a nice coding module:

sage: MS = MatrixSpace(GF(2), 3, 6)
sage: G = MS([ [1,0,0,1,1,0],
....:          [0,1,0,1,0,1],
....:          [0,0,1,0,1,1] ])
sage: C = LinearCode(G)
sage: C.minimum_distance()
3

Answer 2

The code is linear and there are seven non-zero words, so the brute force method of listing all of them is quite efficient in this case. You can further reduce the workload by observiing that the roles of $A,B,C$ are totally symmetric. What this means is that you only need to check the weights of the words where you assign one, two or all three of them to have value $1$ (and set the rest of them equal to zero). Leaving that to you, but it sure looks like the minimum distance will be three, and hence the code can correct a single error.

In general the Yes/No question: Does a linear code with a given generator matrix have non-zero words of weight below a given threshold? has been proven to belong to one of those nasty NP-complexity classes (NP-hard? NP-complete? IDK), so there is no systematic efficient way of doing this.