Given a residue code representing a number N with the tuple (N, R(N))where R(N) equals N mod A.

What is the error detection distance of a certain check base A? In other words, how many bits can be flipped but still detect an error?

Edit: I would think the minimum distance is 2 for any base. Consider a base A > 2. If N equals 1, R(N) also equals 1. If we now look for for N+1 = 2, R(N) equals 2. The Hamming distance between those residue tuples is HD((1, 1), (2, 2)) = 2, which cannot be better.

  • 1
    $\begingroup$ What do you think? What have you tried, and where have you failed? We're not here to do your homework, we're here to help you do it on your own. $\endgroup$ – Yuval Filmus Feb 20 '17 at 12:26
  • $\begingroup$ @YuvalFilmusI updated my question with thoughts of mine. $\endgroup$ – Thomas U. Feb 20 '17 at 12:56
  • $\begingroup$ If A is a power of two then the minimum distance is 1. For example A = 4, N = 1 and N = 5, R(N) = 1 in either case. $\endgroup$ – gnasher729 Feb 20 '17 at 13:39
  • $\begingroup$ HD((1,1), (2,2)) = 4. There are four single bit changes. Check N = 2 and N = 3 instead. $\endgroup$ – gnasher729 Feb 20 '17 at 13:40
  • $\begingroup$ If no power of two is divisible by A, then a single bit change in N creates at least a single bit change in R(N), so minimum distance ≥ 2. On the other hand, R(0) = 0, R(1) = 1, so the minimum is achievable. $\endgroup$ – gnasher729 Feb 20 '17 at 13:43

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.