EmbDev.net

Forum: FPGA, VHDL & Verilog divide by 3 in vhdl


Author: lelo (Guest)
Posted on:

Rate this post
-1 useful
not useful
hi
i want to know how to divide by 3 in vhdl

Author: Frank (Guest)
Posted on:

Rate this post
0 useful
not useful
Divide what exactly?

Time? A clock? An integer? signed/unsigned? Some wierd float? Some 
standard float? Divide bread? Designs in functions?

I think you got the point.

Author: Thomas Reinemann (Company: abaxor engineering) (abaxor)
Posted on:

Rate this post
0 useful
not useful
lelo wrote:
> hi
> i want to know how to divide by 3 in vhdl


I suppose you will do that using integer numbers. A divide by three is 
nothing more than a multiplication by 0.33333. Therefore you increase 
0.33333 by 2**n and multiply your operand by this factor. From your 
product you have to use the the digits product'high downto n.

Tom

Author: Lothar Miller (lkmiller) (Moderator)
Posted on:

Rate this post
0 useful
not useful
Thomas Reinemann wrote:
> Therefore you increase 0.33333 by 2**n and multiply your operand by
> this factor. From your product you have to use the the digits
> product'high downto n.
In other words for a 16 bit integer:
     result <= (value*(2**16/3))/2**16;

Author: Rolf S. (audiorolf)
Posted on:

Rate this post
0 useful
not useful
I once found this cyclic definition:

x/4 + x/16 + x/64 + ...

= 0,333333333 x X

Author: Detlef _a (detlef_a)
Posted on:

Rate this post
0 useful
not useful
Or use this from

http://graphics.stanford.edu/~seander/bithacks.htm...

Compute modulus division by (1 << s) - 1 without a division operator
unsigned int n;                      // numerator
const unsigned int s;                // s > 0
const unsigned int d = (1 << s) - 1; // so d is either 1, 3, 7, 15, 31, ...).
unsigned int m;                      // n % d goes here.

for (m = n; n > d; n = m)
{
  for (m = 0; n; n >>= s)
  {
    m += n & d;
  }
}
// Now m is a value from 0 to d, but since with modulus division
// we want m to be 0 when it is d.
m = m == d ? 0 : m;

This method of modulus division by an integer that is one less than a 
power of 2 takes at most 5 + (4 + 5 * ceil(N / s)) * ceil(lg(N / s)) 
operations, where N is the number of bits in the numerator. In other 
words, it takes at most O(N * lg(N)) time.

: Edited by Moderator
Author: Lothar Miller (lkmiller) (Moderator)
Posted on:

Rate this post
0 useful
not useful
Detlef _a wrote:
> for (m = n; n > d; n = m)
> {
>     for (m = 0; n; n >>= s)
Hopefulley lelo (Guest) doesn't try to do this in real hardware. The 
variable end of the first loop will not even work in VHDL...

: Edited by Moderator
Author: Detlef _a (detlef_a)
Posted on:

Rate this post
0 useful
not useful
Lothar Miller wrote:
> Detlef _a wrote:
>> for (m = n; n > d; n = m)
>> {
>>     for (m = 0; n; n >>= s)
> Hopefulley lelo (Guest) doesn't try to do this in real hardware. The
> variable end of the first loop will not even work in VHDL...


No, not in this form. I quoted a C-program, you can transfer the algo to 
VHDL, for ex. with a state machine.

Is there anything you cant do with VHDL? I'm not an expert in VHDL, but 
the answer must be 'No'.

Cheers
Detlef

: Edited by User
Author: ChristophZ (Guest)
Posted on:

Rate this post
0 useful
not useful
Detlef _a wrote:
> Is there anything you cant do with VHDL? I'm not an expert in VHDL, but
> the answer must be 'No'.

The question is not, can you do it or not. The question is the cost.

When you write software, your costs are: code size, requried memory and 
execution time.

When you describe hardware, your costs are: required logic elements, 
power consumption and latency.


A solution that is cheap in software could be expensive in hardware and 
vice versa.

Author: Lothar Miller (lkmiller) (Moderator)
Posted on:

Rate this post
0 useful
not useful
Detlef _a wrote:
> Is there anything you cant do with VHDL?
> I'm not an expert in VHDL, but the answer must be 'No'.
Why must the answer be 'No'?

Author: Detlef _a (detlef_a)
Posted on:

Rate this post
0 useful
not useful
Ok, messed up this one. lelo wanted a division by 3, my post was about 
modulus division :-(

Here is the right answer. It is adapted from
http://www.hackersdelight.org/divcMore.pdf

and comes with only shifts and addition and without variable count loops 
;-)

That comes in handy, you VHDL gurus, right? (but still its C language 
though)

Cheers
Detlef

PS:
>> Is there anything you cant do with VHDL?
>> I'm not an expert in VHDL, but the answer must be 'No'.
>Why must the answer be 'No'?

Because VHDL is turing-complet, hopefully.



unsigned int n=33333;                      // numerator
unsigned q, r;

q = (n >> 2) + (n >> 4); // q = n*0.0101 (approx).
q = q + (q >> 4); // q = n*0.01010101.
q = q + (q >> 8);
q = q + (q >> 16);
//printf("%d \n",q ); // Returning q + r/3.
//r = n - q*3; // 0 <= r <= 15.
r = n-(q<<1)-q; // 0 <= r <= 15.
//r=q + ((11*r) >> 5);
r=q + (((r<<3)+(r<<1)+r) >> 5);
     printf("%d \n",r); // Returning q + r/3.
// return q + (5*(r + 1) >> 4); // Alternative 1.
// return q + ((r + 5 + (r << 2)) >> 4);// Alternative 2.
return;

: Edited by User
Author: qnd (Guest)
Posted on:

Rate this post
0 useful
not useful
you#re mixing up things. If you can write it in VHDL it does not mean 
you can built a efficent FPGA design from it.

Of course you can write an SOFT-CPU in VHDL, implement an FPGA with it 
and programm the core in C - but thats rather inefficient.


Best regards,

Author: Lothar Miller (lkmiller) (Moderator)
Posted on:

Rate this post
0 useful
not useful
Detlef _a wrote:
> PS:
>>> Is there anything you cant do with VHDL?
>>> I'm not an expert in VHDL, but the answer must be 'No'.
>> Why must the answer be 'No'?
> Because VHDL is turing-complet, hopefully.
Of course you can do anything in VHDL. You also can drive in a screw 
with a hammer. Its a fairly inefficient way, not always leading to the 
best result, but of course you can...

To get good results (=small and fast) you must use algorithms that can 
be implemented on Hardware in an efficient way (try google translator, 
its german):
http://www.lothar-miller.de/s9y/archives/67-Vektor...
http://www.lothar-miller.de/s9y/archives/34-Vektor...
http://www.lothar-miller.de/s9y/archives/78-Bubblesort.html
http://www.lothar-miller.de/s9y/archives/89-BCD-na...

: Edited by Moderator
Author: lelo (Guest)
Posted on:

Rate this post
0 useful
not useful
Lothar Miller wrote:
> Thomas Reinemann wrote:
>> Therefore you increase 0.33333 by 2**n and multiply your operand by
>> this factor. From your product you have to use the the digits
>> product'high downto n.
> In other words for a 16 bit integer:     result <=
> (value*(2**16/3))/2**16;

it can be implemented also

Reply

Entering an e-mail address is optional. If you want to receive reply notifications by e-mail, please log in.

Rules — please read before posting

  • Post long source code as attachment, not in the text
  • Posting advertisements is forbidden.

Formatting options

  • [c]C code[/c]
  • [avrasm]AVR assembler code[/avrasm]
  • [vhdl]VHDL code[/vhdl]
  • [code]code in other languages, ASCII drawings[/code]
  • [math]formula (LaTeX syntax)[/math]




Bild automatisch verkleinern, falls nötig
Note: the original post is older than 6 months. Please don't ask any new questions in this thread, but start a new one.