Suppose the original code is a 2-bit binary coding with 3 possible alphabet. \begin{align} a&\rightarrow 00\\ b&\rightarrow 10\\ c&\rightarrow 11 \end{align}
Is that $\operatorname{Hamming}(7,4)$ coding? Isn't 7-bit too long?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Hint: look into repetition coding. $\endgroup$– MBazCommented Dec 16, 2020 at 14:48
-
$\begingroup$ Like, repeat 3 times? So it's 6 bits long？I'm not sure if it has the same property with hamming code... $\endgroup$– RUAAACommented Dec 16, 2020 at 17:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
In order to correct 1-bit errors, we need to have a Hamming distance (the number of bits that must be flipped) of 3 between all the symbols: when we flip one bit at random, then flipping another bit by random must either get us back to the original symbol (if the same bit was flipped twice) or an invalid symbol.
With only two symbols we can encode as 000 and 111 because this gives us the required Hamming distance, so clearly we can encode 3 symbols with 6 bits. Can we can do better though?
If we use 4 bits to encode one symbol as 0000 then 3 flips result in 0111, 1011, 1101 or 1110. These all differ from each other by no more than 2 bits, so clearly 4 bits is not enough.
On the other hand, if we use 5 bits to encode one symbol as 00000 then 3 flips give us 00111, 01011, 01101, 01110, 11100, 11010 and 11001. If we then encode the 2nd symbol as 00111, we're left with the following valid choices for the 3rd symbol: 11100, 11010 or 11001. These are all distance 3 from the first symbol and distance 4 from the second symbol.
So one of the many possible encodings for 3 symbols using 5 bits is: a = 00000, b = 00111, c = 11100.
