Check sums and error detection

s = “H88CMK9BVJ10” n = decode(s) r = n % 37 print(r) print(encode(n, checksum=True)) This produces 32 H88CMK9BVJ10* As we said above, a remainder of 32 is represented by *.ProofIf you change one character in a base 32 number, its remainder by 37 will change as well, and so the check sum changes.Specifically, if you change the nth digit from the right, counting from 0, by an amount k, then you change the number by a factor of k 2n..Since 0 < k < 32, k is not divisible by 37, nor is 2n..Because 37 is prime, k 2n is not divisible by 37 [1]..The same argument holds if we replace 37 by any larger prime.Now what about transpositions?.If you swap consecutive digits a and b in a number, you also change the remainder by 37 (or any larger prime) and hence the check sum.Again, let’s be specific..Suppose we transpose the nth and n+1st digits from the right, again counting from 0..Denote these digits by a and b respectively..Then swapping these two digits changes the number by an amount(b 2n+1 + a 2n) – (a 2n+1 + b 2n) = (b – a) 2nIf a ≠ b, then b – a is a number between -31 and 31, but not 0, and so b – a is not divisible by 37..Neither is any power of 2 divisible by 37, so we’ve changed the remainder by 37, i.e..changed the check sum..And as before, the same argument works for any prime larger than 47.Related postsCrockford’s base 32 encodingErasure coding[1] A prime p divides a product ab only if it divides a or it divides b..This isn’t true for composite numbers.. More details

Leave a Reply