SBIR Phase I: A New Class of Fast Fourier Transforms

SBIR 第一阶段：新型快速傅里叶变换

• 批准号: 0711638
• 负责人: J Greg Nash
• 金额: $ 9.98万
• 依托单位: Centar
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-07-01 至 2007-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0711638&HistoricalAwards=false
• 关键词: SBIR; Phase; New; Class; Fast

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.

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