Patent ID: 8271569

Claim:
A method for performing a discrete Fourier transform on a radix-2 platform, comprising: storing, in a single-port memory, multiple signal points; fetching a first group of consecutive ones of the multiple signal points, from a first line of the single-port memory, to a first input register associated with a processor, wherein the processor includes multiple arithmetic units that are each configured to perform multiply accumulate operations; fetching a second group of consecutive ones of the multiple signal points, from a second line of the single-port memory, to a second input register associated with the processor; loading selected pairs of the multiple signal points into the multiple arithmetic units during an initial butterfly stage, wherein each of the selected pairs includes one of the multiple signal points from the first input register and one of the multiple signal points from the second input register; and performing butterfly operations in parallel on the selected pairs of the multiple signal points using the multiple arithmetic units to provide respective first output elements during the initial butterfly stage, wherein the butterfly operations are radix-M butterfly operations and M is a prime factor not equal to two, and wherein the multiple arithmetic units exhibit substantially one-hundred percent utilization during the butterfly operations by computing a first output point for each said radix-M butterfly operation, and subsequently computing the other output points for said radix-M operation.