Verilog Binary Division

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?

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

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

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

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

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

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

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

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 mo=
st 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 stude=
nt. 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

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