RE: [oc] Binary Divides for uP core

["Paul McFeeters" <paul.mcfeeters@ntlworld.com>]

Jean,

I will have a look for that book thanks.

I put my brain into neutral and an idea for unsigned division came to me.
For the equation A/B = modulus, remainder

<snip out the checks for div-zero and B>A)

A.MSB is the index to the MSB bit used in A
B.MSB is the index to the MSB bit used in B

A.temp = A
for (count = A.MSB-B.MSB; count >= 0; count = count - 1)
begin
	if (B.MSB << count) <= A.temp
	begin
		A.temp = A.temp - (B.MSB << count)	
		modulus = modulus + (1 << count)
	end
end
remainder = A.temp

Its the simplest I can get the formula so far as I need it to handle 8, 16, 32 
and even 64bit numbers in my uP core. The function works perfectly on paper 
but haven't done any specific timing on it yet. As I'm still learning the 
basics of Verilog please forgive the roughness of the examples.

My unsigned multiplication solution was even easier,

A*B

result = 0
for(count=0; count <A'width; count = count + 1)
begin
	if (A[count] = 1) 
		result = result + (B << count)
end

I even considered listing each possible iteration rather than a for loop, 
is that a good idea? If anybody can help me optimise these functions or you 
wish to discuss these functions further then please email me direct rather 
than via the list. Don't want to put any noses out of joint.

Paul
mailto:paul.mcfeeters@ntlworld.com

PS I did look at the 8051 ALU module but couldn't understand how they did even 8bit
division! Still to naive in Verilog I guess.


> -----Original Message-----
> From: owner-cores@opencores.org [mailto:owner-cores@opencores.org]On
> Behalf Of Jean Masson
> Sent: 15 January 2002 12:29
> To: cores@opencores.org
> Subject: Re: [oc] Binary Divides for uP core
> 
> 
> Hello Paul,
> 
> I use a book of Niklaus Wirth which gives the architecture and synthesis listing of integer 8 bits
> multiplier and divider.
> HDL used in the book is Lola, a language created by N. Wirth. It is relatively easy to translate
> Lola files to VHDL or Verilog.
> 
> The name's book is approximately : Introduction to logic synthesis for computing students. Springer
> Verlag editor.
> This is a fine book, full of information for logic synthesis biased guys.
> 
> It is not possible, at my knowledge, to do division in one cycle. This is typically an iterative
> process. You must evaluate in
> parallel 2 integer numbers : result and rest. Division is not like multiplication, that is
> implement able in pure combinatory logic.
> In DSPs, multiplication is performed in 1 cycle, division takes always a number of cycles equal to
> its format.
> 
> Wirth uses a sequential process with conditional substraction of a shifted word. A 8 bits word is
> divided in 8 cycles.
> If you use a combinatorial multiplier, an SAR register could gives you the result, like SAR of ADC.
> 
> Another method is an approximation by Newton's algorithm. You search by iteration the inverse of
> divider and do
> multiplication with inverse : A/B = A*(1/B). Consult the old Data Book on AMD2901, where I have
> found the idea.
> 
> If you find THE trick (the divider of  McFeeters) to do division in 1 cycle, please give us a mail
> with the description
> of your method.
> 
> Best regards,
> 
> Jean MASSON
> 
> 
> > On Tuesday 15 January 2002 04:30 am, Paul McFeeters wrote:
> > > Hi,
> > >
> > > Does anybody know the routine for doing a binary division in HDL?
> > > I'm developing a uP core and would like to do divisions in one
> > > clock cycle if possible? The multiple instruction was easy to
> > > figure out but I'm still stuck on the division one.
> >
> > > Paul
> > --
> 
> --
> To unsubscribe from cores mailing list please visit http://www.opencores.org/mailinglists.shtml
--
To unsubscribe from cores mailing list please visit http://www.opencores.org/mailinglists.shtml