[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:	Mathematics at DEC

Moderator:	RUSURE::EDP

Created:	Mon Feb 03 1986
Last Modified:	Fri Jun 06 1997
Last Successful Update:	Fri Jun 06 1997
Number of topics:	2083
Total number of notes:	14613

894.0. "Using remainder mod P as an error detection code" by SSDEVO::LARY () Tue Jun 28 1988 00:33

A number A is a primitive root of a prime P if there is no K < P-1
such that A**K = 1 (mod P).

Note that if A is a primitive root of P then A**((P-1)/2) = -1 (mod P),
and no K < (P-1)/2 satisfies A**K = -1 (mod P).

A practical application of this is: take a large prime P that has 2 as
a primitive root, then you can divide a large bit string by P and use the
remainder as an error-detecting code that will detect any pair of
single-bit errors in the bit string, provided the bit string is less than
(P-1)/2 bits long.

This is because the four permutations of two single-bit errors change the
numerical value of the bit string by +-(2**k+-1) * 2**r [+- means "plus or
minus", I'm on an old terminal] where r is the position of the first bit in
error and k is the difference between the bit positions of the two errors,
and none of these values is divisible by P.

This is kinda useful, since VAXen that don't implement CRC do implement EDIV,
and EDIV can be faster than a software-implemented CRC. However, a good CRC
polynomial (e.g. all of the commercial ones) will also detect any trio of
single-bit errors in a message, because it multiplies a primitive irreducable
polynomial (a GF(2) analogue of "a prime that has 2 as a primitive root") by
a "parity polynomial" which detects any odd number of bits in error.

My question, after all this long-winded introduction, is: for reasonable
message lengths (4096 bits is reasonable, more is better) is there a
prime P < 2**31 such that the operation of "divide by P and take the remainder"
generates a code that will detect any trio of single-bit errors?

T.R	Title	User	Personal Name	Date	Lines
894.1	completing the thought...	SSDEVO::LARY		`Tue Jun 28 1988 00:37`	3
	Or, by analogy with CRC, is there a composite number R < 2**31 which has that property?
894.2	How about errors in the modulus?	AKQJ10::YARBROUGH	I prefer Pi	`Thu Jun 30 1988 17:17`	12
	On of the nice things about a CRC code is that one can concatenate the 'message' with the error code and catch 3-bit errors in the concatenated string, e.g. 2 bits in the message and 1 bit in the CRC code. While it may be possible to get the same result with a prime modulus, my guess is that the analysis [to prove that errors in the modulus, as well as in the message, are always caught] will be horrendous. The approach I would take would be to start with some small message lengths and do an exhaustive analysis for several primes, just to get a feel for the complexity of the cases. Lynn
894.3		CLT::GILBERT		`Wed Jul 06 1988 16:56`	19
	My gut feeling says that this is easy. Choose a value for P and test it as follows: Check that 2 is a primitive root of P. Check that { 2^a mod P, -2^a mod P \| 0 <= a < 4096 } has 2*4096 distinct values. This guarantees that neither 2^b + 2^a nor 2^b - 2^a is a multiple of P. Alternately, you could check that neither 2^a + 1 nor 2^a - 1 is a multiple of P (since you've already determined that 2 isa primitive root of P). Check that none of the following are multiples of P: 2^b + 2^a + 1, 0 < a < b < 4096 2^b + 2^a - 1, 0 < a < b < 4096 2^b - 2^a + 1, 0 < a < b < 4096 2^b - 2^a - 1, 0 < a < b < 4096 I think there must be a better approach to error detection than taking the bit string modulo P, but that wasn't the question, was it? :^)
894.4	One answer...	SSDEVO::LARY	One more thin gypsy thief	`Fri Jul 29 1988 23:58`	23
	If remainder mod 2147483613 (= 2^31-35) (=3x11x2953x22037) is used, the resulting code detects all triple errors in strings up to ~69000 bits long. The program that found this was a variant of .3; it computes all the values of 2^a mod P and -2^a mod P for 0<=a<=message length, then it sorts these values and compares adjacent pairs to see if they are equal or different by 1. This reduces the N^2 complexity of .3 to Nln(N) complexity, where N is the message length, but it still takes a second or two of VAX 8700 time to check each number. The program also checks if P is prime and, if so, if it has 2 as a primitive root; interestingly enough, the first value found (searching backwards from 2^31-1) is neither. In answer to .2: yes, this is a problem, but I believe it is easily solved; instead of appending the remainder mod P to the message, you append a bit string to the message that makes the remainder mod P of the extended message equal to 0; then as long as the extended message falls within the limits of the code you are OK. In this case, you do this by finding the remainder R of (message 2^31) mod P and appending the 31-bit quantity P-R to the message. I'll run a more exhaustive check this weekend to find other values of P, and then code the routine up and compare it against software CRC...
894.5		SSDEVO::LARY	One more thin gypsy thief	`Wed Aug 03 1988 04:55`	12
	Best modulus so far: 2145833891 = 17 * 2131 * 59233, protects against triple errors in strings up to 271448 bits long. That's a lot longer than I expected, because in the absence of any principle, the probability of finding adjacent elements in {2^i mod N} is a function related to the "birthday" function and should go to 1 VERY rapidly as the cardinality of the set goes above sqrt(N), but the distribution is not like that at all. So there's some number-theory principle at work, but I'll be damned if I know what it is. (The bad news is I coded up the EDIV-based routine and it runs no faster than the best software CRC, at least on an 8700 - no big gains here. Oh well...)