1
$\begingroup$

What is the minimal Hamming distance of $12$-error detecting code and $8$-error correcting code?

We know that a code is said to be $x$ error detecting if, and only if, the minimum Hamming distance between any two of its codewords is at least $x+1$ ($13$ in our case). In addition a code is $y$-errors correcting if, and only if, the minimum Hamming distance between any two of its codewords is at least $2y+1$ ($17$ in our case). Then the overall minimal Hamming distance of the code should be $17$. But I think we need an additional bit in order to distinguish between the case of detecting $3$ errors and correcting $1$ error. Another special case is correcting $2$ errors vs. detecting $5$, correcting $3$ errors and detecting $7$ errors, correcting $4$ errors and detecting $9$ and correcting $5$ errors and detecting $11$. Does this mean we need additional $5$ bits to account for additional $5$ special cases or we just need $1$ additional bit which will be enough for each special case?

$\endgroup$

1 Answer 1

2
$\begingroup$

The way to think about this is the following. Let $k_d$ be the number of errors you want to detect and $k_c$ be the number of errors you want to correct.

Any pair $(k_d,k_c)$ satisfying

$$ 2k_c+k_d+1\leq d_{min} $$ can be simultaneously detected and corrected, you do not need the extra bit. If you like you can think of an inner radius of $k_c$ for correction and an outer shell of $k_d$ for detection and an extra distance of $1$ to ensure separation. Let $c$ be a codeword and $c'$ be another at distance exactly $d_{min}$ away $$ \begin{array}{cccccc} codeword & \leftarrow~distance~\rightarrow & \leftarrow~distance~\rightarrow & \leftrightarrow & \leftarrow~distance~\rightarrow & codeword \\ \mathbb{c}& ~\cdots~k_c~\cdots & \cdots~ k_d ~\cdots & 1 & \cdots ~ k_c ~\cdots & \mathbb{c}'\\ \end{array} $$

In the two extremes, we have by letting $k_c=0$ (don't want to correct errors) $$ k_d+1\leq d_{min} $$ and by letting $k_d=0$ (don't want to detect errors) $$ 2k_c+1\leq d_{min}. $$

$\endgroup$
6
  • $\begingroup$ What is the meaning of the extra distance of $1$? Does this mean the answer would be $2k_c+1=17+1=18$? $\endgroup$
    – Yos
    Commented Jul 21, 2020 at 7:40
  • 1
    $\begingroup$ that's your $2y+1$ the 1 is not extra, it's the usual $1$ ensuring two spheres don't meet, which would destroy unique decoding. If you are correcting your 2 spheres of radius $y$ around the two codewords must be disjoint, thus an extra bit of 1 is needed to ensure this. going backwards, $d-1$ errors can be detected and $\lfloor (d-1)/2\rfloor$ can be corrected. $\endgroup$
    – kodlu
    Commented Jul 21, 2020 at 8:24
  • $\begingroup$ So the answer should be $2y+1$ or $2k_c+k_d+1$? $\endgroup$
    – Yos
    Commented Jul 21, 2020 at 8:44
  • $\begingroup$ I think the answer should be $12+8+1=21$ because if it's less than $21$ we can't know for sure if $x$ errors were detected or $y$ errors need to be corrected. What part of your answer says that? $\endgroup$
    – Yos
    Commented Jul 23, 2020 at 12:55
  • $\begingroup$ You decide what you want to correct. Then use the relationship to obtain how many you can detect. Or vice versa. $\endgroup$
    – kodlu
    Commented Jul 23, 2020 at 14:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .