Continue to Site

Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Polynomial Division on hardware

Status
Not open for further replies.

ghattas.akkad

Member level 1
Joined
Apr 30, 2013
Messages
39
Helped
1
Reputation
2
Reaction score
1
Trophy points
1,288
Activity points
1,555
Hello
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
 

No padding to the left. Start with the numbers left aligned (the first '1' in both numbers aligned),
then Xor whenever the highest '1''s are aligned. Stop when the LSB's are aligned.

Code:
100011011
1100110 (do xor)
010000011
 1100110 (do xor)
 01001111
  1100110 (do xor then stop because LSB's are aligned)
  0101001 (remainder)

Xor in all steps => quotient is 111 = x^2 + x + 1
Remainder is 101001 = x^5 + x^3 + 1
 
Status
Not open for further replies.

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Back
Top