How many errors will detect and how many will correct the code with the following set of all code words:
a) $(00000), (01011), (10101), (11110)$
b) $(000000), (010101), (101010), (111111)$
I have task like this in my discrete mathematics set of tasks and I am bit confused. I have tried to read lecture notes, however I still don't have any idea how to start it. Can someone guide me?
A code can detect $k$ errors if when any $k$ bits are changed in any of the words, we get something that is outside our code. For example, we can see that your code $b$ cannot detect 3 errors, because by changing three bits, you can turn the first word into the second. However, if you change any two bits in any of the four words, you will get something that is not a code word, and thus be able to detect an error.
Go through code $a$ and see if you can find a code word that you can turn into another by changing two bits. If so then you can detect at most one error. If not then you can definitely detect two, and can check for three.
Correction is more complicated. Imagine you round off any code word that's off by a single bit in code $b$. This means that if your string is one bit away from a code word, you replace it with the code word. Thus you could turn 00001 into 00000, since that is the only way to turn that message into one of your words by changing only one bit. Thus we can correct any one error in $b$ as there is no word that could get rounded off by changing a single bit into two different words. We can't correct two errors, since if we got say $10001$, instead of the intended $00000$, we wouldn't know if that came from $10101$ and had only one error.
There are tricks for doing this in the case of a linear code. Both of your codes are linear in the sense that if you add any two code words, you get another code word. This is because $1+1=0$ in $\mathbb{Z}_2.$
Here you can take the non-zero word with the smallest number of 1's and call that number the Hamming weight for your code. The weight of codes $a$ and $b$ are both three since we cannot get fewer than three 1's in a word that is not all zeroes.
So what can you do with the Hamming weight? One can prove that in a code with weight $k$ you can always detect $k-1$ errors. This is because if you could turn $v$ in $w$ changing fewer than $k-1$ bits, then you can turn $v-w$ into $w-w$ by changing fewer than $k$ bits. This means you can change $v-w$ into the zero vector in less than $k$ changes, but we already said that the least number of 1's was $k$, a contradiction.