[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.RTitleUserPersonal
Name
DateLines
894.1completing the thought...SSDEVO::LARYTue Jun 28 1988 00:373
Or, by analogy with CRC, is there a composite number R < 2**31 which has
that property?

894.2How about errors in the modulus?AKQJ10::YARBROUGHI prefer PiThu Jun 30 1988 17:1712
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.3CLT::GILBERTWed Jul 06 1988 16:5619
    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.4One answer...SSDEVO::LARYOne more thin gypsy thiefFri Jul 29 1988 23:5823
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 N*ln(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.5SSDEVO::LARYOne more thin gypsy thiefWed Aug 03 1988 04:5512
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...)