Fast DFT algorithms for diagonally symmetric 2-D data
P.K. Rajan · 2003
An efficient algorithm is presented for the evaluation of DFTs (discrete Fourier transforms) of diagonally symmetric 2-D data of size N*N, where N is a prime number. The general Winograd algorithm for 3*3 size data is modified to take into account the diagonal symmetry present in the data. This diagonal symmetry based algorithm for 3*3 DFTs requires four scalar multiplications and 21 scalar additions, whereas the general Winograd algorithm requires nine scalar multiplications and 36 scalar additions. The above procedure is extended for N*N (where N is prime) data processing diagonal symmetry. The resulting symmetry-based transform is nearly half the size of the conventional transform, and, hence requires considerably less computation than the conventional 2-D FFT (fast Fourier transform).>