hi i want to know how to divide by 3 in vhdl
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.
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
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; |
I once found this cyclic definition: x/4 + x/16 + x/64 + ... = 0,333333333 x X
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
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
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
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.
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'?
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
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,
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
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
Log in with Google account
No account? Register here.