Patent ID: 6938064
Filing Date: 2005-08-30
Classification: G06F

Abstract:
1. A method of calculating a fast Fourier transform or an inverse fast Fourier transform of a digital signal defined by a series of N real starting samples x(n), with N a power of two and n ε [0 . . . N−1], the method comprising the steps of: transforming input samples into output samples in a first transformation step; transforming input samples into output samples in at least one successive transformation step to the first transformation step; and storing the input samples and output samples of each transformation step in a storage memory; wherein each of the transformation steps is performed by means of a single set of butterfly circuits with several inputs and several outputs, the operating mode of the set of butterfly circuits modified selectively in each transformation step, a series of N output samples y(n) representative of the fast Fourier transform or the inverse fast Fourier transform of the output samples x(n) being provided in a last transformation step; wherein output samples y(n) are real; wherein output samples of a butterfly circuit replace the corresponding input samples of the same rank in the storage memory, so that, if the starting samples x(n) processed in the first transformation step are classified in bit-reversed order of their index n, output samples y(n) are provided in the last transformation step in ascending order of index n and are defined by the following relations: wherein samples X (n), with n ε [0 . . . N−1], designate complex samples of the series corresponding to the fast or inverse fast Fourier transform of the starting samples series x(n).