Impulse Testing the FFT

Greetings,

I have been experimenting with several FFT routines and none of them seem to
work like they are supposed to.

From what I understand of the theory, an impulse in the time domain is supposed
to correspond to a sinusoid in the frequency domain with a frequency the same as
the offset of the impulse.

I have been testing using 16 point signals (imaginary parts set to 0) and there
are 2 problems I have observed which are common to all the FFT routines I have
tried :-

1. A very large number sometimes appears where the zero crossings should be.

2. The resulting sinusoids do not have the correct frequency (as far as I can
tell this only happens for numbers which are not a power of 2)

Can anyone explain this?
	

Shadow-

> I have been experimenting with several FFT
routines and none of them seem to work like they are supposed to.
> 
> From what I understand of the theory, an impulse in the time domain is
supposed to correspond to a sinusoid in the frequency domain with a frequency
the same as the offset of the impulse.

No -- impulse in time domain is a flat line in freq domain.  The ideal impulse
is
infinitely narrow and infinitely tall -- it contains all possible frequencies in
equal amounts.

You need a good DSP book stuff, here is a one:

  http://www.prenhall.com/~dspfirst/

Straightforward and easy to understand, but written by famous experts
nevertheless.

-Jeff

Oops - forgot to hit reply all instead of reply :-

I should also have mentioned that the results of inverse FFT are nowhere
 near the same as the original signal - this applies to all routines I 
have tested.  The errors are far too big to count as round off noise.  
Something is clearly wrong here.
	--- Jeff Brower <jbrower@jbro...> wrote:

From: Jeff Brower <jbrower@jbro...>
Date: Sun, 27 Feb 2005 18:55:15 -0600
To: shadowsedge@shad...
Cc: audiodsp@audi...
Subject: Re: [audiodsp] Impulse Testing the FFT

Shadow-

> I have been experimenting with several FFT
routines and none of them seem to work like they are supposed to.
> 
> From what I understand of the theory, an impulse in the time domain is
supposed to correspond to a sinusoid in the frequency domain with a frequency
the same as the offset of the impulse.

No -- impulse in time domain is a flat line in freq domain.  The ideal impulse
is
infinitely narrow and infinitely tall -- it contains all possible frequencies in
equal amounts.

You need a good DSP book stuff, here is a one:

  http://www.prenhall.com/~dspfirst/

Straightforward and easy to understand, but written by famous experts
nevertheless.

-Jeff
	_____________________________________________________________
Get free email that shows your true colors...
http://www.YellowSnow.com
	

Hi Shadow,
 
      Too add little more to Jeffs comments:
      Time Domain unit step function ---FFT--> unit impluse. This means that
input signal contains only DC component. 
 
     Time Domain unit impluse function ---FFT--> unit step.  This means that
unit impluse function contains all the frequency components............!. Why it
contains all the frequency components already jeff has given hints.
 
Amaresh

Jeff Brower <jbrower@jbro...> wrote:
Shadow-

> I have been experimenting with several FFT
routines and none of them seem to work like they are supposed to.
> 
> From what I understand of the theory, an impulse in the time domain is
supposed to correspond to a sinusoid in the frequency domain with a frequency
the same as the offset of the impulse.

No -- impulse in time domain is a flat line in freq domain.  The ideal impulse
is
infinitely narrow and infinitely tall -- it contains all possible frequencies in
equal amounts.

You need a good DSP book stuff, here is a one:

  http://www.prenhall.com/~dspfirst/

Straightforward and easy to understand, but written by famous experts
nevertheless.

-Jeff
	   To
	---------------------------------
Do you Yahoo!?
 Yahoo! Sports -  Sign up for Fantasy Baseball.
	

Martin-

> From: "Jeff Brower"
<jbrower@jbro...>
> 
> > No -- impulse in time domain is a flat line in freq domain.
> > The ideal impulse is infinitely narrow and infinitely tall
> 
> Alas, both of these statements are inaccurate. That strange
> thing, the Dirac delta is the ideal *continuous-time* impulse. In
> discrete time, the Kronecker delta d[n] = {1, n=0; 0, else} is as
> ideal as it gets. But it is true of both that they contain
> > all possible frequencies in equal amounts
> under the Fourier transform or D(T)FT, respectively -- that's the
> definition of ideality here and leads to the other point: While
> the *magnitude* spectrum of a displaced impulse is indeed flat,
> its transform is a complex exponential in the frequency variable
> as the OP has found. It is a constant exactly when the impulse is
> at the time origin.

Thanks for pointing out my inaccuracies.  I hope Shadow has gained full
confidence in
the FFT algorithm :-)

-Jeff

From: "Jeff Brower" <jbrower@jbro...>

> No -- impulse in time domain is a flat line in
freq domain.
> The ideal impulse is infinitely narrow and infinitely tall

Alas, both of these statements are inaccurate. That strange
thing, the Dirac delta is the ideal *continuous-time* impulse. In
discrete time, the Kronecker delta d[n] = {1, n=0; 0, else} is as
ideal as it gets. But it is true of both that they contain
> all possible frequencies in equal amounts
under the Fourier transform or D(T)FT, respectively -- that's the
definition of ideality here and leads to the other point: While
the *magnitude* spectrum of a displaced impulse is indeed flat,
its transform is a complex exponential in the frequency variable
as the OP has found. It is a constant exactly when the impulse is
at the time origin.
	Martin
	

> Date: Mon, 28 Feb 2005 07:05:13 -0800 (PST)
> From: Amaresh patil <amaresh_p@amar...>
> Subject: Re: Impulse Testing the FFT
>
> Time Domain unit step function ---FFT--> unit impluse.

Yet another myth. It is the derivative of the Heavyside function
(unit step fct) that is the Dirac delta function. No Fourier transform
is involved.

> Time Domain unit impluse function ---FFT-->
unit step.

Wrong point. It is the integral of the Dirac function that is the
unit step function.

> This means that unit impluse function contains all
the frequency components

What is an FT coefficient then?

Originally, the Fourier theorem was about decomposing a function in a sum
of sines and cosines of different frequencies. Hence, the Fourier coefficients
are magnitudes of the corresponding base functions.

Best regards,

Andrew

P.S. Speaking about small non-zero coefficients shown in an earlier post
to this thread, there is something wrong with them. They are unrealistically
small for single precision and unrealistically large for double precision,
if IEEE-754 numbers were used. The double precision epsilon is about 1.0E-22
if my memory serves me correct. Perhaps the Fourier matrix (the twiddle
factors) were calculated with lesser accuracy.
	

Andrew-

> > Time Domain unit step function ---FFT-->
unit impluse.
> 
> Yet another myth. It is the derivative of the Heavyside function
> (unit step fct) that is the Dirac delta function. No Fourier transform
> is involved.
> 
> > Time Domain unit impluse function ---FFT--> unit step.
> 
> Wrong point. It is the integral of the Dirac function that is the
> unit step function.
> 
> > This means that unit impluse function contains all the frequency
components
> 
> What is an FT coefficient then?
> 
> Originally, the Fourier theorem was about decomposing a function in a sum
> of sines and cosines of different frequencies. Hence, the Fourier
coefficients
> are magnitudes of the corresponding base functions.

These are great comments.  The finer points are appreciated.

I would however point out that the OP appeared to be entry-level (at least in
DSP). 
I continue to be surprised by the number of BSEEs and MSEEs who I interview, and
when
I ask them to **sketch** (sketch, not elaborate with theory) the magnitude
response
of a delta function, they do not draw anything like a flat line.

For entry-level engineers, I feel like if they know in their heads what to
expect
from Fourier transform of a) pure sinusoid, b) delta function, and c) a
constant,
then they have some basic idea of when and why an FFT could be helpful in their
work,
and they came out of school in good shape.

-Jeff

Hi Andrew,
 
  Thanks for correcting my statements. your absolutely right, Heavy side   
These are practical observation what we come across put it without mapping them
to   classical integral mathematics. If the Pulse is wide in time domain, it  is
narrow in the frequency domain and vice versa. 
 
Once i agree to your statements then i am left with two questions...!
 
 Time Domain unit step function ---FFT--> unit impluse.

Yet another myth. It is the derivative of the Heavyside function
(unit step fct) that is the Dirac delta function. No Fourier transform is
involved. 
 
Then what would be the Fourier tranform of (unit) step function. 
 
> Time Domain unit impluse function ---FFT-->
unit step.

Wrong point. It is the integral of the Dirac function that is the
unit step function.
 
What will be the fourier transform of impluse function. 
 
What we will get when we compute on the Digital Machines.
 
regards
Amaresh
	

I have to add something here. I believe Jeff was trying to help a novice,
and his comments were very much appropriate for a novice audience.
I don't think the finer, theoretical points made by others, although
technically accurate and welcome by myself and, I'm sure, also by Jeff,
would be much help to a novice. If fact, the novice would only get more
confused by them.

As an analogy, V=RI is universally known as Ohm's Law, but strictly
speaking, this is a simplified version of the original Ohm's Law, in which
current, resistance, etc. are actually functions, and not constants. 
However,
since,in practical terms, V=RI is perfectly accurate 99.999% of the time , I 
don't think
I'd be wrong to tell a novice that ohm's law is simply V=RI.

Tony
----- Original Message ----- 
From: "Jeff Brower" <jbrower@jbro...>
To: "Andrew Nesterov" <andrew.nesterov@andr...>
Cc: <audiodsp@audi...>
Sent: Thursday, March 03, 2005 8:41 AM
Subject: Re: [audiodsp] Re: Impulse Testing the FFT
	>
> Andrew-
>
>> > Time Domain unit step function ---FFT--> unit impluse.
>>
>> Yet another myth. It is the derivative of the Heavyside function
>> (unit step fct) that is the Dirac delta function. No Fourier transform
>> is involved.
>>
>> > Time Domain unit impluse function ---FFT--> unit step.
>>
>> Wrong point. It is the integral of the Dirac function that is the
>> unit step function.
>>
>> > This means that unit impluse function contains all the frequency 
>> > components
>>
>> What is an FT coefficient then?
>>
>> Originally, the Fourier theorem was about decomposing a function in a
sum
>> of sines and cosines of different frequencies. Hence, the Fourier 
>> coefficients
>> are magnitudes of the corresponding base functions.
>
> These are great comments.  The finer points are appreciated.
>
> I would however point out that the OP appeared to be entry-level (at least 
> in DSP).
> I continue to be surprised by the number of BSEEs and MSEEs who I 
> interview, and when
> I ask them to **sketch** (sketch, not elaborate with theory) the magnitude 
> response
> of a delta function, they do not draw anything like a flat line.
>
> For entry-level engineers, I feel like if they know in their heads what to 
> expect
> from Fourier transform of a) pure sinusoid, b) delta function, and c) a 
> constant,
> then they have some basic idea of when and why an FFT could be helpful in 
> their work,
> and they came out of school in good shape.
>
> -Jeff
>
>
> 
>
>
>
>
>
>
>