Optimized FFT/IFFT module

• US 7,333,422 B2
• Filed: 09/12/2003
• Issued: 02/19/2008
• Est. Priority Date: 09/12/2003
• Status: Active Grant

• Current Assignee: Zarbana Digital Fund LLC (Intellectual Ventures LLC)
• Original Assignee: Zarbana Digital Fund LLC (Intellectual Ventures LLC)
• Inventors: Amer, Maher
• Primary Examiner(s): Patel; Jay K.
• Assistant Examiner(s): HALIYUR, VENKATESH N
• Application Number:
  US10/662,063
• Publication Number:
  US 20050058059A1
• Time in Patent Office: 1,621 Days
• Field of Search: 370/310, 370/503, 370/319, 370204-211, 375/344, 375/355
• 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 to perform Fast Fourier Transform (FFT) and Inverse Fast Fourier Transform (IFFT) operations, the system comprising:

a first module to receive a plurality of inputs, said plurality of inputs being combined after first multiplicands are applied to each corresponding input;

a first multiplicand generator to provide said first multiplicands to said first module;

a first multiplier module to receive an output of said first module;

a second multiplicand generator to provide 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 to receive an output of said first multiplier module;

a third multiplicand generator to provide 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 to receive said output of said first multiplier module, said third multiplier module being configured to generate first and second outputs;

a fourth multiplicand generator to provide 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 to receive outputs of said multiplier modules and to apply multiplication factors to selected outputs of said multiplier modules, said map module having multiple outputs; and

an accumulation module to receive each of said multiple outputs of said map module, said accumulation module being configured to perform an accumulation task for each of said multiple outputs of said map module, said accumulation module having multiple outputs, where the multiple outputs of the accumulation module are one of an FFT and an IFFT of the plurality of inputs.

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 to perform an N-point FFT/IFFT operation, where N is an integer number of input samples, the system comprising:

an input module to receive a plurality of inputs in parallel and to combine said inputs after applying a multiplication factor to each of said inputs;

at least one multiplicand generator to provide multiplicands to said system;

at least two multiplier modules to perform complex multiplications, at least one of said multiplier modules being configured to receive an output of said input module, each of said multiplier modules being configured to receive multiplicands from said at least one multiplicand generator, at least one of said multiplier modules being configured to receive an output of another multiplier module;

a map module to receive outputs of all of said at least two multiplier modules, said map module to apply a multiplication factor to each of said outputs of said at least two multiplier modules, said map module being configured to generate multiple outputs; and

an accumulation module for to accumulate said multiple outputs of said map module, the accumulation module being configured to generate multiple outputs, where said multiple outputs of said accumulation module are one of an FFT and an IFFT of the plurality of inputs.

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 multiple outputs of said accumulation module 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 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 to provide said first set of multiplication factors to said first summing module;

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

a first multiplicand generator to provide 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 to receive an output of said first complex multiplier module;

a second multiplicand generator to provide 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 to receive said output of said first complex multiplier module, said third complex multiplier module to generate first and second outputs;

a third multiplicand generator to provide 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 to receive said outputs of said complex multiplier modules, said map module generating a plurality of outputs by applying a second set of multiplication factors to selected outputs of said complex multiplier modules; and

an accumulation module to receive said plurality of outputs from said map module, said accumulation module to generate a plurality of outputs by performing an accumulation task for each of said plurality of outputs from said map module, wherein said plurality of outnuts of said accumulation module are one of an FFT and an IFFT of the four inputs.

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 .