A password is required for access.
Jerry
--
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������
Reply by Jitendra Rayala●December 18, 20052005-12-18
Wolfgang wrote:
> 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.
Reply by Randy Yates●December 16, 20052005-12-16
I also have used something similar to this with good results. Thanks
Jim for the trick!
--Randy
"Korenje" <korenje@yahoo.co.uk> writes:
>> 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
Reply by Wolfgang●December 16, 20052005-12-16
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...
>
>> 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
>
Reply by Korenje●December 16, 20052005-12-16
> 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 ?
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
Reply by Tim Wescott●December 15, 20052005-12-15
Randy Yates wrote:
> 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
Reply by Randy Yates●December 15, 20052005-12-15
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
Reply by Tim Wescott●December 15, 20052005-12-15
Wolfgang wrote:
> 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