Fast algorithm for optimal design of Fermat number transform based block digital filters

International audienceTransform-based block digital filtering (BDF) is a powerful tool for reducing computational complexity and increasing the parallelism of digital filtering systems. Most commonly used transforms, such as the discrete Fourier transform (DFT) and the discrete cosine transform (DCT), are not suitable for fixed-point implementation since they lead to a large quantization error. Otherwise, Fermat number transform (FNT) ensures an error-free computation in addition to a lower computational cost. In this paper, we propose an efficient algorithm for the optimal FNT-BDF design based on a quadratic criterion. A significant reduction in the computational cost of the algorithm is achieved through the use of the properties of circulant matrices and the Babai estimate method, used to solve integer least squares problem. Compared to DFT-BDF design, simulation results verify that our optimal FNT-BDF is more efficient and more accurate