Browse Prior Art Database

Pipeline Fast Fourier Transform Processor

IP.com Disclosure Number: IPCOM000079500D
Original Publication Date: 1973-Jul-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 3 page(s) / 35K

Publishing Venue

IBM

Related People

Dieffenderfer, JW: AUTHOR [+3]

Abstract

The Fast Fourier Transform (FFT) is a well-known technique for computing the finite fourier transform of a series of data points. Many special purpose machine architectures have been designed to implement the FFT algorithm. Among these are the Sequential Processor, the Pipeline (Cascade) Processor, the Parallel Iterative Processor, and the Array Analyzer.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 56% of the total text.

Page 1 of 3

Pipeline Fast Fourier Transform Processor

The Fast Fourier Transform (FFT) is a well-known technique for computing the finite fourier transform of a series of data points. Many special purpose machine architectures have been designed to implement the FFT algorithm. Among these are the Sequential Processor, the Pipeline (Cascade) Processor, the Parallel Iterative Processor, and the Array Analyzer.

One major drawback to the Pipeline Architecture has been the output occurring in bit-reversed order. A possible solution to this problem is a reordering network. Another possible solution is loading the bit reversed data into a random-access memory, and addressing the random-access memory in such a way so as to reorder the data to regular order.

Both of these methods require extra hardware (the reordering network or the random-access memory to perform the reordering.

A block diagram of the 16-sample pipeline FFT is shown and the concept of the process will be described using this diagram.

In the FFT Pass 16 samples of data (f0 to f15) are input to the processor two at a time, samples f0 to f7 are input at A, samples f8 to f15 are input at B. The answers come out in Bit Reversed Order (BRO).

The following chart shows the switch positions during the FFT Pass. In the chart N means Normal Position or the data goes straight through the switch, C means Crossed Position or the data crosses at the switch.

(Image Omitted)

The FFT operation is well documented in available literature and will not be described in detail here.

It is possible to take the FFT output, feed it back around to the input and stream the data through the pipeline (performing no arithmetic operations) and by proper switching reorder the data to regular order. The unscramble passes are shown in the following chart.

(Image Omitted)

Obviously the FFT Pass can be packed into the unscramble passes to form:

(Image Omitted)

This is a l6;sample case, 2/N/ = 16, N = 4. It takes 4 passes (8-time counts...