Adaptive Filter | ADPCM | ADSP | ADSP-2181 | Aliasing | AMR | Anti-Aliasing | ARMA | Autocorrelation | AutoCovariance | Beamforming | Bessel | Blackfin | Butterworth | C6713 | CCS | Chebyshev | CIC Filter | Circular Convolution | Code Composer Studio | Comb Filter | Compression | Convolution | Cross Correlation | DCT | Decimation | Deconvolution | Demodulation | DM642 | DSP Boards | DSP/BIOS | DTMF | Echo Cancellation | Equalization | Equalizer | ETSI | EZLITE (Ez-kit Lite) | FFT | FFTW | FIR Filter | Fixed Point | FSK | G.711 | G.723 | G.729 | Gaussian Noise | Goertzel | GPIO | Hilbert Transform | IFFT | IIR Filter | Interpolation | Invariance | JTAG | Kalman | Laplace Transform | Levinson | LPC | McBSP | MIPS | Modulation | MPEG | Multirate | Notch Filter | Nyquist | OFDM | Oversampling | Pink Noise | Pitch | PLL | Polyphase | QAM | QDMA | Quantization | Quantizer | Radar | Random Noise | Reed Solomon | Remez | Resampling | RTDX | Sampling | Sharc | TI C6711 | Undersampling | Viterbi | Wavelets | White Noise | Wiener Filter | Windowing | XDS510PP | Z Transform

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

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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,
> --Shafik

The 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.
———————————————————————————————————————————————————————————————————————

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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?

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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" <s...@u.arizona.edu> wrote in message
news:1...@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?
>

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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.
———————————————————————————————————————————————————————————————————————

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

"Jon Harris" <g...@hotmail.com> wrote in message
news:<2...@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" <s...@u.arizona.edu> wrote in message
> news:1...@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?
> >

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

Rune Allnor wrote:

> "Jon Harris" <g...@hotmail.com> wrote in message
news:<2...@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

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
-- 
... 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.
———————————————————————————————————————————————————————————————————————

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

On 2004-10-02 15:30:12 +0200, Jerry Avins <j...@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.
-- 
Stephan M. Bernsee
http://www.dspdimension.com

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

Stephan M. Bernsee wrote:

> On 2004-10-02 15:30:12 +0200, Jerry Avins <j...@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.
———————————————————————————————————————————————————————————————————————

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

On 2004-10-02 16:52:03 +0200, Jerry Avins <j...@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.
> 
> Jerry

Yes. That's why I said you *can* get the same result if you take this 
into account.
-- 
Stephan M. Bernsee
http://www.dspdimension.com

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.