Beginner: Integer FFT and Fixed Point FFT

"Al Clark" <dsp@danvillesignal.com> wrote in message
news:Xns966097AD67874aclarkdanvillesignal@66.133.129.71...
> "Jon Harris" <jon_harrisTIGER@hotmail.com> wrote in
> news:1196uts4b5krfe6@corp.supernews.com:
>
> > "Richard Owlett" <rowlett@atlascomm.net> wrote in message
> > news:1196sh38u0kgm10@corp.supernews.com...
> >> Jerry Avins wrote:
> >>
> >> > Mark Borgerding wrote:
> >> >
> >> >   ...
> >> >
> >> >> Bud: What's the difference between fixed-point and integer
> >> >> processing? Lou: Just a bit.
> >> >> Bud: But what exactly is the difference?
> >> >> Lou: I told you -- just a bit.
> >> >> Bud: Look here. Do you know how to do both types of processing?
> >> >> Lou: Yes.
> >> >> Bud: What do you do differently?
> >> >> Lou: I halve the fixed-point product.
> >> >> Bud: Sure. In the end everyone wants to have a product, but how do
> >> >> you get there.
> >> >>
> >>
> >> I'm a sucker.
> >> I'll bite.
> >>
> >> What's the difference between fixed-point and integer?
> >>
> >> I suspect something subtle but significant.
> >
> > I'm not sure about the terminology used above, but in the many DSPs, a
> > fixed-point number can be interpreted as either an integer or a
> > fractional value.  Assuming a signed 16-bit two's complement
> > representation, the fraction interpretation of the bits means that the
> > number is between -1 and +0.9999694. On the other hand with an integer
> > interpretation, it is between -32768 and +32767.  On the SHARC, when
> > you multiply 2 fixed-point numbers together, you can specify for each
> > number if it should be treated as integer or fractional.  The
> > difference is simply in the shifting of the result, but obviously it
> > is quite significant to the answer!
>
> I'm not sure if Jon's explanation makes the difference clear:
>
> If you assume fixed point representation, you normally assume one sign
> bit and N fractional bits. For example, the Sharc fractional format is
> typically in 1.31. If the multiplier didn't do anything special, then
> when you multiplied two 1.31 numbers you would get a result that was in
> 2.62 format. There would be a redundant sign bit. This is automatically
> adjusted for by the DSP by a bit shift of 1, so that the result is in
> 1.63 format and therefore the fractional numbers are interpreted
> correctly (you often round the result to 1.31 format at some point).
>
> Now if you reread Bud and Lou, you will get the joke.

I didn't get the "halve" part the first time either, but now that you've
explained it, I do!
-Jon

"glen herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message
news:m_mdnRGTIqACFQ7fRVn-uA@comcast.com...
> Jon Harris wrote:
>
> (snip)
>
> > I'm not sure about the terminology used above, but in the many DSPs, a
> > fixed-point number can be interpreted as either an integer or a fractional
> > value.  Assuming a signed 16-bit two's complement representation, the
fraction
> > interpretation of the bits means that the number is between -1 and
+0.9999694.
> > On the other hand with an integer interpretation, it is between -32768 and
> > +32767.  On the SHARC, when you multiply 2 fixed-point numbers together, you
can
> > specify for each number if it should be treated as integer or fractional.
The
> > difference is simply in the shifting of the result, but obviously it is
quite
> > significant to the answer!
>
> The computer hardware, of course, doesn't know about the binary point at
>   all. <snip>

On the SHARC at least, I think the hardware does "know about the binary point".
Or at least you can tell it where the binary point is on the multiplicands, and
it will give you the correct product based on that data.  The low level multiply
instructions can deal with 4 different types of data, each with a different
binary point: unsigned integer, signed integer, unsigned fractional, signed
fractional.  But you are correct that the data in memory is just 32 bits, and
what you make of them is up you as to the programmer.

Al--

>>> What's the difference between fixed-point and integer?
>>>
>>> I suspect something subtle but significant.
>> 
>> I'm not sure about the terminology used above, but in the many DSPs, a
>> fixed-point number can be interpreted as either an integer or a
>> fractional value.  Assuming a signed 16-bit two's complement
>> representation, the fraction interpretation of the bits means that the
>> number is between -1 and +0.9999694. On the other hand with an integer
>> interpretation, it is between -32768 and +32767.  On the SHARC, when
>> you multiply 2 fixed-point numbers together, you can specify for each
>> number if it should be treated as integer or fractional.  The 
>> difference is simply in the shifting of the result, but obviously it
>> is quite significant to the answer!
>> 
>> 
>> 
>
>I'm not sure if Jon's explanation makes the difference clear:
>
>If you assume fixed point representation, you normally assume one sign 
>bit and N fractional bits. For example, the Sharc fractional format is 
>typically in 1.31. If the multiplier didn't do anything special, then 
>when you multiplied two 1.31 numbers you would get a result that was in 
>2.62 format. There would be a redundant sign bit. This is automatically 
>adjusted for by the DSP by a bit shift of 1, so that the result is in 
>1.63 format and therefore the fractional numbers are interpreted 
>correctly (you often round the result to 1.31 format at some point).

While you are not wrong in anything you said, just rephrase some of what
you said in TI friendly language

Now, am not sure if this a SHARC peculiarity, but in TI and I suspect
elsewhere too, we always say Q0.31(where Q stands for the "Quantity of
fractional bits) or Q31 but never 1.31, the reason being that a fixed
point number is represented in m+n+1 number of bits where m->no of integer
bits n->number of fractional bits and 1 *extra* sign bit(which also has a
magnitude btw...)

So, a Q0.31*Q0.31(fully fractional data) would result in a Q1.62, with one
extra sign bit(which is sort of like a sign extension) but this aint a
fully fractional number as the case was with the two inputs.And most
likely one would want their output to be in the same *Q format* as the
input many times and hence we need to condition the resulting Q1.62 number
to become Q0.63 which is achieved by a simple left shift(loose out the
*extra* sign bit but this also equal to multypliying the result by two,
which is correct result in this case).This is achieved auto in many TI
dsp's by simply using the appropriate fixed point multiply
instruction.Ofcourse it is a different matter whether the processor will
support 32 bit multiplication as was illustrated in this thread but
something similar happens at the 16 bit level as well (Q15*Q15->Q1.30 left
shifted by one bit, it results in Q0.31)...

Finally, I have made some notes for my own personal reading and
understanding on fixed point math.If someone needs it I can mail it across
to you but folks please be forewarned there is nothing original or new
about it, its just a collection of stuff I have read and assimilated at
one place in an easier and friendly powerpoint format.

--Bhooshan
		
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com

Glen--

>The computer hardware, of course, doesn't know about the binary point at

>all.Many high-level languages only provide an integer type and let 
>the user worry about anything else.

The ANSI embedded C language(am not sure if the standard has alrady been
published), as I understand , will incorporate support for fixed point
formats, specifically for the use of DSP programmers along with support
for various other embedded nuances, including support for a file called .b
(which indicates "both").In this file one would be able to declare and
define variables. For folks who have had to do work around on sharing a
bunch of global variables across multiple files but needed to declare all
of em at one place like a header file but could not do it because of
multiple inclusion or multiple definition problems can now breathe a
little easy...But may be not too soon, who is going to support embedded C
standard?

--Bhooshan
		
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com

bhooshaniyer wrote:

(snip)

> Now, am not sure if this a SHARC peculiarity, but in TI and I suspect
> elsewhere too, we always say Q0.31(where Q stands for the "Quantity of
> fractional bits) or Q31 but never 1.31, the reason being that a fixed
> point number is represented in m+n+1 number of bits where m->no of integer
> bits n->number of fractional bits and 1 *extra* sign bit(which also has a
> magnitude btw...)

(snip)

I always like the PL/I notation better, which is FIXED BINARY(p,q) where
p is the total number of bits, and q is the number after the binary 
point.  q is allowed to be negative, too.  And yes, for signed numbers 
the sign bit doesn't count.   Q35.-4 looks very strange to me, but
FIXED BINARY(31,-4) doesn't seem so strange.  q can also be larger than
p, so Q-4.35 would also be allowed, that is, FIXED BINARY(31,35)

-- glen

"bhooshaniyer" <bhooshaniyer@gmail.com> wrote in
news:P8CdnZZczL13kgnfRVn-3g@giganews.com: 

> Al--
> 
>>>> What's the difference between fixed-point and integer?
>>>>
>>>> I suspect something subtle but significant.
>>> 
>>> I'm not sure about the terminology used above, but in the many DSPs,
>>> a fixed-point number can be interpreted as either an integer or a
>>> fractional value.  Assuming a signed 16-bit two's complement
>>> representation, the fraction interpretation of the bits means that
>>> the number is between -1 and +0.9999694. On the other hand with an
>>> integer interpretation, it is between -32768 and +32767.  On the
>>> SHARC, when you multiply 2 fixed-point numbers together, you can
>>> specify for each number if it should be treated as integer or
>>> fractional.  The difference is simply in the shifting of the result,
>>> but obviously it is quite significant to the answer!
>>> 
>>> 
>>> 
>>
>>I'm not sure if Jon's explanation makes the difference clear:
>>
>>If you assume fixed point representation, you normally assume one sign
>>bit and N fractional bits. For example, the Sharc fractional format is
>>typically in 1.31. If the multiplier didn't do anything special, then 
>>when you multiplied two 1.31 numbers you would get a result that was
>>in 2.62 format. There would be a redundant sign bit. This is
>>automatically adjusted for by the DSP by a bit shift of 1, so that the
>>result is in 1.63 format and therefore the fractional numbers are
>>interpreted correctly (you often round the result to 1.31 format at
>>some point). 
> 
> While you are not wrong in anything you said, just rephrase some of
> what you said in TI friendly language

There is a TI friendly language? ;-)

Q31 is the TI way of expressing 1.31 in ADI language. It means the same 
thing. I am a ADI partisan so I used an ADI example.

I don't think Bud and Lou care either way.

Al








> 
> Now, am not sure if this a SHARC peculiarity, but in TI and I suspect
> elsewhere too, we always say Q0.31(where Q stands for the "Quantity of
> fractional bits) or Q31 but never 1.31, the reason being that a fixed
> point number is represented in m+n+1 number of bits where m->no of
> integer bits n->number of fractional bits and 1 *extra* sign bit(which
> also has a magnitude btw...)
> 
> So, a Q0.31*Q0.31(fully fractional data) would result in a Q1.62, with
> one extra sign bit(which is sort of like a sign extension) but this
> aint a fully fractional number as the case was with the two inputs.And
> most likely one would want their output to be in the same *Q format*
> as the input many times and hence we need to condition the resulting
> Q1.62 number to become Q0.63 which is achieved by a simple left
> shift(loose out the *extra* sign bit but this also equal to
> multypliying the result by two, which is correct result in this
> case).This is achieved auto in many TI dsp's by simply using the
> appropriate fixed point multiply instruction.Ofcourse it is a
> different matter whether the processor will support 32 bit
> multiplication as was illustrated in this thread but something similar
> happens at the 16 bit level as well (Q15*Q15->Q1.30 left shifted by
> one bit, it results in Q0.31)... 
> 
> Finally, I have made some notes for my own personal reading and
> understanding on fixed point math.If someone needs it I can mail it
> across to you but folks please be forewarned there is nothing original
> or new about it, its just a collection of stuff I have read and
> assimilated at one place in an easier and friendly powerpoint format.
> 
> --Bhooshan
>           
> This message was sent using the Comp.DSP web interface on
> www.DSPRelated.com



-- 
Al Clark
Danville Signal Processing, Inc.
--------------------------------------------------------------------
Purveyors of Fine DSP Hardware and other Cool Stuff
Available at http://www.danvillesignal.com

Al--

>> While you are not wrong in anything you said, just rephrase some of
>> what you said in TI friendly language
>
>There is a TI friendly language? ;-)

Even if not friendly there is definitely a TI peculiar language for sure
and for most of us(With a TI market share of ~50% in programmable DSP
market) who have been working a long time with TI DSP's the language ends
up being friendly! :-)


>Q31 is the TI way of expressing 1.31 in ADI language. It means the same 
>thing. I am a ADI partisan so I used an ADI example.

Absoultely it means the same thing, no question there.I just wanted to
help the *budding TI partisans* there...:-)

>I don't think Bud and Lou care either way.

Are they a distant relatives of Tom Engibous? If they are, they would sure
care! :-)

--Bhooshan
		
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com

Jon Harris wrote:

(snip)

> On the SHARC at least, I think the hardware does "know about the binary point".
> Or at least you can tell it where the binary point is on the multiplicands, and
> it will give you the correct product based on that data.  The low level multiply
> instructions can deal with 4 different types of data, each with a different
> binary point: unsigned integer, signed integer, unsigned fractional, signed
> fractional.  But you are correct that the data in memory is just 32 bits, and
> what you make of them is up you as to the programmer.

Well...

A 32 bit multiply should generate a 64 bit product.  So they supply 
instruction to generate the high and low half.  But it is still only
the relative position of the binary point that matters.  The binary point
of the product depends on the sum of the digits after the binary point
of the numbers being multiplied, so only the sum needs to be known.

For addition and subtraction the binary points must agree, but the 
hardware doesn't care which position it is, as long as they are both the 
same.

-- glen

Al Clark wrote:
>> If the multiplier didn't do anything special, then 
>>when you multiplied two 1.31 numbers you would get a result that was in 
>>2.62 format. There would be a redundant sign bit. 

[snip]
bhooshaniyer wrote:
> So, a Q0.31*Q0.31(fully fractional data) would result in a Q1.62, with one
> extra sign bit(which is sort of like a sign extension) 

I was going to wait for Randy to jump in, but since he hasn't yet, I 
will.  That "extra sign bit" is NOT extra.  There is one case where the 
two msb's are not equal (and thus not redundant), and that's when you 
multiply -1 and -1 (or 0x8000000 and 0x8000000).  The result is +1, aka 
0x40000000:00000000 in 2.62.  A fractional multiplier will automatically 
shift the result left one bit, which is fine for every combinaiton of 
inputs EXCEPT -1 times -1.  In this case, it overflows, because +1 
cannot be represented in 1.63 (or 1.31).

-- 
Jim Thomas            Principal Applications Engineer  Bittware, Inc
jthomas@bittware.com  http://www.bittware.com    (603) 226-0404 x536
Nothing is ever so bad that it can't get worse. - Calvin

"The computer hardware, of course, doesn't know about the binary point
at
  all.   Many high-level languages only provide an integer type and let

the user worry about anything else."

And it seems, in my experience anyway,  that all the other high level
languages that provide hidden shifts/data types to help the user work
with fixed point numbers just confuses everyone.

As far as new hardware is concerned, looking at the results of  couple
of sample fixed point operations tells me immediatly if the microcode
has any screwy "added fixed point features".

"For multiply and divide hardware it is very useful to have a multiply
that produces a double length product and divide that takes a double
length dividend."

Yes that hardware feature is key to preserve fixed point accuracy,
always follow a fixed point mutliply with a fixed point divide and not
the other way around. e.g., (32bit x 32 bit = 64bit)/ 32 bit