Multi-dimensional FFT computation pipelined hardware architecture using Radix-3 and Radix-22 butterflies

Patent metadata

Field	Value
Publication number	US-12045582-B2
Application number	US-202117351699-A
Country	US
Kind code	B2
Filing date	Jun 18, 2021
Priority date	Nov 17, 2020
Publication date	Jul 23, 2024
Grant date	Jul 23, 2024

Abstract

A Radix-3 butterfly circuit includes a first FIFO input configured to couple to a first FIFO. The circuit includes a first adder and first subtractor coupled to the first FIFO input, and a second FIFO input configured to couple to a second FIFO. The circuit includes a second adder and second subtractor coupled to the second FIFO input, and an input terminal coupled to the first adder and first subtractor. The circuit includes a first scaler coupled to the second adder and a first multiplexer, and a second scaler coupled to a third adder and second multiplexer. The circuit includes a third scaler coupled to a third subtractor and third multiplexer. An output of the first multiplexer is coupled to a complex multiplier. An output of the second multiplexer is coupled to a second FIFO output. An output of the third multiplexer is coupled to a first FIFO output.

First claim

What is claimed is:

1. A system, comprising:
a Radix-3 butterfly circuit, including:
a first first-in-first-out (FIFO) input configured to couple to a first FIFO;
a first adder and a first subtractor coupled to the first FIFO input;
a second FIFO input configured to couple to a second FIFO;
a second adder and a second subtractor coupled to the second FIFO input;
an input terminal coupled to the first adder and the first subtractor;
a first scaler coupled to the second adder and a first multiplexer;
a second scaler coupled to a third adder and a second multiplexer; and
a third scaler coupled to a third subtractor and a third multiplexer, wherein an output of the first multiplexer is coupled to a complex multiplier, an output of the second multiplexer is coupled to a second FIFO output that is configured to couple to the second FIFO, and an output of the third multiplexer is coupled to a first FIFO output that is configured to couple to the first FIFO.

2. The system of claim 1 , further comprising:
a state counter coupled to the first multiplexer, the second multiplexer, and the third multiplexer.

3. The system of claim 1 , further comprising:
a counter configured to provide an address for a twiddle lookup table.

4. The system of claim 3 , wherein the complex multiplier is configured to multiply an output sample from the first multiplexer with a weighting factor from the twiddle lookup table.

5. The system of claim 3 , further comprising:
a two-dimensional (2D) fast Fourier transform (FFT) converter configured to zero out a bit of the counter to perform a 2D FFT.

6. The system of claim 1 , wherein the input terminal is configured to receive an input sample for an FFT.

7. The system of claim 1 , wherein the complex multiplier is configured to output a sample to a next stage of an FFT architecture.

8. The system of claim 1 , wherein the Radix-3 butterfly circuit is coupled to a Radix-2 2 butterfly stage to perform 3×2 N point FFT.

9. The system of claim 8 , wherein the first FIFO is a FIFO of a first Radix-2 2 butterfly stage, and the second FIFO is a FIFO of a second Radix-2 2 butterfly stage.

10. A system, comprising:
a multi-dimensional Radix-2 2 butterfly architecture, including:
a first butterfly stage including:
a first first-in-first-out (FIFO) input configured to couple to a first FIFO;
a first adder and a first subtractor coupled to the first FIFO input;
an input terminal coupled to the first adder and the first subtractor;
a first multiplexer coupled to the first adder; and
a second multiplexer coupled to the first subtractor, wherein an output of the first multiplexer is coupled to a third multiplexer, and an output of the second multiplexer is coupled to a first FIFO output that is configured to couple to the first FIFO; and

a second butterfly stage including:
a second FIFO input configured to couple to a second FIFO;
a second adder and a second subtractor coupled to the second FIFO input;
an input terminal coupled to the second adder and the second subtractor;
a fourth multiplexer coupled to the second adder; and
a fifth multiplexer coupled to the second subtractor, wherein an output of the fourth multiplexer is coupled to a complex multiplier, and an output of the fifth multiplexer is coupled to a second FIFO output that is configured to couple to the second FIFO.

11. The system of claim 10 , further comprising:
a first counter coupled to the first multiplexer, the second multiplexer, and the third multiplexer; and
a second counter coupled to the fourth multiplexer and the fifth multiplexer.

12. The system of claim 11 , wherein the second counter is configured to provide an address for a twiddle lookup table.

13. The system of claim 12 , wherein the complex multiplier is configured to multiply an output sample from the fourth multiplexer with a weighting factor from the twiddle lookup table.

14. The system of claim 13 , further comprising:
a two-dimensional (2D) fast Fourier transform (FFT) converter configured to zero out a bit of the second counter to perform a 2D FFT.

15. The system of claim 13 , further comprising:
a Radix-2 converter configured to zero out a bit of the second counter to convert the second butterfly stage to a Radix-2 butterfly stage.

16. The system of claim 15 , wherein the multi-dimensional Radix-2 2 butterfly architecture is configured to perform an FFT greater than two dimensions by:
suppressing N least significant bits of the twiddle lookup table address, where N is a sum of lower dimension log 2 sizes; and
reconfiguring a butterfly stage to a Radix-2 butterfly stage at a stage transition.

17. A method, comprising:
receiving data samples at respective inputs of a Radix-3 butterfly stage that includes first and second multiplexers, the data samples including a new data sample, a first feedback data sample output by the first multiplexer based on processing of a previous data sample, and a second feedback data sample output by the second multiplexer based on processing of the previous data sample;
performing a 3-point fast Fourier transform (FFT) at the Radix-3 butterfly stage;
providing a first output data sample from the Radix-3 butterfly stage to a Radix-2 2 butterfly stage;
performing a 2-point butterfly operation and a twiddle multiplication on the first output data sample at the Radix-2 2 butterfly stage;
providing a second output data sample from the Radix-2 2 butterfly stage to a memory; and
providing a third output data sample from the Radix-2 2 butterfly stage to another Radix-2 2 butterfly stage.

18. The method of claim 17 , further comprising:
performing a bit reversal on an output data sample for a 3×2 N one-dimensional (1D) FFT or a 3.2 M ×2 N two-dimensional (2D) FFT.

19. The method of claim 17 , further comprising:
performing a window pre-multiplication with an unrolled 1D window before performing a 2D FFT.

20. The method of claim 17 , further comprising:
reconfiguring the Radix-3 butterfly stage to perform a two-dimensional (2D) FFT by zeroing a bit in a first counter in the Radix-3 butterfly stage;
reconfiguring the Radix-2 2 butterfly stage to perform a 2D FFT by zeroing a bit in a second counter in the Radix-2 2 butterfly stage; and
performing a 3.2 M ×2 N point FFT.

Assignees

• Texas Instruments Inc

Inventors

• Gupta Pankaj
• Subburaj Karthik
• Ramalingam Sujaata
• Ramasubramanian Karthik
• Prathapan Indu

Classifications

• G06F17/142

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

• G06F7/501

  Half or full adders, i.e. basic adder cells for one denomination · CPC title

• G06F17/144

  Prime factor Fourier transforms, e.g. Winograd transforms, number theoretic transforms · CPC title

• G06F7/49 Primary

  Computations with a radix, other than binary, 8, 16 or decimal, e.g. ternary, negative or imaginary radices, mixed radix {non-linear PCM (G06F7/4824 takes precedence)} · CPC title

• G06F7/5443 Primary

  Sum of products (for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00) · CPC title