# Linear Code in Cryptography

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

-
Surely coding-theory is a more appropriate tag for this question? – Jyrki Lahtonen Feb 11 '12 at 22:06
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$. – Dilip Sarwate Feb 11 '12 at 22:26

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.

To add to Jyrki's excellent answer, the Hamming bound that the OP said he thought he needed to use (and Jyrki filled in the details) actually shows that no binary code (whether linear or nonlinear) with $4$ codewords of length $6$ can correct $2$ errors. – Dilip Sarwate Feb 11 '12 at 22:27
>Why do you assume there are 4 codewords? Because the terminology $[n,k]$ linear binary code usually means a code with $2^k$ binary vectors of length $n$ that constitute a $k$-dimensional subspace of $\mathbb Z_2^n$. Older books also used $(n,k)$ instead of $[n,k]$ but in more modern texts, a $[n,k]$ code is linear (or at least has $2^k$ or $q^k$ codewords) while a $(n,M)$ code means $M$ vectors (of length $n$) that do not necessarily constitute a linear code. – Dilip Sarwate Feb 12 '12 at 1:45