Potential of non-uniformly partitioned convolution with freely adaptable FFT sizes

摘要

The standard class of algorithms used for FIR filtering with long impulse responses and short input-to-output latencies are non-uniformly partitioned fast convolution methods. Here a filter impulse response is split into several smaller sub filters of different sizes. Small sub filters are needed for a low latency, whereas long filter parts allow for more computational efficiency. Finding an optimal filter partition that minimizes the computational cost is not trivial, however optimization algorithms are known. Mostly the Fast Fourier Transform (FFT) is used for implementing the fast convolution of the sub filters. Usually the FFT transform sizes are chosen to be powers of two, which has a direct effect on the partitioning of filters. Recent studies reveal, that the use of FFT transform sizes which are not powers two has a strong potential to lower the computational costs of the convolution even more. This paper presents a novel real-time low-latency convolution algorithm, which performs non-uniformly partitioned convolution with freely adaptable FFT sizes. Alongside, an optimization technique is presented that allows adjusting the FFT sizes in order to minimize the computational complexity for this new framework of non-uniform filter partitions. Finally the performance of the algorithm is compared to conventional methods.