SBIR Phase II: A New Class of Fast Fourier Transforms

This Small Business Innovation Research (SBIR) Phase II project is directed at development of a high performance, programmable fast Fourier transform (FFT) circuit for use in embedded signal processing integrated circuits. Over the last 40 years the technology for executing parallel FFT implementations has remained relatively unchanged, being based essentially on different permutations of the signal flow graph and mappings thereof. Performance improvements are now largely achieved by shrinking circuit geometries according to Moore's Law. Because of the limits imposed by physics of integrated circuit fabrication, it is expected that continued improvement in signal processing will only be achieved with more efficient algorithmic implementations in combination with advanced integrated circuit technologies. This proposal focusses on a radically different architecture for parallel FFT circuits based on a new matrix formulation of the discrete Fourier transform (DFT) to achieve exactly this goal. The specific advantages of this new formulation include: 1) logic and memory resource requirements are reduced; 2) less power is consumed; 3) significant added functionality is accrued; and 4) design, test, and maintenance efforts are diminished because the circuits are simple, locally connected and structured. The outcomes of this project is a commercial quality FFT circuit based on the feasibility prototypes developed during SBIR Phase I. The DFT sub-system is a critical and important component of large number of real-time communications, radar, medical, acoustics, navigation, surveillance, remote sensing, and robotic inspection applications and is arguably the most prominent of all signal processing algorithms. Consequently, the availability of more functional, efficient, and higher performance FFTs will significantly improve the efficacy of a host of electronic products. The benefits of this new FFT technology would be best suited to mobile wireless devices, the largest and fastest growing market for electronic products, because future 4G wireless protocols will be based on orthogonal frequency division multiplexing, which is a scheme that makes use of the FFT. Consequently, most wireless devices of the future will use embedded FFT circuitry. However, the computational demands to support 4G communication requirements will increase by a factor of ~10 compared to today's wireless mobile devices. Therefore, more efficient integrated circuit implementations of FFTs will be required to continue to keep the cost and power usage of mobile appliances low.