Re: fft and loss of samples

Gentlemen, you make things look a bit clearer now. Which leads to a much
more specific question - in case of 1024 real values as input, and 512
"non-redundant" analytic values as output of an FFT, what is a good way to
feed the IFFT? I came across some people padding the rest 512 with 0's so
that the IFFT will receive 1024 complex and output 1024 time domain
complex values..


"stefan_k" <stefan@xxxxxxxxxxxx> wrote in message
news:s9GdnavNNvIoDZDbnZ2dnUVZ_oernZ2d@xxxxxxxxxxxxxxx
Hi all:

I'm going to pose a question that everyone has come across some time
or
another.

Say I'd like to do an FFT of a 1024 point vector. The result is
complex
values from 0 to f/2 (513 complex values). In case some bins are
zeroed
for filtering purposes, and IFFT is to be done, should it be performed
directly to the 513 values or should they be expanded with their
mirroring
to 1024. And if so should the IFFT be done with order 2^9 (since only
512
values are available) or 2^10 since it's a part of 1024 point package?
Because it seems like of we go from 1024 real time domain values to
513
complex frequency domain and then back to 513 real time domain values,
half of the samples will be lost forever...

Others have already said this in one way or another:

An N-point DFT (or IDFT) yields the same number of output points as input

points. If the input is real, there is a zero complex part. So, 1024
real
samples as input are really 1024 "special" complex numbers. Thus, 2048
values in both sequences - input and output.

An FFT of 1024 real samples yields 1024 complex samples.
An IFFT of 1024 complex samples yields 1024 complex samples - where the
imaginary part *may* be zero.

That's all there is to it. However .....

Because of redundancy in some cases, the *particular* implementation
(which
you have not identified) may take advantage of redundancy and do many
different things:
- if the input is real then the output is complex: real symmtetric,
imaginary antisymmetric. Thus, if you understand this and can deal with
it
you can eliminate half the output samples (with caution).
- the inverse transform still needs all the samples ... one way or
another.
Either explicitly or by some algorithmic "trick".

It is not correct to say that 1024 real samples yields 512 complex
samples
(thus it's still 1024 samples). This incorrect observation actually
alludes
to a trick. As a related matter, it *is* correct to say that 1024 real
samples yields 512 complex *non-redundant* samples - but that is a matter
of
information content and not about the most straightforward implementation
of
the FFT algorithm. More clever implementations may take advantage of
this
but requires some care in how to deal with the result.

It is correct to say that 1024 real samples *implies* 1024 complex
samples
and yields 1024 complex samples. Quite a few mainstream FFT algorithms
carry the zero-valued complex samples along in the input.

Fred






_____________________________________
Do you know a company who employs DSP engineers?
Is it already listed at http://dsprelated.com/employers.php ?
.

Relevant Pages

  • Re: Frequency response to time domain - lack of understanding!
    ... I'm having problems with the IFFT and time domain issues. ... frequency response is originally 600 points long, ... I can't get my head round understanding how the samples in the FFT relate ...
    (comp.dsp)
  • Re: fft and loss of samples
    ... "non-redundant" analytic values as output of an FFT, what is a good way to ... feed the IFFT? ... documentation of the FFT library. ... complex time domain values, ...
    (comp.dsp)
  • Frequency response to time domain - lack of understanding!
    ... I'm having problems with the IFFT and time domain issues. ... frequency response is originally 600 points long, ... I can't get my head round understanding how the samples in the FFT relate ...
    (comp.dsp)
  • Re: is FFT always approximate?
    ... spectrum, which should be discrete, will this FFT procedure be approximate? ... If you want it to give you the exact Fourier series ... coefficients, which would extend beyond the Nyquist frequency, then you ... you IFFT back to the time domain, you see what you "really" have. ...
    (comp.dsp)
  • Comparison between FFT and Convolution
    ... Convolution in time domain is equal to multiplication in Frequency ... Comparison between FFT and Convolution ... I did 2D FFT in such a way that, row wise 1D FFT then column wise 1D ...
    (comp.dsp)