Techniques for performing discrete fourier transforms on radix-2 platforms
View Patent ↗A technique for performing a discrete Fourier transform (DFT) includes storing, in a single-port memory, multiple signal points. A first group of consecutive ones of the multiple signal points are fetched (from a first line of the single-port memory) to a first input register associated with a processor that includes multiple arithmetic units (AUs) that are each configured to perform multiply accumulate (MAC) operations. A second group of consecutive ones of the multiple signal points are then fetched (from a second line of the single-port memory) to a second input register associated with the processor. Selected pairs of the multiple signal points are then loaded (one from each of the first and second input registers for each pair) into the multiple arithmetic units during an initial butterfly stage. Radix-2 butterfly operations are then performed on the selected pairs of the multiple signal points (using the multiple AUs) to provide respective output elements.
1. 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.
2. The method of claim 1 , wherein the radix-2 platform is configured as a decimation-in-frequency implementation.
3. The method of claim 1 , further comprising:
storing, during the initial butterfly stage, first ones of the respective first output elements in selected locations in a first output register and second ones of the respective first output elements in selected locations in a second output register; and
storing, in the single-port memory, the first ones of the respective first output elements in the first output register and the second ones of the respective first output elements in the second output register.
4. The method of claim 3 , wherein the first ones of the respective first output elements are stored in the first line and the second ones of the respective first output elements are stored in the second line.
5. The method of claim 3 , wherein the first ones of the respective first output elements are stored in a third line of the single-port memory and the second ones of the respective first output elements are stored in a fourth line of the single-port memory.
6. The method of claim 3 , further comprising:
fetching a first group of consecutive ones of the respective first output elements, from the single-port memory, to the first input register;
fetching a second group of consecutive ones of the respective first output elements, from the single-port memory, to the second input register;
loading selected pairs of the respective first output elements, from the first input register, into the multiple arithmetic units during at least one intermediate butterfly stage, wherein the at least one intermediate butterfly stage is subsequent to the initial butterfly stage;
loading selected pairs of the respective first output elements, from the second input register, into the multiple arithmetic units during the at least one intermediate butterfly stage; and
performing butterfly operations on the selected pairs of the respective first output elements using the multiple arithmetic units to provide respective second output elements during the at least one intermediate butterfly stage.
7. The method of claim 6 , further comprising:
storing, during the at least one intermediate butterfly stage, first ones of the respective second output elements in selected locations in the first output register and second ones of the respective second output elements in selected locations in the second output register; and
storing, in the single-port memory, the first ones of the respective second output elements in the first output register and the second ones of the respective second output elements in the second output register.
8. The method of claim 7 , wherein the first ones of the respective second output elements are stored in the first line and the second ones of the respective second output elements are stored in the second line.
9. The method of claim 7 , wherein the first ones of the respective second output elements are stored in a third line of the single-port memory and the second ones of the respective second output elements are stored in a fourth line of the single-port memory.
10. The method of claim 7 , further comprising:
fetching a first group of consecutive ones of the respective second output elements, from the single-port memory, to the first input register;
fetching a second group of consecutive ones of the respective second output elements, from the single-port memory, to the second input register;
loading selected pairs of the respective second output elements, from adjacent locations in the first input register, into the multiple arithmetic units during a final butterfly stage, wherein the final butterfly stage is subsequent to the at least one intermediate butterfly stage;
loading selected pairs of the respective second output elements, from adjacent locations in the second input register, into the multiple arithmetic units during the final butterfly stage; and
performing butterfly operations on the selected pairs of the respective second output elements using the multiple arithmetic units to provide respective third output elements during the final butterfly stage.
11. The method of claim 10 , further comprising:
storing, during the final butterfly stage, the respective third output elements associated with the first input register in selected adjacent locations in the first output register;
storing, during the final butterfly stage, the respective third output elements associated with the second input register in selected adjacent locations in the second output register; and
storing, in the single-port memory, the respective third output elements in the first output register and the respective third output elements in the second output register.
12. The method of claim 1 , wherein the first and second groups each include thirty-two of the multiple signal points.
13. 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, from adjacent locations in the first input register, into the multiple arithmetic units during an initial butterfly stage;
loading selected pairs of the multiple signal points, from adjacent locations in the second input register, into the multiple arithmetic units during the initial butterfly stage; 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.
14. The method of claim 13 , wherein the radix-2 platform is configured as a decimation-in-time implementation.
15. The method of claim 13 , further comprising:
storing, during the initial butterfly stage, first ones of the respective first output elements in selected locations in a first output register and second ones of the respective first output elements in selected locations in a second output register; and
storing, in the single-port memory, the first ones of the respective first output elements in the first output register and the second ones of the respective first output elements in the second output register.
16. The method of claim 15 , further comprising:
fetching a first group of consecutive ones of the respective first output elements, from the single-port memory, to the first input register;
fetching a second group of consecutive ones of the respective first output elements, from the single-port memory, to the second input register;
loading selected pairs of the respective first output elements, from the first input register, into the multiple arithmetic units during at least one intermediate butterfly stage, wherein the at least one intermediate butterfly stage is subsequent to the initial butterfly stage;
loading selected pairs of the respective first output elements, from the second input register, into the multiple arithmetic units during the at least one intermediate butterfly stage; and
performing butterfly operations on the selected pairs of the respective first output elements using the multiple arithmetic units to provide respective second output elements during the at least one intermediate butterfly stage.
17. The method of claim 16 , further comprising:
storing, during the at least one intermediate butterfly stage, first ones of the respective second output elements in selected locations in the first output register and second ones of the respective second output elements in selected locations in the second output register; and
storing, in the single-port memory, the first ones of the respective second output elements in the first output register and the second ones of the respective second output elements in the second output register.
18. The method of claim 17 , further comprising:
fetching a first group of consecutive ones of the respective second output elements, from the single-port memory, to the first input register;
fetching a second group of consecutive ones of the respective second output elements, from the single-port memory, to the second input register;
loading selected pairs of the respective second output elements into the multiple arithmetic units during at least one final butterfly stage, wherein the at least one final butterfly stage is subsequent to the at least one intermediate butterfly stage and each of the selected pairs includes one of the respective second output elements from the first input register and one of the respective second output elements from the second input register; and
performing butterfly operations on the selected pairs of the respective second output elements using the multiple arithmetic units to provide respective third output elements during the at least one final butterfly stage.
19. The method of claim 18 , further comprising:
storing, during the final butterfly stage, the respective third output elements associated with the first input register in selected adjacent locations in the first output register;
storing, during the final butterfly stage, the respective third output elements associated with the second input register in selected adjacent locations in the second output register; and
storing, in the single-port memory, the respective third output elements in the first output register and the respective third output elements in the second output register.
20. 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 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 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 a 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 stage corresponds to one or more initial butterfly stages having one or more subsequent butterfly stages when the radix-2 platform is configured as a decimation-in-frequency implementation or one or more final butterfly stages having one or more prior butterfly stages when the radix-2 platform is configured as a decimation-in-time implementation, and wherein the discrete Fourier transform is a mixed radix discrete Fourier transform and the butterfly operations are radix-M butterfly operations, where M is a prime factor and a size of the mixed radix discrete Fourier transform corresponds to M*K, and where K is a power of 2 and 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.
21. The method of claim 20 , further comprising:
representing the radix-M butterfly operations as M-1 of the multiply accumulate operations.
22. The method of claim 21 , further comprising:
processing the radix-M butterfly operations in batches of L, where L is a power of 2 and corresponds to a maximum number of the multiply accumulate operations that can be performed in parallel on the multiple arithmetic units.
23. The method of claim 21 , wherein the mixed radix discrete Fourier transform includes multiple prime factors each of which corresponds to respective radix-M butterfly operations and the method further comprises:
processing each of the respective radix-M butterfly operations in batches of L, where L is a power of 2and corresponds to a maximum number of the multiply accumulate operations that can be performed in parallel on the multiple arithmetic units.