3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. Can you please spell out how to arrive at E = 1/5? The numbers don't seem to fit. $\endgroup$
    – greybeard
    Dec 2, 2020 at 8:49
  • $\begingroup$ E= 2/10 =1/5; since the number of original message bits is 2(binary can be 0 or 1). $\endgroup$ Dec 2, 2020 at 10:18
  • $\begingroup$ You misunderstood what is meant by original message bits. This means the main terms that can be used to construct a set of codewords can be either 0 or 1. For example, 0010110010, 1100101100, 0101001110 are considered to be 3 codewords of 10 bits with a 2 as an original message bits. $\endgroup$ Dec 2, 2020 at 10:33
  • $\begingroup$ the number of original message bits is 2 that sounds extremely unlikely - there would be exactly four messages possible. Can you quote or at least hyperlink the original problem? $\endgroup$
    – greybeard
    Dec 2, 2020 at 20:57

2 Answers 2

0
$\begingroup$

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$.

$\endgroup$
2
  • $\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$ Right, the code is useless. $\endgroup$ Dec 2, 2020 at 14:15
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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