# 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.

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.
-
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
This is all very interesting stuff, I appreciate the help with all of this. I'm guessing applications such as maple and matlab would be good for playing around with these types of codes. –  Jackson Hart Feb 11 '12 at 23:07
Why do you assume there are 4 codewords? What if it were 2 codewords? Then it might work, right? –  Jackson Hart Feb 11 '12 at 23:11
>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
@Jackson: A 2-dimensional binary linear code (or any binary code with 4 words) is so small that you can play with them without any CAS. If we look at 2-dimensional codes of length 6, then the best code (in terms of minimum distance) is {000000,111100,110011,001111}. You see that its minimum distance is four, so it can correct one error and detect two. Notice two further things: the bits here are in groups of two so that the second bit always the same as the first, the fourth the same as the third, ditto the sixth and the fifth. –  Jyrki Lahtonen Feb 12 '12 at 7:20