JSMCM
asked on
Modulo-2 arithmetic
Hello,
I need to do long division of one binary number by another, and I need the remainder. I know that in VB there is the Mod operator and in C it is the % operator.
The problem is that the division needs to use modulo-2 arithmetic, ie, no carries and no borrows.
The Mod and % operators use normal arithmetic, so the answer is not what I want.
A simple example follows:
What I need:
------------
1010 0
--------------------------
1011 |1001 1101
1011
----
010 1
000 0
-----
10 11
10 11
-----
0 000
0 000
-----
000 1
000 0
-----
00 1
I need to do long division of one binary number by another, and I need the remainder. I know that in VB there is the Mod operator and in C it is the % operator.
The problem is that the division needs to use modulo-2 arithmetic, ie, no carries and no borrows.
The Mod and % operators use normal arithmetic, so the answer is not what I want.
A simple example follows:
What I need:
------------
1010 0
--------------------------
1011 |1001 1101
1011
----
010 1
000 0
-----
10 11
10 11
-----
0 000
0 000
-----
000 1
000 0
-----
00 1
ASKER
Hi KDO
Thanks. This is not a homework assignment. Never even studied IT. I am working on some software that recieves messages from tags in a RF field. The reader (the device plugged into the PC which reads the tags), reads the tags and then sends the tag data to the PC via RS232. The tags transmit about 16 bytes of data which I need to calculate the CRC's on.
The above example is a simplified version of the long division required to work out the 16 bit CRC. I already have the CRC calculations working fine if I emulate a shift register, but this works out the CRC bit for bit, and on tags of 128 bits this may take too long because the tags are trasmitting at very high speeds. With the long division, the CRC is calculated one byte at a time which might save me some time.
The problem is that if I need to run through a whole lot of loops and things to manipulate the steps of the long division, I go back to "wasting" time.
Any input you may have with the limited info would be appreciated, for instance, should I just store the incomming tag data until all the tags have all been read (ie, there is no more tag data comming in after n milliseconds), then start calculating CRC, or should I try somehow to calculate CRC's as the data is comming in sothat any errors will be picked up straight away.
Thanks
John
Thanks. This is not a homework assignment. Never even studied IT. I am working on some software that recieves messages from tags in a RF field. The reader (the device plugged into the PC which reads the tags), reads the tags and then sends the tag data to the PC via RS232. The tags transmit about 16 bytes of data which I need to calculate the CRC's on.
The above example is a simplified version of the long division required to work out the 16 bit CRC. I already have the CRC calculations working fine if I emulate a shift register, but this works out the CRC bit for bit, and on tags of 128 bits this may take too long because the tags are trasmitting at very high speeds. With the long division, the CRC is calculated one byte at a time which might save me some time.
The problem is that if I need to run through a whole lot of loops and things to manipulate the steps of the long division, I go back to "wasting" time.
Any input you may have with the limited info would be appreciated, for instance, should I just store the incomming tag data until all the tags have all been read (ie, there is no more tag data comming in after n milliseconds), then start calculating CRC, or should I try somehow to calculate CRC's as the data is comming in sothat any errors will be picked up straight away.
Thanks
John
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
I found this by searching with Google for "Modulo-2"
http://www2.rad.com/networks/1994/err_con/modulo.htm
Good luck with your project!
http://www2.rad.com/networks/1994/err_con/modulo.htm
Good luck with your project!
Hmm... I'd convert it to a decimal ... and convert the divisor to a decimal .. divide them as two longs .. and then convert back out to binary...
pseudo:
str="101101"
t=0
for i=len(l) to 0 step -1
n=str[i]-'0';
t=t+n*10^i-1
next i
// ^^ will convert to decimal -- you work out the code
long n1,n2,result
result=(long)n1/n2 // think this will work been a while
long n
n=result
int ar[40]
i=0
do {
n=result/2
r=result%2
ar[i]=r
result=result/2
i++;
}
while (n>0);
print out ar reversed . . and you have the answer ..
convert it to a string ...
-- Rough pseudo...
// David
too long huh...
-David
pseudo:
str="101101"
t=0
for i=len(l) to 0 step -1
n=str[i]-'0';
t=t+n*10^i-1
next i
// ^^ will convert to decimal -- you work out the code
long n1,n2,result
result=(long)n1/n2 // think this will work been a while
long n
n=result
int ar[40]
i=0
do {
n=result/2
r=result%2
ar[i]=r
result=result/2
i++;
}
while (n>0);
print out ar reversed . . and you have the answer ..
convert it to a string ...
-- Rough pseudo...
// David
too long huh...
-David
use the xor function
If you are looking for a fast method fo computing CRCs, try http://www.lawrencechitty.uklinux.net/wizardwiki/index.php?fast%20CRC
It is for the polynomial x**0 + x**5 + x**12 + x**16
It is for the polynomial x**0 + x**5 + x**12 + x**16
I don't know of a built-in function to do this in any of the popular languages.
You already know the math and have described the process.
Since this appears to be a homework assignment, I can only suggest that all there is left to do is to write the program.
Kdo