Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

up vote 0 down vote accepted

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!

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.