fft and loss of samples

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



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

On Mar 30, 3:35 pm, "stefan_k" <ste...@cygnusnj.com> wrote:
> 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).

If your input vector is real, you get out a real value at 0, an
imaginary value at f/2 and 511 complex values in between. This gives
something like  511 + 2/2 = 512 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.

This depends on the calling format of the ifft function you use. YMMV.

And you might taper your filtering weighting more gradually than 1
1 ... 1 0 0 ... 0.

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

The inverse transform should probably be called the same size at the
forward transform, like: '1024 real to complex fft'  and  'complex to
1024 real ifff', but dsp libraries are not alway consistant. YMMV.

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

1024 real => 511 + 2/2 complex => 1024 real, no problem.

Try reading the documentation of you fft/ifft functions, if there is
any.

Dale B. Dalrymple
http://dbdimages.com

On 31 Mar, 00:35, "stefan_k" <ste...@cygnusnj.com> wrote:
> 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.

Why?

> The result is complex
> values from 0 to f/2 (513 complex values).

Only if your signal was real-valued, and only if you use an
implementation of the FFT which rely on the input data being
real-valued.

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

It depends. An FFT of an N-point data sequence produces N
coefficients in the spectrum. If the input data are real-valued,
the spectrum is conjugate symmetric, meaning that

X(k) = conj(X(-k))

which means you really only need half the coefficients; the
other half only take up space while contributing no information
about the signal.

Rune

Stefan wrote:
> 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 ...

For filtering, you should only use the FFT approach if you really know
what you are doing. It's complicated to understand and program, and
beginners inevitably make mistakes because they don't understand
circular convolution, overlapping and FIR filter design.

If you want to notch-filter at some frequenices, the simplest approach
is to use one IIR biquad for each notch frequency, as described in r b-
j's ubiquitous "Filter Cookbook" [1]. Other filtering operations
(lowpass, highpass, bandpass) can also easily be implemented this way.
IIR filter are very compute and memory efficient and extremely simple
to program - up and running in one day. The only drawback is if you
are working in low-precision (16 or 24bit) compute environments.
Obviously you aren't, because it's even worse for FFT filtering.

Only if you need complicated frequency responses, linear-phase or
extreme filter requirements should you turn to FIR filters.

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

That depends on the format of your FFT routines. If you have routine
called a "complex to real FFT" (perhaps also "inverse real FFT"), then
the former. If all you have is a "complex FFT", then the latter. Don't
forget to take the conjugate of the frequency response if you you use
a standard complex FFT routine to compute the inverse FFT.

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

Same as above.

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

512 complex (or, as Dale properly points out, 511 complex plus 2 real)
values can store the same information as 1024 real values. Nothing
will be lost.

Regards,
Andor

[1] http://www.musicdsp.org/files/Audio-EQ-Cookbook.txt

"stefan_k" <stefan@cygnusnj.com> wrote in message 
news:s9GdnavNNvIoDZDbnZ2dnUVZ_oernZ2d@giganews.com...
> 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 

Yes, you are right, I forgot to mention the implementation: I'm using the
Intel Signal Processing Library 4.1.

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

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@cygnusnj.com> wrote in message 
>news:s9GdnavNNvIoDZDbnZ2dnUVZ_oernZ2d@giganews.com...
>> 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 ?

Stefan wrote:
> Gentlemen, you make things look a bit clearer now.

Really.

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

Did you read the responses to your original question at all? You
already have the answer to the above question three times in three
different wordings. For another explanation, you could read the
documentation of the FFT library.

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

What do you think: complex time domain values, good or bad?

Regards,
Andor

"stefan_k" <stefan@cygnusnj.com> wrote in message 
news:_4GdnSq_d5otBJPbnZ2dnUVZ_qSrnZ2d@giganews.com...
> 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..

It's hard for me to imagine a consistent algorithm implementation that would 
cause you to manipulate the FFT output in order to do the IFFT.  Generally 
I'd expect 1:1 correspondence.  This leads to RTFM.

Fred 

You didn't say which routine you're using in the Intel Signal Processing 
Library.  So, assuming that it is Fft specifically, it takes N complex 
inputs and generates N complex outputs.  Why make it more complicated?

Fred