How do fourier processing algorithms deal with quotdata edgesquot

De openkb
Aller à : Navigation, rechercher

Sommaire

Questions

I am doing some interesting experiments with audio and image files and Fast-Fourier Transforms (FFTs).

Fast Fourier Transforms are used in signal processing rather than other Fourier Transform algorithms because for large quantities of data they are the only (or one of the only) viable algorithm variants to use, as they scale as O(n log(n)), rather than n^2 as the naive implementation does.

The disadvantage is that the data must be stored in an array which has 2^n elements, for n integer.

When processing some data which does not have 2^n elements, the simple approach is to extend the array to be length 2^n and fill the "empty" elements with zero. (Assuming the mean value of the input signal is zero.)

I wrote a program to process some audio samples taken from WAV files. I tried implementing things such as a low-cut filter. In this case I found that my output signal (after doing the reverse transform) cuts to zero amplitude after a certain period of time . This is obviously not what one would expect of a low-pass filter.

I could dump my code at this point, but that is neither useful, nor legal as the source of my algorithm is a text-book with closed source code.

Instead I shall ask the following question.

Is packing out the array with zeros the best possible thing to do? Could this be causing my program to produce the unexpected results I am seeing? if I understand fourier mathematics correctly, having a bunch of zeros at the end of my array will introduce a large amount of low and high-frequency content as this essentially looks like a step-function (low frequency square wave). Should I be doing something else such as implementing my band-pass filter in a different way, for example, splitting the data into smaller groups of say 1024 samples and applying the FT, filter and IFT (inverse FT) to those small groups?

This question has been tagged with theory as it is not related to any specific programming language. (I assume that is the correct tag to use?)

 Edit: It s now working beautifully, thanks all, I was able to pinpoint the 2 mistakes I made using the information below.  

Answers

All finite length DFTs and FFT multiply longer data (longer source data or wav file than the FFT) with a rectangular window, which convolves the spectrum with a (periodic) Sinc function. Zero padding uses a shorter rectangular window, which results in the convolution of the spectrum with a wider Sinc function.

Filtering by multiplication of FFTs results in circular convolution, which wraps the impulse response of the filter around the FFT/IFFT result (e.g. the end of your filtered signal will interfere with the beginning of the filtered signal within the IFFT result). So you want to zero-pad your data before the FFT, and then see the impulse response of your filter go to zero at or before the very end of the filtered result (e.g. not wrap around). Look up the overlap-add and overlap-save algorithms, for using short FFTs for fast convolution filtering of longer signals, which take care of the filter impulse response extending into the zero-padded portion.

You can also use FFTs that are not a power of 2 in length. Any length that can be factored into small primes will work with most modern FFT libraries.

Source

License : cc by-sa 3.0

http://stackoverflow.com/questions/38857263/how-do-fourier-processing-algorithms-deal-with-data-edges

Related

Outils personnels
Espaces de noms

Variantes
Actions
Navigation
Outils