| Author |
Message |
Wolfgang
Guest
|
 Posted:
Thu Dec 15, 2005 5:16 pm Post subject:
Division in Fixed Point |
|
|
Dear all,
Can anyone point me to some code how to implement a division in a Fixed
Point DSP ?
(Just to see how it works to fit it in mine)
Thx, Wolfgang |
|
| Back to top |
|
 |
Tim Wescott
Guest
|
| Posted:
Thu Dec 15, 2005 5:16 pm Post subject:
Re: Division in Fixed Point |
|
|
Wolfgang wrote:
| Quote: | Dear all,
Can anyone point me to some code how to implement a division in a Fixed
Point DSP ?
(Just to see how it works to fit it in mine)
Thx, Wolfgang
All of the fixed point DSP chips that I have worked with have a divide |
primitive; it basically does one bit's worth of division and leaves the
processor in a state to perform the next step with no intervening
instructions -- so you can just repeat the thing once for each
significant bit in your divisor.
So if you're doing this in assembly look in the instruction set
reference; there should be examples. If you're doing something like
fractional fixed-point in C then do the divide itself in assembly --
it'll be much faster.
--
Tim Wescott
Wescott Design Services
http://www.wescottdesign.com |
|
| Back to top |
|
|
Randy Yates
Guest
|
| Posted:
Thu Dec 15, 2005 5:16 pm Post subject:
Re: Division in Fixed Point |
|
|
"Wolfgang" <Never@nowhere.com> writes:
| Quote: | Dear all,
Can anyone point me to some code how to implement a division in a Fixed
Point DSP ?
(Just to see how it works to fit it in mine)
|
http://groups.google.com/group/comp.dsp/browse_frm/thread/9a21147500a7ee03/87630d175dd965db?lnk=st&q=fixed+point+division&rnum=4&hl=en#87630d175dd965db
Or, repeated here:
#include <stdint.h>
uint64_t Divide32(uint32_t y, uint32_t x)
{
uint16_t n;
uint64_t answer;
uint64_t remainder;
uint64_t divisor;
answer = 0;
remainder = x;
divisor = (uint64_t)y << 32;
for (n = 0; n < 32; n++)
{
divisor = divisor >> 1;
if (remainder >= divisor)
{
remainder -= divisor;
answer |= (uint64_t)1 << (63 - n);
}
}
for (n = 0; n < 32; n++)
{
remainder = remainder << 1;
if (remainder >= divisor)
{
remainder -= divisor;
answer |= (uint64_t)1 << (31 - n);
}
}
return answer;
}
--
% Randy Yates % "And all that I can do
%% Fuquay-Varina, NC % is say I'm sorry,
%%% 919-577-9882 % that's the way it goes..."
%%%% <yates@ieee.org> % Getting To The Point', *Balance of Power*, ELO
http://home.earthlink.net/~yatescr |
|
| Back to top |
|
|
Wolfgang
Guest
|
| Posted:
Thu Dec 15, 2005 5:16 pm Post subject:
Re: Division in Fixed Point |
|
|
Many thanks, Randy.
Yes Google is your friend I was impressed how fast I got relatively good
infos.
Thanks again, Wolfgang
"Randy Yates" <yates@ieee.org> schrieb im Newsbeitrag
news:64pqebz5.fsf@ieee.org...
| Quote: | "Wolfgang" <Never@nowhere.com> writes:
Dear all,
Can anyone point me to some code how to implement a division in a Fixed
Point DSP ?
(Just to see how it works to fit it in mine)
http://groups.google.com/group/comp.dsp/browse_frm/thread/9a21147500a7ee03/87630d175dd965db?lnk=st&q=fixed+point+division&rnum=4&hl=en#87630d175dd965db
Or, repeated here:
#include <stdint.h
uint64_t Divide32(uint32_t y, uint32_t x)
{
uint16_t n;
uint64_t answer;
uint64_t remainder;
uint64_t divisor;
answer = 0;
remainder = x;
divisor = (uint64_t)y << 32;
for (n = 0; n < 32; n++)
{
divisor = divisor >> 1;
if (remainder >= divisor)
{
remainder -= divisor;
answer |= (uint64_t)1 << (63 - n);
}
}
for (n = 0; n < 32; n++)
{
remainder = remainder << 1;
if (remainder >= divisor)
{
remainder -= divisor;
answer |= (uint64_t)1 << (31 - n);
}
}
return answer;
}
--
% Randy Yates % "And all that I can do
%% Fuquay-Varina, NC % is say I'm sorry,
%%% 919-577-9882 % that's the way it goes..."
%%%% <yates@ieee.org> % Getting To The Point', *Balance of
Power*, ELO
http://home.earthlink.net/~yatescr |
|
|
| Back to top |
|
|
Tim Wescott
Guest
|
| Posted:
Fri Dec 16, 2005 1:16 am Post subject:
Re: Division in Fixed Point |
|
|
Randy Yates wrote:
| Quote: | Yes, you're absolutely right about this, Tim. I chose to do it this
way on my DM642 project since I don't yet know the architecture
of this machine very well and, being a parallel machine it's a lot
more difficult to pick up than, e.g., the TMS32054x. The routine
is also invoked at a very low rate, so two to three times the
cycles of an assembly implementation isn't a problem.
--Randy
At a former employer I maintained a little library of fixed-point |
routines -- I had a couple of versions that were hand-optimized for
their target processors, and one version that was written as close to
the ANSI C++ spec as I could get that would compile and run correctly on
nearly anything.
The portable version used long division pretty much like yours.
--
Tim Wescott
Wescott Design Services
http://www.wescottdesign.com |
|
| Back to top |
|
|
Randy Yates
Guest
|
| Posted:
Fri Dec 16, 2005 1:16 am Post subject:
Re: Division in Fixed Point |
|
|
Yes, you're absolutely right about this, Tim. I chose to do it this
way on my DM642 project since I don't yet know the architecture
of this machine very well and, being a parallel machine it's a lot
more difficult to pick up than, e.g., the TMS32054x. The routine
is also invoked at a very low rate, so two to three times the
cycles of an assembly implementation isn't a problem.
--Randy |
|
| Back to top |
|
|
Korenje
Guest
|
| Posted:
Fri Dec 16, 2005 9:16 am Post subject:
Re: Division in Fixed Point |
|
|
| Quote: | Do you also have a starting point on how to determine the angle of an
X/Y-pair given in fixed point.
Is there a keyword for an algorithm I can google ?
|
take a look at http://dspguru.com/comp.dsp/tricks/alg/fxdatan2.htm
works fine for me
there is also magnitude estimator on the same site, if you need one
Mitja |
|
| Back to top |
|
|
Wolfgang
Guest
|
| Posted:
Fri Dec 16, 2005 9:16 am Post subject:
Re: Division in Fixed Point |
|
|
Dear Randy & Tim,
Many thanks, DM642 let my "ears ring".
Many thanks for the "assembly implementation" hint, now sitting in front of
TI's
Integer Division document.
Do you also have a starting point on how to determine the angle of an
X/Y-pair given in fixed point.
Is there a keyword for an algorithm I can google ?
Many thanks, Wolfgang |
|
| Back to top |
|
|
Randy Yates
Guest
|
| Posted:
Fri Dec 16, 2005 5:16 pm Post subject:
Re: Division in Fixed Point |
|
|
I also have used something similar to this with good results. Thanks
Jim for the trick!
--Randy
"Korenje" <korenje@yahoo.co.uk> writes:
| Quote: | Do you also have a starting point on how to determine the angle of an
X/Y-pair given in fixed point.
Is there a keyword for an algorithm I can google ?
take a look at http://dspguru.com/comp.dsp/tricks/alg/fxdatan2.htm
works fine for me
there is also magnitude estimator on the same site, if you need one
Mitja
|
--
% Randy Yates % "How's life on earth?
%% Fuquay-Varina, NC % ... What is it worth?"
%%% 919-577-9882 % 'Mission (A World Record)',
%%%% <yates@ieee.org> % *A New World Record*, ELO
http://home.earthlink.net/~yatescr |
|
| Back to top |
|
|
Wolfgang
Guest
|
| Posted:
Fri Dec 16, 2005 5:16 pm Post subject:
Re: Division in Fixed Point |
|
|
Many thanks Mitja,
Very interesting case.
Thank you for the link.
Wolfgang
"Korenje" <korenje@yahoo.co.uk> schrieb im Newsbeitrag
news:1134720961.351978.102620@g44g2000cwa.googlegroups.com...
| Quote: |
Do you also have a starting point on how to determine the angle of an
X/Y-pair given in fixed point.
Is there a keyword for an algorithm I can google ?
take a look at http://dspguru.com/comp.dsp/tricks/alg/fxdatan2.htm
works fine for me
there is also magnitude estimator on the same site, if you need one
Mitja
|
|
|
| Back to top |
|
|
Jitendra Rayala
Guest
|
| Posted:
Sun Dec 18, 2005 9:15 am Post subject:
Re: Division in Fixed Point |
|
|
Wolfgang wrote:
| Quote: | Dear all,
Can anyone point me to some code how to implement a division in a Fixed
Point DSP ?
(Just to see how it works to fit it in mine)
Thx, Wolfgang
|
In many DSPs usually a primitive division assist operation is
available. In those processors where it is not available, there is a
fast algorithm that uses multiply-accumulate operations which are
usually found in many DSPs to compute the division. It's a fairly old
algorithm developed by R.E. Goldschimdt for his MS thesis in 1964 [1].
A Matlab implementation of the algorithm for computing the reciprocal
of a 16-bit integer (1<x<2^15) is:
function Q = reciprocal(D)
if (D < 1) | (D > 32767),
error(' Reciprocal Error: Input out of bounds ');
end
% Normalize the input to fraction 0.5 <= D < 1
%
L = 0;
while D < 16384
D = 2*D;
L = L + 1;
end
N0 = 1;
D0 = D/(2^15);
% Reciprocal through multiplication algorithm
%
y = (1 - D0);
N1 = N0*(1 + y);
N2 = N1*(1 + y^2);
N3 = N2*(1 + y^4);
N4 = N3*(1 + y^8);
% Round the result.
%
Q = round(N4*2^(L));
% Saturate the result
%
Q = min(Q, 32767);
For example, on ZSP400 DSP core (http://www.zsp.com) which does not
have 1-bit division assist, it takes around 16 cycles to perform one
reciprocal. You can find more details on the algorithm and
implementation in a small application note here:
http://www.zsp.com/support/downloads/docs/pdf/fixedpointrecipalgo.pdf
Jitendra
[1] R. E. Goldschmidt, "Applications of Division by Convergence",
Master's Thesis, MIT, 1964. |
|
| Back to top |
|
|
Jerry Avins
Guest
|
| Posted:
Sun Dec 18, 2005 5:15 pm Post subject:
Re: Division in Fixed Point |
|
|
Jitendra Rayala wrote:
...
| Quote: | http://www.zsp.com/support/downloads/docs/pdf/fixedpointrecipalgo.pdf
|
A password is required for access.
Jerry
--
Engineering is the art of making what you want from things you can get.
ŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻ |
|
| Back to top |
|
|
m
Guest
|
| Posted:
Mon Dec 19, 2005 11:22 pm Post subject:
Re: Division in Fixed Point |
|
|
On Sun, 18 Dec 2005 10:18:26 -0500, Jerry Avins <jya@ieee.org> wrote:
Just cancel, register and download. |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in