基于FPGA的快速并行FFT及其在空间太阳望远镜图像锁定系统中的应用

出处：力博发布于：2007-05-25 15:01:33

空间太阳望远镜项目是我国太阳物理学家为了实现对太阳的高分辨率观测而提出的科学计划。它可以得到空间分辨率为０．１″的向量磁图和０．５″的Ｘ射线图像，实现这样高的观测的前提就是采用高的姿态控制系统和高的相关跟踪系统。从整个系统来看，相关运算所需的时间成为限制系统性能能否提高的一个重要环节。

目前，国际国内相关计算比较通用的实现方法有两种：用高速ＤＳＰ或者专用（ＦＦＴ）处理芯片。用ＤＳＰ完成相关计算（关键是ＦＦＴ）受到航天级ＤＳＰ性能的限制，现有的航天级ＤＳＰ（如ＡＤＳＰ２１０２０ADSP21020）计算一个３２×３２点８ｂｉｔ的二维ＦＦＴ所用时间需要１．５ｍｓ以上，远远不能满足系统设计要求；而现有的ＦＦＴ处理芯片在处理速度、系统兼容性、抗辐射能力等方面不能满足空间太阳望远镜所提出的要求。

为克服这一矛盾，本文利用ＦＰＧＡ资源丰富、易于实现并行流水的特点设计专用的ＦＦＴ处理芯片来完成复杂的、大量的数据处理；并通过在运算中作溢出监测来保证定点运算的，从而大大缩短系统的响应时间，将极大地提高空间太阳望远镜的在轨实时图像处理能力；同时由于ＦＰＧＡ具有抗辐射能力可以提高系统的可靠性，其在航天遥测遥感和星载高速数据处理等方面将有广泛的应用前景。

１算法构成

１.１ＦＦＴ算法选择

提高ＦＦＴ速度的两个主要途径是采用流水结构和并行运算１。采用高基数结构也可以提高速度，只是用ＦＰＧＡ实现时必须综合考虑系统要求、结构特点及片内资源。针对本系统自身特点，这里按时间抽选算法进行分析。由于３２不满足Ｎ＝４ｍ，所以３２点ＦＦＴ算法不能采用基－４ＦＦＴ运算。当详细分析基－２蝶形图时，有些蝶形运算并不需要做乘法，例如Ｗ＝１Ｗ＝－Ｊ等２；对于３２点ＤＩＴ－ＦＦＴ，一共８０个蝶形运算，这种结构就有４６个，极大地降低了运算复杂度。在一维ＦＦＴ计算效率提高的基础上对二维ＦＦＴ采用常用的行列算法３，综合各项指标本系统采用基－２ＤＩＴ行列算法。

１．２算术运算方案

本系统是针对３２×３２点１６ｂｉｔ的二维图像进行快速傅里叶变换（ＦＦＴ），设计要求运算在０．５ｍｓ之内完成，所以采用定点运算更符合系统对时间的要求。对于定点运算，必须用定比例的方法防止溢出，即必须解决动态范围问题。下面对其进行理论分析：

若ｘｎ是一Ｎ点序列，其ＤＦＴ为ＸＫ，由Ｐａｒｓｅｖａｌ定理得４

由式１可知变换结果的均方值是输入序列均方值的Ｎ倍。考虑基－２算法的第ｍ级蝶形运算，用Ｘｍｉ、Ｘｍｊ表示原来的复数，则新的一对复数Ｘｍ＋１ｉ、Ｘｍ＋１ｊ为：

Ｘｍ＋１ｉ＝Ｘｍｉ＋Ｘｍｊ×Ｗ（２）

Ｘｍ＋１ｊ＝Ｘｍｉ－Ｘｍｊ×Ｗ

其中，Ｗ为旋转因子。首先，考虑复数的均方根值。由（２）式可得：

因此，从均方根意义来看，数值（实数或复数）每级都增加倍。其次，再考虑复数的模。由（２）式可以证明［５］：

ｍａｘ｜Ｘｍｉ｜｜Ｘｍｊ｜≤ｍａｘ｜Ｘｍ＋１ｉ｜｜Ｘｍ＋１ｊ｜≤２ｍａｘ｜Ｘｍｉ｜｜Ｘｍｊ｜（４）

因此，复数数组的模是非减的。所以，对于ＤＩＴ－ＦＦＴ，其每的蝶形运算之后数值都会增加１＋≈２．４１４倍。在每运算完成之后，须将结果右移２ｂｉｔｓ以满足要求。

２系统实现

系统原理如图１所示，整个ＦＦＴ运算处理单元分为三部分：存储单元（两个输入／运算存储器、一个输出存储器及旋转因子存储器）、蝶形运算单元、地址产生器。

２．１存储器

本系统实时接收前端ＣＣＤ相机的图像。为保证ＣＣＤ相机采集图像的准确率，图像的每一行、每一帧之间都必须有一定的时间间隔，故采用两个存储单元作为输入数据和中间数据的暂存单元（如图１所示），以节省时间实现实时处理。当系统工作时，将图像存入存储器、计算上采集的图像、将存储器中的结果输出，这三个工作同时进行，用简单的流水方式减少存储数据所需的时间。旋转因子则预先存储在器件的内置ＲＯＭ中。根据级数不同选用不同的因子。

２．２蝶形运算单元

一个基－２蝶形运算由一个复乘和两个复加（减）组成，采用完全并行运算，进一步分解为四个实数乘法，六个实数加（减）法，分三级并行完成，加上前后输入输出的数据锁存，共需要６个时钟周期。３２点的ＦＦＴ需要１６×５＝８０个基－２的蝶形运算，一幅图像一共是３２行３２列，不考虑不需要做乘法的蝶形运算，一路串行共需要６×８０×３２×２＝３０７２０个时钟周期，采用频率为１０ＭＨｚ的时钟，即为３ｍｓ。对于蝶形运算的、第二级都可以由不带乘法器的蝶形结构来实现同步并行运算，每一个蝶形运算加上前后的数据锁存仅需４个时钟周期即可完成；对于第三、第四、第五级，由于带乘法器和不带乘法器的两种蝶形运算结构同时存在，必须加入等待时间才可以实现严格同步。同时由于各级计算时间不同，所以不能实现深度流水。因此，采用多路并行及部分流水，在时间上即可满足系统要求。

上面讨论了当运算从转到另时，序列中数值的幅度一般会增大。因而，运算方法是在内循环中作溢出监测。如果没有溢出，则计算照常进行；若有溢出，则把产生溢出的数据右移，一直到没有溢出为止。记录下移位的次数（０、１或２），并把整个序列右移同样位数，移位总数进行累计，累计数的负值作为２的幂，由此得出终序列的总的比例因子。比例因子ｓ由下式定义６７：

根据公式（６），ＦＦＴ的终结果要除以比例因子。式中ｘｎ为原始数据，Ｘｋ为除以比例因子之前的结果，Ｘ′ｋ为终结果，１／ｓ为比例因子的倒数。

如图２所示，对于一个基－２蝶形单元，当从存储器中读取的Ｂｂｉｔ输入数据进入蝶形运算单元ＰＥ１后，经过乘法运算（ＭＵ１）乘以旋转因子，数据变为Ｂ＋Ｂωｂｉｔ，然后作加（减）法，得到蝶形运算结果Ｂ＋Ｂω＋１ｂｉｔ。为防止溢出，进行移位操作。Ｍ１、Ｍ２为比例选择器，根据不同的级数，选择不同的比例因子。，输出数据再放回到存储器中。

３ＦＰＧＡ器件选择

本设计采用ＸＩＬＩＮＸ公司的ＶＥＲＴＥＸ系列ＸＣＶ３００－４ＨＱ２４０XCV300-4HQ240芯片。该芯片有丰富的可配置逻辑模块ＣＬＢｓ（ＣｏｎｆｉｇｕｒａｂｌｅＬｏｇｉｃＢｌｏｃｋｓ）、大量的触发器以及内置的不占系统资源的块ＲＡＭ。系统工作频率可达２００ＭＨｚ，兼容多种接口标准，有相应的航天级产品，是目前市场上为数不多的能达到此项要求的高性能可编程逻辑器件。

ＶＥＲＴＥＸ系列器件的一个显著特点是内置的延迟锁相环ＤＬＬ（Ｄｅｌａｙ－ＬｏｃｋｅｄＬｏｏｐ）它可以减少时钟传输的衰减，每一个ＤＬＬ可以驱动两个全局时钟信号。ＤＬＬ可以倍频，或者１．５、２、２．５、３、４、５、８以及１６分频。ＶＥＲＴＥＸ系列器件内部的４－输入查找表ＬＵＴｓ（Ｌｏｏｋ－ＵｐＴａｂｌｅｓ）也具有多种功能：可以作为１６×１ｂｉｔ的同步ＲＡＭ，而且一个块（Ｓｌｉｃｅ）中的两个ＬＵＴｓ可以组合成一个１６×２ｂｉｔ或者一个３２×１ｂｉｔ的同步ＲＡＭ或者一个１６×１ｂｉｔ的同步多口ＲＡＭ。另外，ＬＵＴｓ还可作为一个１６ｂｉｔ的移位寄存器使用，该寄存器用来获取高速或者突发数据非常理想，特别适用于数字图像处理中的数据存储８。

本设计充分利用了ＶＥＲＴＥＸ器件的ＬＵＴｓ替代触发器和基本门电路搭建乘法器和加法器这两个显著的结构特点，节省大量触发器资源，避免了缺少触发器而ＬＵＴｓ大量剩余的尴尬；增加了器件利用率、布通率，降低布线延迟。由于本系统终用于空间太阳望远镜，所以板上时钟频率不可超过２０ＭＨｚ。但基于地面测试的需要，特利用ＤＬＬ对外部时钟信号进行了倍频，以提高芯片内部的运行速度。

本设计利用ＦＰＧＡ易于实现并行运算的特点实现专用的ＦＦＴ处理芯片，解决了在轨实时大数据量图像处理与航天级ＤＳＰ运算速度不足之间的矛盾提高了系统实时处理能力。两维ＦＦＴ不到４００μｓ即可完成，高于航天级ＤＳＰＡＤＳＰ２１０２０１．５ｍｓ的处理速度。对太阳米粒组织图像进行处理（实验数据如表１所示），结果显示数据误差都在１％左右。这样的误差满足空间太阳望远镜中的相关摆镜的系统要求。实验证明用高性能ＦＰＧＡ实现空间化的ＦＦＴ处理芯片是完全可行的。