Algorithm and architecture yield fast FFTs - Embedded.com

Algorithm and architecture yield fast FFTs

Silicon Computing, Inc. has announced availability of an innovative algorithm and architecture for Fast Fourier Transforms (FFT). According to the company, this technology will allow cost effective implementation of devices for such as communication, medical imaging, computer vision, military, and aerospace applications.

Traditionally, 2-D FFT has been computed by applying 1-D FFT computations on rows(columns) and then columns(rows) sequentially. This approach requires a transpose memory buffer. Due to the sequential computation of row and column transforms, speed has been limited. In higher dimensional FFTs, the computation time and hardware complexity increases exponentially.

The new approach is based on a new multi-dimensional FFT algorithm that does not rely on 1-D FFT computations. As a result, no transpose memory buffer is required. This allows faster computation with smaller hardware complexity. As an example, in 2-D FFT computation of an MxM data array, only M2 clocks are required — the same as the number of data clocks.

This computational efficiency extends to N-dimensional (N-D) FFT requiring only MN clocks for an N-D array of size MxMx…xM. Silicon Computing claims that this technology achieves the lower limit of the FFT computational complexity in all dimensions.

The technology is available for licensing.

Silicon Computing, Inc.
Mountain View, CA
650-210-8651
www.silicon-computing.com

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.