Fast algorithms for polynomial time frequency transform

The computation of polynomial time frequency transform (PTFT) is required for the maximum likelihood method to estimate the phase parameters of the polynomial-phase signals (PPSs). The transform can be computed by directly using the 1D fast Fourier transforms (FFT), which requires a prohibitive computational load for higher-order PPSs. By exploiting two properties of the PTFT, this paper presents a decimation-in-time fast algorithm to significantly reduce the computational complexity compared with that by only using 1D FFT. For example, the numbers of both complex multiplications and additions are reduced by a factor of 2Mlog2N for N  -point (M+1)(M+1)th-order PTFTs.