Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The basic problem is not about zero padding vs the assumed periodicity, but that Fourier analysis decomposes the signal into sine waves which, at the most basic level, are assumed to be infinite in extent. <strong>Both approaches are correct</strong> in that the IFFT using the full FFT will return the exact input waveform, and <strong>both approaches are incorrect</strong> in that using less than the full spectrum can lead to effects at the edges (that usually extend a few wavelengths). The only difference is in the details of what you assume fills in the rest of infinity, not in whether you are making an assumption.</p> <p>Back to your first paragraph: Usually, in DSP, the biggest problem I run into with FFTs is that they are non-causal, and for this reason I often prefer to stay in the time domain, using, for example, FIR and IIR filters.</p> <p><strong>Update:</strong></p> <p>In the question statement, the OP correctly points out some of the problems that can arise when using FFTs to filter signals, for example, edge effects, that can be particularly problematic when doing a convolution that is comparable in the length (in the time domain) to the sampled waveform. It's important to note though that not all filtering is done using FFTs, and <em>in the paper cited by the OP, they are not using FFT filters, and the problems that would arise with an FFT filter implementation do not arise using their approach</em>.</p> <p>Consider, for example, a filter that implements a simple average over 128 sample points, using two different implementations. </p> <p><strong>FFT</strong>: In the FFT/convolution approach one would have a sample of, say, 256, points and convolve this with a wfm that is constant for the first half and goes to zero in the second half. The question here is (even after this system has run a few cycles), what determines the value of the first point of the result? The FFT assumes that the wfm is circular (i.e. infinitely periodic) so either: the first point of the result is determined by the <em>last</em> 127 (i.e. future) samples of the wfm (skipping over the middle of the wfm), or by 127 zeros if you zero-pad. Neither is correct.</p> <p><strong>FIR</strong>: Another approach is to implement the average with an FIR filter. For example, here one could use the average of the values in a 128 register FIFO queue. That is, as each sample point comes in, 1) put it in the queue, 2) dequeue the oldest item, 3) average all of the 128 items remaining in the queue; and this is your result for this sample point. This approach runs continuously, handling one point at a time, and returning the filtered result after each sample, and has none of the problems that occur from the FFT as it's applied to finite sample chunks. Each result is just the average of the current sample and the 127 samples that came before it.</p> <p>The paper that OP cites takes an approach much more similar to the FIR filter than to the FFT filter (note though that the filter in the paper is more complicated, and the whole paper is basically an analysis of this filter.) See, for example, <a href="http://www.dspguide.com/" rel="noreferrer">this free book</a> which describes how to analyze and apply different filters, and note also that the Laplace approach to analysis of the FIR and IIR filters is quite similar what what's found in the cited paper.</p>
    singulars
    1. This table or related slice is empty.
    1. POWhy do the convolution results have different lengths when performed in time domain vs in frequency domain?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. UStom10
    1. UStom10
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POWhy do the convolution results have different lengths when performed in time domain vs in frequency domain?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. COThanks tom10, "(that usually extend a few wavelengths)." This is what I observe on the few test cases I've investigated. That is, the middle 1/3'rd of the waveform appears perfectly stable after IFFT of the product of the two spectrums (e.g. freq conv approach). Is there any theory/math that can show the dividing line where the steady-state response becomes perfectly valid in this approach? That is, I'm looking for a way to predict based on theory what region of the filtered time-domain waveform (e.g. the result from IFFT of the product of the filter FFT and the waveform FFT) is stable.
      singulars
      1. PO
      1. USggkmath
    2. COsigh... now I have to get out a book... to quote form Numerical Recipes: "To summarize — we need to pad the data with a number of zeros on one end equal to the maximum positive duration or maximum negative duration of the response function, whichever is larger. (For a symmetric response function of duration M , you will need only M/2 zero pads.) Combining this operation with the padding of the response rk described above, we effectively insulate the data from artifacts of undesired periodicity." see hebb.mit.edu/courses/9.29/2002/readings/c13-1.pdf around Fig. 13.1.14
      singulars
      1. PO
      1. UStom10
    3. COAt least this answers the specific question about convolutions, though not the general consequences of assumed periodicity of FFTs in general. As I recall, there is some theory for that too, but I don't recall it off-hand.
      singulars
      1. PO
      1. UStom10
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload