低复杂度混合基FFT研究与设计.doc

低复杂度混合基FFT研究与设计快速傅里叶变换（FastFourierTransform,FFT）算法是雷达微波探测、通信及图像等领域的核心处理算法，也是相关处理算法中运算量较大的部分。但针对合成孔径雷达（SyntheticApertureRadar,SAR）以及正交频分复用技术（OrthogonalFrequencyDivisionMultiplexing,OFDM）应用，现有FFT数字处理实现方法存在处理长度不灵活、处理器资源浪费严重、处理延迟大等问题。因此，研究资源节约、高时效的低复杂度混合基FFT设计技术具有重要的应用价值。本文通过对各种FFT算法进行分析比较，提出了低复杂度混合基FFT设计方法。首先研究了基本蝶形单元的硬件实现方法，在此基础上，研究了混合基FFT的低复杂度设计方法以及基于多存储结构的FFT设计方法。上述研究方法降低了FFT算法在数字电路中实现的复杂度，提高了FFT处理的实时性。主要工作和创新成果如下：1.作为混合基FFT的一种特例，有必要对固定基FFT进行研究。现有FFT实现方法通常采用补零方式来满足基-2或基-4FFT，该方法的不足之处在于浪费存储资源、计算时间长。针对这一问题，研究了基于单精度浮点运算的以基-3和基-5蝶形单元为代表的小面积基-rFFT设计方法。同时，为了减少占用的存储资源，在保证精度的前提下用定点格式来表示旋转因子，设计了一种有效的、高精度的乘法器，以达到定点存储旋转因子的目的。2.针对基-rFFT仅限于点数为r的幂次方的情况，提出了基于原位存储结构的混合基FFT设计。首先研究了基-r1/r2FFT数据访问地址的生成方案，该方法通过一个计数器来获得一种低复杂度的地址映射关系。进一步推导通用混合基，即基-r1/r2/.../rsFFT数据访问地址的产生方案。针对混合基FFT中蝶形单元种类增多的问题，推导出一种可配置的蝶形单元设计方法，解决了多种蝶形占用大量资源的问题。3.针对原位存储结构实时性差这一问题，研究了基于多存储结构的混合基FFT实现方法。在两种情况下进行了讨论：(a)单蝶形处理单元：给出了最优的存储器数目设置、优化的数据分配方法以及对多个存储空间的“并行&流水”访问方式；(b)多蝶形处理单元：研究了蝶形单元的数目设置以及对多个蝶形单元和多个存储空间的结构设计。该方案提高了混合基FFT的处理速度。