Method and apparatus for fast fourier transform calculation

摘要

A method and apparatus for transforming a first m-dimensional indexed array with N elements into a second m-dimensional indexed array with M elements. The first array may be a representation of a physical signal in a telecommunications network or system and the second array represents the transform of this signal or an intermediate array generated as part of a method to obtain the transform. The representation of the first array may be formed by indexing time discrete values of a signal into the first array, for example row-by-row, column-column; e.g. by sampling a physical, analog signal. In a first aspect of the invention data locality improvement schedules are presented. In a first embodiment a full data locality improvement schedule is disclosed while in a second embodiment a partial data locality improvement schedule is shown.