摘要 |
An apparatus and method for performing Fourier transformations on an input stream of digital data without switches in the cross channel communication paths. A new systolic method for performing a Fast Fourier Transform (FFT) is derived from a constant geometry method using phase shifting of data in a channel to obtain the proper data sequence, rather than switches to transfer data among channels. A standard global shuffle operator is decomposed into phase shift operators and random access memory shuffle operators that operate only in one channel. The result is further simplified by merging the phase shift operators with twiddle factors from the constant geometry method. The communications paths for the data are thereby fixed, creating the opportunity for higher radix operations than are available with devices employing switches for cross channel data transfer.
|