FFT engine having combined bit-reversal and memory transpose operations

Patent metadata

Field	Value
Publication number	US-11170071-B2
Application number	US-201816221470-A
Country	US
Kind code	B2
Filing date	Dec 15, 2018
Priority date	Dec 15, 2018
Publication date	Nov 9, 2021
Grant date	Nov 9, 2021

Abstract

A data processing device includes: 1) Fast Fourier Transform (FFT) logic configured to generate FFT output samples for each of a plurality of digital input signals; 3) a first memory device with a plurality of banks; 4) a second memory device; 5) a bit-reversed address generator and first set of circular shift components configured to shift between the plurality of banks when writing the generated FFT output samples in bit-reversed address order to the first memory device; and 6) a second set of circular shift components configured to shift between the plurality of banks when reading FFT output samples in linear address order from the first memory device for storage in the second memory device, wherein the first and second set of circular shift components together are configured to read FFT output samples in transpose order using combined bit-reversal and memory transpose operations.

First claim

What is claimed is:

1. A data processing device that comprises:
Fast Fourier Transform (FFT) logic configured to generate FFT output samples for each of a plurality of digital input signals;
a first memory device with a plurality of banks;
a second memory device;
a bit-reversed address generator configured to provide a bit-reversed address order;
a first set of circular shift components coupled to the bit-reversed address generator and configured to shift between the plurality of banks when writing the generated FFT output samples in the bit-reversed address order to the first memory device; and
a second set of circular shift components configured to shift between the plurality of banks when reading FFT output samples in linear address order from the first memory device for storage in the second memory device, wherein the first and second set of circular shift components together are configured to read FFT output samples in transpose order using combined bit-reversal and memory transpose operations.

2. The data processing device of claim 1 , wherein the first set of circular shift components are configured to write FFT output samples corresponding to each digital input signal across the plurality of banks of the first memory device in bit-reversed address order.

3. The data processing device of claim 2 , wherein the second set of circular shift components are configured to read FFT output samples from the first memory device for storage in the second memory device such that FFT output samples corresponding to each of the digital input signals are read in linear order from the plurality of banks of the first memory device.

4. The data processing device of claim 1 , wherein the first set of circular shift components include a set of data multiplexers coupled between the FFT logic and the first memory device.

5. The data processing device of claim 4 , wherein the set of data multiplexers is a set of K data multiplexers configured to write each one of K FFT output samples to one of X banks of the first memory device before shifting to another of X banks of the first memory device for a next FFT operation, wherein X is at least equal to K, and wherein K is at least 2.

6. The data processing device of claim 1 , wherein an index number is used to control shift operations of the first set of circular shift components, and wherein the index number is incremented after each FFT operation and is a modulo X number.

7. The data processing device of claim 1 , wherein the first set of circular shift components include a set of address multiplexers coupled between the bit-reversed address generator and the first memory device.

8. The data processing device of claim 7 , wherein the set of address multiplexers are configured to use K addresses from the bit-reversed address generator to write to one of the plurality of banks of the first memory device before shifting to another of the plurality of banks of the first memory device for a next FFT operation, and wherein K is at least 2.

9. The data processing device of claim 7 , wherein the bit-reversed address generator is configured to generate addresses from 0 to N/4-1 in bit-reversed order for one bank of the first memory device, and wherein the bit-reversed address generator is configured to generate addresses for other banks of the first memory device by adding an address offset of N/K to a previous bank address, where N is the size of the FFT, and where K is the number of parallel inputs and outputs of the FFT logic.

10. The data processing device of claim 1 , wherein the second set of circular shift components include a set of read data multiplexers coupled between the first memory device and direct memory access (DMA) logic coupled to the second memory device.

11. The data processing device of claim 10 , wherein the set of read data multiplexers are configured to shift reads of FFT output samples from one of the plurality of banks of the first memory device to another of the plurality of banks of the first memory device at a predetermined rate to read FFT output samples for each digital input signal in order.

12. The data processing device of claim 11 , wherein the set of read data multiplexers are reconfigured at a predetermined rate equal to N/K read cycles, where N is the size of the FFT logic, and K is the number of parallel inputs and parallel outputs of the FFT logic.

13. The data processing device of claim 1 , wherein the first memory device has a capacity to store at least K FFT output size and has at least K banks, and wherein the second memory device has a capacity that is greater than or equal to first memory device, and where K is the number of parallel inputs and parallel outputs of the FFT logic.

14. The data processing device of claim 1 , wherein the data processing device further comprising image processing components, and wherein the data processing device performs multi-dimensional FFT operations of a multi-dimensional array.

15. The data processing device of claim 1 , wherein the data processing device is a stand-alone FFT engine.

16. The data processing device of claim 1 , further comprising direct memory access (DMA) logic configured to transfer data from the first memory device to the second memory after the combined bit-reversal and transpose operations, and wherein the DMA logic is also configured to transfer data from the second memory device to the FFT logic to perform multi-dimensional FFT operations.

17. An integrated circuit that comprises:
Fast Fourier Transform (FFT) logic configured to generate K FFT output samples at a time and N total FFT output samples for each of the plurality of digitized sense signals, wherein N is a multiple of K, and wherein K is an integer equal to at least 2;
a bit-reversed address generator configured to provide a bit-reversed address order;
a first set of circular shift components coupled to the bit-reversed address generator and configured to provide shifts when writing the N FFT output samples in the bit-reversed address order in a first memory device with K banks; and
a second set of circular shift components configured to perform shifts when reading the N FFT output samples in linear address order from a first memory device for storage in a second memory device, wherein the first and second set of circular shift components together are used to read FFT output samples in transpose order, and wherein at least some bit-reversal operations and some memory transpose operations are combined.

18. The integrated circuit of claim 17 , wherein the first set of circular shift components is configured to write the N FFT output samples for each of the plurality of digitized sense signals across the K banks so that each of the K banks stores some of the N FFT output samples for each of the plurality of digitized sense signals.

19. The integrated circuit of claim 17 wherein the second set of circular shift components are configured to read FFT output samples from the first memory device for storage in the second memory device such that FFT output samples corresponding to each of the digitized sense signals are read in sequential order from the K banks of the first memory device.

20. The integrated circuit of claim 17 , wherein the first set of circular shift components include a set of write data multiplexers coupled between the FFT logic and a first memory device, wherein the set of write data multiplexers are configured to write the K FFT output samples to one of the K banks of the first memory device before shifting writes to anothe

Assignees

• Texas Instruments Inc

Inventors

• Prathapan Indu
• Jayanthi Sai Ram Prakash

Classifications

• G06F13/287 Primary

  Multiplexed DMA (G06F13/30 takes precedence) · CPC title

• G06F17/142 Primary

  Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm · CPC title

• G06F7/768

  Data position reversal, e.g. bit reversal, byte swapping · CPC title