Patent ID: 9582474
Date: 2017-02-28
CPC Classifications: G06F

Claim:
1. A method for performing a FFT computation, comprising: providing first and second input data elements in multiple memory areas of a memory unit; in each of a number of consecutive computation stages, simultaneously performing multiple butterfly operations by at least one computer processor, each based on a first input data element and a second input data element, to obtain two output data elements, wherein the first and second input data elements for a plurality of the multiple butterfly operations are each simultaneously retrieved from predetermined memory locations of a first and second memory areas of the memory unit, and wherein one or more computation stages are associated with a first phase and one or more subsequent computation stages are associated with a second phase; and for each of the computation stages, storing the two output data elements in the memory unit as input data elements for a next computation stage according to a mapping scheme, wherein the mapping scheme is configured to store the output data elements at memory locations in the first and second memory areas so that they are simultaneously retrievable as input data elements for a plurality of butterfly operations of the subsequent computation stage; wherein, according to the mapping scheme for each of the butterfly operation of each of the computation stages of the first phase, the two output data elements resulting from the respective butterfly operation are stored into the same memory locations in the first and second memory areas as the input data elements of the respective butterfly operation which have been retrieved; and wherein, according to the mapping scheme for each of the butterfly operations of each of the computation stages of the second phase, the input data elements input to the respective butterfly operations are retrieved from memory locations of the first and second memory areas that are different from the memory locations in which the two output data elements resulting from the respective butterfly operation are stored.