Radix-3 fast algorithms for polynomial time frequency transforms

The polynomial time frequency transforms have been used as an effective tool to reveal the polynomial-phase information by converting a one-dimensional polynomial-phase signal in the time domain into a multi-dimensional output array in the frequency domain. To significantly reduce the prohibitive computational complexity for dealing with high order polynomial-phase signals, efficient fast algorithms are extremely important for any practical applications. Based on radix-3 decomposition techniques, this paper presents fast algorithms for any order of the polynomial-phase signals. It shows that the computational complexity, except that for twiddle factors, of the radix-3 algorithm is independent of the order of the polynomial time frequency transform. The proposed algorithms are simple in concept and achieve significant savings on computational complexity.