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

发布时间：2018-01-22 09:38

本文关键词： 混合基FFT 低复杂度可配置蝶形单元实时性并行流水　出处：《北京理工大学》2014年博士论文　论文类型：学位论文

【摘要】：快速傅里叶变换（Fast Fourier Transform, FFT）算法是雷达微波探测、通信及图像等领域的核心处理算法，也是相关处理算法中运算量较大的部分。但针对合成孔径雷达（Synthetic Aperture Radar, SAR）以及正交频分复用技术（Orthogonal FrequencyDivision Multiplexing, 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的处理速度。
[Abstract]:Fast Fourier transform (FFTT) algorithm is the core processing algorithm of radar microwave detection, communication and image. It is also a part of the correlation processing algorithm, but it is aimed at synthetic Aperture Radar of synthetic Aperture Radar (SAR). And orthogonal FrequencyDivision Multiplexing (OFDM). The existing implementation methods of FFT digital processing have some problems, such as processing length is not flexible, processor resource is wasted seriously, processing delay is large, and so on. High-aging and low-complexity hybrid FFT design technology has important application value. This paper analyzes and compares various FFT algorithms. A low complexity hybrid base FFT design method is proposed. Firstly, the hardware implementation method of the basic butterfly unit is studied. The low complexity design method of hybrid base FFT and the design method of FFT based on multi-storage structure are studied. These methods reduce the complexity of FFT algorithm in digital circuits. The real-time performance of FFT processing is improved. The main work and innovative results are as follows: 1. As a special case of mixed radix FFT, it is necessary to study fixed base FFT, which is usually implemented by adding zero to satisfy radix-2 or radix-4FFT. The disadvantage of this method is that it wastes storage resources and takes a long time to calculate. This paper studies the design method of small area radix-rFFT based on single-precision floating-point operation, which is represented by radix--3 and radix-5 butterfly units. At the same time, in order to reduce the consumption of storage resources. On the premise of ensuring precision, the rotation factor is represented by fixed point format, and an effective and high precision multiplier is designed to store rotation factor at fixed point. 2. For the case that radix-rFFT is limited to the power power of the point r. A hybrid base FFT design based on in-situ storage structure is proposed. Firstly, the data access address generation scheme of radix-r-1 / r2FFT is studied. In this method, a low complexity address mapping relation is obtained by a counter, and the general mixed basis is further derived. In order to solve the problem of increasing the types of butterfly units in mixed radix FFT, a configurable design method of butterfly units is derived. It solves the problem that many kinds of butterfly take up a lot of resources. 3. Aiming at the problem of poor real-time performance of in-situ storage structure. In this paper, a hybrid base FFT implementation method based on multi-memory structure is studied. In two cases, the single butterfly processing unit is discussed: the optimal memory number setting is given. Optimized data allocation method and "parallel income" access to multiple storage spaces; (B) Multi-butterfly processing units: the number of butterfly units and the structural design of multiple butterfly cells and multiple storage spaces are studied. This scheme improves the processing speed of mixed base FFT.
【学位授予单位】：北京理工大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TN911.7

【参考文献】