Advertisement
If you have a new account but are having problems posting or verifying your account, please email us on hello@boards.ie for help. Thanks :)
Hello all! Please ensure that you are posting a new thread or question in the appropriate forum. The Feedback forum is overwhelmed with questions that are having to be moved elsewhere. If you need help to verify your account contact hello@boards.ie
Hi there,
There is an issue with role permissions that is being worked on at the moment.
If you are having trouble with access or permissions on regional forums please post here to get access: https://www.boards.ie/discussion/2058365403/you-do-not-have-permission-for-that#latest

modulo 2 division?

  • 29-03-2004 2:46pm
    #1
    Closed Accounts Posts: 7,134 ✭✭✭


    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


Comments

  • Registered Users, Registered Users 2 Posts: 2,426 ✭✭✭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?


  • Closed Accounts Posts: 7,134 ✭✭✭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


  • Registered Users, Registered Users 2 Posts: 2,426 ✭✭✭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.


  • Closed Accounts Posts: 34 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 :p

    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.


  • Closed Accounts Posts: 7,134 ✭✭✭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


  • Advertisement
  • Registered Users, Registered Users 2 Posts: 2,426 ✭✭✭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,


  • Closed Accounts Posts: 34 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.........:)


  • Registered Users, Registered Users 2 Posts: 2,426 ✭✭✭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: .


  • Closed Accounts Posts: 34 gwladys boy


    righto

    i will give it a go . im off home

    cheers for the tips mate

    eric

    :)


  • Closed Accounts Posts: 34 gwladys boy


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


  • Advertisement
Advertisement