Power and area efficient fast fourier transform processor

• US 6,061,705 A
• Filed: 01/21/1998
• Issued: 05/09/2000
• Est. Priority Date: 01/21/1998
• Status: Expired due to Term

• Current Assignee: Wi-Fi One, LLC (Inception Holdings, LLC)
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Hellberg, Richard
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US09/010,130
• Time in Patent Office: 839 Days
• Field of Search: 708/403-409
• US Class Current: 708/408
• CPC Class Codes: G06F 17/142 Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm

Abstract

A fast Fourier transform (FFT) processor is constructed using discrete Fourier transform (DFT) butterfly modules having, in preferred example embodiments, sizes greater than 4. In a first example embodiment, the FFT processor employs size-8 butterflies. In a second example embodiment, the FFT processor employs size-16 butterflies. In addition, low power, fixed coefficient multipliers are employed to perform nontrivial twiddle factor multiplications in each butterfly module. The number of different, nontrivial twiddle factor multipliers is reduced by separating trivial and nontrivial twiddle factors and by taking advantage of twiddle factor symmetries in the complex plane and/or twiddle factor decomposition. In accordance with these and other factors, the present invention permits construction of an FFT processor with minimal power and IC chip surface area consumption.

Claims

1. A fast Fourier transform (FFT processor formed using minimal integrated circuit chip area for efficiently performing low power fast Fourier transform operations, comprising:

one or more butterfly modules having a radix greater than four, at least one butterfly module including a fixed coefficient multiplier circuit for performing a twiddle factor multiplication,

wherein an input data stream is processed by the one or more butterfly modules to generate a transformed output data sequence.

2. The FFT processor in claim 1, wherein the radix of each butterfly module is eight.

3. The FFT processor in claim 2, wherein all of the nontrivial twiddle factor multiplications in each 8-point butterfly module are implemented using only one fixed coefficient multiplier circuit.

4. The FFT processor in claim 3, wherein the one fixed coefficient multiplier circuit includes:

real and imaginary component multipliers with the output of the real component multiplier added in a first adder to the output of the imaginary component multiplier and the real multiplier output subtracted in a second adder from the imaginary multiplier output.

5. The FFT processor in claim 1, wherein the radix of each butterfly module is sixteen.

6. The FFT processor in claim 3, wherein the 16-point butterfly module employs two fixed coefficient multiplier circuits to perform all nontrivial twiddle factor multiplications.

7. The EFT processor in claim 6, wherein the two fixed coefficient multiplier circuits in each 16-point DFT module including:

a first fixed coefficient multiplier circuit having real and imaginary component multipliers, with the output of the real component multiplier added in a first adder to the output of the imaginary component multiplier and the real multiplier output subtracted in a second adder from the imaginary multiplier output, and

a second fixed coefficient multiplier circuit having real and imaginary shifters shifted to a first state for one twiddle factor multiplication and to a second state for another twiddle factor multiplication.

8. The FFT processor in claim 1, wherein twiddle factor multiplications include nontrivial multiplications and trivial multiplications, and wherein nontrivial multiplications are performed using fixed coefficient multipliers.

9. The FFT processor in claim 4, wherein the trivial multiplications are performed without multipliers, by performing no operation, making a sign change, or shifting real and imaginary components.

10. The FFT processor in claim 4, wherein different nontrivial twiddle factor value multiplications are performed using the same fixed coefficient multiplier circuitry.

11. The FFT processor in claim 8, wherein at least one nontrivial twiddle factor is decomposed into two component twiddle factors to reduce the number of different nontrivial twiddle factor values.

12. The FFT processor in claim 8, wherein a symmetrical relationship between at least two nontrivial twiddle factors is used to reduce the number of different nontrivial twiddle factor values.

13. A method for computing a fast Fourier transform (FFT) with an FFT processor formed using minimal integrated circuit chip area to efficiently perform fast Fourier transform operations with reduced power, comprising the steps of:

constructing the FFT processor with plural processing modules having a radix greater than four, each processing module including a fixed coefficient multiplier for performing a twiddle factor multiplication, and

processing an input data stream in each processing module to generate a transformed output data sequence.

14. The method in claim 13, wherein the radix of each processing module is eight.

15. The method in claim 14, further comprising:

implementing all of the nontrivial twiddle factor multiplications in each 8-point processing module using only one fixed coefficient multiplier circuit to perform all nontrivial twiddle factor multiplications in each 8-point processing module.

16. The method in claim 13, wherein the radix of each processing module is sixteen.

17. The method in claim 16, further comprising:

implementing all of the nontrivial twiddle factor multiplications in each 16-point processing module using only two fixed coefficient multiplier circuits to perform all nontrivial twiddle factor multiplications in each 16-point processing module.

18. The method in claim 13, further comprising:

separating twiddle factor multiplications in each processing module into nontrivial multiplications and trivial multiplications, and

performing the nontrivial multiplications using one or more fixed coefficient multipliers.

19. The method in claim 18, wherein the trivial multiplications are performed without multipliers, either by performing no operation, mating a sign change, or shifting real and imaginary components.

20. The method in claim 18, further comprising:

performing different nontrivial twiddle factor value multiplications in each processing module using fixed coefficient multiplier circuitry corresponding to each different nontrivial twiddle factor value multiplication.

21. The method in claim 18, further comprising:

performing different nontrivial twiddle factor value multiplications in each processing module using the same fixed coefficient multiplier circuitry.

22. The method in claim 18, further comprising:

decomposing at least one nontrivial twiddle factor into two component twiddle factors to reduce the number of different nontrivial twiddle factor values.

23. The method in claim 18, further comprising:

using a symmetrical relationship between at least two nontrivial twiddle factors to reduce the number of different nontrivial twiddle factor values.

24. A fast Fourier transform (FFT) processor formed using minimal integrated circuit chip area for efficiently performing low power fast Fourier transform operations, comprising:

one or more discrete Fourier transfer (DFT) modules, each DFT module having three, 2-point butterfly units coupled together, and

one or more twiddle factor multipliers implemented using a fixed coefficient multiplier circuit linking two of the 2-point butterfly units,

wherein an input data stream is processed by the three butterfly units to generate a transformed output data sequence.

25. The FFT processor in claim 24, wherein the FFT processor is pipelined with a pipeline register located between each butterfly unit, and each 2-point butterfly unit includes a feedback path between an output therefrom to and an input thereto.

26. The FFT processor in claim 25, wherein the feedback path is a single delay feedback path, and wherein each DFT module includes three feedback registers each accommodating different size feedback sequences.

27. The FFT processor in claim 26, wherein DFT modules are connected to a twiddle factor memory through a dynamic multiplier such that the output from one of the butterfly modules is multiplied by twiddle factors retrieved from the twiddle factor memory in the dynamic multiplier before being processed in the adjacent DFT module.

28. The FFT processor in claim 24, wherein trivial twiddle factor multiplications are performed without using multiplier circuitry.

29. The FFT processor in claim 28, wherein trivial twiddle factor multiplications are performed using no operation, sign change operation, or a real and imaginary component swapping operations.

30. The FFT processor in claim 24, wherein the fixed coefficient multiplier circuit includes real and imaginary component multipliers with the output of the real multiplier added in a first adder to the output of the imaginary multiplier and with the real output subtracted in a second adder from the imaginary output.

31. The FFT processor in claim 24, wherein the same fixed coefficient multiplier circuit is used to perform all nontrivial twiddle factor multiplications to be performed in each DFT module.

32. A fast Fourier transform (FFT) processor formed using minimal integrated circuit chip area for efficiently performing low power fast Fourier transform operations, comprising:

one or more discrete Fourier transform (DFT) modules, each DFT module having four, 2-point butterfly units coupled together, and

one or more twiddle factor multipliers implemented using a fixed coefficient multiplier circuit linking at least two of the 2-point butterfly units,

wherein an input data stream is processed by the three butterfly units to generate a transformed output data sequence.

33. The FFT processor in claim 32, wherein the FFT processor is pipelined with a pipeline register located between each butterfly unit, and each 2-point butterfly unit includes a feedback path between an output therefrom to and an input thereto.

34. The FFT processor in claim 33, wherein the feedback is a single delay feedback path, and wherein each DFT module includes four feedback registers each accommodating different size feedback sequences.

35. The FFT processor in claim 32, wherein trivial twiddle factor multiplications are performed without using multiplier circuitry.

36. The FFT processor in claim 35, wherein trivial twiddle factor multiplications are performed using no operation, a sign change operation, or a real and imaginary component swapping operations.

37. The FFT processor in claim 32, wherein a first fixed coefficient multiplier circuit includes first real and imaginary component multipliers with the output of the first real multiplier added in a first adder to the output of the first imaginary multiplier and with the real multiplier output subtracted in a second adder from the imaginary multiplier output.

38. The FFT processor in claim 37, wherein a second fixed coefficient multiplier circuit includes real and imaginary component shifters, the shifters being shifted to a first state for one twiddle factor multiplication and to a second state for another twiddle factor multiplication.

39. The FFT processor in claim 38, wherein the first and second fixed multiplier circuits are used to perform all nontrivial twiddle factor multiplications to be performed in each DFT module.

40. A method for computing a fast Fourier transform (FFT) with an FFT processor formed using minimal integrated circuit chip area to efficiently perform fast Fourier transform operations with reduced power, comprising the steps of:

constructing the FFT processor with one or more processing modules, each processing module implementing three, 2-point butterfly units coupled together in pipeline fashion and at least two of the butterfly units linked by a fixed coefficient multiplier circuit;

applying an input data stream to an input of a first one of the three butterfly units and processing the input data stream;

processing an output of the first butterfly unit in a second one of the three butterfly units; and

processing an output of the second butterfly unit in a third one of the three butterfly units to generate an output data sequence.

41. The method in claim 40, further comprising:

performing different nontrivial twiddle multiplications using the same fixed coefficient multiplier circuit.

42. The method in claim 41, wherein all nontrivial twiddle factor multiplications for each processing module are performed using the fixed coefficient multiplier circuit.

43. A method for computing a fast Fourier transform (FFT) with an FFT processor formed using minimal integrated circuit chip area to efficiently perform fast Fourier transform operations with reduced power, comprising the steps of:

constructing the FFT processor with one or more processing modules, each processing module having four, 2-point butterfly units coupled together in pipeline fashion with at least two of the 2-point butterfly units linked by a fixed coefficient multiplier circuit;

applying an input data stream to an input of a first one of the four butterfly units and processing the input data stream;

processing an output of the first butterfly unit in a second one of the four butterfly units;

processing an output of the second butterfly unit in a third one of the four butterfly units; and

processing an output of the second butterfly unit in a fourth one of the four butterfly units to generate an output data sequence.

44. The method in claim 43, further comprising:

performing different, nontrivial multiplications using the same fixed coefficient multiplier circuit.

45. The method in claim 43, wherein all nontrivial twiddle factor multiplications for each processing module are performed using two fixed coefficient multiplier circuits.