I am struggling to find how can I know the number of errors that can be corrected and detected using (n=10) bit code with a (k=550) codewords. As far as I know, to calculate the number of errors to be corrected and/or detected someone must know the Hamming distance between 2 codewords. However, I do not have any relevant information to find out a solution to this question. I tried to calculate the efficiency of this code using the formula: (E = Number of original message bits / length of the codeword). The efficiency in my case is 1/5. But, I do not know how can I use this information to calculate the number of errors that can be corrected and detected.
$\begingroup$
$\endgroup$
4
2 Answers
$\begingroup$
$\endgroup$
2
There are $2^{10}$ binary strings of length $10$. We can partition them into pairs $x_1\ldots x_90,x_1\ldots x_91$. Since your code contains more than $2^9$ codewords, it will contain at least one such pair. Hence the minimum distance of your code is only $1$.
answered Dec 2, 2020 at 7:30
-
$\begingroup$ If the minimum distance is 1. Therefore, no errors can be corrected and/or detected. Am I right? $\endgroup$ Dec 2, 2020 at 13:37
-
$\begingroup$
$\endgroup$
While the Hamming distance is used in general to determine the number of bit errors that can be detected or corrected, this particular problem is a degenerate case where the code is so large that the Hamming distance of the code is 1.
More specifically, the set $\{0,1\}^{10}$ of all 1024 10-bit strings can be partitioned into 512 subsets of the form $\{a,b\}$, where $a,b \in \{0,1\}^n$, $a$ contains a 0 in the first position and $b$ contains a 1 in the first position, and $a$ and $b$ have the same values in the other positions. Thus, the Hamming distance between two codewords in the same subset is exactly $1$.
If the codebook has 550 codewords, then by the pigeonhole principle some two codewords must belong to the same subset, i.e. must have a Hamming distance between them of only 1. This means, if even one bit is flipped, the receiver will not be able to decode the transmitted signal correctly. Hence, this code does not have any error detection (or correction) capability.
E = 1/5? The numbers don't seem to fit. $\endgroup$the number of original message bits is 2that sounds extremely unlikely - there would be exactly four messages possible. Can you quote or at least hyperlink the original problem? $\endgroup$