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

I am completely new to the field of DSP -- so this question may be
elementry

I was wondering about the worst case performance of a butterworth
bandpass filter. I know that the FFT algorithm has a worst case
performance of O(N log N). Does a second order bandpass filter have a
similar computational cost? How does this cost vary as a function of
the order of the filter?

Any insight would be grately appreciated.

Thanks,

Arctan

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

<a...@gmail.com> wrote in message
news:1...@o13g2000cwo.googlegroups.com...
> I am completely new to the field of DSP -- so this question may be
> elementry
>
> I was wondering about the worst case performance of a butterworth
> bandpass filter. I know that the FFT algorithm has a worst case
> performance of O(N log N). Does a second order bandpass filter have a
> similar computational cost? How does this cost vary as a function of
> the order of the filter?

With an FFT, you have a block of data of N samples.  So assuming you want to run
a Butterworth bandpass filter on the same block of N samples, the cost would be
O(N).

If the filter is higher order, it is still an O(N) algorithm, though the actual
cost is increased linearly (i.e. the constant multiplier is higher for higher
orders).  Now if you assume that N is the order of the filter rather than the
length of the block of samples to filter, then when you filter a fixed block,
the filter cost is O(N) again, i.e. cost increases linearly with increasing
filter order.

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

a...@gmail.com wrote:
> I am completely new to the field of DSP -- so this question may be
> elementry
> 
> I was wondering about the worst case performance of a butterworth
> bandpass filter. I know that the FFT algorithm has a worst case
> performance of O(N log N). Does a second order bandpass filter have a
> similar computational cost? How does this cost vary as a function of
> the order of the filter?
> 
> Any insight would be grately appreciated.
> 
> Thanks,
> 
> Arctan
> 
A second-order filter will require, at most, 5 multiplies, a first-order 
3.  For an N-order filter you'll want to break it down into as many 
first-order filters as you can, with only the resonant pole-pairs being 
second order (an N-order butterworth filter has zero or one first-order 
sections, and floor(N/2) 2nd-order sections).

-------------------------------------------
Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

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

Arctan wrote (by the way, did you know that Lem names his humanoid
robots in "The Invincible" Arctan?):

>I was wondering about the worst case performance of a butterworth
>bandpass filter. I know that the FFT algorithm has a worst case
>performance of O(N log N). Does a second order bandpass filter have a
>similar computational cost? How does this cost vary as a function of
>the order of the filter?
>
>Any insight would be grately appreciated.

You're not comparing apples to apples.

Fast convolution (FFT) filtering uses O( (N+M) (log (N+M) + 1) ) time
to run M samples through an FIR of order N, as compared to time domain
convolution which uses O( N M ) for the same process. If you want to
run M samples through a IIR butterworth filter of order N, then this
also takes O(  N M ) time.

However, depending on the filter requirement, the N for a FIR and the N
for an IIR implementation will vary strongly. Also, depending on your
programming capabilities and the hardware platform, the constants that
we have ignored so far can make a big difference. Furthermore, the
computation time of the fast convolution filter algorithm can be tuned
in a streaming application (by selecting M appropriatly) such that the
constants become small (this again depends on the hardware available,
cache, memory, etc.). And lastly, there is no "worst case" for
computing filters. It's a deterministic process.

Regards,
Andor

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