1
$\begingroup$

Is it possible to construct a [6,2] linear code that is two-error correcting?

I think I need to use this Theorem:

Suppose that C is a t-error correcting code in (Z_2)^8. Then order(C)*((n choose 0)+(n choose 1) +...+(n choose t)) is less than or equal to 2^n

  • 1
    Yes, you have the "correct theorem" to use in proving the result (except that you probably meant to type $\mathbb Z_2^6$ instead of $\mathbb Z_2^8$ and of course $n$ is $6$.2012-02-11

1 Answers 1

3

No. At least not, if you are talking about binary linear codes (which seems to be the case judging from everything else that you say). There are several ways of seeing that this is impossible. The result that you described is one of them. There are $ {6\choose 0}+{6\choose 1}+{6\choose 2}=22 $ binary vectors at distance $\le 2$ from a given codeword. So if you had 4 codewords in a double-error correcting binary code of length 6, then these 4 Hamming spheres sets of vectors should not intersect. Therefore between themselves they would cover a total of $4\cdot 22=88$ vectors. But there are only $2^6=64$ in the entire space $F_2^6$! Therefore this is impossible.

This also follows from the so called Griesmer bound stating that if a binary code of dimension $k$ has minimum distance at least $d$, then its length $n$ satisfies the bound $ n\ge \sum_{i=0}^{k-1}\lceil\frac{d}{2^i}\rceil. $ So if a 2-dimensional binary linear code can correct two errors, its minimum distance is at least $d5$, then its length must be at least $ n\ge \lceil\frac51\rceil+\lceil\frac52\rceil=5+3=8. $ The double-error correcting code in your other question is an example of a shortest possible binary linear double error correcting code that has 4 codewords.


Continue to read at your own peril:

Note: It is possible to find 2-dimensional double error correcting codes of length six over a larger alphabet. For example using suitably chosen Reed-Solomon codes you can shorten it to form a code with the properties:

  1. The codewords have six components, all of which are bytes (as opposed to bits like here).
  2. Two out of the six bytes carry information, and the remaining four are check bytes.
  3. The code can recover from any error, where at most two out of the six bytes are incorrectly received/read.
  • 0
    ... The e$x$ample code in your other question has similar repetitive blocks on len$g$ths three also. Furthermore, this [6,2,4]-code achieves the Griesmer bound. It is easy to check that you can always achieve the Griesmer bound when the dimension of the code is 2.2012-02-12