VelociChicken wrote:>>>> Hello Fred, I'm curious to know why I can't simply zero out the top >>>> half of >>>> the FFT. Will multiplying by the halfband filter remove the need for >>>> 'overlap/add window' code? >>> Multiplying in frequency is equivalent to convolving in time. The >>> effective convolution kernel created by zeroing an unwanted band is >>> infinitely long; you can't pad an FFT enough to make the convolution >>> linear instead of circular. There will be lots of ringing and probably >>> other artifacts. > >> Correct. > >>> If you multiply be the the FFT of a practical filter, you will get a >>> result where the math doesn't break down. > >> ...and if you want to mess with *really* long sequences >> a time-domain implementation of a simple filter may become >> cheaper than using the FFT. > >> In the FFT you need to implement the FFT step (which is O(NlogN)), >> a complex multiplication step (O(N)) and an IFFT step (O(NlogN)) >> in addition to handling the logistics of the overlap-add method. >> >> When you add all the numbers (remember, constants are omitted >> in the 'big oh' notation!), it is cheaper to implement the >> time domain filter if a filter contains less than c*log(N) >> coefficients, where c is one of those omitted constants. > >> Rune > > Thanks for all the help guys, that's lead to some good reading. I need a > vertical cut across at half-band because I want to completely eliminate one > half of a mirrored spectrum, so any kind of signal past this point gets > wrongly introduced later. > So with CPU speed and slope it looks like frequency domain is going to win > afterall.The sharper the frequency cutoff, the more severe the time-domain ringing. If your system -- whatever it is -- requires all of the signal below some frequency and none of the signal above it, the system is designed wrong; it can't be implemented. Do you how Loki escaped beheading for killing Balder? He insisted "All of my head and none of my neck." It couldn't be done. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Low pass filter at half Nyquist
Started by ●March 1, 2008
Reply by ●March 2, 20082008-03-02
Reply by ●March 2, 20082008-03-02
"VelociChicken" <bob@yahoob.com> wrote in message news:fEzyj.225598$3m6.169377@fe2.news.blueyonder.co.uk...> > Hello Fred, I'm curious to know why I can't simply zero out the top half > of the FFT. Will multiplying by the halfband filter remove the need for > 'overlap/add window' code?Dave, Just to be clear, a normal FFT would be zeroed from fs/4 to 3fs/4 rather than from fs/2 to fs. So, it depends on what you mean by the "top half". Most FFTs have the top half being from fs/2 to fs-fs/N. Jerry and Rune have made good points that amplify what I was suggesting. I might note this in case it's of any value (something I've used for interpolation in time working the frequency domain): Once you've halfband filtered one time then the region fs/2 to 3fs/2 will be "nearly zero". In interpolation the idea is to increase the sample rate. So, let's say the desired increase is a factor of 2. We can readily envision the spectrum from zero to 2fs as being 2 periods of the original. If its already been halfband filtered one time then the regions fs/4 to 3fs/4 and 5fs/4 to 7fs/4 are nearly zero. What we need to get rid of is the repeated spectrum from 3fs/2 to 5fs/2. Another halfband filter at the new sample rate will do this. However, the result at 3fs/2 to 5fs/2 will be nearly zero AND the cutoff frequency of this halfband filter will occur where the energy is also nearly zero. Accordingly, we might well multiply 3fs/2 to 5fs/2 by zero. If this operation is at all offensive to some then there are a couple of observations to make: 1) The operation is identical to zero padding that is done in the time domain all the time, pre-FFT! 2) The operation is similar to zero padding in time *after* a window is applied. That's because the halfband filter is a window in frequency. This reduces the edge effects that cause the problems one might like to avoid. To answer your question about overlap/add: If you're only doing a single convolution then it isn't needed. If you're implementing a streaming process then it is. If you simply do a streaming process in the time domain then nothing more is needed. But, it may be relatively expensive in compute load. If you substitute a contiguous time domain filter by frequency domain implementation in order to save compute load (I really can't think of why else you'd do this), you're stuck with the "chunks" of data being processed and are forced to deal with the edges somehow - thus overlap add or overlap save or .... Fred
Reply by ●March 2, 20082008-03-02
Hi Dave, Here's some more reading material. This gives you a benchmark: how good of frequency response you can obtain versus how long of a filter kernel is used (for a windowed-sinc FIR filter). This should be where you start, treating all other techniques as a delta from this. Regards, Steve http://www.dspguide.com/ch16.htm
Reply by ●March 2, 20082008-03-02
"VelociChicken" <bob@yahoob.com> writes:>>> > Hello Fred, I'm curious to know why I can't simply zero out the top >>> > half of >>> > the FFT. Will multiplying by the halfband filter remove the need for >>> > 'overlap/add window' code? >> >>> Multiplying in frequency is equivalent to convolving in time. The >>> effective convolution kernel created by zeroing an unwanted band is >>> infinitely long; you can't pad an FFT enough to make the convolution >>> linear instead of circular. There will be lots of ringing and probably >>> other artifacts. > >>Correct. > >>> If you multiply be the the FFT of a practical filter, you will get a >> >result where the math doesn't break down. > >>...and if you want to mess with *really* long sequences >>a time-domain implementation of a simple filter may become >>cheaper than using the FFT. > >>In the FFT you need to implement the FFT step (which is O(NlogN)), >>a complex multiplication step (O(N)) and an IFFT step (O(NlogN)) >>in addition to handling the logistics of the overlap-add method. >> >>When you add all the numbers (remember, constants are omitted >>in the 'big oh' notation!), it is cheaper to implement the >>time domain filter if a filter contains less than c*log(N) >>coefficients, where c is one of those omitted constants. > >>Rune > > Thanks for all the help guys, that's lead to some good reading. I need a > vertical cut across at half-band because I want to completely eliminate one > half of a mirrored spectrum, so any kind of signal past this point gets > wrongly introduced later. > So with CPU speed and slope it looks like frequency domain is going to win > afterall.Hi Dave, Keep in mind that fixed-point frequency-domain filtering loses at least 1/2 bit per FFT stage: http://groups.google.com/group/comp.dsp/msg/f38e3ae59c6f49d8?dmode=source -- % Randy Yates % "With time with what you've learned, %% Fuquay-Varina, NC % they'll kiss the ground you walk %%% 919-577-9882 % upon." %%%% <yates@ieee.org> % '21st Century Man', *Time*, ELO http://www.digitalsignallabs.com
Reply by ●March 2, 20082008-03-02
DSPGURU <kruptan@gmail.com> writes:> [...] > Hello Mr. Chicken, > > If you read about halfband filter (books or old posts in comp.dsp) you > see they have really bad transition and are EXACTLY NOT what you want. > Keep looking.You're answering a question that was not originally asked. However, with further information Dave has provided from subsequent posts, it does appear that he's decimating and thus needs something better. -- % Randy Yates % "Ticket to the moon, flight leaves here today %% Fuquay-Varina, NC % from Satellite 2" %%% 919-577-9882 % 'Ticket To The Moon' %%%% <yates@ieee.org> % *Time*, Electric Light Orchestra http://www.digitalsignallabs.com
Reply by ●March 2, 20082008-03-02
On Mar 2, 7:42�pm, Randy Yates <ya...@ieee.org> wrote:> DSPGURU <krup...@gmail.com> writes: > > [...] > > Hello Mr. Chicken, > > > If you read about halfband filter (books or old posts in comp.dsp) you > > see they have really bad transition and are EXACTLY NOT what you want. > > Keep looking. > > You're answering a question that was not originally asked. However, with > further information Dave has provided from subsequent posts, it does > appear that he's decimating and thus needs something better. > -- > % �Randy Yates � � � � � � � � �% "Ticket to the moon, flight leaves here today > %% Fuquay-Varina, NC � � � � � �% �from Satellite 2" > %%% 919-577-9882 � � � � � � � �% 'Ticket To The Moon' > %%%% <ya...@ieee.org> � � � � � % *Time*, Electric Light Orchestrahttp://www.digitalsignallabs.comHello Randy, In first post Mr Chicken expresses intrest in "perfect cutoff". Halfband far from perfect. Kamar Ruptan DSP Guru (not associated with DSPGURU of Grant Griffin)
Reply by ●March 3, 20082008-03-03
Hi,>"DSP_PHD2BE" <kruptan@gmail.com> wrote in message >news:79eeaf0e-516c-412e-88cc-527bf7b66789@c33g2000hsd.googlegroups.com... >On Mar 2, 7:42 pm, Randy Yates <ya...@ieee.org> wrote: > DSPGURU <krup...@gmail.com> writes: > > [...] > > Hello Mr. Chicken, > > > If you read about halfband filter (books or old posts in comp.dsp) you > > see they have really bad transition and are EXACTLY NOT what you want. > > Keep looking. > > You're answering a question that was not originally asked. However, with > further information Dave has provided from subsequent posts, it does > appear that he's decimating and thus needs something better. > -- > % Randy Yates % "Ticket to the moon, flight leaves here today > %% Fuquay-Varina, NC % from Satellite 2" > %%% 919-577-9882 % 'Ticket To The Moon' > %%%% <ya...@ieee.org> % *Time*, Electric Light > Orchestrahttp://www.digitalsignallabs.com>Hello Randy, >In first post Mr Chicken expresses intrest in "perfect cutoff". >Halfband far from perfect. >Kamar Ruptan >DSP Guru (not associated with DSPGURU of Grant Griffin)Well, yes, I do want a perfect cutoff, but everybody was so helpful anyways, thanks all. And yet.... I've just found some references to Two-Path Polyphase filters, they look like the cool kids on the block. If only I could understand them! : ) Cheers, D
Reply by ●March 3, 20082008-03-03
DSP_PHD2BE <kruptan@gmail.com> writes:> On Mar 2, 7:42�pm, Randy Yates <ya...@ieee.org> wrote: >> DSPGURU <krup...@gmail.com> writes: >> > [...] >> > Hello Mr. Chicken, >> >> > If you read about halfband filter (books or old posts in comp.dsp) you >> > see they have really bad transition and are EXACTLY NOT what you want. >> > Keep looking. >> >> You're answering a question that was not originally asked. However, with >> further information Dave has provided from subsequent posts, it does >> appear that he's decimating and thus needs something better. >> -- >> % �Randy Yates � � � � � � � � �% "Ticket to the moon, flight leaves here today >> %% Fuquay-Varina, NC � � � � � �% �from Satellite 2" >> %%% 919-577-9882 � � � � � � � �% 'Ticket To The Moon' >> %%%% <ya...@ieee.org> � � � � � % *Time*, Electric Light Orchestrahttp://www.digitalsignallabs.com > > Hello Randy, > > In first post Mr Chicken expresses intrest in "perfect cutoff". > Halfband far from perfect.Yes, he did say that. And therefore he was wrong in an "absolute truth" sense since no filter in the real world is a "perfect" lowpass filter. So then the question was, "How far from perfect is acceptable for 'Mr. Chicken'?" Since he did not mention he was decimating, half-band filters seemed a perfectly reasonable compromise. My comment to you stands. -- % Randy Yates % "Maybe one day I'll feel her cold embrace, %% Fuquay-Varina, NC % and kiss her interface, %%% 919-577-9882 % til then, I'll leave her alone." %%%% <yates@ieee.org> % 'Yours Truly, 2095', *Time*, ELO http://www.digitalsignallabs.com
Reply by ●March 3, 20082008-03-03
"VelociChicken" <bob@yahoob.com> writes:> Hi, > >>"DSP_PHD2BE" <kruptan@gmail.com> wrote in message >>news:79eeaf0e-516c-412e-88cc-527bf7b66789@c33g2000hsd.googlegroups.com... >>On Mar 2, 7:42 pm, Randy Yates <ya...@ieee.org> wrote: >> DSPGURU <krup...@gmail.com> writes: >> > [...] >> > Hello Mr. Chicken, >> >> > If you read about halfband filter (books or old posts in comp.dsp) you >> > see they have really bad transition and are EXACTLY NOT what you want. >> > Keep looking. >> >> You're answering a question that was not originally asked. However, with >> further information Dave has provided from subsequent posts, it does >> appear that he's decimating and thus needs something better. >> -- >> % Randy Yates % "Ticket to the moon, flight leaves here today >> %% Fuquay-Varina, NC % from Satellite 2" >> %%% 919-577-9882 % 'Ticket To The Moon' >> %%%% <ya...@ieee.org> % *Time*, Electric Light >> Orchestrahttp://www.digitalsignallabs.com > >>Hello Randy, >>In first post Mr Chicken expresses intrest in "perfect cutoff". >>Halfband far from perfect. >>Kamar Ruptan >>DSP Guru (not associated with DSPGURU of Grant Griffin) > > Well, yes, I do want a perfect cutoff,First of all, "perfect cutoff" is somewhat imprecise. I assume you mean a filter with a 0 Hz transition bandwidth and infinite stopband attenuation (these are the terms commonly used in filter design). Such a filter doesn't exist in the real world.> but everybody was so helpful anyways, > thanks all. > And yet.... I've just found some references to Two-Path Polyphase filters, > they look like the cool kids on the block. If only I could understand > them!I've never heard of "two-path" polyphase filters, but the operation of polyphase decimation filters is very straightforward: since you're going to throw away M-1 of M samples when decimating by M, simply don't compute them. The rest is bookkeeping. -- % Randy Yates % "She has an IQ of 1001, she has a jumpsuit %% Fuquay-Varina, NC % on, and she's also a telephone." %%% 919-577-9882 % %%%% <yates@ieee.org> % 'Yours Truly, 2095', *Time*, ELO http://www.digitalsignallabs.com
Reply by ●March 3, 20082008-03-03
On Mar 3, 7:48�am, Randy Yates <ya...@ieee.org> wrote:> DSP_PHD2BE <krup...@gmail.com> writes: > > On Mar 2, 7:42�pm, Randy Yates <ya...@ieee.org> wrote: > >> DSPGURU <krup...@gmail.com> writes: > >> > [...] > >> > Hello Mr. Chicken, > > >> > If you read about halfband filter (books or old posts in comp.dsp) you > >> > see they have really bad transition and are EXACTLY NOT what you want. > >> > Keep looking. > > >> You're answering a question that was not originally asked. However, with > >> further information Dave has provided from subsequent posts, it does > >> appear that he's decimating and thus needs something better. > >> -- > >> % �Randy Yates � � � � � � � � �% "Ticket to the moon, flight leaves here today > >> %% Fuquay-Varina, NC � � � � � �% �from Satellite 2" > >> %%% 919-577-9882 � � � � � � � �% 'Ticket To The Moon' > >> %%%% <ya...@ieee.org> � � � � � % *Time*, Electric Light Orchestrahttp://www.digitalsignallabs.com > > > Hello Randy, > > > In first post Mr Chicken expresses intrest in "perfect cutoff". > > Halfband far from perfect. > > Yes, he did say that. And therefore he was wrong in an "absolute truth" > sense since no filter in the real world is a "perfect" lowpass filter. > > So then the question was, "How far from perfect is acceptable for > 'Mr. Chicken'?" Since he did not mention he was decimating, half-band > filters seemed a perfectly reasonable compromise. > > My comment to you stands. > -- > % �Randy Yates � � � � � � � � �% "Maybe one day I'll feel her cold embrace, > %% Fuquay-Varina, NC � � � � � �% � � � � � � � � � �and kiss her interface, > %%% 919-577-9882 � � � � � � � �% � � � � � �til then, I'll leave her alone." > %%%% <ya...@ieee.org> � � � � � % � � � �'Yours Truly, 2095', *Time*, ELO �http://www.digitalsignallabs.com- Hide quoted text - > > - Show quoted text -Mr Randy, Halfband as lowpass filter is what to do AVOID perfect. For pass gain of 1.0, gain at FS/2 = 0.5 !!! Transition band tend to be WWWWIIIIDDDDDEEEE !!! Nuf said, but you can have last word. Regards, Kamar Ruptan DSP Guru (not with DSPGURU of Grant Griffin)
