• Status: Solved
• Priority: Medium
• Security: Public
• Views: 1785

# 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

0
JSMCM
1 Solution

Data Warehouse Architect / DBACommented:

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
0

Author Commented:
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
0

Data Warehouse Architect / DBACommented:
Cool.  (Sure looked like homework.  :) )

I'm going to make a couple of assumptions regarding the statement that the data is coming in via RS232 (a serial port).

* You're dealing with raw data.  (If a ^H is embedded in the stream it really represents an 0x08 and not a backspace.)

* I assume that you have your own interrupt handler and are grabbing the data as it arrives.

The first item is key.  Since you don't have to backspace (erase/delete a character) you can build the checksum on the fly.

And since you already have a custom interrupt handler, it's a piece of cake to build the checksum as each character arrives.  With the speed of today's machines this is probably the way to go.  There are a lot of "free cycles" between serial port interrupts so you'll be putting them to good use.  If fact, there may NOT be enough free cycles to checksum the entire buffer between interrupts.

I'd set up the handler to manage an arbitrary number of buffers.  (Start with 4.  8 or 16 may later prove advantageous.  And be careful about naming.  There are a number of C/C++ items that contain "Stream" in the name.)

typedef struct
{
int StreamLength;
unsigned char Buffer[MAX_STREAM_LENGTH];
int CheckSum;
bool BufferFull;
} TMyStream;

TMyStream MyStream[4];
int       StreamIndex;
int       NextStream;

MyStream.BufferFull is the interrupt handler / application lock.  When it is false, only the interrupt handler can modify fields in the MyStream[].  When it is true, only the application can modify fields in the MyStream[].

As data comes in via the serial (RS232) port, the interrupt handler stores it at:

MyStream[StreamIndex].Buffer[MyStream[StreamIndex].StreamLength++]

When the buffer is full, the handler sets:

MyStream[StreamIndex].BufferFull = true;
StreamIndex = (StreamIndex+1) % 4;

Then within the application you are free to check the BufferFull flags and process the buffers when appropriate.  Remember to set BufferFull to false when the application has completed processing the buffer.

I assume that the order of the buffers is important.  If you're not using signals, then the application must "poll" the Streams to see when one is available for processing.  NextStream is used by the application to know which buffer will fill next. Just query:

MyStream[NextStream].BufferFull;

Hope this helps,
Kdo
0

Commented:
I found this by searching with Google for "Modulo-2"

0

Commented:
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

0

Commented:
use the xor function
0

Commented:
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
0

## Featured Post

Tackle projects and never again get stuck behind a technical roadblock.