SBIR Phase I: A New Class of Fast Fourier Transforms

该小型企业创新研究(SBIR)第一阶段研究项目旨在开发一种高性能、参数化的快速傅立叶变换(FFT)电路，该电路将作为知识产权产品出售，用于ASIC和FPGA嵌入式信号处理应用。在过去40年中，并行FFT实现相对保持不变，基本上基于信号流图及其映射的不同排列。因此，信号流图的内在不规则性反映在复杂的换向器或置换电路、大的蝶形单元、全局互连以及当今FFT中的级到级的差异中，并导致固有的僵化和缺乏性能。基于离散傅里叶变换(DFT)的一种新的矩阵形式，提出了一种完全不同的并行FFT实现方法，该方法将离散傅里叶变换分解成无乘法的4点DFT的结构化集合。因此，(1)实现简单、本地连接和结构化，从而允许更低的功耗和更高的性能映射到现代的FPGA和ASIC；(2)固有的可扩展性显著增加了功能和灵活性；以及(3)保持了良好的算术效率。提出的研究计划将通过适当的分析、建模、电路设计和FPGA实现来验证这些说法。DFT出现在大量的实时信号处理、通信、雷达、声学和电磁应用中，可以说是所有信号处理算法中最突出的。因此，功能更强大、更灵活、性能更高的FFT的可用性将显著提高一系列电子产品的效能。这种新的FFT技术的好处将最适合无线设备，无线设备是电子产品最大、增长最快的市场。未来的4G协议将基于正交频分复用(Ofdm)和可伸缩的正交频分多址(OFDMA)，这是利用FFT的数字调制方案。因此，未来的大多数无线通信设备将使用嵌入式FFT电路。然而，今天的FFT技术不具备满足未来无线协议需求所需的综合吞吐量、功能性、灵活性和低功耗。拟议的第一阶段研究将展示一种能够满足未来无线协议的所有计算需求的FFT电路架构。

This Small Business Innovation Research (SBIR) Phase I research project is directed at development of a high performance, parameterized fast Fourier transform (FFT) circuit that will be sold as an intellectual property product to be used in ASIC and FPGA embedded signal processing applications. For the past 40 years parallel FFT implementations have remained relatively unchanged, being based essentially on different permutations of the signal flow graph and mappings thereof. Consequently, the inherent irregularities of the signal flow graph are reflected in the complex commutators or permutation circuits, large butterfly units, global interconnections, and stage-to-stage differences seen in today's FFTs and result in an inherent inflexibility and lack of performance. A radically different approach to parallel FFT implementation is proposed here based on a new matrix formulation of the discreet Fourier transform (DFT) which decomposes it into structured sets of multiplication-free 4-point DFTs. As a result, (1) implementations are simple, locally connected and structured, thereby allowing lower power and higher performance mappings to modern FPGAs and ASICs; (2) significant added functionality and flexibility accrues from the inherent scalability; and (3) good arithmetic efficiency is retained. The proposed research plan will validate these claims by appropriate analysis, modeling, circuit designs, and FPGA implementations.The DFT appears throughout a large number of real-time signal processing, communications, radar, acoustics, and electromagnetic applications and is arguably the most prominent of all signal processing algorithms. Consequently, the availability of more functional, flexible, 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 wireless devices, the largest and fastest growing market for electronic products. Future 4G protocols will be based on orthogonal frequency division multiplexing (OFDM) and scalable orthogonal frequency division multiple access (OFDMA), which are digital modulation schemes that make use of the FFT. Consequently, most wireless communication devices of the future will use embedded FFT circuitry. However, today's FFT technology does not possess the combined throughput, functionality, flexibility and low power necessary to meet the needs of future wireless protocols. The proposed Phase I research will demonstrate an FFT circuit architecture that can meet all the computational demands of future wireless protocols.