I am beginning the implementation of the polynomial binary division algorithm now as I understood i will be checking the MSB bit if 1 to XOR and shift the sum if 0 i will only shift. What I am not getting well with is the numerator and denominator degree calculation and when to stop the the division in a case of a polynomial division with M=8 and an irreducible polynomial : X^8+X^4+X^3+X+1 will be divided by X^6+X^5+X^2+X at first I will have to pad with zeros to obtain the same size

I have found that shifting the numerator by L and denominator by K until hitting the first '1' will give me the degree being M-L and M-K-1 of each polynomial and the division will be of Deg(N)-Deg(D) cycles in this example: it will be: Numerator: 100011011 Denominator: 01100110

Numerator MSB is 1 then degree(N) is M-0=8 Denominator MSB is 0 : then it will be shifted to the left by 1 and the Degree(D)=8-1-1=6 the needed counter is 8-6=2 steps and 8-6+1=3 XOR operations

what I would like to ask is this a correct way to start and won't the following degree calculation step includes a large hardware delay since it is done sequentially and M might get to 233

What is the best way of calculating the : Degree of numerator and denominator and when can i know where to stop the division

Thank you

up vote 0 down vote accepted

The method you describe is called the "pencil and paper algorithm" and is well described in Knuth's Book, Semi-Numerical Algorithm II.

In fact the number of steps can be easily determined by the size of operands. If Dividend D, is m-bit and Divisor d, is n-bit, then the Quotient q, will be (m-n+1)-bit, and the remainder in case of binary division will be at most (n-1)-bit.

Under these conditions, the algorithm il like that follow:

Shift the divisor (m-n)-bit left (this is called Normalization step by Knuth), We use some registers to be initiated by the operand 
Reg_D <-- D: init with D, used as an Accumulator,
Reg_d <-- d: init with divisor $2^{m-n}$d; remains unchanged during all the process iteration,
Reg_q <-- 0: init with Operand 0,

for k from (m-n) DownTo 0, Do:
   - Reg_q <-- 2.Reg_q;  //Shift Reg_q 1-bit Left (or equivalently q = 2.q)
   - Reg_D = Reg_D XOR Reg_d;   //... XORing(Reg_D, Reg_d): 
   - q_k=MSB(Reg_D); //Get the bit which represent the partial bit of quotient. 
   - Reg_q = Reg_q + q_k; //... Inject bit q_k in Reg_q, or 
   - if( !k)
           Reg_D = 2.Reg_D;  //... Shift  1-bit Left D excepted for last step!
End For;

NB: Observe:

  • The Remainder is contained in Reg_D,

  • To obtain the quotient, Complement the content of Reg_q.

To optimise the process, in case of multiple division with the same divisor you can try two methods described by Knuth:

  • Normalization of the Divisor,
  • Precomputation tables.

Good Luck for your project.

  • Thank you, do you mean by m and n as the degree of each or the total number of bits ?, the total number of bits I have for D is 9 ans for n is 8 in such case m-n bit is always 1 and always initiate 1 iteration – user3368764 Dec 22 '14 at 10:39
  • 1- Yes! m and n are the total number of bits for the Dividend D and divisor d respectivelly, assuming that the MSB of each operand is 1. 2- No! I confirm that the number of iterations in you case is 9-8+1=2. You have to execute 2 iterations. PS: If fact the ALGORITHM I show you is only formal. I'll edit it again and gives additional precisions. Note that the quotient bit computed during each step is in Complement-ONE representation. I'll correct it. Bye – Robert NACIRI Dec 22 '14 at 13:22

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.