Member Avatar for nemo

in one of my course my teacher and i do not agree on how 100100000 should be divided by 1101 using binary division , after solution the quotient i get is 010110 with remainder 010.
my teacher gets another, can someone please confirm a correct solution for it.

regards,
nemo

  • 7 Contributors
  • 8 Replies
  • 351 Views
  • 4 Years Discussion Span
  • Latest Post Latest Post by murphp

Dani AI

Generated

A lot of the disagreement here comes from using two different kinds of "binary division." and treated the 9‑bit string as a base‑2 integer (288 ÷ 13 → quotient 22 remainder 2). CRC work, however, uses modulo‑2 polynomial division: subtraction is bitwise XOR (no borrows), exactly as pointed out and as later discovered. Those two procedures generally produce different remainders.

Viewed as polynomials (bits are coefficients over GF(2)): generator 1101 = x^3 + x^2 + 1, and the 9‑bit dividend 100100000 = x^8 + x^5 (this is the typical message padded with three zeros when the generator degree is 3). Doing polynomial long division over GF(2) (XOR at each subtraction step) yields remainder 1, which as a 3‑bit CRC is 001. If the original 6‑bit message was 100100 (padded to 100100000), the transmitted codeword becomes 100100001; dividing that codeword by 1101 leaves a zero remainder, which is the intended CRC check.

A short, practical routine (Python) that performs the modulo‑2 division and returns the r = deg(generator) bits of remainder:

def crc_remainder(data, poly):
    data = list(map(int, data))
    poly = list(map(int, poly))
    for i in range(len(data) - len(poly) + 1):
        if data[i] == 1:
            for j in range(len(poly)):
                data[i + j] ^= poly[j]
    return ''.join(str(b) for b in data[-(len(poly)-1):])

# Example: crc_remainder('100100000', '1101')  -> '001'

Important notes: CRC uses modulo‑2 (XOR) division, not integer division. Converting bits to decimal can help spot arithmetic errors, but it does not replace the GF(2) procedure required for correct CRC remainder and codeword formation.

Recommended Answers

All 8 Replies

Member Avatar for Member #46692

in one of my course my teacher and i do not agree on how 100100000 should be divided by 1101 using binary division , after solution the quotient i get is 010110 with remainder 010.
my teacher gets another, can someone please confirm a correct solution for it.

regards,
nemo

If you convert it to decimal you can easily check your answer.

288 / 13 = 22.153846153846153846153846153846

If you use remainders however, the answer is 22r2. the accuracy of your solution will yield different answers.

Member Avatar for nemo

If you convert it to decimal you can easily check your answer.

If you use remainders however, the answer is 22r2. the accuracy of your solution will yield different answers.

you're right converting to decimal is an easy way to check answer. i am happy with my answer, the problem is my teacher is not :( and i dont want him to mark my solution wrong, i desperately want an A here, cant lose a single mark.
actually it is a data communication course and we have to use the remainder to generate the CRC code for reliable data tranfer and detection of errors over communication lines.

thnx for ur help
nemo

Member Avatar for Rashakil Fol

You can check convincingly by multiplying them back up.

13 * 22 + 2 = 288.

So your answer is correct.

Member Avatar for nemo

i found the correct answer last night, when doing binary division for CRC checksum method we are not suppose to do the normal subtraction in the division instead a XOR is performed between the values and this eventually gives the desired remainder that is appended with the original message in CRC checksum technique.

Member Avatar for rakesh20004u

you are right....

You can try all the possiblities and u will get the answer

Member Avatar for BestJewSinceJC

Thanks for that enlightening and philosophical reply.

commented: :D +12
Member Avatar for hondros

It's been dead for 4 years!!! Why would you revive it!

Member Avatar for murphp

when you are calculating CRC you don't do normal division. you do polynomial division :) its slightly different

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.