Hi,>> - multiplies each block with the Hann window function, >NO! Not with overlap. How did this nonsense get started? It just won'tdie! <snip>>> The reason why I do this that way? Simple, I read it in a book ;-) > What book? It needs a few pages ripped out.Sorry, I was a bit inaccurate there; it wasn't a printed book but something I read on the Internet - took me a while to remember where I read it, and then quite a bit longer to find it again. Here it is: http://crca.ucsd.edu/~msp/techniques/latest/book-html/node172.html> It isn't for fast convolution.I never heard "fast convolution" before, but it *might* be what I'm trying to accomplish. "Ordinary convolution" is, if I recall this correctly, the process of multiplying an impulse response with every sample from the input (and summing up the results from the individual samples). I would have done this in favor of the FFT/iFFT approach which I described in the original post, but the required length of the impulse response (aka the filter kernel, if my memory serves me well) would have meant much too many multiplies-and-adds (target platform is an ordinary PC, not a DSP). So I tried an FFT/modify/iFFT approach instead. Is that approach "fast convolutiuon", or is it something else?>Some people seem to think that because their applications don't >require windows, that they should tell others not to use windows. >Windowing continues because some people have applications that shouldI guess there must be a reason for windows; otherwise, there wouldn't be soo many of 'em to choose from. In my case, windowing seemed to be what I needed (from my newbie point of view), since I process the data in blocks. I remember that an FFT always considers the data as periodic. If I truncate a wave right in the middle (which is likely to happen and the beginning and the end of the block), I get harmonics. Yes, there is an approach which pads the block with zeros at both sides, but this still resultzs in unwanted harmonic content - and it does, as far as I can tell, not invalidate the idea of windowing (since this approach is just a sort of rectangular window...).> You can see from the rest of his post that he's filtering by fast > convolution. That it can be made to work with a von Hann window (it's > symmetrical about .5, offset) makes the idea that you need to window all> the more pernicious. You can do it, but with needless cost. Bah!Humbug! As far as I can see, windowing would not be needed if the added harmonic content would cancel itself again during the iFFT stage. my math goes so far that I believe that this is the case if I pass the result from FFT back to the iFFT without any modification. However, I do modify the spectrum between FFT and iFFT. Is the modification irrelevant, or does it f*** up the signal beyond recognition?>A question for the original poster is: which 'Blackman' window do you >mean and what do you think it will do for you? This answer might allow >us to repond if windowing is appropriate for you or why not.Hm, I didn't know that where diifferent Blackmans. Or Blackmen? :-) I mean, apart from Blackman-Harris and whatever. Okay, a quick search revealed http://www.eng.vt.edu/me5714/textbook/windows.pdf - which indeed lists Blackman and Exact Blackman. And I have no idea which one I want. The reason for me asking about the Blackman windiow was I once saw a comparision of different window functions, and how they affect things in the frequency domain. The Blackman window appeared to have a better stopband attenuation than the Hann window, while still not causing too much other harm, so it appeared to me as a choice which I might prefer. However, as I now have found the above mentioned paper, other questions arise... 1. The paper has a table with a column "overlap correlation", for both a 50% and 75% overlap. Does this mean that, in practise, only two overlap intervals are used? Are the values, which appear in these columns, the "exactness" with which the recombination of the overlapping windowed blocks works? 2. Am I using a Hann window with alpha=1 or with alpha=2 ("Hann squared")? May seem to be a dumb question, but I apply the Hann window twice (before FFT and after iFFT), so I guess that it might be that I'm performing some sort of squaring to the window function which might be not totally obvious to a newbie like me. 3. The table has a column "side lobe fall off (db/Oct)". Does that correspond to the maximum attainable filter slope in my audio signal application? In other words, if I choose a triangle window and filter a signal by zeroing all frequencies below 1000 Hz (in the complex data, which I have between FFT and iFFT step), that at 500 Hz the signal will be only -12dB down? And with a rectangular window only -6dB? Or am I just getting something wrong there? You have two problem here. 1) You have applied a window function to your fft. You thus have to apply the "inverse windowing function" to your data before the ifft ! 2) Do you truncate your output signal in order to cancel the overlap effect ?> last step of your application. If you use Matlab, have a look to the > Matlab function called specgram.m (you can find it in the Signal > Processing Toolbox) and its inverse function that you can find here :<snip> I do not have Matlab, and it appears that the Matlab website is currently experiencing a problem with my registration, so I can't get to the code right now :-(> If it is not the case, you just will have to translate the m-code inthe language you use. ;-) My language is called "newbie babble" ;-)> If you apply a "good", i.e. with no bug, inverse STFT, you will be > able to choose any overlap !I use the FFTW library (the precompiled version, so I'm sure that I didn't break anything during compilation :-)), so errors can creep in only in my choice of windowing or in the general concept (well, I guess I got the complex*real multiplication in the frquency domain right...not so difficult, I think).> So, to normalize the result, divide somewhere in the process by theintegral> of the window function I do believe.Correct, I figured that out already, but didn't mention it in my description. Without that normalization, the output signal is indeed +12dB higher than the input signal. I measured only the peaks, though. One of my concern is that the window adds some kind of modulation (AM) to the resulting signal, despite overlapping, especially if the window function does not add up to 100% (or 400%) after overlapping at each sample. Or are all window function designed in way that this is always ensured? (I guess my last question proves that I'm indeed a "math noob"...butter I think it's better to ask than to stay a noob (or idiot)). Best regards, Klaus
How do I perfrom the correct overlap after FFT/iFFT when using a Blackman window?
Started by ●February 26, 2007
Reply by ●February 27, 20072007-02-27
Reply by ●February 27, 20072007-02-27
>3. The table has a column "side lobe fall off (db/Oct)". Does that >correspond to the maximum attainable filter slope in my audio signal >application? In other words, if I choose a triangle window and filter a >signal by zeroing all frequencies below 1000 Hz (in the complex data, >which I have between FFT and iFFT step), that at 500 Hz the signal willbe>only -12dB down? And with a rectangular window only -6dB? Or am I just >getting something wrong there?Okay, I guess that I think I can answer that myself, after I found another table at http://www.bores.com/courses/advanced/windows/10_end.htm - which happens to have a column which I interpret as the "-6dB point, given in FFT bins". What the heck is a "bin"? I *assume* that a bin coresponds to one of the complex number which I receive as a result after the FFT (and which I shove back into the iFFT after some processing). So my 16384 point FFT results in, erm, dunno 8192 or 8193 bins (for DC and the Nyquist frequency, the complex number is only filled "half" with meaningful data, as there is no phase information - dunno how this corresponds to the numbre of "bins" though...leaving alone the question if my assumption about the meaning of the word "bin" is correct). Best regards, Klaus
Reply by ●February 27, 20072007-02-27
KlausS wrote:> Hi, > >>> - multiplies each block with the Hann window function, >> NO! Not with overlap. How did this nonsense get started? It just won't > die! > <snip> >>> The reason why I do this that way? Simple, I read it in a book ;-) >> What book? It needs a few pages ripped out. > > Sorry, I was a bit inaccurate there; it wasn't a printed book but > something I read on the Internet - took me a while to remember where I > read it, and then quite a bit longer to find it again. Here it is: > http://crca.ucsd.edu/~msp/techniques/latest/book-html/node172.html > >> It isn't for fast convolution. > > I never heard "fast convolution" before, but it *might* be what I'm trying > to accomplish. "Ordinary convolution" is, if I recall this correctly, the > process of multiplying an impulse response with every sample from the > input (and summing up the results from the individual samples). I would > have done this in favor of the FFT/iFFT approach which I described in the > original post, but the required length of the impulse response (aka the > filter kernel, if my memory serves me well) would have meant much too many > multiplies-and-adds (target platform is an ordinary PC, not a DSP). So I > tried an FFT/modify/iFFT approach instead. Is that approach "fast > convolutiuon", or is it something else?That's fast convolution. It's not hard to implement, but it's tricky in that there are considerations that aren't obvious. Multiplication on the time domain does the same thing to a pair of signals as convolution in the frequency domain, and vice versa. It's the vice versa that you do here. There are still impulse responses. In particular, the weighting function you multiply the FFT by is the frequency equivalent of the impulse response of the equivalent time-domain filter. You may not need to know what that impulse response is, but you certainly need to know how long it is because the minimum lengths your FFT and IFFT depend on it. If the impulse response is longer that FFT can accommodate, nasty artifacts are added to the signal. You can't make a usable notch filter by simply zeroing out a band of frequencies. The impulse response that implies is infinite in both directions. There's another gotcha. FFT-multiply-IFFT doesn't really do convolution as you think of it. It does circular convolution, where the end uses the beginning over again. That ruins everything, but there's a fix. If you add enough null samples to an end of the signal chunk, the "used again" part consists of zeros. While the convolution is still circular, the effect is the same as linear convolution, which we need.>> Some people seem to think that because their applications don't >> require windows, that they should tell others not to use windows. >> Windowing continues because some people have applications that should > > I guess there must be a reason for windows; otherwise, there wouldn't be > soo many of 'em to choose from.Ignore that bit of sniping from the sidelines. The point is, *you* don't need a window *here*.> In my case, windowing seemed to be what I needed (from my newbie point of > view), since I process the data in blocks. I remember that an FFT always > considers the data as periodic. If I truncate a wave right in the middle > (which is likely to happen and the beginning and the end of the block), I > get harmonics. Yes, there is an approach which pads the block with zeros > at both sides, but this still results in unwanted harmonic content - and > it does, as far as I can tell, not invalidate the idea of windowing (since > this approach is just a sort of rectangular window...).You are processing in blocks, but you are processing the whole signal. When you adequately zero pad, overlap properly, and then add the overlapped portions, the blocking artifacts cancel and disappear. With or without a window. But the best you can hope for from a window is that it won't be any worse.>> You can see from the rest of his post that he's filtering by fast >> convolution. That it can be made to work with a von Hann window (it's >> symmetrical about .5, offset) makes the idea that you need to window all >> the more pernicious. You can do it, but with needless cost. Bah! Humbug! > > As far as I can see, windowing would not be needed if the added harmonic > content would cancel itself again during the iFFT stage. my math goes so > far that I believe that this is the case if I pass the result from FFT > back to the iFFT without any modification. However, I do modify the > spectrum between FFT and iFFT. Is the modification irrelevant, or does it > f*** up the signal beyond recognition?It's the overlap-add (or overlap save) that cancels the artifacts. ... Dedicated DSP machines have special instructions to speed convolution, but even those benefit from fast convolution when the impulse response of the filter exceeds 40 or so. Go to http://www.dspguide.com/ and read Chapter 17 of the book available there. It'll give you the straight dope. Steer clear of any paper that advises a window. The author may have made fast convolution (aka FFT convolution) work, but he hasn't thought it through. Good luck! Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by ●February 27, 20072007-02-27
Jerry Avins wrote:> ... Go to http://www.dspguide.com/ and read > Chapter 17 of the book available there. ...Oops! That's the wrong place in the book. Read pages 179 to 184 in Chapter 9 and pages 311 to 318 in Chapter 18. Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by ●February 27, 20072007-02-27
Hi,>it. If the impulse response is longer that FFT can accommodate, nasty >artifacts are added to the signal. You can't make a usable notch filter >by simply zeroing out a band of frequencies. The impulse response that >implies is infinite in both directions.I think the impulse response can never get any longer than the FFT window size - the same as with ordinary convolution. This implies the little-known fact that brickwall filters are are impossible (at least in the area of mathematis; in marketing, brickwall filters are presented in regular intervals :-)). Since all kinds of filters share a common set of limitations, it also means that steeper slopes also mean more "time-smear".>There's another gotcha. FFT-multiply-IFFT doesn't really do convolution >as you think of it. It does circular convolution, where the end uses the>beginning over again. That ruins everything, but there's a fix. If you >add enough null samples to an end of the signal chunk, the "used again" >part consists of zeros. While the convolution is still circular, the >effect is the same as linear convolution, which we need.<snip>>You are processing in blocks, but you are processing the whole signal. >When you adequately zero pad, overlap properly, and then add the >overlapped portions, the blocking artifacts cancel and disappear. With >or without a window. But the best you can hope for from a window is that>it won't be any worse.Okay, I think I begin to get it. My previously consumed literature didn't provide me with the insight about the details which you and some others contributed. Using a tool without understanding what it really does usually leads to sub-optimum results...>of the filter exceeds 40 or so. Go to http://www.dspguide.com/ and read >Chapter 17 of the book available there. It'll give you the straightYes, I have read that book. It mentioned zero-padding, but I didn't find any reference to what happens with the additional harmonics which are caused by the chopping of the signal. Now, since you mentioned the effect of zeroing a frequency on the impulse response, how much zero-padding do I need to be as safe as possible (or reasonable...)? If use a 16K point FFT to convolve a signal, the impulse response can be 16K points long at most. So I'd need another 16K zero samples as "spare" to be safe...but I guess this means that the FFT now works on 32K samples, and the maximum impulse response lengths also gets 32K samples...? Or do I have to process the target frequency response in a way that the impulse response gets short enough for the filtr to work (by performing an iFFT of the target frequency response, chopping off excessive length, perform an FFT and use the result)?>It's the overlap-add (or overlap save) that cancels the artifacts.This seems to mean that the interval which was zeroed before the FFT (the "zero-pad zone") also needs to be included in the overlap operation. Is that correct? Thanks for you help, and best regards, Klaus
Reply by ●February 27, 20072007-02-27
KlausS wrote: ...> Okay, I think I begin to get it. My previously consumed literature didn't > provide me with the insight about the details which you and some others > contributed. Using a tool without understanding what it really does > usually leads to sub-optimum results... > >> of the filter exceeds 40 or so. Go to http://www.dspguide.com/ and read >> Chapter 17 of the book available there. It'll give you the straight > > Yes, I have read that book. It mentioned zero-padding, but I didn't find > any reference to what happens with the additional harmonics which are > caused by the chopping of the signal.Did you read the passages as I corrected? Pages 179 to 184 in Chapter 9 and pages 311 to 318 in Chapter 18. Actually, the artifacts introduced by chopping needn't be harmonic.> Now, since you mentioned the effect of zeroing a frequency on the impulse > response, how much zero-padding do I need to be as safe as possible (or > reasonable...)? If use a 16K point FFT to convolve a signal, the impulse > response can be 16K points long at most. So I'd need another 16K zero > samples as "spare" to be safe...but I guess this means that the FFT now > works on 32K samples, and the maximum impulse response lengths also gets > 32K samples...? Or do I have to process the target frequency response in a > way that the impulse response gets short enough for the filter to work (by > performing an iFFT of the target frequency response, chopping off > excessive length, perform an FFT and use the result)?Read the book passages I listed, and gain further enlightenment in the thread here " fast convolution crossover/break even point for DSPs, FPGAs". When you try to make the filter do to much, you get artifacts, mostly ringing -- Gibbs phenomenon. A way to know what you have starts with the frequency response you want. IFFT it to get the impulse response, and truncate that to a practical length. You can FFT that to see the modified frequency response and live with that, or window it -- see? windows _are_ useful -- and then FFT it to get the (now tame) shaping function. It sounds like a lot of work, but you only need to do it once. ScopeDSP from http://www.iowegian.com/ will do it for you. There's a free evaluation version to play with.>> It's the overlap-add (or overlap save) that cancels the artifacts. > > This seems to mean that the interval which was zeroed before the FFT (the > "zero-pad zone") also needs to be included in the overlap operation. Is > that correct?In the abstract I suppose, but no harm ever came of failing to add zero.> Thanks for you help, and best regards, KlausI hope I help more than confuse. Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by ●February 27, 20072007-02-27
On Feb 27, 5:45 am, "KlausS" <k...@stock-consulting.com> wrote:> Hm, I didn't know that where diifferent Blackmans. Or Blackmen? :-) I > mean, apart from Blackman-Harris and whatever. Okay, a quick search > revealedhttp://www.eng.vt.edu/me5714/textbook/windows.pdf- which indeed > lists Blackman and Exact Blackman. And I have no idea which one I want. > The reason for me asking about the Blackman windiow was I once saw a > comparision of different window functions, and how they affect things in > the frequency domain. The Blackman window appeared to have a better > stopband attenuation than the Hann window, while still not causing too > much other harm, so it appeared to me as a choice which I might prefer. >You have found the classic Harris paper on windows. The table of window parameters has an error for Exact Blackman, the first column entry: highest sidelobe level should be -68 dB not -51. Exact Blackman has better first sidelobe rejection and narrower mainlobe but only -6 dB/octave sidelobe rolloff. The other common Blackman trades for -18 dB/octave sidelobe rolloff. This 'Blackman' window might be functionally described as "2 digit rounded 3-term Blackman". Blackman originally published it as "R. Blackman's not very serious proposal" so I call it "Blackman-nvsp".> However, as I now have found the above mentioned paper, other questions > arise... > > 1. The paper has a table with a column "overlap correlation", for both a > 50% and 75% overlap. Does this mean that, in practise, only two overlap > intervals are used? Are the values, which appear in these columns, the > "exactness" with which the recombination of the overlapping windowed > blocks works?These table columns are intended for guidance when performing weighted overlapped segment averaging (WOSA) spectrum analysis (aka Welch's method), which you aren't. Further discussion of this topic in Harris' 1976 paper for the Navy lab didn't make the cut for the IEEE Proceedings 1978 paper you have found.> 2. Am I using a Hann window with alpha=1 or with alpha=2 ("Hann squared")? > May seem to be a dumb question, but I apply the Hann window twice (before > FFT and after iFFT), so I guess that it might be that I'm performing some > sort of squaring to the window function which might be not totally obvious > to a newbie like me.An operation like this is used by people doing combined analysis/ synthesis processing with time varying parameters, but you don't need to.> 3. The table has a column "side lobe fall off (db/Oct)". Does that > correspond to the maximum attainable filter slope in my audio signal > application?Yes. In other words, if I choose a triangle window and filter a> signal by zeroing all frequencies below 1000 Hz (in the complex data, > which I have between FFT and iFFT step), that at 500 Hz the signal will be > only -12dB down? And with a rectangular window only -6dB? Or am I just > getting something wrong there? > ...It means that whatever sidelobe response is a n bins away, at 2*n bins away the response will be down further by the sidelobe fall off (dB/ Oct) The Harris table also includes columns with -3 dB and -6 dB mainlobe respose widths.> Best regards, KlausDale B. Dalrymple
