We are performing a convolution of audio signal, with 511th order FIR filters, using fast convolution methods: overlap-add or overlap-save. Filters are being designed in frequency domain several thousand times per second. Filters need to be zeros padded to be used in order to be used in fast convolution algorithms, so to acquire appropriately padded filters we do:
- frequency domain filter design, filters of 511th order
- IFFT into time domain
- zeros padding to 2048 length (1536 zeros)
- FFT back into frequency domain (for multiplication with spectral representation of input audio signal)
Computational complexity of such operation occurred be to high for our needs. We're trying to figure out if there's a method to avoid IFFF->FFT steps and reduce the overall complexity from O(NlogN) to O(N). Any ideas if it is possible, and, if so, how can it be achieved?