# Binary code and Hamming distance

I'm learning about CRC and Hamming distance and I have three questions. Lets say we have binary code described by ($+$ refers to sum modulo $2$):

\begin{alignat*}{1} a_1 &+ a_2 &+ a_3 &+ a_4 &+ a_5 &= 0\\ a_6 &+ a_7 &+ a_8 &+ a_9 &+ a_{10} &= 0\\ a_1 &+ a_6 &+ a_{11} &&&= 0\\ a_2 &+ a_7 &+ a_{12} &&&= 0\\ a_3 &+ a_8 &+ a_{13} &&&= 0\\ a_4 &+ a_9 &+ a_{14} &&&= 0\\ a_5 &+ a_{10} &+ a_{15} &&&= 0 \end{alignat*} We received: $11011\ 01010\ 10111$

So if I would like to check minimal Hamming distance, then I should compare each codeword with others, right?

$\begin{pmatrix} 1&1&1&1&1& & & & & & & & & & \\ & & & & &1&1&1&1&1& & & & & \\ 1& & & & &1& & & & &1& & & & \\ &1& & & & &1& & & & &1& & & \\ & &1& & & & &1& & & & &1& & \\ & & &1& & & & &1& & & & &1& \\ & & & &1& & & & &1& & & & &1\\ \end{pmatrix}$

I have done so, and minimal Hamming distance $= 6$. Is there any faster method?

Second question: how many distortions causing undetectable errors? Is there any formula for that?
And last one, how to compute redundancy using above information. I'm using formula:
$R = \dfrac{n-k}{n}$. In above example $n=15$, but I don't understand how to obtain $k$.

• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
– Raphael
Jan 24, 2018 at 20:20
• The rule is one question per post. Your two questions are completely unrelated. Jan 25, 2018 at 21:45
• Possible duplicate of Minimum hamming distance of multiple binary words Jan 25, 2018 at 22:16

## 1 Answer

In a linear code, the minimum distance is the same as the minimum weight of a non-zero codeword. It's a nice exercise to prove this, and reduces the computation time quadratically.

Computing the minimum distance of a code given the generator matrix (or the parity check matrix) is NP-hard, that is, given a generator matrix (or a parity check matrix) and an integer $w$, it is NP-complete to determine whether the minimum distance of the code generated by the matrix is at most $w$. The task could become easier if the code has some structure, but for arbitrary codes it is quite difficult.