Math Is Fun Forum

Onyx

Member

Registered: 2009-02-24

Posts: 48

polynomial long division modulo 2

I'm stuck with the algorithm of polynomial long division modulo 2. Say we have

, and

, where

, the finite field with elements 0 and 1. Then P(x) and Q(x) can be represented as (n+1) and (m+1) bit binary numbers respectively.

I need to know how to make the division:

In order to find the remainder, R(x). The application is Cyclic Redundancy Checks (CRCs) used for error detection of digital packets, and the quotient polynomial (or binary number) is not of interest.

I know that long division is repeated subtraction, and that subtraction modulo 2 represents a bitwise XOR between the coefficients of the operands, and the CRC hardware used to compute these checks is a Shift Register containing XOR gates with feedback to the SR, reflecting the fact that the algorithm is based on repeated shifting and XORing of the divisor. I'm not sure exactly how this goes though, could someone help me out using an example?

Let P(x)=1011011010, Q(x)=11011, then how would the long division go (using binary numbers)?

Bob

Administrator

Registered: 2010-06-20

Posts: 10,621

Re: polynomial long division modulo 2

hi Onyx

I have set your division out like a long division.  The nice thing about doing this in binary is that there are only two possibilities at each stage;  either the dividend is smaller than the divisor, in which case write a zero in the quotient; or not, in which case write a one and subtract to get the remainder.  Do this for each step until you run out of dividend.

(glossary:  Your P is called the dividend; Q the divisor;  D the quotient; R the remainder.)

Here the quotient is 11011 and the remainder 1.

So you should be able to test the subtraction for negative; put zero or one in the answer bit; and roll for the next digit.

Is that what you were after?

Bob

Last edited by Bob (2011-01-07 00:34:41)

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

Onyx

Member

Registered: 2009-02-24

Posts: 48

Re: polynomial long division modulo 2

Thanks, thats exactly what I was after, but would you mind explaining the process to me?

You start with the MSB (Most significant bit) of the divisor aligned with the second MSB of the dividend, why not the first?

Then I was expecting an XOR operation, since the arithmetic is modular in the finite field GF(2), so addition is equivalent to subtraction is equivalent to a bitwise XOR operation between digits of the operands, meaning there should no be carry or borrow bits in the calculation. However, the first stage of the division, you have:

1011011010
 11011
 ------
 100101

Shouldnt the result be 101101, not 100101, since 1XOR0=0XOR1=1, and 1XOR1=0XOR0=0.

Last edited by Onyx (2011-01-07 07:30:44)

Bob

Administrator

Registered: 2010-06-20

Posts: 10,621

Re: polynomial long division modulo 2

hi Onyx

To construct an algorithm to 'do' division you would have to start with the most significant bit.  To shorten the visible working I left out all the leading zero steps and started when the dividend had 5 bits like the divisor.

I noticed that the dividend (5 bits) was smaller so I entered a zero in the quotient and 'brought down' the next bit.  This time the dividend was clearly bigger (having 6 bits) so I subtracted.

The subtraction, as displayed,  is correct;  the step you highlighted  is 45 - 27 = 18 in base 10.

So where did you get the idea you only need to XOR the bits?    Have a look at

http://www.cs.uaf.edu/2000/fall/cs301/notes/node54.html

Observe that a+b is identical to the logical xor operation and that carry is the same as the logical and operation.

Added later:  Do subtraction by taking the 'twos complement' and adding.

Bob

Last edited by Bob (2011-01-08 03:05:22)

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

dwb

Guest

Re: polynomial long division modulo 2

> So where did you get the idea you only need to XOR the bits?    Have a look at

Equally confused by my university text, also stated here: http://www.relisoft.com/science/crcmath.html

dwb

Guest

Re: polynomial long division modulo 2

See also http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/ecc.html section Mathematical Digression: Modulo-2 Arithmetic and following.