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

　　因此，从均方根意义上看，数据（实数或复数）复级都增加（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列，不考虑不需要做乘法的蝶形运算，一路串行共需要6×80×32×2=30720个时钟周期，采用频率为10MHz的时钟，即为3ms。对于蝶形运算的第一、第二级都可以由不带乘法器的蝶形结构来实现同步并行运算，每一个蝶形运算加上前后的数据锁存仅需4个时钟周期即可完成；对于第三、第四、第五级，由于带乘法器不带乘法器的两种蝶形运算结构同时存在，必须加入等待时间才可以实现严格同步。同时由于各级计算时间不同，所以不能实现深度流水。因此，采用多路并行及部分流水，在时间上即可满足系统要求。
　　
　　上面讨论了当运算从一级转到另一级时，序列中数值的幅度一般会增大。因而，运算方法是在内循环中作溢出监测。如果没有溢出，则计算照常进行；若有溢出，则把产生溢出的数据右移，一直到没有溢出为止。记录下移位的次数（0、1或2），并把整个序列右移同样位数，移位总数进行累计，累计数的负值作为2的幂，由此得出最终序列的总的比例因子。比例因子s由下式定义[6][7]：
　　
　　
　　
　　这里bi为比例参数。
　　
　　k=0,1,2,…，N-1（6）
　　
　　根据公式(6)，FFT的最终结果要除以比例因子。式中x(n)为原始数据，X(k)为除以比例因子之前的结果，X'(k)为最终结果，1/s为比例因子的倒数。
　　
　　如图2所示，对于一个基-2蝶形单元，当从存储器中读取的Bbit输入数据进入蝶形运算单元PE1后，经过乘法运算（MU1）乘以旋转因子，数据变为（B+Bω）bit，然后作加（减）法，得到蝶形运算结果（B+Bω+1）bit。为防止溢出，进行移位操作。M1、M2为比例选择器，根据不同的级数，选择不同的比例因子。最后，输出数据再放回到存储器中。

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