Just how flat need a window be to utilize "overlap and add" Window data -- FFT -- manipulate in freq domain -- IFFT -- add in time domain
Windows and "overlap and add"
Started by ●September 19, 2004
Reply by ●September 19, 20042004-09-19
Depends on the window. Some windows blend together quite easily. An example is triangle. Harrris has a paper from a preceedings in the late seventies that address this subject. I have a copy at work, somewhere. In article <10krp16rl55gq4b@corp.supernews.com>, rowlett@atlascomm.net wrote:>Just how flat need a window be to utilize "overlap and add" > >Window data -- FFT -- manipulate in freq domain -- IFFT -- add in time >domain > > >
Reply by ●September 19, 20042004-09-19
Richard Owlett wrote:> Just how flat need a window be to utilize "overlap and add" > > Window data -- FFT -- manipulate in freq domain -- IFFT -- add in time > domainWhy window? the artifacts caused by a rectangular window should cancel in the overlap. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●September 19, 20042004-09-19
Jerry Avins wrote:> Richard Owlett wrote: > >> Just how flat need a window be to utilize "overlap and add" >> >> Window data -- FFT -- manipulate in freq domain -- IFFT -- add in time >> domain > > > Why window? the artifacts caused by a rectangular window should cancel > in the overlap. > > JerrySome of my analysis will be in frequency domain and comparing frequency domain of multiple sequential "samples". I'm grouping for a well formulated question. This has much to do with my other post titled As "Nyquist" is to "sample rate" "????" is to "sample period/duration/width/?" ?
Reply by ●September 19, 20042004-09-19
Hi Richard, Jerry et al. - I hope you don't mind my jumping in here. Richard - the "overlap and add" technique is a method of convolving a finite sequence (presumably a filter) with a longer, indefinite sequence (i.e., data) using the DFT (or FFT). When this technique is used, there is no need to use a window like Hamming, Blackman, etc. The convolution is exact (if it is performed properly) without any sort of window. --Randy Richard Owlett <rowlett@atlascomm.net> writes:> Jerry Avins wrote: >> Richard Owlett wrote: >> >>> Just how flat need a window be to utilize "overlap and add" >>> >>> Window data -- FFT -- manipulate in freq domain -- IFFT -- add in >>> time domain >> Why window? the artifacts caused by a rectangular window should >> cancel >> in the overlap. >> Jerry > > Some of my analysis will be in frequency domain and comparing > frequency domain of multiple sequential "samples". > > I'm grouping for a well formulated question. > > This has much to do with my other post titled > > As "Nyquist" is to "sample rate" "????" is to "sample > period/duration/width/?" ? >-- % Randy Yates % "The dreamer, the unwoken fool - %% Fuquay-Varina, NC % in dreams, no pain will kiss the brow..." %%% 919-577-9882 % %%%% <yates@ieee.org> % 'Eldorado Overture', *Eldorado*, ELO http://home.earthlink.net/~yatescr
Reply by ●September 19, 20042004-09-19
Randy Yates wrote:> Hi Richard, > > Jerry et al. - I hope you don't mind my jumping in here. > > Richard - the "overlap and add" technique is a method of convolving a > finite sequence (presumably a filter) with a longer, indefinite > sequence (i.e., data) using the DFT (or FFT). When this technique is > used, there is no need to use a window like Hamming, Blackman, etc. > The convolution is exact (if it is performed properly) without any > sort of window. > > --RandyThanks for putting it loud and clear. That's what I was getting at, but too timidly. Richard has a different problem, identifying phonemes, and I wanted to think how to address it before answering. That's why he asked about sample duration. At this point, I give up. It's so far off the path that I don't know where to begin. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●September 20, 20042004-09-20
Richard Owlett wrote:> Jerry Avins wrote: > >> Richard Owlett wrote: >> >>> Just how flat need a window be to utilize "overlap and add" >>> >>> Window data -- FFT -- manipulate in freq domain -- IFFT -- add in >>> time domain >> >> >> >> Why window? the artifacts caused by a rectangular window should cancel >> in the overlap. >> >> Jerry > > > Some of my analysis will be in frequency domain and comparing frequency > domain of multiple sequential "samples". > > I'm grouping for a well formulated question. > > This has much to do with my other post titled > > As "Nyquist" is to "sample rate" "????" is to "sample > period/duration/width/?" ? >It kind of depends on your overlap percentage and the amount of ripple you can tollerate back in the time domain. It also depends on how coloured the data is. Whitening the data prior to windowing should help a bit as well.
Reply by ●September 20, 20042004-09-20
Jerry Avins <jya@ieee.org> writes:> Randy Yates wrote: > >> Hi Richard, >> Jerry et al. - I hope you don't mind my jumping in here. >> Richard - the "overlap and add" technique is a method of convolving a >> finite sequence (presumably a filter) with a longer, indefinite >> sequence (i.e., data) using the DFT (or FFT). When this technique is >> used, there is no need to use a window like Hamming, Blackman, etc. >> The convolution is exact (if it is performed properly) without any >> sort of window. >> --Randy > > Thanks for putting it loud and clear. That's what I was getting at, but > too timidly. Richard has a different problem, identifying phonemes, and > I wanted to think how to address it before answering. That's why he > asked about sample duration. At this point, I give up. It's so far off > the path that I don't know where to begin. > > JerryI'm really confused. If Richard is addressing a completely different problem, then why wouldn't you have stated that explicitly? The words "overlap and add" only refer to one specific thing that I know of - if that's not what he's trying to do, then someone needs to elucidate. -- % Randy Yates % "How's life on earth? %% Fuquay-Varina, NC % ... What is it worth?" %%% 919-577-9882 % 'Mission (A World Record)', %%%% <yates@ieee.org> % *A New World Record*, ELO http://home.earthlink.net/~yatescr
Reply by ●September 20, 20042004-09-20
Hi Richard, "Richard Owlett" <rowlett@atlascomm.net> wrote in message news:10krp16rl55gq4b@corp.supernews.com...> Just how flat need a window be to utilize "overlap and add" > > Window data -- FFT -- manipulate in freq domain -- IFFT -- add in time > domainI don't think anyone has given you bad information, here, but I also don't think anyone has appreciated what it is you're trying to do. As I understand it, you want to do frequency-domain using FFTs of overlapping blocks, and you naturally want to use a window that reduces aliasing, am I right? Well, your desires are quite reasonable. "lapped orthogonal transforms" (googleable) are very close to what you say you want. One of them, the MDCT (googlable) is used in most common lossy audio compression formats (MP3, ogg, WMA etc.). These transforms are carefully constructed so that the frequency-domain data is critically sampled. For your application, I would recommend something more natural with a bit more redundancy: - Divide the input streams into blocks with 50% overlap, so that 12345 becomes 12, 23, 34, 45, etc... - Window each block with a sine window. Be sure the sine period is exactly twice the block length, i.e., put the window zeros on the last sample and sample -1 of each block. - FFT - manipulate the frequency-domain coefficients - IFFT - Apply the sine window to each block again. - Add overlapping blocks. I wrote more about exactly how this works, w.r.t. aliasing and perfect reconstruction, in this old thread: http://groups.google.ca/groups?hl=en&lr=&ie=UTF-8&frame=right&th=47676f2a6c523d4d&seekm=xUiC9.4307%24kS3.483091%40news20.bellglobal.com#link3 -- Hope that helps, Matt
Reply by ●September 21, 20042004-09-21
On Mon, 20 Sep 2004 21:36:20 -0400, "Matt Timmermans" <mt0000@sympatico.nospam-remove.ca> wrote:>>- Window each block with a sine window. Be sure the sine period is exactly >>twice the block length, i.e., put the window zeros on the last sample and >>sample -1 of each block.I suspect that you meant that one zero-crossing of the sine window should occur at the initial point in the block, and that the next zero crossing (in the opposite direction) of the sine window should occur one point beyond the end of the block. Correct?>>- FFT >> >>- manipulate the frequency-domain coefficients >> >>- IFFT >> >>- Apply the sine window to each block again. >> >>- Add overlapping blocks.I read the accompanying thread that you referenced. Nowhere in this discussion or that thread do you mention the fact that, after applying the window and before applying the FFT, the block must be zeropadded with at least as many zeroes as there are points in the impulse response of the filter that you are applying. This is necessary to avoid circular-convolution effects. Or do I not fully understand what you are doing here? Greg Berchin
