Pipelined, high-precision fast fourier transform processor

• US 6,081,821 A
• Filed: 08/05/1993
• Issued: 06/27/2000
• Est. Priority Date: 08/05/1993
• Status: Expired due to Term

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Mitre Corporation
• Inventors: Hopkinson, Thomas M., Butler, G. Michael
• Primary Examiner(s): MOISE, EMMANUEL LIONEL
• Application Number:
  US08/102,562
• Time in Patent Office: 2,518 Days
• Field of Search: 364/726, 364/725, 364/727, 708/403, 708/404, 708/405, 708/406, 708/408, 708/409
• US Class Current: 708/406
• CPC Class Codes: G06F 17/142 Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm

Abstract

The Fast Fourier Transform (FFT) processor includes a plurality of pipelined, functionally identical stages, each stage adapted to perform a portion of an FFT operation on a block of data. The output of the last stage of the processor is the high-precision Fast Fourier Transform of the data block. Support functions are included at each stage. Thus, each stage includes a computational element and a buffer memory interface. Each stage also includes apparatus for coefficient generation.

Claims

1. Fast fourier transform processor comprising a plurality of pipelined, functionally identical stages, each stage including only a single memory component and including means for providing coefficient and programmable memory address generation support functions necessary to perform a portion of a fast fourier transform operation on a block of data, the output of the processor being the fast fourier transform of the data block.

2. The processor of claim 1 wherein each stage includes a computational butterfly.

3. The processor of claim 2 wherein the computational butterfly is fully programmable.

4. The processor of claim 2 wherein the computational butterfly employs iterative multiplication.

5. The processor of claim 1 wherein the support function includes coefficient generation by recursive multiplication of the consecutive powers of a complex seed value.

6. The processor of claim 1 including log₆ N stages where r is the radix order and N is the number of samples.

7. The processor of claim 1 wherein each stage includes a buffer memory interface.

8. The processor of claim 7 wherein the buffer memory interface is an interface to static random access memory.