Beginner: Integer FFT and Fixed Point FFT

First things First..I am totally new to DSP...just completed an
introductory course...never coded for DSP...not in C...not in
Assembly..but I did use the built in functions in Matlab :D...

I am trying to learn programming the Motorola DSP(I dont know which one
:D My Prof wants me to code in C first...then code in Assembly...so the
it doesn't matter).

So, to start with, I was told to try and implement the Integer FFT.
At first, I thought it must be some kinda new FFT algrithm :D
But after going thru the comp.dsp archives..I figured out it must be
that the data types they use in integer-fft are integers...hence it
must be the same as fixed-pt FFT.

But then I was given this IEEE trans. on Sig. Proc. paper to
read...(The Integer Fast Fourier Transform by Nyugen ,et.al. (2000?))

I could not make out much...but integer-fft and fixed pt FFT seem to be
different.. :O

Can anybody help me out of my confusion?

What is Fixed Point FFT?
What is Integer FFT?


thanx in advance...:D

Karthik Ravikanti
---

Let There Be Sound!
http://students.iiit.net/~karthik_ravikanti

Karthik Ravikanti wrote:

(snip)

> So, to start with, I was told to try and implement the Integer FFT.
> At first, I thought it must be some kinda new FFT algrithm :D

I think you are right, but there IS an algorithm called ICT, Integer 
Cosine Transform, a modified DCT designed to minimize the number of '1' 
bits in the coefficients for fast implementation on machines without a 
multiply instruction, such as the CDP1802.  The inverse transform is 
expected to be done on a faster machine, so speed is less significant.

http://tmo.jpl.nasa.gov/tmo/progress_report/42-119/119M.pdf

-- glen

"glen herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message 
news:5aKdnQrnr9uFbhPfRVn-gA@comcast.com...
> Karthik Ravikanti wrote:
>
> (snip)
>
>> So, to start with, I was told to try and implement the Integer FFT.
>> At first, I thought it must be some kinda new FFT algrithm :D
>
> I think you are right, but there IS an algorithm called ICT, Integer 
> Cosine Transform, a modified DCT designed to minimize the number of '1' 
> bits in the coefficients for fast implementation on machines without a 
> multiply instruction, such as the CDP1802.  The inverse transform is 
> expected to be done on a faster machine, so speed is less significant.
>
> http://tmo.jpl.nasa.gov/tmo/progress_report/42-119/119M.pdf
>
> -- glen
>
Could it be that his prof means the (original?) Cooley-Tukey type thing with 
all the bit rearrangements and maybe twiddle factors in integer arithmetic?

Best of Luck - Mike

I can't believe it...this is the first time that I asked a question on
comp.dsp and it went unanswered...:(

There was good pointer though.:D

But no one answered my most important questions...

What is integer-FFT??
and
What is fixed-point FFT?

Pleeeeezz answer.....:D

regards...

Karthik

Mike Yarwood wrote:
> "glen herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message
> news:5aKdnQrnr9uFbhPfRVn-gA@comcast.com...
> > Karthik Ravikanti wrote:
> >
> > (snip)
> >
> >> So, to start with, I was told to try and implement the Integer
FFT.
> >> At first, I thought it must be some kinda new FFT algrithm :D
> >
> > I think you are right, but there IS an algorithm called ICT,
Integer
> > Cosine Transform, a modified DCT designed to minimize the number of
'1'
> > bits in the coefficients for fast implementation on machines
without a
> > multiply instruction, such as the CDP1802.  The inverse transform
is
> > expected to be done on a faster machine, so speed is less
significant.
> >
> > http://tmo.jpl.nasa.gov/tmo/progress_report/42-119/119M.pdf
> >
> > -- glen
> >
> Could it be that his prof means the (original?) Cooley-Tukey type
thing with
> all the bit rearrangements and maybe twiddle factors in integer
arithmetic?
> 
> Best of Luck - Mike

It doesn't really matter what, if any, distinction we conjecture your 
Professor draws between integer and fixed-point FFTs.  It's his opinion 
that matters.

Get him to explain his terms. I, for one, would be interested in the answer.

--Mark

Karthik Ravikanti wrote:
> I can't believe it...this is the first time that I asked a question on
> comp.dsp and it went unanswered...:(
> 
> There was good pointer though.:D
> 
> But no one answered my most important questions...
> 
> What is integer-FFT??
> and
> What is fixed-point FFT?
> 
> Pleeeeezz answer.....:D
> 
> regards...
> 
> Karthik
> 

"Karthik Ravikanti" <karthik.ravikanti@gmail.com> schrieb im Newsbeitrag 
news:1116794963.723110.17580@o13g2000cwo.googlegroups.com...
>I can't believe it...this is the first time that I asked a question on
> comp.dsp and it went unanswered...:(
>
> There was good pointer though.:D
>
> But no one answered my most important questions...
>
> What is integer-FFT??
> and
> What is fixed-point FFT?
>
> Pleeeeezz answer.....:D
>
> regards...
>
> Karthik

Hello Karthik,
now after you have clarified your desire, it's very simple.

Integer FFT:
You program the whole algorithm with integer data types and
instructions which only deal with integer numbers.
It can take ten times the time to develop it with integer only
if highest precision/resolution is desired.


Floating point FFT:
You can do the math with floating point data types and instructions.
This can be a child's play compared to a fixed point implementation.
You can't do anything wrong here with the dynamic range.


What is an integer?
This is number with N-bits, mostly 16 or 32 bits. Ok,
Freescale(?) have 24bit processors too.
Data and dynamic range is 2^N.

What is floating point?
The numbers have a mantissa and an exponent field.
Standard formats use 32bits(single prec.) or 64bits(double prec.).
The data range is from 10e-37 to 10e37(single precision) or something
like 10e-200 to 10e-200 for double precision. The dynamic range
is 24bits or 53bits. I am too lazy to look for the precise numbers.

Best regards,
Helmut


>
> Mike Yarwood wrote:
>> "glen herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message
>> news:5aKdnQrnr9uFbhPfRVn-gA@comcast.com...
>> > Karthik Ravikanti wrote:
>> >
>> > (snip)
>> >
>> >> So, to start with, I was told to try and implement the Integer
> FFT.
>> >> At first, I thought it must be some kinda new FFT algrithm :D
>> >
>> > I think you are right, but there IS an algorithm called ICT,
> Integer
>> > Cosine Transform, a modified DCT designed to minimize the number of
> '1'
>> > bits in the coefficients for fast implementation on machines
> without a
>> > multiply instruction, such as the CDP1802.  The inverse transform
> is
>> > expected to be done on a faster machine, so speed is less
> significant.
>> >
>> > http://tmo.jpl.nasa.gov/tmo/progress_report/42-119/119M.pdf
>> >
>> > -- glen
>> >
>> Could it be that his prof means the (original?) Cooley-Tukey type
> thing with
>> all the bit rearrangements and maybe twiddle factors in integer
> arithmetic?
>>
>> Best of Luck - Mike
> 

Thanx a lot Helmut...:-)

That makes it better..

Now you introduce further doubt...:D
What is dynamic range?
I know what is range..(2 to the power of the no. of bits?)
But what is dynamic range?

Another doubt...
I read somewhere that we have to handle overflow&underflow of bits in
Integer FFT...
What is over flow and underflow...???

in article 1116863331.721049.221440@f14g2000cwb.googlegroups.com, Karthik
Ravikanti at karthik.ravikanti@gmail.com wrote on 05/23/2005 11:48:

> What is dynamic range?
> I know what is range..(2 to the power of the no. of bits?)
> But what is dynamic range?

i usually define dynamic range to be the S/N ratio (in dB) plus the headroom
(in dB).  it is usually pretty close to 6.02 dB per bit in the wordsize.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

"Karthik Ravikanti" <karthik.ravikanti@gmail.com> schrieb im Newsbeitrag
news:1116863331.721049.221440@f14g2000cwb.googlegroups.com...
> Thanx a lot Helmut...:-)
>
> That makes it better..
>
> Now you introduce further doubt...:D
> What is dynamic range?
> I know what is range..(2 to the power of the no. of bits?)
> But what is dynamic range?
>
> Another doubt...

Hello Karthik,

You can represent numbers from 1e-37 to 1e37(=data range) with single
precision
floating point, but the useful dynamic range is only about 1e7.
That means if you add 1e-9 to 1, then the 1e-9 get lost,
because your mantissa has only 24bits which is a dynamic range of about 1e7.

I am not sure whther my naming is standard, but the facts are correct.


> I read somewhere that we have to handle overflow&underflow of bits in
> Integer FFT...
> What is over flow and underflow...???

Overflow is when the numbers over-run the positive data range.
Underflow is when the numbers under-run the negative data range.

Now there are different methods to treat overflow and underflow.
It depends on the application what's necessary. Doing nothing in
this case makes the result unpredictable and maybe totally useless.

1. The numbers will saturate to the max. positive/negative number.

2. The numbers will be shiftet to the right and the shift has
to be kept in mind when the number is used the next time.

Best regards,
Helmut

"Helmut Sennewald" <HelmutSennewald@t-online.de> wrote in message 
news:d6t5tm$on9$03$1@news.t-online.com...
> "Karthik Ravikanti" <karthik.ravikanti@gmail.com> schrieb im Newsbeitrag
> news:1116863331.721049.221440@f14g2000cwb.googlegroups.com...
>> Thanx a lot Helmut...:-)
>>
>> That makes it better..
>>
>> Now you introduce further doubt...:D
>> What is dynamic range?
>> I know what is range..(2 to the power of the no. of bits?)
>> But what is dynamic range?
>>
>> Another doubt...
>
> Hello Karthik,
>
> You can represent numbers from 1e-37 to 1e37(=data range) with single
> precision
> floating point, but the useful dynamic range is only about 1e7.
> That means if you add 1e-9 to 1, then the 1e-9 get lost,
> because your mantissa has only 24bits which is a dynamic range of about 
> 1e7.
>
> I am not sure whther my naming is standard, but the facts are correct.
>
>
>> I read somewhere that we have to handle overflow&underflow of bits in
>> Integer FFT...
>> What is over flow and underflow...???
>
> Overflow is when the numbers over-run the positive data range.
> Underflow is when the numbers under-run the negative data range.
>
> Now there are different methods to treat overflow and underflow.
> It depends on the application what's necessary. Doing nothing in
> this case makes the result unpredictable and maybe totally useless.
>
> 1. The numbers will saturate to the max. positive/negative number.
>
> 2. The numbers will be shiftet to the right and the shift has
> to be kept in mind when the number is used the next time.
>
> Best regards,
> Helmut
>
Hi Karthik - as Helmut says above , you need to decide at which points in 
your all integer algorithm you need to rescale so you don't end up with 
multiplies that take you outside the maximum and minimum limits.

I know that it's getting into the exam season and some profs have a habit of 
going to ground round about now but it really may well be worth your while 
trying to dig him/her out and asking for a bit more detail as Mark 
Borgerding suggested.  There's a whole load of FFTs using number theoretic 
transforms which are specifically designed for integer math with no error 
and , if you have that sort of background already and you just want to use 
them for convolution or correlation, he/she may have something like that in 
mind.

Best of Luck- Mike