# Error Correcting Codes

Let $C$ be the two-error correcting code: $\{(00000000),(11100011),(00011111),(11111100)\}$ in $(Z_2)^8$.

Then it says to find two vectors that are correctable to a codeword in $C$ (of bit length $1$ and $2$).

I think that since $t=2$, my two vectors could be: $(00000001)$, and $(00000011)$

Then it asks for two vectors that are at least three bit errors from a codeword in $C$, but are uniquely correctable to a codeword in $C$.

Should I use the nearest neighbor policy here?

-
I put the cryptography tag back in there, because you originally had it. I just don't see any cryptography here, but that may be just me :-) – Jyrki Lahtonen Feb 11 '12 at 22:10

## 1 Answer

Yes. "Unique correctability" of the received vector $y$ means that there is a unique closest vector of $C$ to $y$ in terms of the Hamming distance.

In this case the question asks for a vector at distance exactly $3$ from one of the codewords, and at distance $>3$ from all the others. Because your code is linear you might as well look for a word at distance $3$ from the all-zeros vector and at distance $>3$ from all the others.

As a further hint: Notice how the 8 bit positions have been partitioned into three subsets in such a way that for all the codewords either all the bits within a subset are set ($=1$) or all are off ($=0$). Also, the bits on an even number (two or none) of subsets are always set. If you toggle one bit per subset, then check what happens!

-
Ok, so how many codewords of one or two bit errors are there from a codeword in C? Is it just 4*[(8 choose 1)+(8 choose 2)]? – Jackson Hart Feb 11 '12 at 21:33
@JacksonHart: Yes, that is correct. The minimum distance of this code is five, so the Hamming spheres of radius two centered at all the codewords won't overlap at all. – Jyrki Lahtonen Feb 11 '12 at 21:36