modulo 2 division?

x in the city

can onyone help me out doing ex-or division, (also known as modulo 2...so im told).

this is for crc error checking, cant for the life of me figure out this........

tks

eza

ressem

Any part in particular?

It's like primary school long division.
see
http://www.netrino.com/Connecting/2000-01/

but instead of subtracting though at each 'level', you use XOR.

from the first stage of the example on the link.
Xoring
11100
11011

---

00111

Or from right to left
0 xor 1 = 1
0 xor 1 = 1
1 xor 0 = 1
1 xor 1 = 0
1 xor 1 = 0

You don't carry-over,
Then at the next stage, carry down the 1.
11011 doesn't go into 001111, so 0 is added to the quotient

Carry down the 0
11011 goes into 11110, so 1 is added to the quotient
and
Xoring
11110
11011

---

00101

and carry down the next one
etc, etc.


I take it that you know the XOR table
0 xor 0 = 0
0 xor 1 = 1
1 xor 0 = 1
1 xor 1 = 0

Or have I missed the source of your problems altogether?

x in the city

thanks for that

we are basically given a polynomial and a data stream, you multiply the data stream by the number of bits in the polynomial and the resultant data is divided by the polynomial.......mmmmmm

this is where im stuck,

im only interested in the remainder (if any) ......

i would have something like this

10110 | 10110001010110
___________


etc

ressem

fresher homework.

Not quite

There's always going to be a remainder, even if it's 0000.

From your mail
Data Stream
=10110001010110

Divisor
=10110
(in real life it'd be a prime no)

Multiply by 2 to power of (no of bits in the polynomial - 1).
in other words left shift the datastream by 4
=101100010101100000

So
For each bit of the datastream, going from most important to least important,

Append the next datastream bit to the remainder
If the remainder is indivisible append 0 to the quotient
If the remainder is divisible append 1 to the quotient
Carry out a XOR on the 2 numbers, the result is your new remainder.

So.
Starting rem=0.

bring down 1, rem=1,add 0 to quotient
bring down 0, rem=10,add 0 to quotient
bring down 1, rem=101,add 0 to quotient
bring down 1, rem=1011,add 0 to quotient
bring down 0, rem=10110,add 1 to quotient
10110 XOR 10110 = 00000, so rem =0

bring down 0, rem=0,add 0 to quotient
bring down 0, rem=0,add 0 to quotient
bring down 1, rem=1,add 0 to quotient
bring down 0 , rem=10, add 0 to quotient
bring down 1, rem=101,add 0 to quotient
bring down 0 , rem=1010, add 0 to quotient
bring down 1 , rem=10101, add 1 to quotient
10101 XOR 10110 = 00011

bring down 1 , rem=111, add 0 to quotient
bring down 0 , rem=1110, add 0 to quotient
bring down 0 , rem=11100, add 1 to quotient
11100 XOR 10110 = 01010

bring down 0 , rem=10100, add 1 to quotient
10100 XOR 10110 = 00010

bring down 0 , rem=100, add 0 to quotient
bring down 0 , rem=what, add 0 to quotient

Your datastreams all gone, and you can't XOR divide since the remainder is only 4 bits, so this is your final remainder.

-
You always get these qns in the exams so you'd better take the time to understand it now.

gwladys boy

excellent,

yer dead right about exams, we got one wednesday.....and its gonna come up in the summer as well, so must get it into (and out of) my system

did you ever consider lecturing

i had a java exam today, it was goddamn awful, you do java as well?

well, it was awful, but thats cos of me.........it was about threads and animation and erm, sockets and clients.

x in the city

thanks for your tips,


can you convert the binary to hex/dec and divide as normal with claculator? i know its cutting alot of cornerrs , but thats my way.......^^ i can kinda do the division, but would be handy if you could back up your answer with a calculator

eza

ressem

Well you could convert to hex/dec/bin/oct and divide (or rather mod() , you want the remainder) as normal...
but you'd get the answer to a different question, on any exam calculator I've seen. Try it out and see.

You could build the thing from 74LS chips, shift registers and LEDs and carry it into the exam hall.

Just draw it out as shown in the first graphic of the link mentioned in first reply.

After the first few, it's less awkward than standard long division.

yours,
another curmudgeonly old ex-student,

gwladys boy

nice one about making it and bringing it into the exam hall.........

ultra cool. !

can you have a look at this one?

data message 10111

polynomial x3+x2+x (1110)?

do you do division my using x's rather than binary?

we got a exam 2moro on this stuff......


do you know stuff about networks as well?

say i want to send a 12 meg file down a network with a bandwidth of 28kbps,

how would i calculate the time to send it say in 1 go or if it was broken into packets (xxxs byyes)

?

thanks for your help, your better than my lecturer.........:)

ressem

Jaysus quit the flattery, stomach churning.

>>do you do division my using x's rather than binary?
Whatever way you wanted in my school, unless you're asked specifically, provided you make a note saying that
1*x^3+1*x^2+1*x+0*x^0
can be represented by 1110 at the start.

alternatively, if you have really neat writing and patience
Convert data message
1*x^4 + 0*x^3 + 1*x^2 + 1*x^1 + 1*x^0

Multiply data by highest term from divisor x^3.

And xor divide, i.e subtracting matching powers of X, and ignoring sign of remainders.
See enclosed gif.


--But you should be copying the style from the notes that yr lecturer uses. Which is where you should be reading this stuff from.

---
Same with the network stuff

If it's in packets, you're going to have a packet overhead, probably 20 bytes per packet.

So get the size of the packets you're using subtract the header stuff to get the message size per packet.

Divide the file by this message size to get the number of packets.

Multiply this number by the size of a full packet, to get the total data transmission size.
Divide by bandwidth to get seconds.


For one block add just one header to the file size and divide by bandwidth.


Now this question really is academic BS, but :dunno: .

gwladys boy

righto

i will give it a go . im off home

cheers for the tips mate

eric

gwladys boy

OH , LECTURER IS SHYTE...........!