Hi all, I want to filter out very narrow band signal, and thinking about using fast-convolution filtering. The input signal is real (not analytic) and the output signal should be real. I wonder if there is any trick I can play to take advantage of real signal processing? Is there any saving on computation I can achieve since I deal with real signal? I have huge data to process, thus, even small saving on computation will help. Could you let me know or point me to any helpful reference? Thanks, Gongdori
Fast-convolution filtering on real signal
Started by ●November 21, 2012
Reply by ●November 21, 20122012-11-21
On Wednesday, November 21, 2012 6:55:52 AM UTC-8, gongdori wrote:> Hi all, > > I want to filter out very narrow band signal, and thinking about using > fast-convolution filtering. The input signal is real (not analytic) and the > output signal should be real. I wonder if there is any trick I can play to > take advantage of real signal processing? Is there any saving on > computation I can achieve since I deal with real signal? > I have huge data to process, thus, even small saving on computation will > help. > Could you let me know or point me to any helpful reference? > > Thanks, > > GongdoriOne effective approach is to use a multiple stage implementation of "frequency response masking" as proposed by Lim and others. An example of the design of the basic structure is: DESIGN AND EFFICIENT IMPLEMENTATION OF SINGLE FILTER FREQUENCY-RESPONSE MASKING FIR FILTERS by Oscar Gustafsson , H�kan Johansson , Lars Wanhammar which can be downloaded at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.8508 The references in that paper will lead you to other papers on the topic. Dale B. Dalrymple
Reply by ●November 21, 20122012-11-21
On Wed, 21 Nov 2012 08:55:51 -0600, gongdori wrote:> Hi all, > > I want to filter out very narrow band signal, and thinking about using > fast-convolution filtering. The input signal is real (not analytic) and > the output signal should be real. I wonder if there is any trick I can > play to take advantage of real signal processing? Is there any saving on > computation I can achieve since I deal with real signal? > I have huge data to process, thus, even small saving on computation will > help. > Could you let me know or point me to any helpful reference? > Thanks, > > GongdoriDepending on what you're trying to keep and what you're trying to reject, you may also want to consider an IIR filter (good for narrow-band, but be very careful of precision and phase shift effects) or a heterodyne approach (good if you want to keep a narrow signal that doesn't have a lot of close-in noise). -- Tim Wescott Control system and signal processing consulting www.wescottdesign.com
Reply by ●November 21, 20122012-11-21
"gongdori" <16548@dsprelated> writes:> Hi all, > > I want to filter out very narrow band signal, and thinking about using > fast-convolution filtering. The input signal is real (not analytic) and the > output signal should be real. I wonder if there is any trick I can play to > take advantage of real signal processing? Is there any saving on > computation I can achieve since I deal with real signal? > I have huge data to process, thus, even small saving on computation will > help. > Could you let me know or point me to any helpful reference? > Thanks, > > GongdoriHi Gongdori, There certainly are FFT-based frequency-domain filtering architectures that support real input data, real filters, and real outputs. The FFTW documentation talks about their functions for doing this here: http://www.fftw.org/fftw3_doc/One_002dDimensional-DFTs-of-Real-Data.html#One_002dDimensional-DFTs-of-Real-Data I couldn't find any other references right off, but will keep searching. -- Randy Yates Digital Signal Labs http://www.digitalsignallabs.com
Reply by ●November 21, 20122012-11-21
On 11/21/12 9:55 AM, gongdori wrote:> > I want to filter out very narrow band signal, and thinking about using > fast-convolution filtering.i think i agree with Tim in that it might make sense to consider using a narrow band IIR filter. especially if computational burden is important.> The input signal is real (not analytic) and the > output signal should be real. I wonder if there is any trick I can play to > take advantage of real signal processing? Is there any saving on > computation I can achieve since I deal with real signal?when you do fast-convolution, you are implementing an FIR filter. a very long FIR filter. (short FIR filters are best done the old-fashioned way.) now, in order for fast-convolution to be fast, the FFT must be used as the DFT component. now, it's a known fact that the Fourier Transform of a real signal has this "hermitian symmetry" where the spectrum of the real signal looks like it is reflected about f=0 axis. for the DFT, it means that X[k] = conj{ X[N-k] } where N is the DFT length. anyway, you can get these FFT programs in various flavors, one variant is that N real samples are input and N/2 complex pairs (the other N/2 points are superfluous since they are reflected from the N/2 points that are returned). if you use a regular old complex-to-complex FFT, and your fast-convolution is convolving a real signal with a real impulse response, then you can save half of the computation by processing two frames of real data as one frame of complex data. all you have to do is put one real frame in the real part and the following real frame into the complex part, FFT, multiply in frequency domain, iFFT, separate the real and imag parts back into two real frames and do whatever you do with overlap-add or overlap-save. it's getting two for the price of one.> I have huge data to process, thus, even small saving on computation will > help.seems to me that you could do this with an IIR bandpass filter and save a lot of computation. or, as Tim suggested, you might want to hetrodyne it down to around DC and lowpass filter it. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●November 21, 20122012-11-21
robert bristow-johnson <rbj@audioimagination.com> wrote:> On 11/21/12 9:55 AM, gongdori wrote:>> I want to filter out very narrow band signal, and thinking about using >> fast-convolution filtering.> i think i agree with Tim in that it might make sense to consider using a > narrow band IIR filter. especially if computational burden is important.>> The input signal is real (not analytic) and the >> output signal should be real. I wonder if there is any trick I can play to >> take advantage of real signal processing? Is there any saving on >> computation I can achieve since I deal with real signal?> when you do fast-convolution, you are implementing an FIR filter. a > very long FIR filter. (short FIR filters are best done the > old-fashioned way.) now, in order for fast-convolution to be fast, the > FFT must be used as the DFT component.> now, it's a known fact that the Fourier Transform of a real signal has > this "hermitian symmetry" where the spectrum of the real signal looks > like it is reflected about f=0 axis.Why does everyone forget the Hartley transform, and also the equivalent discrete and fast versions? http://en.wikipedia.org/wiki/Discrete_Hartley_transform I do understand that the Fourier transform is more popular, and used more, but it seems that there is pretty much zero discussion about the Hartley transform.> for the DFT, it means that> X[k] = conj{ X[N-k] } where N is the DFT length.> anyway, you can get these FFT programs in various flavors, one variant > is that N real samples are input and N/2 complex pairs (the other N/2 > points are superfluous since they are reflected from the N/2 points that > are returned).And there are also FHT algorithms that give you N real transform values from N real input values. No imaginary numbers need apply. (Not that I don't like the FFT, but maybe it isn't always best.) -- glen
Reply by ●November 21, 20122012-11-21
On Wednesday, November 21, 2012 2:32:25 PM UTC-5, robert bristow-johnson wrote:> On 11/21/12 9:55 AM, gongdori wrote: > > > > > > I want to filter out very narrow band signal, and thinking about using > > > fast-convolution filtering. > > > > i think i agree with Tim in that it might make sense to consider using a > > narrow band IIR filter. especially if computational burden is important. > > > > > The input signal is real (not analytic) and the > > > output signal should be real. I wonder if there is any trick I can play to > > > take advantage of real signal processing? Is there any saving on > > > computation I can achieve since I deal with real signal? > > > > when you do fast-convolution, you are implementing an FIR filter. a > > very long FIR filter. (short FIR filters are best done the > > old-fashioned way.) now, in order for fast-convolution to be fast, the > > FFT must be used as the DFT component. > > > > now, it's a known fact that the Fourier Transform of a real signal has > > this "hermitian symmetry" where the spectrum of the real signal looks > > like it is reflected about f=0 axis. for the DFT, it means that > > > > X[k] = conj{ X[N-k] } where N is the DFT length. > > > > anyway, you can get these FFT programs in various flavors, one variant > > is that N real samples are input and N/2 complex pairs (the other N/2 > > points are superfluous since they are reflected from the N/2 points that > > are returned). > > > > if you use a regular old complex-to-complex FFT, and your > > fast-convolution is convolving a real signal with a real impulse > > response, then you can save half of the computation by processing two > > frames of real data as one frame of complex data. all you have to do is > > put one real frame in the real part and the following real frame into > > the complex part, FFT, multiply in frequency domain, iFFT, separate the > > real and imag parts back into two real frames and do whatever you do > > with overlap-add or overlap-save. it's getting two for the price of one. > > > > > > > I have huge data to process, thus, even small saving on computation will > > > help. > > > > seems to me that you could do this with an IIR bandpass filter and save > > a lot of computation. or, as Tim suggested, you might want to hetrodyne > > it down to around DC and lowpass filter it. > > > > > > -- > > > > r b-j rbj@audioimagination.com > > > > "Imagination is more important than knowledge."It is a little tricky to get the indexing right when unpacking the result. The math is simple though. John
Reply by ●November 21, 20122012-11-21
On Wednesday, November 21, 2012 12:17:39 PM UTC-8, glen herrmannsfeldt wrote:> ....> Why does everyone forget the Hartley transform, and also the .> equivalent discrete and fast versions?> > http://en.wikipedia.org/wiki/Discrete_Hartley_transform > > I do understand that the Fourier transform is more popular, and > used more, but it seems that there is pretty much zero discussion > about the Hartley transform. > ... > -- glenWho forgets? Reading even the wiki reference on Discrete Hartley transforms will tell you that except for large prime transform sizes, DHTs are less efficient than DFTs. That and the inability to deal with complex data as well as real makes DHT unattractive for implementations in signal processing libraries. Dismissed? Yes, rightfully. Forgotten? Maybe by some, but Bracewell's mis-benchmarking of the DHT against complex DFT routines remains a classic lesson in DSP from the 1980s. Dale B. Dalrymple
Reply by ●November 21, 20122012-11-21
>On Wednesday, November 21, 2012 12:17:39 PM UTC-8, glen herrmannsfeldtwrot=>e: >> ... >=20 >.> Why does everyone forget the Hartley transform, and also the >.> equivalent discrete and fast versions? >>=20 >> http://en.wikipedia.org/wiki/Discrete_Hartley_transform >>=20 >> I do understand that the Fourier transform is more popular, and >> used more, but it seems that there is pretty much zero discussion >> about the Hartley transform. >> ... >> -- glen > >Who forgets? Reading even the wiki reference on Discrete Hartleytransforms=> will tell you that except for large prime transform sizes, DHTs are lesse=>fficient than DFTs. That and the inability to deal with complex data aswel=>l as real makes DHT unattractive for implementations in signal processingl=>ibraries. Dismissed? Yes, rightfully. Forgotten? Maybe by some, butBracewe=>ll's mis-benchmarking of the DHT against complex DFT routines remains acla=>ssic lesson in DSP from the 1980s. > >Dale B. Dalrymple > >Thanks all for your reply. I considered shifting it to baseband and using some efficient filter such as cic, and shift it back up, but I need to compensate for sinx/x roll off. Thus, I decided to go for fast convolution filter. I'm not familiar with IIR filter so, I haven't really considered it. I studied how it works long time ago. It does not have linear phase, right? I wonder if it is used often in digital system? Could you give me a reference on IIR on digital system if you have any? I couldn't find the paper, DESIGN AND EFFICIENT IMPLEMENTATION OF SINGLE FILTER FREQUENCY-RESPONSE MASKING FIR FILTERS, but Thanks! I am about to code up to test what b-j mentioned, but it would be great if I can see how it works mathematically. If you have any reference on this, could you let me know please? Thanks so much!!!
Reply by ●November 21, 20122012-11-21
On Wed, 21 Nov 2012 13:21:44 -0800 (PST), dbd <dbd@ieee.org> wrote:>On Wednesday, November 21, 2012 12:17:39 PM UTC-8, glen herrmannsfeldt wrot= >e: >> ... >=20 >.> Why does everyone forget the Hartley transform, and also the >.> equivalent discrete and fast versions? >>=20 >> http://en.wikipedia.org/wiki/Discrete_Hartley_transform >>=20 >> I do understand that the Fourier transform is more popular, and >> used more, but it seems that there is pretty much zero discussion >> about the Hartley transform. >> ... >> -- glen > >Who forgets? Reading even the wiki reference on Discrete Hartley transforms= > will tell you that except for large prime transform sizes, DHTs are less e= >fficient than DFTs. That and the inability to deal with complex data as wel= >l as real makes DHT unattractive for implementations in signal processing l= >ibraries. Dismissed? Yes, rightfully. Forgotten? Maybe by some, but Bracewe= >ll's mis-benchmarking of the DHT against complex DFT routines remains a cla= >ssic lesson in DSP from the 1980s. > >Dale B. DalrympleThere have been some discussions of DHTs here in the past, and a few folks, one in particular, wound up being a bit offended by their consideration. As Dale mentioned, there's little advantage to the DHT beyond a very small difference in program memory storage since the DHT is its own inverse. I used DHTs extensively in my academic research mostly because the flow was simpler since all of the data vectors were real-valued. The only technical/complexity advantage was in program storage, which I suppose could still be an advantage in memory-limited embedded systems, and that advantage is not big. Eric Jacobsen Anchor Hill Communications http://www.anchorhill.com
