fixed point implementation of Acoustic Echo Cancellor

Dear all,

I am implementing a fixed point acoustic echo cancellor algorithm on
TMS320VC5510 DSK board. In the first step, I have to convert existing
Matlab code to fixed point C code. I am new to this fixed point
implementation. I did a lot of search to understand fixed point math
used for these DSP algorithms. I found some, but I couldn't understand
how to handle overflow and round off errors we face during addition
and multiplication operations. If anyone has any documents with
examples about fixed point implementation, can you please forward.

Thank you all in advance,
Rahul Start a New Thread

> Subject: fixed point implementation of Acoustic Echo Cancellor
> Posted by: "rahul_mot" rahul_mot
> Date: Fri Jan 30, 2009 4:36 pm ((PST))
>
> Dear all,
>
> I am implementing a fixed point acoustic echo cancellor algorithm on
> TMS320VC5510 DSK board. In the first step, I have to convert existing
> Matlab code to fixed point C code. I am new to this fixed point
> implementation. I did a lot of search to understand fixed point math
> used for these DSP algorithms. I found some, but I couldn't understand
> how to handle overflow and round off errors we face during addition
> and multiplication operations. If anyone has any documents with
> examples about fixed point implementation, can you please forward.
>
> Thank you all in advance,
> Rahul
>

Hi Rahul,

Basically, there are only two methods to handle an overflow exception:
if the CPU in use has got a hardwired interrupt or flag then the software
may monitor this condition; alternately, if the CPU does not provide with
the interrupt and/or flag, then the software may implement a number of
checks for overflow condition on its own. Yet another way (to save time
othervise spent for the tests) is to use saturation arithmetic that
many CPUs would provide you with.

The roundoff is much more specific to the floating point than to the
fixed point math. For example, nether fixed point addition not subtraction
produce any roundoff. Results of fixed point multiplication and division
might be rounded, down to complete cancellation, so again, either the CPU
or software need to check such conditions. In fact, the cancellation might
not be very dangerous, unless such a result is used to scale down some
other data. For example you divide two non zero numbers to obtain a factor,
which is cancelled and then you scale down an array by this factor, which
is zero in the particular fixed point representation. The same thing
may occur in a floating point math as in any finite precision system.

As far as a document, the best one is David Goldberg's paper "What every
computer scientist should know about floating point arithmetic" which is
available on the net free of charge. I remember I got it on
http://docs.sun.com/ Yes, it is dealing with the floating point math, but
you may always think about a fixed point system as of being a floating point
system with a constant exponent.

HTH,

Andrew Start a New Thread

Hello Andrew,

Thank you for your information and suggestions. I have another
question. I have to do a fixed point division between two 32-bit
numbers. I am trying to write a function that will take two 32-bit
numbers (x,y) in Q31 format and returns a 32-bit result of x/y in Q31
format. Can you please help me with this?

Thanks a lot in advance.
Rahul

--- In c..., Andrew Nesterov wrote:
>
> > Subject: fixed point implementation of Acoustic Echo Cancellor
> > Posted by: "rahul_mot" rahul_mot
> > Date: Fri Jan 30, 2009 4:36 pm ((PST))
> >
> > Dear all,
> >
> > I am implementing a fixed point acoustic echo cancellor algorithm on
> > TMS320VC5510 DSK board. In the first step, I have to convert existing
> > Matlab code to fixed point C code. I am new to this fixed point
> > implementation. I did a lot of search to understand fixed point math
> > used for these DSP algorithms. I found some, but I couldn't understand
> > how to handle overflow and round off errors we face during addition
> > and multiplication operations. If anyone has any documents with
> > examples about fixed point implementation, can you please forward.
> >
> > Thank you all in advance,
> > Rahul
> > Hi Rahul,
>
> Basically, there are only two methods to handle an overflow exception:
> if the CPU in use has got a hardwired interrupt or flag then the
software
> may monitor this condition; alternately, if the CPU does not provide
with
> the interrupt and/or flag, then the software may implement a number of
> checks for overflow condition on its own. Yet another way (to save time
> othervise spent for the tests) is to use saturation arithmetic that
> many CPUs would provide you with.
>
> The roundoff is much more specific to the floating point than to the
> fixed point math. For example, nether fixed point addition not
subtraction
> produce any roundoff. Results of fixed point multiplication and division
> might be rounded, down to complete cancellation, so again, either
the CPU
> or software need to check such conditions. In fact, the cancellation
might
> not be very dangerous, unless such a result is used to scale down some
> other data. For example you divide two non zero numbers to obtain a
factor,
> which is cancelled and then you scale down an array by this factor,
which
> is zero in the particular fixed point representation. The same thing
> may occur in a floating point math as in any finite precision system.
>
> As far as a document, the best one is David Goldberg's paper "What every
> computer scientist should know about floating point arithmetic" which is
> available on the net free of charge. I remember I got it on
> http://docs.sun.com/ Yes, it is dealing with the floating point
math, but
> you may always think about a fixed point system as of being a
floating point
> system with a constant exponent.
>
> HTH,
>
> Andrew
> Start a New Thread

Rahul,

If I were to be done a Q31 division routine, I would have used
an idea like this: at first I would have calculated the sign of
the result and made both operands unsigned, next I would have
determined the exponents of both (the amounts of leading zeroes),
shifted both left by the corresponding exponents, but making
sure the result of integer division is < 1 (thus the dividend
is left shifted by its exponent minus 1), along with this the
result exponent is also calculated that gives the amount of shift
right the result of unsigned integer division. After that has been
done, the rest is to mix all the three, the sign, the shift right and
the unsigned integer division.

A few caveats: don't try to divide by zero :) next, if your dividend
is >= the divisor, take care that you render the result of division
as a sum of an integer part and a Q31 fractional part, otherwise result
would be in the Q31 range. That means that your routine might need to
have a paramter that returns an error code in case of division by zero
and a paramter that is used to store the integer part.

That seem to be the right track for me, however I might have made a mistake
by a chance, if someone spots something wrong, please let me know.

Rgds,

Andrew

> Subject: Re: fixed point implementation of Acoustic Echo Cancellor
> Posted by: "rahul_mot"
> Date: Tue Feb 10, 2009 3:24 am ((PST))
>
> Hello Andrew,
>
> Thank you for your information and suggestions. I have another
> question. I have to do a fixed point division between two 32-bit
> numbers. I am trying to write a function that will take two 32-bit
> numbers (x,y) in Q31 format and returns a 32-bit result of x/y in Q31
> format. Can you please help me with this?
>
> Thanks a lot in advance.
> Rahul Start a New Thread

Hi Andrew,

Thanks for your information and suggestions.

- Rahul
--- In c..., Andrew Nesterov wrote:
> Rahul,
>
> If I were to be done a Q31 division routine, I would have used
> an idea like this: at first I would have calculated the sign of
> the result and made both operands unsigned, next I would have
> determined the exponents of both (the amounts of leading zeroes),
> shifted both left by the corresponding exponents, but making
> sure the result of integer division is < 1 (thus the dividend
> is left shifted by its exponent minus 1), along with this the
> result exponent is also calculated that gives the amount of shift
> right the result of unsigned integer division. After that has been
> done, the rest is to mix all the three, the sign, the shift right and
> the unsigned integer division.
>
> A few caveats: don't try to divide by zero :) next, if your dividend
> is >= the divisor, take care that you render the result of division
> as a sum of an integer part and a Q31 fractional part, otherwise result
> would be in the Q31 range. That means that your routine might need to
> have a paramter that returns an error code in case of division by zero
> and a paramter that is used to store the integer part.
>
> That seem to be the right track for me, however I might have made a
mistake
> by a chance, if someone spots something wrong, please let me know.
>
> Rgds,
>
> Andrew
>
> > Subject: Re: fixed point implementation of Acoustic Echo Cancellor
> > Posted by: "rahul_mot"
> > Date: Tue Feb 10, 2009 3:24 am ((PST))
> >
> > Hello Andrew,
> >
> > Thank you for your information and suggestions. I have another
> > question. I have to do a fixed point division between two 32-bit
> > numbers. I am trying to write a function that will take two 32-bit
> > numbers (x,y) in Q31 format and returns a 32-bit result of x/y in Q31
> > format. Can you please help me with this?
> >
> > Thanks a lot in advance.
> > Rahul
> >
> Start a New Thread