Re: Problem with using fft and ifft functions

[Maynard Wright]

On Tuesday 21 July 2009 18:13, Sergei Steshenko wrote:
> --- On Tue, 7/21/09, babelproofreader <address@hidden> wrote:
> > From: babelproofreader <address@hidden>
> > Subject: Problem with using fft and ifft functions
> > To: address@hidden
> > Date: Tuesday, July 21, 2009, 7:37 AM
>
> [snip]
>
> > when I use the functions fft and then ifft something seems
> > to go wrong, but
> > in my ignorance I can't figure out how to fix it, or even
> > what is going
> > wrong.
>
> [snip]
>
> Did I delete anything which describes what exactly went wrong ?
> Or which describes why you think it went wrong ?
>
> ...
>
> I haven't looked closely in your code, but a couple of quick tips:
>
> 1) 'octave' uses full complex FFT opposed, to say, typically used
> half-complex ones;
>
> 2) because of the above direct FFT -> filter application -> inverse FFT
> sequence produces ("slightly") complex results due to rounding errors.
>
>
>
> So in 'octave' I typically do the following:
>
> 1) forcefully make second half of the spectrum to be complex conjugate of
> the first (I mean the case of real, not complex, input signal);
>
> 2) apply filter to the first half of the spectrum;
>
> 3) again forcefully make second half of the spectrum to be complex
> conjugate of the first;
>
> 4) perform inverse FFT;
>
> 4a) do a sanity check to make sure complex parts of the filtered signal
> are small;
>
> 5) discard complex parts of the filtered signal - since mathematically
> they should be zeros.
>
>
> Regards,
>   Sergei.
>
>
Sergei's method is sound and can save a lot of work in implementing the 
filtering.  You can often do a lot of signal processing using only the 
positive frequencies and add in the negative frequencies only when it's 
necessary to convert back to the time domain.

You need to be careful how you treat the elements of the transformed array of 
frequencies.  Octave uses a system that is pretty universal, but it isn't the 
only method in use for storing frequency domain amplitudes.  This is important 
when you supply the complex conjugate negative frequencies after computing 
the positive ones:

If the number of time domain samples, N, is even:

element 1 = constant or DC amplitude
elements 2 to N/2 = amplitudes of positive frequency components in increasing 
order
elements N to N/2 = amplitudes of negative frequency components in decreasing 
order

Note that element N/2 is the algebraic sum of the highest positive and highest 
negative frequencies and, for real time domain signals, the imaginary 
components cancel and N/2 is always real.  The first sinusoidal component 
(fundamental) has it's positive component in element 2 and its negative 
component in element N.

If the number of time domain samples, N, is odd:

element 1 = constant or DC amplitude
elements 2 to (N+1)/2 = amplitudes of positive frequency components in 
increasing order
elements N to ((N+1)/2 + 1) = amplitudes of positive frequency components in 
decreasing order

Note that for an odd number of samples there is no "middle" element and all 
the frequency domain amplitudes will, in general, be complex.

Regards,
Maynard