Prime-factor algorithm and Winograd Fourier transform algorithm for real symmetric and antisymmetric sequences

摘要

In the paper, algorithms for computing discrete Fourier transform (DFT) of 1-D real symmetric and antisymmetric sequences, using the prime-factor algorithm (PFA) and the Winograd Fourier transform algorithm (WFTA), are presented. These algorithms are obtained from different factorisations of the Fourier matrix, and it is shown that symmetry conditions exist at each stage which are used to construct efficient algorithms for computing DFTs.