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?
Best Answer
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}. $$