2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Raphael Jan 24 '18 at 20:20
  • $\begingroup$ The rule is one question per post. Your two questions are completely unrelated. $\endgroup$ – Yuval Filmus Jan 25 '18 at 21:45
  • 3
    $\begingroup$ Possible duplicate of Minimum hamming distance of multiple binary words $\endgroup$ – David Richerby Jan 25 '18 at 22:16
1
$\begingroup$

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.

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