Hey guys, I was wondering if anyone could validate my current understanding of FIR dsp filters. Consider an input sequence "x" of size M and a FIR filter sequence "f" of size "N", then: 1. The filtered output "y" is: y[k] = SUM:n-N (x[k-n] * f[n]) 2. The size of the "y" is the same as "x" 3. M must be greater than N 4. The runtime of filtering is O(M*N) Thanks, --Shafik
FIR facts: True or False.
Started by ●September 29, 2004
Reply by ●September 29, 20042004-09-29
Shafik wrote:> Hey guys, > > I was wondering if anyone could validate my current understanding of > FIR dsp filters. > > Consider an input sequence "x" of size M and a FIR filter sequence "f" > of size "N", then: > > 1. The filtered output "y" is: y[k] = SUM:n-N (x[k-n] * f[n]) > > 2. The size of the "y" is the same as "x" > > 3. M must be greater than N > 4. The runtime of filtering is O(M*N) > > > Thanks, > --ShafikThe coefficients of the filter are convolved with the data. The output has M + N - 1 elements. The first and last N-1 elements consist of transients, so the number of fully significant output elements is M - N + 1 Jerry -- ... they proceeded on the sound principle that the magnitude of a lie always contains a certain factor of credibility, ... and that therefor ... they more easily fall victim to a big lie than to a little one ... A. H. �����������������������������������������������������������������������
Reply by ●October 1, 20042004-10-01
Ahh ok. How come then, some DSP packages do an "inplace" buffer filtration. Meaning I can take an input buffer X and just FIR filter it, and I'll get X but filtered (same length). How is that possible?
Reply by ●October 1, 20042004-10-01
They probably internally add zeros before and after the data, run the data through the FIR filter, and then trim off some of the transient elements off the front and back end so the result is equal number of output to input samples. "Shafik" <shafik@u.arizona.edu> wrote in message news:1096677693.488575.276830@k26g2000oda.googlegroups.com...> Ahh ok. > > How come then, some DSP packages do an "inplace" buffer filtration. > Meaning I can take an input buffer X and just FIR filter it, and I'll > get X but filtered (same length). How is that possible? >
Reply by ●October 1, 20042004-10-01
Shafik wrote:> Ahh ok. > > How come then, some DSP packages do an "inplace" buffer filtration. > Meaning I can take an input buffer X and just FIR filter it, and I'll > get X but filtered (same length). How is that possible? >I don't know the details of how it's done, but there must be some intermediate storage somewhere. That the data start and end in the same place doesn't mean that it has never been elsewhere. As for the size being the same, there's a certain amount of sense to discarding the outer parts of the transients. Jerry -- ... they proceeded on the sound principle that the magnitude of a lie always contains a certain factor of credibility, ... and that therefor ... they more easily fall victim to a big lie than to a little one ... A. H. �����������������������������������������������������������������������
Reply by ●October 2, 20042004-10-02
"Jon Harris" <goldentully@hotmail.com> wrote in message news:<2s6dh9F1g4vvpU1@uni-berlin.de>...> They probably internally add zeros before and after the data, run the data > through the FIR filter, and then trim off some of the transient elements off the > front and back end so the result is equal number of output to input samples.Good implementations do that. The quick'n dirty method is to do all the computations in frequency domain: % Matlab pseudocode X=fft(x); H=fft(h,N); y=real(ifft(X.*H)); where x is the data, h is the FIR filter impulse response and N is the number of samples in x. Here, I would expect wrap-around effects. It ought to be easy to spot such a quick'n dirty implementation, though: Test the routine with an impulse sequence x (x(0)=1, all other samples = 0), and plot the output y. If there are non-zero samples near the tail end of y, you know something is wrong. Rune> "Shafik" <shafik@u.arizona.edu> wrote in message > news:1096677693.488575.276830@k26g2000oda.googlegroups.com... > > Ahh ok. > > > > How come then, some DSP packages do an "inplace" buffer filtration. > > Meaning I can take an input buffer X and just FIR filter it, and I'll > > get X but filtered (same length). How is that possible? > >
Reply by ●October 2, 20042004-10-02
Rune Allnor wrote:> "Jon Harris" <goldentully@hotmail.com> wrote in message news:<2s6dh9F1g4vvpU1@uni-berlin.de>... > >>They probably internally add zeros before and after the data, run the data >>through the FIR filter, and then trim off some of the transient elements off the >>front and back end so the result is equal number of output to input samples. > > > Good implementations do that. The quick'n dirty method is to do all the > computations in frequency domain: > > % Matlab pseudocode > X=fft(x); > H=fft(h,N); > y=real(ifft(X.*H)); > > where x is the data, h is the FIR filter impulse response and N is the > number of samples in x. Here, I would expect wrap-around effects. > > It ought to be easy to spot such a quick'n dirty implementation, though: > Test the routine with an impulse sequence x (x(0)=1, all other > samples = 0), and plot the output y. If there are non-zero samples > near the tail end of y, you know something is wrong. > > RuneI was under the impression that ccnvolution was convolution, no matter how implemented; that implemention via FFT/IFFT and via transversal methods produce the same result. Was I wrong? Jerry -- ... they proceeded on the sound principle that the magnitude of a lie always contains a certain factor of credibility, ... and that therefor ... they more easily fall victim to a big lie than to a little one ... A. H. �����������������������������������������������������������������������
Reply by ●October 2, 20042004-10-02
On 2004-10-02 15:30:12 +0200, Jerry Avins <jya@ieee.org> said:> I was under the impression that ccnvolution was convolution, no matter > how implemented; that implemention via FFT/IFFT and via transversal > methods produce the same result. Was I wrong? > > JerryThe DFT produces circular convolution while plain FIRs produce the linear flavor. So, yes and no - the result *can* be the same if you take this into account. -- Stephan M. Bernsee http://www.dspdimension.com
Reply by ●October 2, 20042004-10-02
Stephan M. Bernsee wrote:> On 2004-10-02 15:30:12 +0200, Jerry Avins <jya@ieee.org> said: > >> I was under the impression that ccnvolution was convolution, no matter >> how implemented; that implemention via FFT/IFFT and via transversal >> methods produce the same result. Was I wrong? >> >> Jerry > > > The DFT produces circular convolution while plain FIRs produce the > linear flavor. So, yes and no - the result *can* be the same if you take > this into account.That's a matter of implementation detail. I can do circular transversal convolution as well as linear. With transversal convolution, linear convolution is usually the simple case, while with transform convolution, it's the other way around. Jerry -- ... they proceeded on the sound principle that the magnitude of a lie always contains a certain factor of credibility, ... and that therefor ... they more easily fall victim to a big lie than to a little one ... A. H. �����������������������������������������������������������������������
Reply by ●October 2, 20042004-10-02
On 2004-10-02 16:52:03 +0200, Jerry Avins <jya@ieee.org> said:> That's a matter of implementation detail. I can do circular transversal > convolution as well as linear. With transversal convolution, linear > convolution is usually the simple case, while with transform > convolution, it's the other way around. > > JerryYes. That's why I said you *can* get the same result if you take this into account. -- Stephan M. Bernsee http://www.dspdimension.com
