What is the computatinal complexity of resample(x,p,q)?

Hi I am perform downsampling with resample(x,p,q) in matlab and need to find the computational complexity of it.

y = resample(x,p,q) resamples the input sequence, x, at p/q times the original sample rate. resample applies an FIR Antialiasing Lowpass Filter to x and compensates for the delay introduced by the filter. The function operates along the first array dimension with size greater than 1.

filter:

Let N be the total number of samples, for FIR lowpass filter, the computational complexity is O(N*L), with L being number of filter taps

Decimination: Let p = 1

Then for a signal of N samples what is the time complexity of decimination for p/q with p =1?

Answer 1

[Ravi]

Hi Kalasagarreddi Kottakota,

I assume that you want to know the overall complexity of the “resample” function provided “p = 1”.

The decimation process involves two main steps:

1. Filtering the signal to avoid aliasing.

2. Down-sampling the signal by selecting every q-th sample after filtering.

For the down-sampling process, when “p = 1”, you are simply selecting every “qth” sample from the filtered signal. If the original signal has “N” samples, after filtering, you still have “N” samples, but you will only keep every “qth” sample. Therefore, the number of samples in the down-sampled signal will be approximately “N/q”.

The computational complexity of the down-sampling process is proportional to the number of samples in the down-sampled signal. Since we are only selecting every “qth” sample, the complexity of this step is O(N/q).

Combining the two steps, we have:

1. Filtering: O(N*L)

2. Down-sampling: O(N/q)

The overall complexity is the sum of the complexities of these two steps. However, since O(N*L) is typically much larger than O(N/q) (especially for large “L”), the filtering step dominates the computational complexity. Therefore, the overall complexity of the decimation process when “p = 1” is approximately O(N*L).

Hope this explanation solves your question.

Thanks,

Ravi Chandra