Fast computation of two-dimensional discrete Fourier transform using fast discrete Radon transform

摘要

The author presents a new decomposition in which the two-dimensional discrete Fourier transform (2-D DFT) can be converted into a series of the odd DFT using the discrete Radon transform (DRT). Moreover, the author presents a fast DRT (FDRT) algorithm for computing DRT with a reduced number of additions. As a result, an FDRT-based 2-D DFT algorithm is presented. The regularity and parallel structure of this algorithm make it of great practical value for implementation in VLSI and parallel processing environments. This FDRT-based 2-D DFT algorithm has the same minimal known number of multiplications and slightly more additions compared with other 2-D DFT algorithms. In parallel implementation, the FDRT-based algorithm increases the computation speed greatly.