AAC | ADPCM | Convolution | DAFx | FFT | IIR | Mixer | MP3 | MPEG | MPEG-4

  Hello everyone! I'm trying to implement Goertzel's algorithm on TI C6711 board using
fixed-point arithmetic. The problem is that I always end up with overflow...I'm using Q15
format for the filter coefficients, and I know that the samples of the input are also coded in
Q15. The problem seems to come from the additions that need to be done at each step, which make
the final result overflow. I use short (16-bit) integers to store the coefficients and the
input, and 32-bit integers for the results at each step. Pardon my ignorance, but I really
can't understand how I can avoid this...Moreover, since the sum of two Q15 numbers is also Q15,
it's totally incnomprehensible to me what, for example, an 18-bit Q15 number means. I suppose
either have to use saturation or scale down my input (which comes from the built-in microphones
on the PCM 3003 codec), but I don't know how to do it...I'd be grateful if anyone could give a
little help.

Andrew Milias
student @ E.E. department
University of Patras
Greece

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

C6711 is floating point processor  as such you don't need to spend time in Q format
conversions.
straight away use SP( single precision) and DP( precision) intrinsics or assembly instructions
for your algorithm ,
this will avoid all overflow issues.
 
Go to "help" in CCS for writing filter code, you have lots of sample codes available

 
thanks,
radha.

________________________________

From: a...@yahoogroups.com on behalf of a...@upnet.gr
Sent: Wed 4/26/2006 5:11 PM
To: a...@yahoogroups.com
Subject: [audiodsp] DTMF decoding using fixed-point arithmetic

  Hello everyone! I'm trying to implement Goertzel's algorithm on TI C6711 board using
fixed-point arithmetic. The problem is that I always end up with overflow...I'm using Q15
format for the filter coefficients, and I know that the samples of the input are also coded in
Q15. The problem seems to come from the additions that need to be done at each step, which make
the final result overflow. I use short (16-bit) integers to store the coefficients and the
input, and 32-bit integers for the results at each step. Pardon my ignorance, but I really
can't understand how I can avoid this...Moreover, since the sum of two Q15 numbers is also Q15,
it's totally incnomprehensible to me what, for example, an 18-bit Q15 number means. I suppose
either have to use saturation or scale down my input (which comes from the built-in microphones
on the PCM 3003 codec), but I don't know how to do it...I'd be grateful if anyone could give a
little help.

Andrew Milias
student @ E.E. department
University of Patras
Greece

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Hi,
Your assumption
>since the sum of two Q15 numbers is also Q15
is always not true. It can be Q1.14 (Eg: .99+.99 =
1.99 ) If 0.99 is in Q15 then 1.99 will not fit in
Q15, It shud be represented in Q1.14

So your further calculations should be done depending
on which format the latest result is in and
accordingly display the final result in appropriate Q
format,

-Vishvanath

--- a...@upnet.gr wrote:

>   Hello everyone! I'm trying to implement Goertzel's
> algorithm on TI C6711 board using fixed-point
> arithmetic. The problem is that I always end up with
> overflow...I'm using Q15 format for the filter
> coefficients, and I know that the samples of the
> input are also coded in Q15. The problem seems to
> come from the additions that need to be done at each
> step, which make the final result overflow. I use
> short (16-bit) integers to store the coefficients
> and the input, and 32-bit integers for the results
> at each step. Pardon my ignorance, but I really
> can't understand how I can avoid this...Moreover,
> since the sum of two Q15 numbers is also Q15, it's
> totally incnomprehensible to me what, for example,
> an 18-bit Q15 number means. I suppose either have to
> use saturation or scale down my input (which comes
> from the built-in microphones on the PCM 3003
> codec), but I don't know how to do it...I'd be
> grateful if anyone could give a little help.
> 
> Andrew Milias
> student @ E.E. department
> University of Patras
> Greece
>

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Jeff,
I said we should view the result of addition in Q1.14
format, else the last bit will be lost.
Eg : Could you tell me how do you represent 1.99 in
Q15 format (16 bit is the register width) ?
Your statement is absolutely correct - that overflow
happens and some bits are lost - But if you maintain
the same Q format (Q15) throughout your additions then
your  final result will be wrong.

When you see in binary its just placing the decimal
point to proper position, i mean its just how we view
the number.

Regards,
-Vishvanath 

--- Jeff Brower <j...@signalogic.com> wrote:

> Vishvanath-
> 
> > Your assumption
> >>since the sum of two Q15 numbers is also Q15
> > is always not true. It can be Q1.14 (Eg: .99+.99 =
> > 1.99 ) If 0.99 is in Q15 then 1.99 will not fit in
> > Q15, It shud be represented in Q1.14
> 
> This will confuse the OP.  Adding a series of Q15
> numbers *always results*
> in a Q15 number, although the result may have extra
> bits to left of
> decimal point.  If the register is not long enough,
> or there is not a
> guard-band in the accumulator, then the result will
> overflow and some bits
> lost.
> 
> -Jeff
> 
> > --- a...@upnet.gr wrote:
> >
> >>   Hello everyone! I'm trying to implement
> Goertzel's
> >> algorithm on TI C6711 board using fixed-point
> >> arithmetic. The problem is that I always end up
> with
> >> overflow...I'm using Q15 format for the filter
> >> coefficients, and I know that the samples of the
> >> input are also coded in Q15. The problem seems to
> >> come from the additions that need to be done at
> each
> >> step, which make the final result overflow. I use
> >> short (16-bit) integers to store the coefficients
> >> and the input, and 32-bit integers for the
> results
> >> at each step. Pardon my ignorance, but I really
> >> can't understand how I can avoid this...Moreover,
> >> since the sum of two Q15 numbers is also Q15,
> it's
> >> totally incnomprehensible to me what, for
> example,
> >> an 18-bit Q15 number means. I suppose either have
> to
> >> use saturation or scale down my input (which
> comes
> >> from the built-in microphones on the PCM 3003
> >> codec), but I don't know how to do it...I'd be
> >> grateful if anyone could give a little help.
> >>
> >> Andrew Milias
> >> student @ E.E. department
> >> University of Patras
> >> Greece
> >>
> >>
> >>
> >
> >
> >
> >
> > 
> >
> >
> >     a...@yahoogroups.com
> >
> >
> >
> >
> >

___________________________________________________________ 
Win tickets to the 2006 FIFA World Cup Germany with Yahoo! Messenger.
http://advision.webevents.yahoo.com/fifaworldcup_uk/

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Vishvanath-

> Your assumption
>>since the sum of two Q15 numbers is also Q15
> is always not true. It can be Q1.14 (Eg: .99+.99 =
> 1.99 ) If 0.99 is in Q15 then 1.99 will not fit in
> Q15, It shud be represented in Q1.14

This will confuse the OP.  Adding a series of Q15 numbers *always results*
in a Q15 number, although the result may have extra bits to left of
decimal point.  If the register is not long enough, or there is not a
guard-band in the accumulator, then the result will overflow and some bits
lost.

-Jeff

> --- a...@upnet.gr wrote:
>
>>   Hello everyone! I'm trying to implement Goertzel's
>> algorithm on TI C6711 board using fixed-point
>> arithmetic. The problem is that I always end up with
>> overflow...I'm using Q15 format for the filter
>> coefficients, and I know that the samples of the
>> input are also coded in Q15. The problem seems to
>> come from the additions that need to be done at each
>> step, which make the final result overflow. I use
>> short (16-bit) integers to store the coefficients
>> and the input, and 32-bit integers for the results
>> at each step. Pardon my ignorance, but I really
>> can't understand how I can avoid this...Moreover,
>> since the sum of two Q15 numbers is also Q15, it's
>> totally incnomprehensible to me what, for example,
>> an 18-bit Q15 number means. I suppose either have to
>> use saturation or scale down my input (which comes
>> from the built-in microphones on the PCM 3003
>> codec), but I don't know how to do it...I'd be
>> grateful if anyone could give a little help.
>>
>> Andrew Milias
>> student @ E.E. department
>> University of Patras
>> Greece
>>

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Vishvanath-

> I said we should view the result of addition in Q1.14
> format, else the last bit will be lost.
> Eg : Could you tell me how do you represent 1.99 in
> Q15 format (16 bit is the register width) ?

After adding 0.99 and 0.99 both in Q15 format with a 16-bit accumlator,
the msb is already lost and the result no longer makes sense.  Your
suggestion to use Q14 format to change how we 'view' the result will not
save the bit.

But I know what you mean, just has to be said differently.  It would make
sense to apply Q14 format to values *before* adding, in which case a
result of 1.99 can fit in the 16-bit accumulator result.

> Your statement is absolutely correct - that overflow
> happens and some bits are lost - But if you maintain
> the same Q format (Q15) throughout your additions then
> your  final result will be wrong.

If the accumlator has a guard-band, as many do including all DSPs that
I've used, then you can continue to add Q15 numbers.  For example, if you
have to average 4 Q15 numbers, and you have an  8-bit guard-band, then you
can add them, shift the final sum right by 2 (divide by 4) and you have a
Q15 answer.  The "Q view" never changes.

-Jeff

> --- Jeff Brower <j...@signalogic.com> wrote:
>
>> Vishvanath-
>>
>> > Your assumption
>> >>since the sum of two Q15 numbers is also Q15
>> > is always not true. It can be Q1.14 (Eg: .99+.99 =
>> > 1.99 ) If 0.99 is in Q15 then 1.99 will not fit in
>> > Q15, It shud be represented in Q1.14
>>
>> This will confuse the OP.  Adding a series of Q15
>> numbers *always results*
>> in a Q15 number, although the result may have extra
>> bits to left of
>> decimal point.  If the register is not long enough,
>> or there is not a
>> guard-band in the accumulator, then the result will
>> overflow and some bits
>> lost.
>>
>> -Jeff
>>
>> > --- a...@upnet.gr wrote:
>> >
>> >>   Hello everyone! I'm trying to implement
>> Goertzel's
>> >> algorithm on TI C6711 board using fixed-point
>> >> arithmetic. The problem is that I always end up
>> with
>> >> overflow...I'm using Q15 format for the filter
>> >> coefficients, and I know that the samples of the
>> >> input are also coded in Q15. The problem seems to
>> >> come from the additions that need to be done at
>> each
>> >> step, which make the final result overflow. I use
>> >> short (16-bit) integers to store the coefficients
>> >> and the input, and 32-bit integers for the
>> results
>> >> at each step. Pardon my ignorance, but I really
>> >> can't understand how I can avoid this...Moreover,
>> >> since the sum of two Q15 numbers is also Q15,
>> it's
>> >> totally incnomprehensible to me what, for
>> example,
>> >> an 18-bit Q15 number means. I suppose either have
>> to
>> >> use saturation or scale down my input (which
>> comes
>> >> from the built-in microphones on the PCM 3003
>> >> codec), but I don't know how to do it...I'd be
>> >> grateful if anyone could give a little help.
>> >>
>> >> Andrew Milias
>> >> student @ E.E. department
>> >> University of Patras
>> >> Greece
>> >>
>> >>
>> >>
>> >
>> >
>> >
>> >
>> > 
>> >
>> >
>> >     a...@yahoogroups.com
>> >
>> >
>> >
>> >
>> >
> ___________________________________________________________
> Win tickets to the 2006 FIFA World Cup Germany with Yahoo! Messenger.
> http://advision.webevents.yahoo.com/fifaworldcup_uk/
>

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

  Thank you all very much for the help. I agree that using fixed point arithmetic on a
floating point processor is a little weird, but this is what I've been assigned to do! I'm
currently analyzing the new things I've learned through your posts, and I'll come back soon
with more questions!
Thank you very much again.

Andrew Milias

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Hi 
     The format of the data needs careful selection. it is not strainght. I would suggest you
to first find out the max and min value of delay output data format and current output data
format with worst case input data for loop size your using for the computation of magnitude. 
  So accordingly you need to choose format accordly. It is quite trick do. first start
implementation in floating point in matlab then implament in fixed format based on the 
  y(n), y(n-1), x(n-1) and x(n) ranges.
  The Most popular algorithm for DTMF detection is  goertzel algorithm. It is infact it is a
single point DFT realised as a first order IIR filter form. So important fact is the Q format
depends on LOOP or order of N and input data format (needs scaling) and coefficients format
also.
  hopre this help 
  best regards
  Amaresh

"Deshpande,Vishvanath" <v...@yahoo.com> wrote:
  Hi,
Your assumption
>since the sum of two Q15 numbers is also Q15
is always not true. It can be Q1.14 (Eg: .99+.99 =
1.99 ) If 0.99 is in Q15 then 1.99 will not fit in
Q15, It shud be represented in Q1.14

So your further calculations should be done depending
on which format the latest result is in and
accordingly display the final result in appropriate Q
format,

-Vishvanath

--- a...@upnet.gr wrote:

>   Hello everyone! I'm trying to implement Goertzel's
> algorithm on TI C6711 board using fixed-point
> arithmetic. The problem is that I always end up with
> overflow...I'm using Q15 format for the filter
> coefficients, and I know that the samples of the
> input are also coded in Q15. The problem seems to
> come from the additions that need to be done at each
> step, which make the final result overflow. I use
> short (16-bit) integers to store the coefficients
> and the input, and 32-bit integers for the results
> at each step. Pardon my ignorance, but I really
> can't understand how I can avoid this...Moreover,
> since the sum of two Q15 numbers is also Q15, it's
> totally incnomprehensible to me what, for example,
> an 18-bit Q15 number means. I suppose either have to
> use saturation or scale down my input (which comes
> from the built-in microphones on the PCM 3003
> codec), but I don't know how to do it...I'd be
> grateful if anyone could give a little help.
> 
> Andrew Milias
> student @ E.E. department
> University of Patras
> Greece
>

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Jeff,
I agree to the most of your points. Still one doubt or
rather you can correct my understanding if its wrong,

A Q15 format :  
0 Integer bits(I),1 Sign Bit(S),15 fractional bit(F)  

So Q15 + Q 15 would result,
0 I's, 2 S's, 30 F's of which last 16 F's will be
automatically lost (since it is 16 bit register)
So we are left with,
0 I's 2 S's 14 F's
So now you left shift it by 1 to get rid of sign, 
0 I's 1 S 15 F (lsb fraction bit being 0)

In case of overeflow the overflow bit will be sitting
in place of sign bit so can we use that as one of the
integer bit of Q14 (- which is 1I 1S 14 F) and display
the result ????

Please correct me when i am wrong,

Thanks,
-Vishvanath

--- Jeff Brower <j...@signalogic.com> wrote:

> Vishvanath-
> 
> > I said we should view the result of addition in
> Q1.14
> > format, else the last bit will be lost.
> > Eg : Could you tell me how do you represent 1.99
> in
> > Q15 format (16 bit is the register width) ?
> 
> After adding 0.99 and 0.99 both in Q15 format with a
> 16-bit accumlator,
> the msb is already lost and the result no longer
> makes sense.  Your
> suggestion to use Q14 format to change how we 'view'
> the result will not
> save the bit.
> 
> But I know what you mean, just has to be said
> differently.  It would make
> sense to apply Q14 format to values *before* adding,
> in which case a
> result of 1.99 can fit in the 16-bit accumulator
> result.
> 
> > Your statement is absolutely correct - that
> overflow
> > happens and some bits are lost - But if you
> maintain
> > the same Q format (Q15) throughout your additions
> then
> > your  final result will be wrong.
> 
> If the accumlator has a guard-band, as many do
> including all DSPs that
> I've used, then you can continue to add Q15 numbers.
>  For example, if you
> have to average 4 Q15 numbers, and you have an 
> 8-bit guard-band, then you
> can add them, shift the final sum right by 2 (divide
> by 4) and you have a
> Q15 answer.  The "Q view" never changes.
> 
> -Jeff
> 
> > --- Jeff Brower <j...@signalogic.com> wrote:
> >
> >> Vishvanath-
> >>
> >> > Your assumption
> >> >>since the sum of two Q15 numbers is also Q15
> >> > is always not true. It can be Q1.14 (Eg:
> .99+.99 =
> >> > 1.99 ) If 0.99 is in Q15 then 1.99 will not fit
> in
> >> > Q15, It shud be represented in Q1.14
> >>
> >> This will confuse the OP.  Adding a series of Q15
> >> numbers *always results*
> >> in a Q15 number, although the result may have
> extra
> >> bits to left of
> >> decimal point.  If the register is not long
> enough,
> >> or there is not a
> >> guard-band in the accumulator, then the result
> will
> >> overflow and some bits
> >> lost.
> >>
> >> -Jeff
> >>
> >> > --- a...@upnet.gr wrote:
> >> >
> >> >>   Hello everyone! I'm trying to implement
> >> Goertzel's
> >> >> algorithm on TI C6711 board using fixed-point
> >> >> arithmetic. The problem is that I always end
> up
> >> with
> >> >> overflow...I'm using Q15 format for the filter
> >> >> coefficients, and I know that the samples of
> the
> >> >> input are also coded in Q15. The problem seems
> to
> >> >> come from the additions that need to be done
> at
> >> each
> >> >> step, which make the final result overflow. I
> use
> >> >> short (16-bit) integers to store the
> coefficients
> >> >> and the input, and 32-bit integers for the
> >> results
> >> >> at each step. Pardon my ignorance, but I
> really
> >> >> can't understand how I can avoid
> this...Moreover,
> >> >> since the sum of two Q15 numbers is also Q15,
> >> it's
> >> >> totally incnomprehensible to me what, for
> >> example,
> >> >> an 18-bit Q15 number means. I suppose either
> have
> >> to
> >> >> use saturation or scale down my input (which
> >> comes
> >> >> from the built-in microphones on the PCM 3003
> >> >> codec), but I don't know how to do it...I'd be
> >> >> grateful if anyone could give a little help.
> >> >>
> >> >> Andrew Milias
> >> >> student @ E.E. department
> >> >> University of Patras
> >> >> Greece
> >> >>
> >> >>
> >> >>
> >> >
> >> >
> >> >
> >> >

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Vishvanath-

> I agree to the most of your points. Still one doubt or
> rather you can correct my understanding if its wrong,
>
> A Q15 format :
> 0 Integer bits(I),1 Sign Bit(S),15 fractional bit(F)
>
> So Q15 + Q 15 would result,
> 0 I's, 2 S's, 30 F's of which last 16 F's will be
> automatically lost (since it is 16 bit register)

This is true for multiply of two Q15 numbers, not addition.  After adding,
there is no change in position of decimal point and still only 1 sign bit.

> So we are left with,
> 0 I's 2 S's 14 F's
> So now you left shift it by 1 to get rid of sign,
> 0 I's 1 S 15 F (lsb fraction bit being 0)

True for multiply!

> In case of overeflow the overflow bit will be sitting
> in place of sign bit so can we use that as one of the
> integer bit of Q14 (- which is 1I 1S 14 F) and display
> the result ????

If you use the Q15xQ15 multiply result without left shift, then yes it
must be treated as Q14.  It's of interest that many processors and DSPs
include an option for automatic 1-bit left-shift after multiply.

-Jeff

> --- Jeff Brower <j...@signalogic.com> wrote:
>
>> Vishvanath-
>>
>> > I said we should view the result of addition in
>> Q1.14
>> > format, else the last bit will be lost.
>> > Eg : Could you tell me how do you represent 1.99
>> in
>> > Q15 format (16 bit is the register width) ?
>>
>> After adding 0.99 and 0.99 both in Q15 format with a
>> 16-bit accumlator,
>> the msb is already lost and the result no longer
>> makes sense.  Your
>> suggestion to use Q14 format to change how we 'view'
>> the result will not
>> save the bit.
>>
>> But I know what you mean, just has to be said
>> differently.  It would make
>> sense to apply Q14 format to values *before* adding,
>> in which case a
>> result of 1.99 can fit in the 16-bit accumulator
>> result.
>>
>> > Your statement is absolutely correct - that
>> overflow
>> > happens and some bits are lost - But if you
>> maintain
>> > the same Q format (Q15) throughout your additions
>> then
>> > your  final result will be wrong.
>>
>> If the accumlator has a guard-band, as many do
>> including all DSPs that
>> I've used, then you can continue to add Q15 numbers.
>>  For example, if you
>> have to average 4 Q15 numbers, and you have an
>> 8-bit guard-band, then you
>> can add them, shift the final sum right by 2 (divide
>> by 4) and you have a
>> Q15 answer.  The "Q view" never changes.
>>
>> -Jeff
>>
>> > --- Jeff Brower <j...@signalogic.com> wrote:
>> >
>> >> Vishvanath-
>> >>
>> >> > Your assumption
>> >> >>since the sum of two Q15 numbers is also Q15
>> >> > is always not true. It can be Q1.14 (Eg:
>> .99+.99 =
>> >> > 1.99 ) If 0.99 is in Q15 then 1.99 will not fit
>> in
>> >> > Q15, It shud be represented in Q1.14
>> >>
>> >> This will confuse the OP.  Adding a series of Q15
>> >> numbers *always results*
>> >> in a Q15 number, although the result may have
>> extra
>> >> bits to left of
>> >> decimal point.  If the register is not long
>> enough,
>> >> or there is not a
>> >> guard-band in the accumulator, then the result
>> will
>> >> overflow and some bits
>> >> lost.
>> >>
>> >> -Jeff
>> >>
>> >> > --- a...@upnet.gr wrote:
>> >> >
>> >> >>   Hello everyone! I'm trying to implement
>> >> Goertzel's
>> >> >> algorithm on TI C6711 board using fixed-point
>> >> >> arithmetic. The problem is that I always end
>> up
>> >> with
>> >> >> overflow...I'm using Q15 format for the filter
>> >> >> coefficients, and I know that the samples of
>> the
>> >> >> input are also coded in Q15. The problem seems
>> to
>> >> >> come from the additions that need to be done
>> at
>> >> each
>> >> >> step, which make the final result overflow. I
>> use
>> >> >> short (16-bit) integers to store the
>> coefficients
>> >> >> and the input, and 32-bit integers for the
>> >> results
>> >> >> at each step. Pardon my ignorance, but I
>> really
>> >> >> can't understand how I can avoid
>> this...Moreover,
>> >> >> since the sum of two Q15 numbers is also Q15,
>> >> it's
>> >> >> totally incnomprehensible to me what, for
>> >> example,
>> >> >> an 18-bit Q15 number means. I suppose either
>> have
>> >> to
>> >> >> use saturation or scale down my input (which
>> >> comes
>> >> >> from the built-in microphones on the PCM 3003
>> >> >> codec), but I don't know how to do it...I'd be
>> >> >> grateful if anyone could give a little help.
>> >> >>
>> >> >> Andrew Milias
>> >> >> student @ E.E. department
>> >> >> University of Patras
>> >> >> Greece
>> >> >>
>> >> >>
>> >> >>
>> >> >
>> >> >
>> >> >
>> >>

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Soundararajan K-

> As all the numbers are normalised to be below 1.0, there may not be
> a situation of overflow in case of mutiplication.This will make the
> product of 0.999 and 0.999 still be less than 1.0 and the overflow
> bit may not arise at all.

Overflow cannot occur with Q15 x Q15 multiplication, by definition.

-Jeff

> > Vishvanath-
> >
> > > I agree to the most of your points. Still one doubt or
> > > rather you can correct my understanding if its wrong,
> > >
> > > A Q15 format :
> > > 0 Integer bits(I),1 Sign Bit(S),15 fractional bit(F)
> > >
> > > So Q15 + Q 15 would result,
> > > 0 I's, 2 S's, 30 F's of which last 16 F's will be
> > > automatically lost (since it is 16 bit register)
> >
> > This is true for multiply of two Q15 numbers, not addition.  After
> adding,
> > there is no change in position of decimal point and still only 1
> sign bit.
> >
> > > So we are left with,
> > > 0 I's 2 S's 14 F's
> > > So now you left shift it by 1 to get rid of sign,
> > > 0 I's 1 S 15 F (lsb fraction bit being 0)
> >
> > True for multiply!
> >
> > > In case of overeflow the overflow bit will be sitting
> > > in place of sign bit so can we use that as one of the
> > > integer bit of Q14 (- which is 1I 1S 14 F) and display
> > > the result ????
> >
> > If you use the Q15xQ15 multiply result without left shift, then
> yes it
> > must be treated as Q14.  It's of interest that many processors and
> DSPs
> > include an option for automatic 1-bit left-shift after multiply.
> >
> > -Jeff
> >
> > > --- Jeff Brower <jbrower@...> wrote:
> > >
> > >> Vishvanath-
> > >>
> > >> > I said we should view the result of addition in
> > >> Q1.14
> > >> > format, else the last bit will be lost.
> > >> > Eg : Could you tell me how do you represent 1.99
> > >> in
> > >> > Q15 format (16 bit is the register width) ?
> > >>
> > >> After adding 0.99 and 0.99 both in Q15 format with a
> > >> 16-bit accumlator,
> > >> the msb is already lost and the result no longer
> > >> makes sense.  Your
> > >> suggestion to use Q14 format to change how we 'view'
> > >> the result will not
> > >> save the bit.
> > >>
> > >> But I know what you mean, just has to be said
> > >> differently.  It would make
> > >> sense to apply Q14 format to values *before* adding,
> > >> in which case a
> > >> result of 1.99 can fit in the 16-bit accumulator
> > >> result.
> > >>
> > >> > Your statement is absolutely correct - that
> > >> overflow
> > >> > happens and some bits are lost - But if you
> > >> maintain
> > >> > the same Q format (Q15) throughout your additions
> > >> then
> > >> > your  final result will be wrong.
> > >>
> > >> If the accumlator has a guard-band, as many do
> > >> including all DSPs that
> > >> I've used, then you can continue to add Q15 numbers.
> > >>  For example, if you
> > >> have to average 4 Q15 numbers, and you have an
> > >> 8-bit guard-band, then you
> > >> can add them, shift the final sum right by 2 (divide
> > >> by 4) and you have a
> > >> Q15 answer.  The "Q view" never changes.
> > >>
> > >> -Jeff
> > >>
> > >> > --- Jeff Brower <jbrower@...> wrote:
> > >> >
> > >> >> Vishvanath-
> > >> >>
> > >> >> > Your assumption
> > >> >> >>since the sum of two Q15 numbers is also Q15
> > >> >> > is always not true. It can be Q1.14 (Eg:
> > >> .99+.99 =
> > >> >> > 1.99 ) If 0.99 is in Q15 then 1.99 will not fit
> > >> in
> > >> >> > Q15, It shud be represented in Q1.14
> > >> >>
> > >> >> This will confuse the OP.  Adding a series of Q15
> > >> >> numbers *always results*
> > >> >> in a Q15 number, although the result may have
> > >> extra
> > >> >> bits to left of
> > >> >> decimal point.  If the register is not long
> > >> enough,
> > >> >> or there is not a
> > >> >> guard-band in the accumulator, then the result
> > >> will
> > >> >> overflow and some bits
> > >> >> lost.
> > >> >>
> > >> >> -Jeff
> > >> >>
> > >> >> > --- amhlias@... wrote:
> > >> >> >
> > >> >> >>   Hello everyone! I'm trying to implement
> > >> >> Goertzel's
> > >> >> >> algorithm on TI C6711 board using fixed-point
> > >> >> >> arithmetic. The problem is that I always end
> > >> up
> > >> >> with
> > >> >> >> overflow...I'm using Q15 format for the filter
> > >> >> >> coefficients, and I know that the samples of
> > >> the
> > >> >> >> input are also coded in Q15. The problem seems
> > >> to
> > >> >> >> come from the additions that need to be done
> > >> at
> > >> >> each
> > >> >> >> step, which make the final result overflow. I
> > >> use
> > >> >> >> short (16-bit) integers to store the
> > >> coefficients
> > >> >> >> and the input, and 32-bit integers for the
> > >> >> results
> > >> >> >> at each step. Pardon my ignorance, but I
> > >> really
> > >> >> >> can't understand how I can avoid
> > >> this...Moreover,
> > >> >> >> since the sum of two Q15 numbers is also Q15,
> > >> >> it's
> > >> >> >> totally incnomprehensible to me what, for
> > >> >> example,
> > >> >> >> an 18-bit Q15 number means. I suppose either
> > >> have
> > >> >> to
> > >> >> >> use saturation or scale down my input (which
> > >> >> comes
> > >> >> >> from the built-in microphones on the PCM 3003
> > >> >> >> codec), but I don't know how to do it...I'd be
> > >> >> >> grateful if anyone could give a little help.
> > >> >> >>
> > >> >> >> Andrew Milias
> > >> >> >> student @ E.E. department
> > >> >> >> University of Patras
> > >> >> >> Greece
> > >> >> >>
> > >> >> >>
> > >> >> >>
> > >> >> >
> > >> >> >
> > >> >> >
> > >> >> >
> > >
> > >
> > >
> > >
> > >
> > > 
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> >

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Overflow never happens with multiplication, it is addition/subtraction that=
=20
one has to take care of..
>From: Jeff Brower <j...@signalogic.com>
>To: Soundararajan <n...@yahoo.co.in>
>CC: a...@yahoogroups.com
>Subject: [audiodsp] Re: DTMF decoding using fixed-point arithmetic
>Date: Mon, 01 May 2006 21:10:10 -0500
>
>Soundararajan K-
>
> > As all the numbers are normalised to be below 1.0, there may not be
> > a situation of overflow in case of mutiplication.This will make the
> > product of 0.999 and 0.999 still be less than 1.0 and the overflow
> > bit may not arise at all.
>
>Overflow cannot occur with Q15 x Q15 multiplication, by definition.
>
>-Jeff
>
> > > Vishvanath-
> > >
> > > > I agree to the most of your points. Still one doubt or
> > > > rather you can correct my understanding if its wrong,
> > > >
> > > > A Q15 format :
> > > > 0 Integer bits(I),1 Sign Bit(S),15 fractional bit(F)
> > > >
> > > > So Q15 + Q 15 would result,
> > > > 0 I's, 2 S's, 30 F's of which last 16 F's will be
> > > > automatically lost (since it is 16 bit register)
> > >
> > > This is true for multiply of two Q15 numbers, not addition.  After
> > adding,
> > > there is no change in position of decimal point and still only 1
> > sign bit.
> > >
> > > > So we are left with,
> > > > 0 I's 2 S's 14 F's
> > > > So now you left shift it by 1 to get rid of sign,
> > > > 0 I's 1 S 15 F (lsb fraction bit being 0)
> > >
> > > True for multiply!
> > >
> > > > In case of overeflow the overflow bit will be sitting
> > > > in place of sign bit so can we use that as one of the
> > > > integer bit of Q14 (- which is 1I 1S 14 F) and display
> > > > the result ????
> > >
> > > If you use the Q15xQ15 multiply result without left shift, then
> > yes it
> > > must be treated as Q14.  It's of interest that many processors and
> > DSPs
> > > include an option for automatic 1-bit left-shift after multiply.
> > >
> > > -Jeff
> > >
> > > > --- Jeff Brower <jbrower@...> wrote:
> > > >
> > > >> Vishvanath-
> > > >>
> > > >> > I said we should view the result of addition in
> > > >> Q1.14
> > > >> > format, else the last bit will be lost.
> > > >> > Eg : Could you tell me how do you represent 1.99
> > > >> in
> > > >> > Q15 format (16 bit is the register width) ?
> > > >>
> > > >> After adding 0.99 and 0.99 both in Q15 format with a
> > > >> 16-bit accumlator,
> > > >> the msb is already lost and the result no longer
> > > >> makes sense.  Your
> > > >> suggestion to use Q14 format to change how we 'view'
> > > >> the result will not
> > > >> save the bit.
> > > >>
> > > >> But I know what you mean, just has to be said
> > > >> differently.  It would make
> > > >> sense to apply Q14 format to values *before* adding,
> > > >> in which case a
> > > >> result of 1.99 can fit in the 16-bit accumulator
> > > >> result.
> > > >>
> > > >> > Your statement is absolutely correct - that
> > > >> overflow
> > > >> > happens and some bits are lost - But if you
> > > >> maintain
> > > >> > the same Q format (Q15) throughout your additions
> > > >> then
> > > >> > your  final result will be wrong.
> > > >>
> > > >> If the accumlator has a guard-band, as many do
> > > >> including all DSPs that
> > > >> I've used, then you can continue to add Q15 numbers.
> > > >>  For example, if you
> > > >> have to average 4 Q15 numbers, and you have an
> > > >> 8-bit guard-band, then you
> > > >> can add them, shift the final sum right by 2 (divide
> > > >> by 4) and you have a
> > > >> Q15 answer.  The "Q view" never changes.
> > > >>
> > > >> -Jeff
> > > >>
> > > >> > --- Jeff Brower <jbrower@...> wrote:
> > > >> >
> > > >> >> Vishvanath-
> > > >> >>
> > > >> >> > Your assumption
> > > >> >> >>since the sum of two Q15 numbers is also Q15
> > > >> >> > is always not true. It can be Q1.14 (Eg:
> > > >> .99+.99 =3D
> > > >> >> > 1.99 ) If 0.99 is in Q15 then 1.99 will not fit
> > > >> in
> > > >> >> > Q15, It shud be represented in Q1.14
> > > >> >>
> > > >> >> This will confuse the OP.  Adding a series of Q15
> > > >> >> numbers *always results*
> > > >> >> in a Q15 number, although the result may have
> > > >> extra
> > > >> >> bits to left of
> > > >> >> decimal point.  If the register is not long
> > > >> enough,
> > > >> >> or there is not a
> > > >> >> guard-band in the accumulator, then the result
> > > >> will
> > > >> >> overflow and some bits
> > > >> >> lost.
> > > >> >>
> > > >> >> -Jeff
> > > >> >>
> > > >> >> > --- amhlias@... wrote:
> > > >> >> >
> > > >> >> >>   Hello everyone! I'm trying to implement
> > > >> >> Goertzel's
> > > >> >> >> algorithm on TI C6711 board using fixed-point
> > > >> >> >> arithmetic. The problem is that I always end
> > > >> up
> > > >> >> with
> > > >> >> >> overflow...I'm using Q15 format for the filter
> > > >> >> >> coefficients, and I know that the samples of
> > > >> the
> > > >> >> >> input are also coded in Q15. The problem seems
> > > >> to
> > > >> >> >> come from the additions that need to be done
> > > >> at
> > > >> >> each
> > > >> >> >> step, which make the final result overflow. I
> > > >> use
> > > >> >> >> short (16-bit) integers to store the
> > > >> coefficients
> > > >> >> >> and the input, and 32-bit integers for the
> > > >> >> results
> > > >> >> >> at each step. Pardon my ignorance, but I
> > > >> really
> > > >> >> >> can't understand how I can avoid
> > > >> this...Moreover,
> > > >> >> >> since the sum of two Q15 numbers is also Q15,
> > > >> >> it's
> > > >> >> >> totally incnomprehensible to me what, for
> > > >> >> example,
> > > >> >> >> an 18-bit Q15 number means. I suppose either
> > > >> have
> > > >> >> to
> > > >> >> >> use saturation or scale down my input (which
> > > >> >> comes
> > > >> >> >> from the built-in microphones on the PCM 3003
> > > >> >> >> codec), but I don't know how to do it...I'd be
> > > >> >> >> grateful if anyone could give a little help.
> > > >> >> >>
> > > >> >> >> Andrew Milias
> > > >> >> >> student @ E.E. department
> > > >> >> >> University of Patras
> > > >> >> >> Greece
> > > >> >> >>
> > > >> >> >>
> > > >> >> >>
> > > >> >> >
> > > >> >> >
> > > >> >> >
> > > >> >> >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > > 
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > >

=20

=20

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Hi,

I couldn't get the jist of all the discussion properly, but here is what I
know about Fixed point arithmetic:-

1.> Q15 x Q15 will not generate an overflow except for the case of both
operand being -1 (0x8000 in Fx pt). Therefore ETSI L_mult has a saturation
operation inbuilt.

2.> When you add two Q15 numbers, you should always do it in this manner:-

R =3D=3D (x>>1) + (y>>1);  // Resultant R is in Q14 as mentioned in earlier=
 post

No overflow can occur in this case, therefore no saturation is required.

3.> For filtering, general practice is to calculate the log2 of the filter
Tap, and shift right the input or the accumulated output(usually 32 to 40
bits). The latter is more precise.
Rip

On 5/2/06, Jeff Brower <j...@signalogic.com> wrote:
>
> Soundararajan K-
>
> > As all the numbers are normalised to be below 1.0, there may not be
> > a situation of overflow in case of mutiplication.This will make the
> > product of 0.999 and 0.999 still be less than 1.0 and the overflow
> > bit may not arise at all.
>
> Overflow cannot occur with Q15 x Q15 multiplication, by definition.
> -Jeff
> > > Vishvanath-
> > >
> > > > I agree to the most of your points. Still one doubt or
> > > > rather you can correct my understanding if its wrong,
> > > >
> > > > A Q15 format :
> > > > 0 Integer bits(I),1 Sign Bit(S),15 fractional bit(F)
> > > >
> > > > So Q15 + Q 15 would result,
> > > > 0 I's, 2 S's, 30 F's of which last 16 F's will be
> > > > automatically lost (since it is 16 bit register)
> > >
> > > This is true for multiply of two Q15 numbers, not addition.  After
> > adding,
> > > there is no change in position of decimal point and still only 1
> > sign bit.
> > >
> > > > So we are left with,
> > > > 0 I's 2 S's 14 F's
> > > > So now you left shift it by 1 to get rid of sign,
> > > > 0 I's 1 S 15 F (lsb fraction bit being 0)
> > >
> > > True for multiply!
> > >
> > > > In case of overeflow the overflow bit will be sitting
> > > > in place of sign bit so can we use that as one of the
> > > > integer bit of Q14 (- which is 1I 1S 14 F) and display
> > > > the result ????
> > >
> > > If you use the Q15xQ15 multiply result without left shift, then
> > yes it
> > > must be treated as Q14.  It's of interest that many processors and
> > DSPs
> > > include an option for automatic 1-bit left-shift after multiply.
> > >
> > > -Jeff
> > >
> > > > --- Jeff Brower <jbrower@...> wrote:
> > > >
> > > >> Vishvanath-
> > > >>
> > > >> > I said we should view the result of addition in
> > > >> Q1.14
> > > >> > format, else the last bit will be lost.
> > > >> > Eg : Could you tell me how do you represent 1.99
> > > >> in
> > > >> > Q15 format (16 bit is the register width) ?
> > > >>
> > > >> After adding 0.99 and 0.99 both in Q15 format with a
> > > >> 16-bit accumlator,
> > > >> the msb is already lost and the result no longer
> > > >> makes sense.  Your
> > > >> suggestion to use Q14 format to change how we 'view'
> > > >> the result will not
> > > >> save the bit.
> > > >>
> > > >> But I know what you mean, just has to be said
> > > >> differently.  It would make
> > > >> sense to apply Q14 format to values *before* adding,
> > > >> in which case a
> > > >> result of 1.99 can fit in the 16-bit accumulator
> > > >> result.
> > > >>
> > > >> > Your statement is absolutely correct - that
> > > >> overflow
> > > >> > happens and some bits are lost - But if you
> > > >> maintain
> > > >> > the same Q format (Q15) throughout your additions
> > > >> then
> > > >> > your  final result will be wrong.
> > > >>
> > > >> If the accumlator has a guard-band, as many do
> > > >> including all DSPs that
> > > >> I've used, then you can continue to add Q15 numbers.
> > > >>  For example, if you
> > > >> have to average 4 Q15 numbers, and you have an
> > > >> 8-bit guard-band, then you
> > > >> can add them, shift the final sum right by 2 (divide
> > > >> by 4) and you have a
> > > >> Q15 answer.  The "Q view" never changes.
> > > >>
> > > >> -Jeff
> > > >>
> > > >> > --- Jeff Brower <jbrower@...> wrote:
> > > >> >
> > > >> >> Vishvanath-
> > > >> >>
> > > >> >> > Your assumption
> > > >> >> >>since the sum of two Q15 numbers is also Q15
> > > >> >> > is always not true. It can be Q1.14 (Eg:
> > > >> .99+.99 =3D> > > >> >> > 1.99 ) If 0.99 is in
Q15 then 1.99 will n=
ot fit
> > > >> in
> > > >> >> > Q15, It shud be represented in Q1.14
> > > >> >>
> > > >> >> This will confuse the OP.  Adding a series of Q15
> > > >> >> numbers *always results*
> > > >> >> in a Q15 number, although the result may have
> > > >> extra
> > > >> >> bits to left of
> > > >> >> decimal point.  If the register is not long
> > > >> enough,
> > > >> >> or there is not a
> > > >> >> guard-band in the accumulator, then the result
> > > >> will
> > > >> >> overflow and some bits
> > > >> >> lost.
> > > >> >>
> > > >> >> -Jeff
> > > >> >>
> > > >> >> > --- amhlias@... wrote:
> > > >> >> >
> > > >> >> >>   Hello everyone! I'm trying to implement
> > > >> >> Goertzel's
> > > >> >> >> algorithm on TI C6711 board using fixed-point
> > > >> >> >> arithmetic. The problem is that I always end
> > > >> up
> > > >> >> with
> > > >> >> >> overflow...I'm using Q15 format for the filter
> > > >> >> >> coefficients, and I know that the samples of
> > > >> the
> > > >> >> >> input are also coded in Q15. The problem seems
> > > >> to
> > > >> >> >> come from the additions that need to be done
> > > >> at
> > > >> >> each
> > > >> >> >> step, which make the final result overflow. I
> > > >> use
> > > >> >> >> short (16-bit) integers to store the
> > > >> coefficients
> > > >> >> >> and the input, and 32-bit integers for the
> > > >> >> results
> > > >> >> >> at each step. Pardon my ignorance, but I
> > > >> really
> > > >> >> >> can't understand how I can avoid
> > > >> this...Moreover,
> > > >> >> >> since the sum of two Q15 numbers is also Q15,
> > > >> >> it's
> > > >> >> >> totally incnomprehensible to me what, for
> > > >> >> example,
> > > >> >> >> an 18-bit Q15 number means. I suppose either
> > > >> have
> > > >> >> to
> > > >> >> >> use saturation or scale down my input (which
> > > >> >> comes
> > > >> >> >> from the built-in microphones on the PCM 3003
> > > >> >> >> codec), but I don't know how to do it...I'd be
> > > >> >> >> grateful if anyone could give a little help.
> > > >> >> >>
> > > >> >> >> Andrew Milias
> > > >> >> >> student @ E.E. department
> > > >> >> >> University of Patras
> > > >> >> >> Greece
> > > >> >> >>
> > > >> >> >>
> > > >> >> >>
> > > >> >> >
> > > >> >> >
> > > >> >> >
> > > >> >> >
> > > >
> > > >

=20

=20

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Just to complete what Jeff left unsaid:

----Original Message Follows----
From: Jeff Brower <j...@signalogic.com>
To: Soundararajan <n...@yahoo.co.in>
CC: a...@yahoogroups.com
Subject: [audiodsp] Re: DTMF decoding using fixed-point arithmetic
Date: Mon, 01 May 2006 21:10:10 -0500

Soundararajan K-

 >> As all the numbers are normalised to be below 1.0, there may not be
 >> a situation of overflow in case of mutiplication.This will make the
 >> product of 0.999 and 0.999 still be less than 1.0 and the overflow
 >> bit may not arise at all.

>Overflow cannot occur with Q15 x Q15 multiplication, by definition.

Except in one case where -1(FFFF)*-1(FFFF) results in an EXTRAORDINARY 
situation.

--Bhooshan

-Jeff

 > > Vishvanath-
 > >
 > > > I agree to the most of your points. Still one doubt or
 > > > rather you can correct my understanding if its wrong,
 > > >
 > > > A Q15 format :
 > > > 0 Integer bits(I),1 Sign Bit(S),15 fractional bit(F)
 > > >
 > > > So Q15 + Q 15 would result,
 > > > 0 I's, 2 S's, 30 F's of which last 16 F's will be
 > > > automatically lost (since it is 16 bit register)
 > >
 > > This is true for multiply of two Q15 numbers, not addition.  After
 > adding,
 > > there is no change in position of decimal point and still only 1
 > sign bit.
 > >
 > > > So we are left with,
 > > > 0 I's 2 S's 14 F's
 > > > So now you left shift it by 1 to get rid of sign,
 > > > 0 I's 1 S 15 F (lsb fraction bit being 0)
 > >
 > > True for multiply!
 > >
 > > > In case of overeflow the overflow bit will be sitting
 > > > in place of sign bit so can we use that as one of the
 > > > integer bit of Q14 (- which is 1I 1S 14 F) and display
 > > > the result ????
 > >
 > > If you use the Q15xQ15 multiply result without left shift, then
 > yes it
 > > must be treated as Q14.  It's of interest that many processors and
 > DSPs
 > > include an option for automatic 1-bit left-shift after multiply.
 > >
 > > -Jeff
 > >
 > > > --- Jeff Brower <jbrower@...> wrote:
 > > >
 > > >> Vishvanath-
 > > >>
 > > >> > I said we should view the result of addition in
 > > >> Q1.14
 > > >> > format, else the last bit will be lost.
 > > >> > Eg : Could you tell me how do you represent 1.99
 > > >> in
 > > >> > Q15 format (16 bit is the register width) ?
 > > >>
 > > >> After adding 0.99 and 0.99 both in Q15 format with a
 > > >> 16-bit accumlator,
 > > >> the msb is already lost and the result no longer
 > > >> makes sense.  Your
 > > >> suggestion to use Q14 format to change how we 'view'
 > > >> the result will not
 > > >> save the bit.
 > > >>
 > > >> But I know what you mean, just has to be said
 > > >> differently.  It would make
 > > >> sense to apply Q14 format to values *before* adding,
 > > >> in which case a
 > > >> result of 1.99 can fit in the 16-bit accumulator
 > > >> result.
 > > >>
 > > >> > Your statement is absolutely correct - that
 > > >> overflow
 > > >> > happens and some bits are lost - But if you
 > > >> maintain
 > > >> > the same Q format (Q15) throughout your additions
 > > >> then
 > > >> > your  final result will be wrong.
 > > >>
 > > >> If the accumlator has a guard-band, as many do
 > > >> including all DSPs that
 > > >> I've used, then you can continue to add Q15 numbers.
 > > >>  For example, if you
 > > >> have to average 4 Q15 numbers, and you have an
 > > >> 8-bit guard-band, then you
 > > >> can add them, shift the final sum right by 2 (divide
 > > >> by 4) and you have a
 > > >> Q15 answer.  The "Q view" never changes.
 > > >>
 > > >> -Jeff
 > > >>
 > > >> > --- Jeff Brower <jbrower@...> wrote:
 > > >> >
 > > >> >> Vishvanath-
 > > >> >>
 > > >> >> > Your assumption
 > > >> >> >>since the sum of two Q15 numbers is also Q15
 > > >> >> > is always not true. It can be Q1.14 (Eg:
 > > >> .99+.99 =
 > > >> >> > 1.99 ) If 0.99 is in Q15 then 1.99 will not fit
 > > >> in
 > > >> >> > Q15, It shud be represented in Q1.14
 > > >> >>
 > > >> >> This will confuse the OP.  Adding a series of Q15
 > > >> >> numbers *always results*
 > > >> >> in a Q15 number, although the result may have
 > > >> extra
 > > >> >> bits to left of
 > > >> >> decimal point.  If the register is not long
 > > >> enough,
 > > >> >> or there is not a
 > > >> >> guard-band in the accumulator, then the result
 > > >> will
 > > >> >> overflow and some bits
 > > >> >> lost.
 > > >> >>
 > > >> >> -Jeff
 > > >> >>
 > > >> >> > --- amhlias@... wrote:
 > > >> >> >
 > > >> >> >>   Hello everyone! I'm trying to implement
 > > >> >> Goertzel's
 > > >> >> >> algorithm on TI C6711 board using fixed-point
 > > >> >> >> arithmetic. The problem is that I always end
 > > >> up
 > > >> >> with
 > > >> >> >> overflow...I'm using Q15 format for the filter
 > > >> >> >> coefficients, and I know that the samples of
 > > >> the
 > > >> >> >> input are also coded in Q15. The problem seems
 > > >> to
 > > >> >> >> come from the additions that need to be done
 > > >> at
 > > >> >> each
 > > >> >> >> step, which make the final result overflow. I
 > > >> use
 > > >> >> >> short (16-bit) integers to store the
 > > >> coefficients
 > > >> >> >> and the input, and 32-bit integers for the
 > > >> >> results
 > > >> >> >> at each step. Pardon my ignorance, but I
 > > >> really
 > > >> >> >> can't understand how I can avoid
 > > >> this...Moreover,
 > > >> >> >> since the sum of two Q15 numbers is also Q15,
 > > >> >> it's
 > > >> >> >> totally incnomprehensible to me what, for
 > > >> >> example,
 > > >> >> >> an 18-bit Q15 number means. I suppose either
 > > >> have
 > > >> >> to
 > > >> >> >> use saturation or scale down my input (which
 > > >> >> comes
 > > >> >> >> from the built-in microphones on the PCM 3003
 > > >> >> >> codec), but I don't know how to do it...I'd be
 > > >> >> >> grateful if anyone could give a little help.
 > > >> >> >>
 > > >> >> >> Andrew Milias
 > > >> >> >> student @ E.E. department
 > > >> >> >> University of Patras
 > > >> >> >> Greece
 > > >> >> >>
 > > >> >> >>
 > > >> >> >>
 > > >> >> >
 > > >> >> >
 > > >> >> >
 > > >> >> >
 > > >
 > > >
 > > >
 > > >
 > > >
 > > > 
 > > >
 > > >
 > > >
 > > >
 > > >
 > > >
 > > >
 > >

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Ripinder-

> I couldn't get the jist of all the discussion properly, but here is what I
> know about Fixed point arithmetic:-
> 
> 1.> Q15 x Q15 will not generate an overflow except for the case of both
> operand being -1 (0x8000 in Fx pt). Therefore ETSI L_mult has a saturation
> operation inbuilt.
> 
> 2.> When you add two Q15 numbers, you should always do it in this manner:-
> 
> R == (x>>1) + (y>>1);  // Resultant R is in Q14 as mentioned in earlier post
> 
> No overflow can occur in this case, therefore no saturation is required.

No.  On what conditions addition overflow will occur is machine dependent.  Some
processors have accumlator "guard band" that can tolerate overflow up to 8 digits or
more left of decimal point.  Reducing precision *prior* to addition is a last resort
and should be avoided if at all possible.

> 3.> For filtering, general practice is to calculate the log2 of the filter
> Tap, and shift right the input or the accumulated output(usually 32 to 40
> bits). The latter is more precise.

Again, not necessarily -- you have to look at the specific processor capabilities.

Students:  the whole point of fixed-point arithmetic is to implement fast math on an
embedded processor, for example DSP, FPGA, microcontroller, etc.  Therefore you
*must* look carefully at *which* processor before making assumptions about how you
will implement fixed-point operations.

-Jeff
> On 5/2/06, Jeff Brower <j...@signalogic.com> wrote:
> >
> > Soundararajan K-
> >
> > > As all the numbers are normalised to be below 1.0, there may not be
> > > a situation of overflow in case of mutiplication.This will make the
> > > product of 0.999 and 0.999 still be less than 1.0 and the overflow
> > > bit may not arise at all.
> >
> > Overflow cannot occur with Q15 x Q15 multiplication, by definition.
> >
> >
> > -Jeff
> >
> >
> > > > Vishvanath-
> > > >
> > > > > I agree to the most of your points. Still one doubt or
> > > > > rather you can correct my understanding if its wrong,
> > > > >
> > > > > A Q15 format :
> > > > > 0 Integer bits(I),1 Sign Bit(S),15 fractional bit(F)
> > > > >
> > > > > So Q15 + Q 15 would result,
> > > > > 0 I's, 2 S's, 30 F's of which last 16 F's will be
> > > > > automatically lost (since it is 16 bit register)
> > > >
> > > > This is true for multiply of two Q15 numbers, not addition.  After
> > > adding,
> > > > there is no change in position of decimal point and still only 1
> > > sign bit.
> > > >
> > > > > So we are left with,
> > > > > 0 I's 2 S's 14 F's
> > > > > So now you left shift it by 1 to get rid of sign,
> > > > > 0 I's 1 S 15 F (lsb fraction bit being 0)
> > > >
> > > > True for multiply!
> > > >
> > > > > In case of overeflow the overflow bit will be sitting
> > > > > in place of sign bit so can we use that as one of the
> > > > > integer bit of Q14 (- which is 1I 1S 14 F) and display
> > > > > the result ????
> > > >
> > > > If you use the Q15xQ15 multiply result without left shift, then
> > > yes it
> > > > must be treated as Q14.  It's of interest that many processors and
> > > DSPs
> > > > include an option for automatic 1-bit left-shift after multiply.
> > > >
> > > > -Jeff
> > > >
> > > > > --- Jeff Brower <jbrower@...> wrote:
> > > > >
> > > > >> Vishvanath-
> > > > >>
> > > > >> > I said we should view the result of addition in
> > > > >> Q1.14
> > > > >> > format, else the last bit will be lost.
> > > > >> > Eg : Could you tell me how do you represent 1.99
> > > > >> in
> > > > >> > Q15 format (16 bit is the register width) ?
> > > > >>
> > > > >> After adding 0.99 and 0.99 both in Q15 format with a
> > > > >> 16-bit accumlator,
> > > > >> the msb is already lost and the result no longer
> > > > >> makes sense.  Your
> > > > >> suggestion to use Q14 format to change how we 'view'
> > > > >> the result will not
> > > > >> save the bit.
> > > > >>
> > > > >> But I know what you mean, just has to be said
> > > > >> differently.  It would make
> > > > >> sense to apply Q14 format to values *before* adding,
> > > > >> in which case a
> > > > >> result of 1.99 can fit in the 16-bit accumulator
> > > > >> result.
> > > > >>
> > > > >> > Your statement is absolutely correct - that
> > > > >> overflow
> > > > >> > happens and some bits are lost - But if you
> > > > >> maintain
> > > > >> > the same Q format (Q15) throughout your additions
> > > > >> then
> > > > >> > your  final result will be wrong.
> > > > >>
> > > > >> If the accumlator has a guard-band, as many do
> > > > >> including all DSPs that
> > > > >> I've used, then you can continue to add Q15 numbers.
> > > > >>  For example, if you
> > > > >> have to average 4 Q15 numbers, and you have an
> > > > >> 8-bit guard-band, then you
> > > > >> can add them, shift the final sum right by 2 (divide
> > > > >> by 4) and you have a
> > > > >> Q15 answer.  The "Q view" never changes.
> > > > >>
> > > > >> -Jeff
> > > > >>
> > > > >> > --- Jeff Brower <jbrower@...> wrote:
> > > > >> >
> > > > >> >> Vishvanath-
> > > > >> >>
> > > > >> >> > Your assumption
> > > > >> >> >>since the sum of two Q15 numbers is also Q15
> > > > >> >> > is always not true. It can be Q1.14 (Eg:
> > > > >> .99+.99 => > > >> >> > 1.99 ) If 0.99 is
in Q15 then 1.99 will not fit
> > > > >> in
> > > > >> >> > Q15, It shud be represented in Q1.14
> > > > >> >>
> > > > >> >> This will confuse the OP.  Adding a series of Q15
> > > > >> >> numbers *always results*
> > > > >> >> in a Q15 number, although the result may have
> > > > >> extra
> > > > >> >> bits to left of
> > > > >> >> decimal point.  If the register is not long
> > > > >> enough,
> > > > >> >> or there is not a
> > > > >> >> guard-band in the accumulator, then the result
> > > > >> will
> > > > >> >> overflow and some bits
> > > > >> >> lost.
> > > > >> >>
> > > > >> >> -Jeff
> > > > >> >>
> > > > >> >> > --- amhlias@... wrote:
> > > > >> >> >
> > > > >> >> >>   Hello everyone! I'm trying to implement
> > > > >> >> Goertzel's
> > > > >> >> >> algorithm on TI C6711 board using fixed-point
> > > > >> >> >> arithmetic. The problem is that I always end
> > > > >> up
> > > > >> >> with
> > > > >> >> >> overflow...I'm using Q15 format for the filter
> > > > >> >> >> coefficients, and I know that the samples of
> > > > >> the
> > > > >> >> >> input are also coded in Q15. The problem seems
> > > > >> to
> > > > >> >> >> come from the additions that need to be done
> > > > >> at
> > > > >> >> each
> > > > >> >> >> step, which make the final result overflow. I
> > > > >> use
> > > > >> >> >> short (16-bit) integers to store the
> > > > >> coefficients
> > > > >> >> >> and the input, and 32-bit integers for the
> > > > >> >> results
> > > > >> >> >> at each step. Pardon my ignorance, but I
> > > > >> really
> > > > >> >> >> can't understand how I can avoid
> > > > >> this...Moreover,
> > > > >> >> >> since the sum of two Q15 numbers is also Q15,
> > > > >> >> it's
> > > > >> >> >> totally incnomprehensible to me what, for
> > > > >> >> example,
> > > > >> >> >> an 18-bit Q15 number means. I suppose either
> > > > >> have
> > > > >> >> to
> > > > >> >> >> use saturation or scale down my input (which
> > > > >> >> comes
> > > > >> >> >> from the built-in microphones on the PCM 3003
> > > > >> >> >> codec), but I don't know how to do it...I'd be
> > > > >> >> >> grateful if anyone could give a little help.
> > > > >> >> >>
> > > > >> >> >> Andrew Milias
> > > > >> >> >> student @ E.E. department
> > > > >> >> >> University of Patras
> > > > >> >> >> Greece
> > > > >> >> >>
> > > > >> >> >>
> > > > >> >> >>
> > > > >> >> >
> > > > >> >> >
> > > > >> >> >
> > > > >> >> >
> > > > >
> > > >

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

 As Bhooshan as highlighted one exception as per mathematical multiplication rule.
  But not for practical implementation. many DSP have logic to handle this kind of special
case.   In TI C54xx processor There is special bit called SMUL that takes care this
exception......! Enable the SMUL bit or mode the result will be i.e appro +1(0.9999).
   
  With regards
  Amaresh

Bhooshan iyer <b...@hotmail.com> wrote:
  Just to complete what Jeff left unsaid:

----Original Message Follows----
From: Jeff Brower <j...@signalogic.com>
To: Soundararajan <n...@yahoo.co.in>
CC: a...@yahoogroups.com
Subject: [audiodsp] Re: DTMF decoding using fixed-point arithmetic
Date: Mon, 01 May 2006 21:10:10 -0500

Soundararajan K-

>> As all the numbers are normalised to be below 1.0, there may not be
>> a situation of overflow in case of mutiplication.This will make the
>> product of 0.999 and 0.999 still be less than 1.0 and the overflow
>> bit may not arise at all.

>Overflow cannot occur with Q15 x Q15 multiplication, by definition.

Except in one case where -1(FFFF)*-1(FFFF) results in an EXTRAORDINARY 
situation.

--Bhooshan

-Jeff

> > Vishvanath-
> >
> > > I agree to the most of your points. Still one doubt or
> > > rather you can correct my understanding if its wrong,
> > >
> > > A Q15 format :
> > > 0 Integer bits(I),1 Sign Bit(S),15 fractional bit(F)
> > >
> > > So Q15 + Q 15 would result,
> > > 0 I's, 2 S's, 30 F's of which last 16 F's will be
> > > automatically lost (since it is 16 bit register)
> >
> > This is true for multiply of two Q15 numbers, not addition.  After
> adding,
> > there is no change in position of decimal point and still only 1
> sign bit.
> >
> > > So we are left with,
> > > 0 I's 2 S's 14 F's
> > > So now you left shift it by 1 to get rid of sign,
> > > 0 I's 1 S 15 F (lsb fraction bit being 0)
> >
> > True for multiply!
> >
> > > In case of overeflow the overflow bit will be sitting
> > > in place of sign bit so can we use that as one of the
> > > integer bit of Q14 (- which is 1I 1S 14 F) and display
> > > the result ????
> >
> > If you use the Q15xQ15 multiply result without left shift, then
> yes it
> > must be treated as Q14.  It's of interest that many processors and
> DSPs
> > include an option for automatic 1-bit left-shift after multiply.
> >
> > -Jeff
> >
> > > --- Jeff Brower <jbrower@...> wrote:
> > >
> > >> Vishvanath-
> > >>
> > >> > I said we should view the result of addition in
> > >> Q1.14
> > >> > format, else the last bit will be lost.
> > >> > Eg : Could you tell me how do you represent 1.99
> > >> in
> > >> > Q15 format (16 bit is the register width) ?
> > >>
> > >> After adding 0.99 and 0.99 both in Q15 format with a
> > >> 16-bit accumlator,
> > >> the msb is already lost and the result no longer
> > >> makes sense.  Your
> > >> suggestion to use Q14 format to change how we 'view'
> > >> the result will not
> > >> save the bit.
> > >>
> > >> But I know what you mean, just has to be said
> > >> differently.  It would make
> > >> sense to apply Q14 format to values *before* adding,
> > >> in which case a
> > >> result of 1.99 can fit in the 16-bit accumulator
> > >> result.
> > >>
> > >> > Your statement is absolutely correct - that
> > >> overflow
> > >> > happens and some bits are lost - But if you
> > >> maintain
> > >> > the same Q format (Q15) throughout your additions
> > >> then
> > >> > your  final result will be wrong.
> > >>
> > >> If the accumlator has a guard-band, as many do
> > >> including all DSPs that
> > >> I've used, then you can continue to add Q15 numbers.
> > >>  For example, if you
> > >> have to average 4 Q15 numbers, and you have an
> > >> 8-bit guard-band, then you
> > >> can add them, shift the final sum right by 2 (divide
> > >> by 4) and you have a
> > >> Q15 answer.  The "Q view" never changes.
> > >>
> > >> -Jeff
> > >>
> > >> > --- Jeff Brower <jbrower@...> wrote:
> > >> >
> > >> >> Vishvanath-
> > >> >>
> > >> >> > Your assumption
> > >> >> >>since the sum of two Q15 numbers is also Q15
> > >> >> > is always not true. It can be Q1.14 (Eg:
> > >> .99+.99 =
> > >> >> > 1.99 ) If 0.99 is in Q15 then 1.99 will not fit
> > >> in
> > >> >> > Q15, It shud be represented in Q1.14
> > >> >>
> > >> >> This will confuse the OP.  Adding a series of Q15
> > >> >> numbers *always results*
> > >> >> in a Q15 number, although the result may have
> > >> extra
> > >> >> bits to left of
> > >> >> decimal point.  If the register is not long
> > >> enough,
> > >> >> or there is not a
> > >> >> guard-band in the accumulator, then the result
> > >> will
> > >> >> overflow and some bits
> > >> >> lost.
> > >> >>
> > >> >> -Jeff
> > >> >>
> > >> >> > --- amhlias@... wrote:
> > >> >> >
> > >> >> >>   Hello everyone! I'm trying to implement
> > >> >> Goertzel's
> > >> >> >> algorithm on TI C6711 board using fixed-point
> > >> >> >> arithmetic. The problem is that I always end
> > >> up
> > >> >> with
> > >> >> >> overflow...I'm using Q15 format for the filter
> > >> >> >> coefficients, and I know that the samples of
> > >> the
> > >> >> >> input are also coded in Q15. The problem seems
> > >> to
> > >> >> >> come from the additions that need to be done
> > >> at
> > >> >> each
> > >> >> >> step, which make the final result overflow. I
> > >> use
> > >> >> >> short (16-bit) integers to store the
> > >> coefficients
> > >> >> >> and the input, and 32-bit integers for the
> > >> >> results
> > >> >> >> at each step. Pardon my ignorance, but I
> > >> really
> > >> >> >> can't understand how I can avoid
> > >> this...Moreover,
> > >> >> >> since the sum of two Q15 numbers is also Q15,
> > >> >> it's
> > >> >> >> totally incnomprehensible to me what, for
> > >> >> example,
> > >> >> >> an 18-bit Q15 number means. I suppose either
> > >> have
> > >> >> to
> > >> >> >> use saturation or scale down my input (which
> > >> >> comes
> > >> >> >> from the built-in microphones on the PCM 3003
> > >> >> >> codec), but I don't know how to do it...I'd be
> > >> >> >> grateful if anyone could give a little help.
> > >> >> >>
> > >> >> >> Andrew Milias
> > >> >> >> student @ E.E. department
> > >> >> >> University of Patras
> > >> >> >> Greece
> > >> >> >>
> > >> >> >>
> > >> >> >>
> > >> >> >
> > >> >> >
> > >> >> >
> > >> >> >
> > >
> > >
> > >
> > >
> > >
> > > 
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> >

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )