I would like to get some feedback on this idea. Multiplying a signal in the time domain by a window before computing its FFT is equivalent to the convolution of the transform of the signal with the transform of the window. It seems therefore that one could "undo" the effect of a square window (i.e. FFT with no windowing at all) by applying a complex deconvolution algorithm in the frequency domain. Has this idea ever been tried? I know that deconvolution has many problems, so I'm just testing the waters... thanks -Arrigo

# FFT windowing and deconvolution

Started by ●May 19, 2004

Reply by ●May 19, 20042004-05-19

"Arrigo Benedetti" <arrigo@vision.caltech.edu> wrote in message news:6fd18256.0405191702.22300396@posting.google.com...> I would like to get some feedback on this idea. Multiplying > a signal in the time domain by a window before computing its FFT > is equivalent to the convolution of the transform of the signal > with the transform of the window. > It seems therefore that one could "undo" the effect of a square > window (i.e. FFT with no windowing at all) by applying a complex > deconvolution algorithm in the frequency domain. > Has this idea ever been tried? I know that deconvolution has > many problems, so I'm just testing the waters...Arrigo, Well, it seems to me that the rectangular window creates a type of fundamental limit or at least a very basic point of departure. Deconvolution in frequency is like dividing by a full-length record in the time domain - so it's like a window except the operation is division instead of multiplication. If the dividing function d(t) has zeros - that's a problem! If it doesn't have zeros then perhaps it can be effected with multiplication by its reciprocal 1/d(t). Not a big difference perhaps in principle - only in implementation. You want to divide the time sequence such that the frequency domain smearing and leakage are reduced? This is equivalent to turning the frequency domain transform of the time window into a unit sample. One way to approximate this over a limited region may be to use "supergaining" - by distorting the frequency domain outside the "visible region" as termed by the antenna specialists. Google on "supergain". You can find functions with large peaks outside a given range of frequency that tend to look better and better inside that same range. These peaks outside the range can be used to adjust the function between +/-pi - so that you get "better" response there. Think of the overall function as a sum of shifted sincs and you are adjusting the "middle" of the sum with the tails of the outlying sinc functions. Somehow having sampled data in both time and frequency makes this probably not feasible. Continuous time windows and frequency functions that go from + to - infinity are the thing... Anyway, in a time function that's continuous and time-limited, the frquency domain is infinite and not sampled. What happens is that the supergained time window gets very large at the edges - which corresponds with large peaks at high frequency - and you start running into practical problems of precision of arithmetic, etc..... Fred

Reply by ●May 20, 20042004-05-20

Arrigo Benedetti wrote:> I would like to get some feedback on this idea. Multiplying > a signal in the time domain by a window before computing its FFT > is equivalent to the convolution of the transform of the signal > with the transform of the window. > It seems therefore that one could "undo" the effect of a square > window (i.e. FFT with no windowing at all) by applying a complex > deconvolution algorithm in the frequency domain. > Has this idea ever been tried? I know that deconvolution has > many problems, so I'm just testing the waters... > > thanks > -ArrigoThe problem with no windowing is that the FFT acts on the signal as if it were one cycle of a repeating signal (this is why you get discrete frequencies out of it, by the way). If you have no windowing, and if your signal doesn't match up at the 0 and 2^n-1 points in every way (i.e. the data and it's 1st, 2nd, 3rd .. (n - 1)th derivative all match), then the resulting discontinuity comes through the FFT like a step function, even though your data doesn't really contain a step. Contrast this with windowed data that _does_ contain a step, say in the middle: you deemphasize the ends of your data set, but the middle of the set has that whopping big step in it which shows up in your data in the frequency domain. Since the FFT is completely reversible there ought to be a way to do the calculation after the fact -- but a simple convolution wouldn't have the effect that you're looking for, because it would treat the "real" steps the same way as the "artificial" ones. It may turn out, in fact, that the most computationally efficient way to realize the calculation would be to do the inverse FFT, window the resulting data, then do the forward FFT again! -- Tim Wescott Wescott Design Services http://www.wescottdesign.com

Reply by ●May 20, 20042004-05-20

"Arrigo Benedetti" <arrigo@vision.caltech.edu> wrote in message news:6fd18256.0405191702.22300396@posting.google.com...> It seems therefore that one could "undo" the effect of a square > window (i.e. FFT with no windowing at all) by applying a complex > deconvolution algorithm in the frequency domain. > Has this idea ever been tried? I know that deconvolution has > many problems, so I'm just testing the waters...It's the same as dividing the samples outside the window by 0. All of those deconvolution problems you've heard about are division-by-zero or division-by-nearly-zero problems.

Reply by ●May 20, 20042004-05-20

"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message news:<v5udnczuOcZikjHdRVn-vg@centurytel.net>...> "Arrigo Benedetti" <arrigo@vision.caltech.edu> wrote in message > news:6fd18256.0405191702.22300396@posting.google.com... > > I would like to get some feedback on this idea. Multiplying > > a signal in the time domain by a window before computing its FFT > > is equivalent to the convolution of the transform of the signal > > with the transform of the window. > > It seems therefore that one could "undo" the effect of a square > > window (i.e. FFT with no windowing at all) by applying a complex > > deconvolution algorithm in the frequency domain. > > Has this idea ever been tried? I know that deconvolution has > > many problems, so I'm just testing the waters... > > Arrigo, > > Well, it seems to me that the rectangular window creates a type of > fundamental limit or at least a very basic point of departure. > > Deconvolution in frequency is like dividing by a full-length record in the > time domain - so it's like a window except the operation is division instead > of multiplication. If the dividing function d(t) has zeros - that's a > problem! If it doesn't have zeros then perhaps it can be effected with > multiplication by its reciprocal 1/d(t). Not a big difference perhaps in > principle - only in implementation. > > You want to divide the time sequence such that the frequency domain smearing > and leakage are reduced?Exactly. I want to avoid using a tapering window in the time domain since there might be useful features in the signal near the borders, and the window would kill the energy of those features. Thanks for your comments, -Arrigo

Reply by ●May 20, 20042004-05-20

"Arrigo Benedetti" <arrigo@vision.caltech.edu> wrote in message news:6fd18256.0405192225.11833df6@posting.google.com...> "Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in messagenews:<v5udnczuOcZikjHdRVn-vg@centurytel.net>...> > "Arrigo Benedetti" <arrigo@vision.caltech.edu> wrote in message > > news:6fd18256.0405191702.22300396@posting.google.com... > > > I would like to get some feedback on this idea. Multiplying > > > a signal in the time domain by a window before computing its FFT > > > is equivalent to the convolution of the transform of the signal > > > with the transform of the window. > > > It seems therefore that one could "undo" the effect of a square > > > window (i.e. FFT with no windowing at all) by applying a complex > > > deconvolution algorithm in the frequency domain. > > > Has this idea ever been tried? I know that deconvolution has > > > many problems, so I'm just testing the waters... > > > > Arrigo, > > > > Well, it seems to me that the rectangular window creates a type of > > fundamental limit or at least a very basic point of departure. > > > > Deconvolution in frequency is like dividing by a full-length record inthe> > time domain - so it's like a window except the operation is divisioninstead> > of multiplication. If the dividing function d(t) has zeros - that's a > > problem! If it doesn't have zeros then perhaps it can be effected with > > multiplication by its reciprocal 1/d(t). Not a big difference perhapsin> > principle - only in implementation. > > > > You want to divide the time sequence such that the frequency domainsmearing> > and leakage are reduced? > > Exactly. I want to avoid using a tapering window in the time domain since > there might be useful features in the signal near the borders, and the > window would kill the energy of those features. > > Thanks for your comments, > > -ArrigoArrigo, You should either make your window larger to incorporate those features you want to see (so they're not at the edge of your window) or else use multiple overlapping windows so that you can place those "edge" features in the center of a new window. The windowing is a *good* thing. You're forced to use some kind of window to do a finite FFT so you might as well choose it yourself. Using "no" window imposes a rectangle window which smears your frequencies around quite a bit.

Reply by ●May 20, 20042004-05-20

On Thu, 20 May 2004 13:42:42 GMT, "Brad Griffis" <bradgriffis@hotmail.com> wrote:>The windowing is a *good* thing. You're forced to use some kind of window >to do a finite FFT so you might as well choose it yourself. Using "no" >window imposes a rectangle window which smears your frequencies around quite >a bit.I have been using "no" windowing in a piano tuning application and I find that the difference between windowing and no windowing is most predominate in the lower frequencies. If F is the sampling frequency, then the spectrum from F/4 to F/2 seems to be largely unsmeared. -Robert Scott Ypsilanti, Michigan (Reply through this forum, not by direct e-mail to me, as automatic reply address is fake.)

Reply by ●May 24, 20042004-05-24

Arrigo Benedetti wrote:> I would like to get some feedback on this idea. Multiplying > a signal in the time domain by a window before computing its FFT > is equivalent to the convolution of the transform of the signal > with the transform of the window. > It seems therefore that one could "undo" the effect of a square > window (i.e. FFT with no windowing at all) by applying a complex > deconvolution algorithm in the frequency domain. > Has this idea ever been tried? I know that deconvolution has > many problems, so I'm just testing the waters...There is a book, "Deconvolution of images and spectra" by Jansson, (The first edition was called "Deconvolution: with applications to spectroscopy") It covers very well both linear and non-linear deconvolution. Consider that a power spectrum should never go negative, and an absorption spectrum should stay between 0 and 1, yet linear deconvolution algorithms don't restrict that. -- glen