US 5,293,330 A · Pipeline processor for mixed-size FFTs

Abstract

A method is described for performing fast Fourier transforms (FFTs) of various sizes simultaneously in one pipeline processor. The processor consists of several stages of butterfly computational elements alternated with delay-switch-delay (DSD) modules that reorder the data between the butterfly stages. The sequence of the DSD operations in the pipeline is made arbitrary. This flexibility in choosing the DSD sequence enhances the fault tolerance operation of the pipeline in case of a partial failure in one or more of the DSD modules. If one of the DSDs is no longer capable of operating in its prescribed mode, it is assigned a different operating mode. All the required changes are performed by software control without the need to physically remove or interchange any components. By properly ordering the input data to the pipeline and the butterfly twiddle factors, and by bypassing some butterfly elements for the smaller size transforms, it is shown that any mixture of FFT sizes can be performed. FFTs of radix 2, radix 4, and mixed 2 and 4 are considered. In each case, the principles of operation are explained and examples of timing diagrams are given.

Claims15

Dependent claims

A method for performing on an input signal fast Fourier transforms or inverse fast Fourier transforms of multiple sizes simultaneously in a single pipeline with multiple stages, said method comprising the steps of:

providing a Fourier transform processor comprising a plurality of stages, each of said stages comprising a butterfly computational element and a switch-delay-switch element;
storing an input data stream in memory as data samples;
calculating a new order in which data samples from said stored input data are to be combined for processing by the pipeline in accordance with a number of said stages actively operating on said data samples and in accordance with a configuration of said switch-delay-switch elements;
writing said data samples to a first stage of the pipeline in said new order;
and
processing said data samples through said multiple stages of said pipeline, while bypassing selected ones of said stages when a number of said data samples stored in said memory is less than an predetermined maximum number.

3 more elements

An apparatus for performing on an input signal mixed size fast Fourier transforms (FFT) or inverse fast Fourier transforms (IFFT) simultaneously in a single pipeline structure having multiple stages, said apparatus comprising:

a memory for storing an input data stream in a first order as data samples;
a multiple-stage FFT/IFFT pipeline processor for performing fast Fourier transforms and inverse fast Fourier transforms, each stage of said pipeline processor comprising a butterfly computational element for performing predetermined mathematical operations on data samples applied thereto, and a delay-switch-delay circuit for selectively delaying and ordering data samples operated upon by said butterfly computational element, a first stage of said pipeline processor receiving reordered data samples from said memory;
a controller for calculating a new order in which the data samples are written from memory to the pipeline for controlling said delay-switch-delay elements to select a delay time and data sample order set thereby, and for bypassing selected ones of said stages when a size of said data stream is less than a predetermined value, said new order being determined in accordance with a number of stages actively operating upon said data samples and with delay times and data sample orders set by said delay-switch-delay elements, wherein a single said apparatus can perform Fourier transforms on data streams of different sizes.

Dependencies are inferred from the claim text.

Pipeline processor for mixed-size FFTs

Life of this patent

Pipeline processor for mixed-size FFTs

Life of this patent

Abstract

Claims15