Optimized FFT/IFFT module

• US 20050058059A1
• Filed: 09/12/2003
• Published: 03/17/2005
• Est. Priority Date: 09/12/2003
• Status: Active Grant

• Current Assignee: Zarbana Digital Fund LLC (Intellectual Ventures LLC)
• Original Assignee: Seven Generations Energy Ltd.
• Inventors: Amer, Maher
• Granted Patent: US 7,333,422 B2
• Time in Patent Office: Days
• US Class Current: 370/210
• CPC Class Codes: G06F 17/142 Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm
• CPC Class Codes: H04L 27/263 modification of IFFT/IDFT modulator for performance improvement
• CPC Class Codes: H04L 27/2651 Modification of fast Fourier transform [FFT] or discrete Fourier transform [DFT] demodulators for performance improvement

Abstract

The present invention discloses an optimal hardware implementation of the FFT/IFFT operation that minimizes the number of clock cycles required to compute the FFT/IFFT while at the same time minimizing the number of complex multipliers needed. For performing an N-point FFT/IFFT operation in N clock cycles, the optimal hardware implementation consists of several modules. An input module receives a plurality of inputs in parallel and combines the inputs after applying a multiplication factor to each of the inputs. At least one multiplicand generator is used to provide multiplicands to the system. At least two complex multiplier modules for performing complex multiplications are required with at least one of the complex multiplier modules receiving an output from the input module. Each of the complex multiplier modules receives multiplicands from the at least one multiplicand generator. Furthermore, at least one of the complex multiplier modules receives an output of another complex multiplier module. A map module is provided for receiving outputs of the at least two complex multiplier modules, the map module selecting and applying a multiplication factor to each of the outputs received to generate multiple outputs. Finally, an accumulation module receives and performs an accumulation task on each of the multiple outputs of the map module thereby generating a corresponding number of multiple outputs. In a preferred embodiment, the N-point FFT/IFFT operation is performed in N clock cycles using $\left(\frac{N}{32}+1\right)$complex multipliers. In a specific implementation, a system comprising 3 complex multipliers is used to compute a 64-point FFT/IFFT operation in 64 clock cycles. Advantageously, the total number of clock cycles required to complete the FFT/IFFT operation is minimized while at the same time minimizing the number of complex multipliers needed.

Claims

1. A system for performing Fast Fourier Transform (FFT)/Inverse Fast Fourier Transform (IFFT) operations, the system comprising:

a first module for receiving a plurality of inputs, said plurality of inputs being combined after a first multiplicand is applied to each input;

a first multiplicand generator for providing said first multiplicands to said first module;

a first multiplier module for receiving an output of said first module;

a second multiplicand generator for providing a second multiplicand to said first multiplier module, said second multiplicand being applied to said output of said first module by said first multiplier module;

a second multiplier module for receiving an output of said first multiplier module;

a third multiplicand generator for providing a third multiplicand to said second multiplier module, said third multiplicand being applied to said output of said first multiplier module by said second multiplier module;

a third multiplier module for receiving said output of said first multiplier module, said third multiplier module generating first and second outputs;

a fourth multiplicand generator for providing a fourth multiplicand to said third multiplier module, said fourth multiplicand being applied to said output of said first multiplier module by said third multiplier module to generate said first output of said third multiplier module, an image of said fourth multiplicand being applied to said output of said first multiplier module by said third multiplier module to generate said second output of said third multiplier module;

a map module for receiving outputs of said multiplier modules and for selecting and applying multiplication factors to selected outputs of said multiplier modules, said map module having multiple outputs; and

an accumulation module for receiving each of said multiple outputs of said map module, said accumulation module performing an accumulation task for each of said multiple outputs of said map module.

2. A system according to claim 1 wherein said first multiplicand generator comprises a look-up table (LUT).

3. A system according to claim 1 wherein said first multiplicand generator comprises a truth table.

4. A system according to claim 1 wherein said first multiplicands are chosen from the set comprising +1, −

1, +j or −

j.

5. A system according to claim 1 wherein said second multiplicand generator comprises a look-up table (LUT).

6. A system according to claim 1 wherein said third multiplicand is

$e^{}$

j8π

32 .

7. A system according to claim 1 wherein said fourth multiplicand is

$e^{}$

j4π

32 .

8. A system according to claim 1 wherein said image of said fourth multiplicand is

$e^{}$

j12π

32 .

9. A system according to claim 1 wherein said multiplication factors applied by said map module to selected outputs of said multiplier modules is chosen from the set comprising +1, −

1, +j or −

j.

10. A system for performing an N-point FFT/IFFT operation, where N is the number of the input samples, the system comprising:

an input module for receiving a plurality of inputs in parallel and for combining said inputs after applying a multiplication factor to each of said inputs;

at least one multiplicand generator for providing multiplicands to said system;

at least two multiplier modules for performing complex multiplications, at least one of said multiplier modules receiving an output of said input module, each of said multiplier modules receiving multiplicands from said at least one multiplicand generator, at least one of said multiplier modules receiving an output of another multiplier module;

a map module for receiving outputs of all of said at least two multiplier modules, said map module selecting and applying a multiplication factor to each of said outputs of said at least two multiplier modules, said map module generating multiple outputs; and

an accumulation module for receiving and accumulating said multiple outputs of said map module.

11. A system according to claim 10 wherein said at least two multiplier modules comprises

$\frac{N}{32}+1$

multiplier modules.

12. A system according to claim 10 wherein the N-point FFT/IFFT operation is completed in N clock cycles.

13. A system according to claim 10 wherein said accumulation module generates multiple outputs corresponding to said multiple outputs received from said map module.

14. A system according to claim 10 wherein said at least one multiplicand generator comprises at least one look-up table (LUT).

15. A system according to claim 10 wherein said at least one multiplicand generator comprises at least one truth table.

25. A system according to claim 13 wherein said second set of multiplication factors applied by said map module to selected outputs of said complex multiplier modules is chosen from the set comprising +1, −

1, +j or −

j.

16. A system for performing Fast Fourier Transform/Inverse Fast Fourier Transform (FFT/IFFT) operations, the system comprising:

a first summing module adapted to receive four inputs, said first summing module generating an output by combining said four inputs after applying a first set of multiplication factors to said four inputs;

a first storage means for providing said first set of multiplication factors to said first summing module;

a first complex multiplier module adapted to receive said output of said first summing module;

a first multiplicand generator for providing a first multiplicand to said first complex multiplier module, said first multiplicand being applied to said output of said first summing module by said first complex multiplier module;

a second complex multiplier module for receiving an output of said first complex multiplier module;

a second multiplicand generator for providing a second multiplicand to said second complex multiplier module, said second multiplicand being applied to said output of said first complex multiplier module by said second multiplier module;

a third complex multiplier module for receiving said output of said first complex multiplier module, said third complex multiplier module generating first and second outputs;

a third multiplicand generator for providing a third multiplicand to said third complex multiplier module, said third multiplicand being applied to said output of said first complex multiplier module by said third complex multiplier module to generate said first output of said third multiplier module, an image of said third multiplicand being applied to said output of said first complex multiplier module by said third complex multiplier module to generate said second output of said third complex multiplier module;

a map module for receiving said outputs of said complex multiplier modules, said map module generating a plurality of outputs by selecting and applying a second set of multiplication factors to selected outputs of said complex multiplier modules; and

an accumulation module for receiving said plurality of outputs from said map module, said accumulation module generating a plurality of outputs by performing an accumulation task for each of said plurality of outputs from said map module.

17. A system according to claim 16 wherein said first set of multiplication factors is chosen from the set comprising +1, −

1, +j or −

j.

18. A system according to claim 16 wherein said first storage means comprises a look-up table (LUT).

19. A system according to claim 16 wherein said first storage means comprises a truth table.

20. A system according to claim 16 wherein said first multiplicand generator comprises a look-up table (LUT).

21. A system according to claim 16 wherein first multiplicand generator comprises a truth table.

22. A system according to claim 16 wherein said second multiplicand is

$e^{}$

j8π

32 .

23. A system according to claim 16 wherein said third multiplicand is

$e^{}$

j4π

32 .

24. A system according to claim 16 wherein said image of said third multiplicand is

$e^{}$

j12π

32 .