EmbDev.net

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


von lelo (Guest)


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

:
von Frank (Guest)


Rate this post
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.

von Thomas R. (Company: abaxor engineering) (abaxor)


Rate this post
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

von Lothar M. (Company: Titel) (lkmiller) (Moderator)


Rate this post
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:
1
     result <= (value*(2**16/3))/2**16;

von Rolf S. (audiorolf)


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

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

= 0,333333333 x X

von Detlef _. (detlef_a)


Rate this post
useful
not useful
Or use this from

http://graphics.stanford.edu/~seander/bithacks.html#ModulusDivisionEasy

Compute modulus division by (1 << s) - 1 without a division operator
1
unsigned int n;                      // numerator
2
const unsigned int s;                // s > 0
3
const unsigned int d = (1 << s) - 1; // so d is either 1, 3, 7, 15, 31, ...).
4
unsigned int m;                      // n % d goes here.
5
6
for (m = n; n > d; n = m)
7
{
8
  for (m = 0; n; n >>= s)
9
  {
10
    m += n & d;
11
  }
12
}
13
// Now m is a value from 0 to d, but since with modulus division
14
// we want m to be 0 when it is d.
15
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
von Lothar M. (Company: Titel) (lkmiller) (Moderator)


Rate this post
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
von Detlef _. (detlef_a)


Rate this post
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
von ChristophZ (Guest)


Rate this post
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.

von Lothar M. (Company: Titel) (lkmiller) (Moderator)


Rate this post
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'?

von Detlef _. (detlef_a)


Rate this post
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
von qnd (Guest)


Rate this post
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,

von Lothar M. (Company: Titel) (lkmiller) (Moderator)


Rate this post
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-nach-BCD-kombinatorisch.html
http://www.lothar-miller.de/s9y/archives/34-Vektor-nach-BCD.html
http://www.lothar-miller.de/s9y/archives/78-Bubblesort.html
http://www.lothar-miller.de/s9y/archives/89-BCD-nach-Binaer-wandeln.html

: Edited by Moderator
von lelo (Guest)


Rate this post
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

Please log in before posting. Registration is free and takes only a minute.
Existing account
Do you have a Google/GoogleMail account? No registration required!
Log in with Google account
No account? Register here.