Verilog Binary Division

[Kristo Godari]

I need a Verilog behavioral model (verilog behavioral code) for:
- unsigned 8-bit division

The module I have to use is this one:

module divider(
output reg[7:0] q,
output reg[7:0] r,
input [7:0] a,b);
endmodule

where a=b*q+r

Is preferable to use SRT, Newton-Raphson or Goldschmidt algorithms
to solve it.

Can someone help me?

 

[glen herrmannsfeldt]

Kristo Godari <kristo.godari@gmail.com> wrote:

I need a Verilog behavioral model (verilog behavioral code) for:
- unsigned 8-bit division

The module I have to use is this one:

module divider(
output reg[7:0] q,
output reg[7:0] r,
input [7:0] a,b);
endmodule

where a=b*q+r

Is preferable to use SRT, Newton-Raphson or Goldschmidt algorithms
to solve it.

For 8 bits, usually something simpler than those. You don't
have a clock, so you can't pipeline it.

Remember how you learned to divide in 5th grade?
Just like that, but in binary instead of decimal.

The ones you mention are most often used for floating point.
For one reason, some of those give a rounded quotient, not what
you want.

-- glen

 

[glen herrmannsfeldt]

GaborSzakacs <gabor@alacron.com> wrote:

Kristo Godari wrote:
I need a Verilog behavioral model (verilog behavioral code) for:
- unsigned 8-bit division

(snip)

Is preferable to use SRT, Newton-Raphson or Goldschmidt algorithms
to solve it.

(snip)

This is really a decision based on vailable resources and timing
requirements. For example if you have few resources but lots of time
then you could do successive subtraction. By the way your module
needs a clock to do any sequential algorithm reliably.

Yes, no clock so only combinatorial logic. No matter how long
it takes.

In an FPGA with a spare multiplier and block RAM I might make a table
of inverses in the block RAM and giving the divisor as the address,
use that table's output to multiply by the dividend. That would give
a new result every clock cycle if necessary.

I forgot about that one. I think you need at least one bit more
in the inverse to make it work. Then take the high bits of
the product. Many have an 18x18 multiplier, though, so that
should be plenty of bits. Might be faster than the series
of compare and subtract, too!

You can even test all the combinations in software to make sure
everything rounds the right way. Then another multiply and
subtract to generate the remainder.

Also you say "behavioral" but I'm guessing you want this module to
be synthesizable or else you'd simply use the division operator.

Personally, I write mostly structural verilog with continous
assignment and module references, except for registers and
state machines, but much of behavioral verilog is now
synthesizable.

I believe they can synthesize from a series of if statements
to do conditional subtraction and the appropriate shifts.

-- glen

 

[glen herrmannsfeldt]

GaborSzakacs <gabor@alacron.com> wrote:

Kristo Godari wrote:
I need a Verilog behavioral model (verilog behavioral code) for:
- unsigned 8-bit division

The module I have to use is this one:

module divider(
output reg[7:0] q,
output reg[7:0] r,
input [7:0] a,b);
endmodule

where a=b*q+r

Is preferable to use SRT, Newton-Raphson or Goldschmidt algorithms
to solve it.

Can someone help me?

(snip)

In an FPGA with a spare multiplier and block RAM I might make a table
of inverses in the block RAM and giving the divisor as the address,
use that table's output to multiply by the dividend. That would give
a new result every clock cycle if necessary.

Actually, with a block RAM you can do the whole thing as a
look-up table. You have 16 bits input and 16 bits output.

But you need a clock for the block RAM on many.

For asynchronous RAM you need to use CLB, but it still might
be a fine solution, probably faster and less logic than eight
levels of compare and subtract.

-- glen

 

[Kristo Godari]

I forgot to say that i can't use '/' or '%'.And i can't change the module structure the module must have 2 inputs and 2 outputs:

module divider(
output reg[7:0] q,
output reg[7:0] r,
input [7:0] a,b);

/*
Code goes here
*/

endmodule

 

[GaborSzakacs]

Kristo Godari wrote:

I need a Verilog behavioral model (verilog behavioral code) for:
- unsigned 8-bit division

The module I have to use is this one:

module divider(
output reg[7:0] q,
output reg[7:0] r,
input [7:0] a,b);
endmodule

where a=b*q+r

Is preferable to use SRT, Newton-Raphson or Goldschmidt algorithms
to solve it.

Can someone help me?

This is really a decision based on vailable resources and timing
requirements. For example if you have few resources but lots of time
then you could do successive subtraction. By the way your module
needs a clock to do any sequential algorithm reliably.

In an FPGA with a spare multiplier and block RAM I might make a table
of inverses in the block RAM and giving the divisor as the address,
use that table's output to multiply by the dividend. That would give
a new result every clock cycle if necessary.

Also you say "behavioral" but I'm guessing you want this module to
be synthesizable or else you'd simply use the division operator.

--
Gabor

 

[Thomas Stanka]

Hello,

Am Montag, 4. November 2013 15:48:28 UTC+1 schrieb Kristo Godari:

I need a Verilog behavioral model (verilog behavioral code) for:

- unsigned 8-bit division

behavioral model means not necessary synthesisable.
Easiest is a = b/c.
Your teacher don't like you to use this easiest sollution, so he requestst you to learn about additional algorithms and write them down.

Forget about pipelining, clock etc.
Have a look at the suggested algorithms and translate them in verilog code.

bye Thomas

 

[glen herrmannsfeldt]

Thomas Stanka <usenet_nospam_valid@stanka-web.de> wrote:

Am Montag, 4. November 2013 15:48:28 UTC+1 schrieb Kristo Godari:
I need a Verilog behavioral model (verilog behavioral code) for:
- unsigned 8-bit division

behavioral model means not necessary synthesisable.

This is true, and I prefer structural verilog, but enough is
synthesizable that many do write behavioral model for synthesis.

Easiest is a = b/c.
Your teacher don't like you to use this easiest sollution,
so he requestst you to learn about additional algorithms and
write them down.

Since there is no clock, it has to be all combinatorial logic.
I find continuous assignment more readable for combinatorial
logic than behavioral assignment. On the other hand, I like to
read state machines in behavioral form, where there is a latch
on every state transition.

-- glen

 

[Nikolaos Kavvadias]

Hi all,

what we have here is both a lazy teacher giving an understated assignment, and the typical student of this decade, looking the easy way through. As most of 20ers are these days, he needs time for WoW, tablet time, txting, net news or whatever.

I would start with an untimed version in C, then devise the FSM/FSMD and do the work. Shouldn't be more than an afternoon for each subtask for a student. Of course, this requires to wake up the teacher and ask him whether he really requests a combinational implementation or would allow for a clock.


Best regards
Nikolaos Kavvadias

 

[glen herrmannsfeldt]

Nikolaos Kavvadias <nikolaos.kavvadias@gmail.com> wrote:

what we have here is both a lazy teacher giving an understated
assignment, and the typical student of this decade, looking the
easy way through. As most of 20ers are these days, he needs time
for WoW, tablet time, txting, net news or whatever.

Well, it is presumable in the context of what was taught in class,
which we don't know.

I would start with an untimed version in C, then devise
the FSM/FSMD and do the work. Shouldn't be more than an
afternoon for each subtask for a student. Of course,
this requires to wake up the teacher and ask him whether
he really requests a combinational implementation or would
allow for a clock.

What is wrong with the combinatorial one?

They tend to take more hardware, as you can't time-share
(reuse) parts of the logic, but there is nothing wrong with that.

Seems to me that one should learn the combinatorial one first.

Also, that is what verilog would generate if it synthesized
the / operator. (I presume some do now, especially for only
eight bits.)

Now, often in actual practice one wants either the pipelined
or iterative algorithm, but one should be able to understand
any and all of them.

-- glen

 

[Nikolaos Kavvadias]

Hi Glen,

> What is wrong with the combinatorial one?

There is nothing wrong with the combinational divider in principle.

Eventually, for use in an IP-based scheme, inputs and outputs would be registered. For standalone use/experimentation it is OK.

One would cascade maybe 1 or 2 iterations of either NR or Goldschmidt and this would be fine especially for such small datapath size. I guess a LUT-based scheme would also do.

Also, that is what verilog would generate if it synthesized
the / operator. (I presume some do now, especially for only
eight bits.)

I am very interested to know which of the current RTL tools has a module generator for division. It would be a strong asset.

For instance, tools don't have a module generator for integer modulo (apart from trivial cases). I have an implementation of a very good algorithm (published in 2011) for variable and constant modulo:

http://nkavvadias.com/eshop/index.php?id_product=9&controller=product
https://groups.google.com/forum/#!msg/comp.lang.verilog/7ei2AKq6_Es/7vLHSCkTg3UJ

It is a pay IP alright, but the product brief and documentation are free for downloading. Any of the A, X, L, M, or S companies should provide such module generators in their backend tools.


Best regards
Nikolaos Kavvadias

 

[Thomas Stanka]

Am Mittwoch, 6. November 2013 08:52:16 UTC+1 schrieb Nikolaos Kavvadias:
> I am very interested to know which of the current RTL tools has a module generator for division. It would be a strong asset.

Check out designware for Synopsys design compiler.

regards Thomas

 

[Tim Wescott]

On Mon, 04 Nov 2013 12:51:45 -0800, Kristo Godari wrote:

I forgot to say that i can't use '/' or '%'.And i can't change the
module structure the module must have 2 inputs and 2 outputs:

module divider(
output reg[7:0] q,
output reg[7:0] r,
input [7:0] a,b);

/*
Code goes here
*/

endmodule

So, this is homework?

--

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

 

[Nikolaos Kavvadias]

So, this is homework?

Tim Wescott
Wescott Design Services

Seems so. This guy was also in freelancer (which implies that I was there, too).

Most freelancers offered around 30 USD per divider topology, which is about the cost of a casual (low-cost) dinner for two in Greece. But this is week's payment in a number of countries around the globe.

 

[svenn]

Nikolaos Kavvadias wrote:

Seems so. This guy was also in freelancer (which implies that I was there, too).

Most freelancers offered around 30 USD per divider topology, which is about the cost
of a casual (low-cost) dinner for two in Greece. But this is week's
payment in a number of countries around the globe.

Shit, I need a native USB 2.0 host in VHDL. Any poor sucker who would do
a 4 week job at USD30/week? Cash on Delivery!!!! (though paypal)

Is this how we want globalization to work?

--
Svenn

 

[Nikolaos Kavvadias]

Hi Svenn,

Shit, I need a native USB 2.0 host in VHDL. Any poor sucker who would do
a 4 week job at USD30/week? Cash on Delivery!!!! (though paypal)

Is this how we want globalization to work?

It is not in my best interest to let globalization work this way My hourly and not weekly rate is typically around USD 30. Greek clients would be happy having me work for USD 10 per hour, but I ditch them (like four times since September for some major projects -- like OEMs for license plate recognition -- since there is no margin for any benefit!) So clients are helpless and are typically middle-men who want to go into production (yeah right, thanks for the entertainment Greek IT people!)

For these kind of tasks a reasonable hourly rate e.g. in Germany is around 70-100 USD; this is what the client expects to pay for high-quality work.

I'm afraid that rates of a couple of dollars exist; don't ask me where, you know. But in some aspect or another you will get what you pay for.


Best regards
Nikolaos Kavvadias
http://www.nkavvadias.com
http://www.ajaxcompilers.com
http://www.perfeda.gr