Beginner: Integer FFT and Fixed Point FFT

Jim Thomas <jthomas@bittware.com> wrote in
news:11991803b2lnp06@corp.supernews.com: 

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

That's certainly true. In most DSPs (ADI for example), there is a test flag 
for this condition. If you have situations where this can occur, you 
definitely need to guard against it since the result is a very nasty sign 
inversion.

Sometimes I restrict my negative numbers to 0x80000...1 so that the 
overflow can't occur. This works well for sine tables where I want the 
table to have symmetry.  


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

"bhooshaniyer" <bhooshaniyer@gmail.com> wrote in
news:AcCdneCd3OMKsAnfRVn-hw@giganews.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! :-)

TI and ADI split the market about evenly when you factor out the large 
verical markets that most people are not involved in. For example, about 
70% of all DSPs are targeted at cell phones. 

> 
> 
>>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 suggest that those "budding TI partisans" resist the "dark side of the 
force" before its too late ;-)


> 
>>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! :-)

I am pretty sure that Bud & Lou were drinking buddies with Ray Stata. Tom 
was always too busy counting his cell phone money. 




> 
> --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 Clark wrote:

   ...

> Sometimes I restrict my negative numbers to 0x80000...1 so that the 
> overflow can't occur. This works well for sine tables where I want the 
> table to have symmetry.  

I once wrote a fixed-point arithmetic extension package for a 16-bit 
micro's HLL that reserved $8000 for NAN. It was useful.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jim--

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

That was a good addition to the comments that I made.I just probably left
the boundary cases out, out of pure laziness.And btw, in this *special*
case the TI DSP's solve it by:

1]first look at the 31st and 32nd bit

2]If they contain same info, then they are sign extension,hence carry out
left shifts

3]If the upper two bits contain different info, then make the result equal
to ~1.

--Bhooshan



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

steve wrote:

(snipP

> "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

In the olden days, with shift and add multipliers, or with shift and 
subtract (restoring or non-restoring) dividers, it was natural to have
a double length product and dividend.   With fancier algorithms it is
not so natural, but useful in some cases.

-- glen

Al Clark wrote:
   ...

>Sometimes I restrict my negative numbers to 0x80000...1 so that the 
>overflow can't occur. This works well for sine tables where I want the 
>table to have symmetry

Jerry Wrote:

>>I once wrote a fixed-point arithmetic extension package for a 16-bit 
>>micro's HLL that reserved $8000 for NAN. It was useful.

Hmmm...Clever, I have never thought of this before, I still dont know if
this implies some other restriction somwhere else,have not analyzed
thoroughly.It sounds like a clean idea but if it is so then why dont the
processor manufacturers make it standard? If they are not doing it there
could be a reason...Hmmm...

--Bhooshan

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

Glen--

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

Mmmm...I think you are right but am not sure if I understand what you said
well enough to be sure...If you dont mind you could expand a bit more with
may be an example...I guess it would be useful for many of us...

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

Jerry Avins wrote:

> robert bristow-johnson wrote:
> 
>> in article 1196sh38u0kgm10@corp.supernews.com, Richard Owlett at
>> rowlett@atlascomm.net wrote on 05/24/2005 14:28:
>>
>>
>>> I'm a sucker.
>>> I'll bite.
>>>
>>> What's the difference between fixed-point and integer?
>>>
>>> I suspect something subtle but significant.
>>
>>
>>
>> only where you put the binary point.  for integers, the binary point is
>> always just to the right of the least significant bit.  for 
>> fixed-point, the
>> binary point is somewhere else, agreed upon in advance or, at least,
>> understood by the programmer.  i've done my first digital filtering on a
>> Motorola MC6809 which was an integer machine, yet i had some fixed-point
>> coefficients.
> 
> 
> Richard,
> 
> Another term for fixed point, especially when the hardware makes no 
> low-level provision for it, is "scaled integer". Does that sound  more 
> familiar? 


Not really ;)
I'll politely ignore ~20 subthread replies which seem to be gibrresh - 
or possibly I'm missing something significant :)

> It's a fairly common usage in Forth.


Oh well 'the FORTH may not be with me ']

A register just holds a bit pattern.

If you think binary it contains value (perhaps signed) from 0 to 2^N -1
If scaled there is a *fixed* divisor/multiplier of 2^M

So fixed-point and integer appears to be a "distinction *without* a 
difference".
> 
> Jerry

bhooshaniyer wrote:
> Al Clark wrote:
>    ...
> 
> 
>>Sometimes I restrict my negative numbers to 0x80000...1 so that the 
>>overflow can't occur. This works well for sine tables where I want the 
>>table to have symmetry
> 
> 
> Jerry Wrote:
> 
> 
>>>I once wrote a fixed-point arithmetic extension package for a 16-bit 
>>>micro's HLL that reserved $8000 for NAN. It was useful.
> 
> 
> Hmmm...Clever, I have never thought of this before, I still dont know if
> this implies some other restriction somwhere else,have not analyzed
> thoroughly.It sounds like a clean idea but if it is so then why dont the
> processor manufacturers make it standard? If they are not doing it there
> could be a reason...Hmmm...
> 
> --Bhooshan
> 
> 		
> This message was sent using the Comp.DSP web interface on
> www.DSPRelated.com

The reason is simple. In hardware, there's no difference between an 
unsigned adder and a two's complement adder. To construe $80...0 as NAN 
requires decoding a special case, like detecting a non-redundant sign 
bit in fixed point. My package of routines didn't deal with hardware. It 
simply returned NAN when appropriate and raised an exception is passed 
one. That's slow, though.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Richard Owlett wrote:

   ...

> A register just holds a bit pattern.
> 
> If you think binary it contains value (perhaps signed) from 0 to 2^N -1
> If scaled there is a *fixed* divisor/multiplier of 2^M
> 
> So fixed-point and integer appears to be a "distinction *without* a 
> difference".

Those bits might represent ASCII characters. Is that distinction also 
without difference?

The difference is what you do with the bits. When multiplying 
fixed-point numbers, you use the integer multiplier then shift the 
result and discard different bits than you would if they were integers. 
When adding, two fixed-point numbers with the same scaling, you use the 
integer adder and accept the result as is. If the scaling isn't the same 
for both numbers, at least one of them must be adjusted by shifts.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������