Chirp-Based decompositions for computing fractional fourier transforms

Abstract

The fractional Fourier transform (FrFT) is a tool for analyzing non-stationary signals, associated with rotations of signal representations through energy distributions in the time-frequency plane. The main numerical algorithm for computing the FrFT is derived from its integral definition and, through sampling, produces a form of discrete FrFT (DFrFT). This thesis focuses on the study of this type of DFrFT and chirp signals, both of which are relevant in various modern systems. There are two chirp-based decompositions for computing the DFrFT: (i) one using chirp convolution and (ii) another relying solely on a discrete Fourier transform (DFT); both are typically implemented via fast Fourier transform (FFT) algorithms. The first contribution of this thesis is the implementation of a simplified FrFT(SmFrFT), with variable frequency scaling, in normalized domains. It is demonstrated that SmFrFT, being a particular case of canonical linear transforms, exhibits distinct properties compared to conventional FrFT and offers advantages in chirp signal processing; the reduction in the number of complex multiplications is approximately 77%. The second contribution of this thesis consists of the reformulation of the previously mentioned chirp convolution as a circular convolution, represented over the ring of integers modulo 2b + 1. In this context, an algorithm for computing partial points of an N-point DFrFT based on a 2D convolution scheme is introduced; in this case, it is possible to reduce computational complexity by at least 4N multiplications by employing local circular convolution instead of its global version. This approach includes the use of the Fermat Number Transform (FNT), for which local input and output optimizations are proposed to avoid operations involving zero values and to compute only the points of interest. Numerical simulations, including applications in radar echo modeling, are presented to validate the effectiveness of the proposed algorithm. As a final contribution, the SmFrFT is applied to direction-of-arrival (DoA) estimation of wideband chirp signals in scenarios involving one or multiple targets using a uniform linear array. The multi-target case is reformulated as a multi-line fitting problem. In this context, two innovative approaches are considered: piecewise slope fitting and line detection in the Hough space. Numerical simulations demonstrate that both methods achieve low computational complexity. However, for high-precision scenarios, the ESPRIT algorithm with spatial smoothing, incorporating the discrete SmFrFT, is recommended, where a novel preprocessing step—a peak alignment procedure in the fractional Fourier domain—is introduced