Polynomial division hardware implementation

Question

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

Answer 1

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.