Error Correcting Codes

354 Views Asked by At

Let $C$ be the two-error correcting code: $\{(00000000),(11100011),(00011111),(11111100)\}$ in $( \Bbb 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?

1

There are 1 best solutions below

2
On BEST 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!