Patent ID: 7739322

Claim:
A method for controlling processing elements in a multiprocessor architecture to provide improved throughout for Fast Fourier Transform/Inverse Fast Fourier Transform (FFT/IFFT) computations, the method comprising the steps of: computing, on a multiprocessor architecture including “P” processing elements each butterfly of the first “log 2 P” stages of an FFT/IFFT on either a single one of the processing elements or on each of the “P” processing elements simultaneously; distributing the computations of the butterflies in all the subsequent stages of the FFT/IFFT among the “P” processing elements such that each chain of cascaded butterflies consisting of those butterflies that have inputs and outputs connected together is processed by the same processing element to thereby eliminate the need for inter-processor communication among the processing elements after the computation of the first “log2P” stages of the FFT/IFFT; wherein the distributing of the computation of the butterflies subsequent to the first “log 2 P” butterflies is achieved by assigning operand addresses of each set of butterfly operands to each processing element in such a manner that the butterfly is processed by the same processing element that computed the connected butterfly of the previous stage in the same chain of butterflies; and wherein the desired assignment of operand addresses is achieved by deriving the address of the first operand in the operand pair corresponding to the “i th ” stage of the computation from the address of the corresponding operand in the previous stage by inserting a “0” in the “(i+1) th ” bit position of the address, while the address of the second operand is derived by inserting a “1” in the “(i+1) th ” bit position of the operand address.