- 相关推荐
基于FPGA的快速并行FFT及其在空间太阳望远镜图像锁定系统中的应
摘要：在空间太阳望远镜的在轨高速数据处理中，运算时间是影响系统性能的重要环节之一。利用FPGA丰富的逻辑单元实现快速傅里叶变换（FFT），解决 了在轨实时大数据量图像处理与航天级DSP运算速度不足之间的矛盾；利用溢出监测移位结构解决了定点运算的动态范围问题。经过实验验证，各项指标均达到了设计要求。空间太阳望远镜项目是我国太阳物理学家为了实现对太阳的高分辨率观测而提出的科学计划。它可以得到空间分辨率为0.1"的向量磁图和0.5"的X射线图像，实现这样高的观测精度的前提就是采用高精度的姿态控制系统和高精度的相关跟踪系统。从整个系统来看，相关运算所需的时间成为限制系统性能能否提高的一个重要环节。
目前，国际国内相关计算比较通用的实现方法有两种：用高速DSP或者专用（FFT）处理芯片。用DSP完成相关计算（关键是FFT）受到航天级DSP性能的限制，现有的航天级DSP（如ADSP21020）计算一个32×32点8bit的二维FFT所用时间需要1.5ms以上，远远不能满足系统设计要求；而现有的FFT处理芯片在处理速度、系统兼容性、抗辐射能力等方面不能满足空间太阳望远镜所提出的要求。
为克服这一矛盾，本文利用FPGA资源丰富、易于实现并行流水的特点设计专用的FFT处理芯片来完成复杂的、大量的数据处理；并通过在运算中作溢出监测来保证定点运算的精度，从而大大缩短系统的响应时间，将极大地提高空间太阳望远镜的在轨实时图像处理能力；同时由于FPGA具有抗辐射能力，可以提高系统的可靠性，其在航天遥测遥感和星载高速数据处理等方面将有广泛的应用前景。
1 算法构成
1.1 FFT算法选择
提高FFT速度的两个主要途径是采用流水结构和并行运算[1]。采用高基数结构也可以提高速度，只是用FPGA实现时必须综合考虑系统要求、结构特点及片内资源。针对本系统自身特点，这里按时间抽选算法进行分析。由于32不满足N=4m，所以32点FFT算法不能采用基-4 FFT运算。当详细分析基-2蝶形图时，有些蝶形运算并不需要做乘法，例如
等[2]；对于32点DIT-FFT，一共80个蝶形运算，这种结构就有46个，极大地降低了运算复杂度。在一维FFT计算效率提高的基础上对二维FFT采用最常用的行列算法[3]，综合各项指标本系统采用基-2 DIT行列算法。
1.2 算术运算方案
本系统是针对32×32点16bit的二维图像进行快速傅里叶变换（FFT），设计要求运算在0.5ms之内完成，所以采用定点运算更符合系统对时间的要求。对于定点运算，必须用定比例的方法防止溢出，即必须解决动态范围问题。下面对其进行理论分析：
若{x(n)}是-N点序列，其DFT为{X(K)}，由Parseval定理得[4]：
由式（1）可知变换结果的均方值是输入序列均方值的N倍。考虑基-2算法的第m级蝶形运算，用Xm(i)、Xm(j)表示原来的复数，则新的一对复数Xm 1(i)、Xm 1(j)为：
Xm 1(i)=Xm(i) Xm(j)×W (2)
Xm 1(j)=Xm(i)-Xm(j)×W
其中，W为旋转因子。首先，考虑复数的均方程根值。由（2）式可得：
因此，从均方根意义上看，数据（实数或复数）复级都增加（2的平方根）倍。其次，再考虑复数的最大模。由（2）式可以证明[5]。
max{|Xm(i)|,|Xm(j)|}≤max{|Xm 1(i)|,|Xm 1(j)|}≤2max{|Xm(i)|,|Xm(j)|}
因此，复数数组的最大模是非减的。所以，对于DITFFT，其每一级的蝶形运算之后数值都会增加1 (2的平方根)≈2.414倍。在每一次运算完成之后，须将结果右移2bits以满足要求。
2 系统实现
系统原理如图1所示，整个FFT运算处理单元分为三部分：存储单元（两个输入/运算存储器、一个输出存储器及旋转因子存储器）、蝶形运算单元、地址产生器。
2.1 存储器
本系统实时接收前端CCD相机的图像。为保证CCD相机采集图像的准确率，图像的每一行、每一帧之间都必须有一定的时间间隔,故采用两个存储单元作为输入数据和中间数据的暂存单元（如图1所示），以节省时间实现实时处理。当系统工作时，将图像存入存储器、计算上一次采集的图像、将存储器中的结果输出，这三个工作同时进行，用简单的流水方式减少存储数据所需的时间。旋转因子则预先存储在器件的内置ROM中。根据级数不同选用不同的因子。
2.2 蝶形运算单元
一个基-2蝶形运算由一个复乘和两个复加（减）组成，采用完全并行运算，进一步分解为四个实数乘法，六个实数加（减）法，分三级并行完成，加上前后输入输出的数据锁存，共需要6个时钟周期。32点的FFT需要16×5=80个基-2的蝶形运算，一幅图像一共是32行32列，不考虑不需要做乘法的蝶形
【基于FPGA的快速并行FFT及其在空间太阳望远镜图像锁定系统中的应】相关文章：
基于FPGA的快速傅立叶变换03-19
固定几何结构的FFT算法及其FPGA实现03-18
基于Cyclone系列FPGA的1024点FFT算法的实现03-07
基于FPGA的前端图像采集卡的设计11-22
基于图像处理的数字测色系统03-07