Division in Fixed Point

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.

Jitendra Rayala wrote:

   ...

> 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.
�����������������������������������������������������������������������

On Sun, 18 Dec 2005 10:18:26 -0500, Jerry Avins <jya@ieee.org> wrote:

>Jitendra Rayala wrote:
>
>   ...
>
>> http://www.zsp.com/support/downloads/docs/pdf/fixedpointrecipalgo.pdf
>
>A password is required for access.
>
>Jerry

Just cancel, register and download.