Solved

# Modulo-2 arithmetic

Posted on 2003-03-04
Medium Priority
1,768 Views
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
Question by:JSMCM
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 46

Expert Comment

ID: 8063979

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

LVL 2

Author Comment

ID: 8064291
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

LVL 46

Accepted Solution

Kent Olsen earned 300 total points
ID: 8064522
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

Expert Comment

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

0

Expert Comment

ID: 8065991
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

LVL 84

Expert Comment

ID: 8070677
use the xor function
0

LVL 11

Expert Comment

ID: 8096756
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

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article is meant to give a basic understanding of how to use R Sweave as a way to merge LaTeX and R code seamlessly into one presentable document.
Whether you’re a college noob or a soon-to-be pro, these tips are sure to help you in your journey to becoming a programming ninja and stand out from the crowd.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
In a recent question (https://www.experts-exchange.com/questions/29004105/Run-AutoHotkey-script-directly-from-Notepad.html) here at Experts Exchange, a member asked how to run an AutoHotkey script (.AHK) directly from Notepad++ (aka NPP). This video…
###### Suggested Courses
Course of the Month7 days, 23 hours left to enroll