Re: Something astray in my FFT understanding


SeanOg skrev:
Many thanks for the quick replies. Sorry for the confusion, Im probally
using the terminology a bit to quickly without thinking exactly what it
means.

What my routine does is it accepts an array of N points. This array
represents the signal to be transformed. This is what I meant about the
FFT being real, it accepts one array of real, not complex, numbers, each
point in the array representing one sample.

OK...

The output of the routine is an array of N points which represents (at
least what I believed up to now) the entire DFT; the real part of the DFT,
stored in the first half, and the imaginary part, stored in the second
half.

Maybe I'm just splitting a few hairs here, but we need to agree on the
details.
An N-point DFT produces N complex-valued coefficients, that contain
one real and one imaginary part, 2N in all. Due to a symmetry
when the input signal is real, namely

X(w) = re{X(w)} + j*im{X(w)}
X(-w) = conj(X(w)) = re{X(w)} - j*im{X(w)}

the full spectrum is known from N/2 complex-valued coefficients.
So if your FFT routine accepts only real-valued signals and produces
N real numbers, it is almost certain that N/2 of those numbers
represent
the real part and the other N/2 the imaginary parts...

So using an impulse function of 8 points as an example (input is a single
8 point array);

Input Output
1 0 0 0 0 0 0 0 -> FFT -> 1 1 1 1 0 0 0 0
|real | |img |

(the above output is what it should be, I get all 1's)

....like what you indicate here.


Hi,
I am not sure what you mean by frequency here.

Again bad use of a term on my part. What I was getting at was that in the
example of the impulse shifted by two, the output looked like the output
of the 1 point shifted impulse but with 'twice the frequency'.

I am pretty sure this has to do with the phase term in the twiddle
factors.

Im checking that out at the moment. I have a niggling in the back of my
head that something about how I consider how the phase factors should be
calculated isnt 100% correct.

Try restrict this to N = 2^M, M integer, first. That's how most FFTs
are
designed. Only after that one works, does one extend to general N.

A bad sign... could it be that the FFT algorithm is based on a
real-valued
input, which is guaranteed to produce a symmetric spectrum, and
pops out half the number of real and imaginary coefficients?

Ah, thats news to me. Looks like Ive got a very mixed up view of the whole
real/complex FFT. I always thought that;

x[N] -> FFT -> X[N]

where x[N] is an array of real numbers (ie no complex component)

Nope. See below.

first half X[N] is real part of resulant DFT
second half X[N] is imaginary part of resultant DFT

Only if the FFT routine is specifically designed to accept only
real-valued sequences. In general, you get N complex-valued
coefficients.


Seems I need to go back over this topic. I think then the problem is the
FFT Ive implemented is specifcally for complex inputs or something...Gotta
hate when you think youve finally understood something you regard as
difficult and then realise that youre still as confused as ever :P

Been there, done that. Not with the FFT (never attempted that one
from scratch, but you've got me thinking...), but still. Never mind,
all that is forgotten when you, in the end, know that you finally got
it right...

thanks again, its great to have a soundboard that I can use to figure out
these things rather muttering incoherent abuse at my books. Ill let you
know how I get on.

Rune

.

Relevant Pages

  • Re: Fundamental frequency -- limited resources
    ... Memory is the biggest ... > constraint, the processor horsepower is not as big a constraint. ... > The reality is that the array will actually hold values like ....4200, ... > keep thinking, "if I could just do an FFT and take the dominant freq, ...
    (sci.math.num-analysis)
  • Re: Imaginary values non-null in FFTW Java wrapper real transform
    ... the format of the array returned by the FFTW real to ... An FFT of a totally real input signal will, in general, return results with nonzero real and imaginary parts. ... If the input signal has even symmetry around 0 then the FFT should be all real, ... Wescott Design Services ...
    (comp.dsp)
  • Fundamental frequency -- limited resources
    ... every 100th sample would be non-zero, ... So if I had an array of 50,000 elements, which would represent 5 ... PC, etc...), an FFT could be used on a huge array of time-domain ... samples, and the fundamental frequency of 100 would come through, is ...
    (sci.math.num-analysis)
  • Re: Fundamental frequency -- limited resources
    ... Why is a median filter not good enough? ... your sorted array. ... > constraint, the processor horsepower is not as big a constraint. ... > keep thinking, "if I could just do an FFT and take the dominant freq, ...
    (sci.math.num-analysis)
  • Re: IFFT is not working
    ... fft(N, r, i) // forward fft ... Divide results by N ... The output result in the array ris the same as what I started ... routine that accepts and works with both real and imaginary inputs/ ...
    (comp.dsp)