0
$\begingroup$

i wonder: how can i find minimal distance of a self correcting code in following situation: if we know that a code can fix every 3 errors(if not more than 3 errors, the word is recovered) and can detect every 5 errors(if between 3 and 5 errors, the algorithm will report that the error can not be fixed), how can we find its minimal distance?

i know that a code that fixes(hamming distance properties) $i$ number of errors costs a length of $2i+1$, and for detection of $i$ errors it costs a length of $i+1$. so the minimal length in this scenario is should been 7, but it cannot be 7 because distinguishing an error word E which can be obtained by discovering 5 errors or fixing 3 errors is undistinguisable in the following scenario: let a,b correct code words and E an erroronous word that can be obtained by 5 errors on the word x or by 3 errors from word y, so putting it like this makes it easier: x----E--Y, so it is not possible to distinguish between a word K that might have 3 errors or 5 errors in it, because its hamming distance from X or Y is the same. so, the minimal distance is 8.

what is the correct minimal hamming distance here?

**edit: please show me a formal and correct way to write the explanation why it cannot be 7 so i can learn correctly.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ A code can detect $i$ errors if its minimal distance is at least $i+1$. It can correct $i$ errors if its minimal distance is at least $2i+1$. These don’t “add up”! $\endgroup$ – Yuval Filmus Dec 2 '19 at 12:39
  • $\begingroup$ In particular, if you can correct $i$ errors, then you can detect $2i$ errors. $\endgroup$ – Yuval Filmus Dec 2 '19 at 12:40
  • $\begingroup$ In your case, you can only give a lower bound on the minimal distance, though not what you wrote. For example, consider a repetition code of length 7 (containing the two codewords 0000000 and 1111111). $\endgroup$ – Yuval Filmus Dec 2 '19 at 12:57
  • $\begingroup$ after my fix, can you please help me with a formal explanation on why 7 cannot be the minimal distance on this case? $\endgroup$ – alberto123 Dec 2 '19 at 14:52
  • 1
    $\begingroup$ I gave you an example of a code with minimal distance 7 that can correct any 3 errors and can detect any 5 errors (even any 6 errors!). $\endgroup$ – Yuval Filmus Dec 2 '19 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.