Patent ID: 7430575

Claim:
A calculating apparatus quickly processing a one-dimensional Fourier transform, comprising: a data length resolving unit resolving a data length N of one-dimensional data into a product of m factors N 1 ×N 2 ×. . . ×N m ; a twiddle factor storing unit setting the data length N as P×Q, calculating twiddle factors that are required for a multiplication with results of a one-dimensional Fourier transform of a length Q, which is performed by P times, for an initial one of Q- 1 twiddle factors for multiplication intended for each of P Fourier transform results, while maintaining an order of the product of the m factors and changing P and Q, and storing calculation results in a table; and a Fourier transform unit performing a Fourier transform of data as m separated phases with the table for storing the calculated twiddle factors, wherein said Fourier transform unit includes, a memory area divided into memory regions 1 and 2 , storing m-dimensional array regions for storing input data and output data in the m phases, wherein results of a Fourier transform process for input data stored in the region 1 in an odd-numbered chase are stored in positions where a multi-dimensional transposition for an m-dimensional array is performed in said region 2 , and wherein results of the Fourier transform process for input data stored in the region 2 in an even-numbered phase are stored in positions where the multi-dimensional transposition for an m-dimensional array is performed in the region 1 .