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$
3
  • $\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, 2018 at 20:20
  • $\begingroup$ The rule is one question per post. Your two questions are completely unrelated. $\endgroup$ Jan 25, 2018 at 21:45
  • 3
    $\begingroup$ Possible duplicate of Minimum hamming distance of multiple binary words $\endgroup$ Jan 25, 2018 at 22:16

1 Answer 1

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 and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.