# What is the minimal Hamming distance of $x$-error detecting code and $y$-error correcting code?

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?

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

• What is the meaning of the extra distance of $1$? Does this mean the answer would be $2k_c+1=17+1=18$?
– Yos
Commented Jul 21, 2020 at 7:40
• 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. Commented Jul 21, 2020 at 8:24
• So the answer should be $2y+1$ or $2k_c+k_d+1$?
– Yos
Commented Jul 21, 2020 at 8:44
• 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?
– Yos
Commented Jul 23, 2020 at 12:55
• You decide what you want to correct. Then use the relationship to obtain how many you can detect. Or vice versa. Commented Jul 23, 2020 at 14:16