Fast computation of DFT of 2-D data with symmetry about two diagonals

A fast algorithm to compute the DFT of a diagonally symmetric 2-D array is presented. The algorithm is developed employing the techniques of the multidimensional Winograd Fourier transform algorithm. First, the derivation of the algorithm is presented for quadrantally symmetric 2-D data of size N×N, where N is a prime number. Then a method of converting diagonally symmetric 2-D data and its transform into quadrantally symmetric data and its transform is derived. This is then used to develop the fast symmetry-based algorithm for the DFT of diagonally symmetric data. The new algorithm reduces the required number of multiplications and additions by about 70% for quadrantally or diagonally symmetric 2-D data