一种低复杂度的通用混合基FFT设计方法

摘要

本发明在基于原位存储的结构上，提出一种低复杂度的通用混合基FFT设计方法，步骤一、设计计数器；步骤二、根据步骤一得到的每级的计数器，将其映射到操作数的访问地址；步骤三、根据步骤一得到的计数器，给出生成旋转因子地址的中间值的映射；上面得到的操作数和旋转因子的访问地址即为地址控制单元，选择器Mux设置为：当Mux=0时，表示进入RAM中的数据为外界输入数据；当Mux=1时，表示进入RAM中的数据为由蝶形单元计算按照原位算法存储的数据。

说明书

技术领域

本发明属于数字信号处理技术领域，涉及一种低复杂度的通用混合基FFT 设计方法。

背景技术

随着数字信号处理技术和大规模集成电路的发展，FFT(快速傅里叶变换) 算法的重要性不言而喻，广泛应用于各种科学工程领域，如雷达、声纳、通信 等。在计算FFT时，经典的算法是固定基FFT，比如基-2或基-4FFT，点数限制 在2的幂或4的幂次方，这样限制了其点数的可选择范围。对于某些应用，比如 SAR(合成孔径雷达)信号处理中，尤其是在聚束模式下，由于处理时间和面 积的限制，不能将每个处理的点数都要扩展至满足基-2或基-4FFT算法，尤其 对于大点数的FFT，否则会延长计算时间以及消耗更多的存储空间。为了扩展 FFT处理器的使用范围，本发明是基于一种通用混合基FFT处理算法。

在各种各样的FFT处理器中，一般采用两种结构：流水结构和基于存储的 结构。当对大点数进行处理时，流水结构比基于存储结构会占用更多的资源， 导致面积和功耗增加。因此近些年来，针对大点数FFT的实现，基于存储结构 得到越来越广泛的需求。而为了占用最少的存储资源，通常采用原位存储算法， 该方法是将FFT蝶形单元输出存储到与输入数据读取的地址一致的存储空间 内。

目前关于通用混合基FFT实现方法常用的有以下两种：(1)操作数和旋 转因子采用两个不同的方案实现，且参数多，不易在硬件中实现；(2)采用多 个求模操作实现地址映射。这两种方法都存在各自的问题，因此解决这一问题 是必要的。

发明内容

本发明的目的是为了克服已有技术的缺陷，在基于原位存储的结构上，提 出一种低复杂度的通用混合基FFT设计方法。

本发明是通过下述技术方案实现的：

一种低复杂度的通用混合基FFT设计方法，设FFT点数满足 $N=r_1^{s_1}{\leftrightarrow }_2^{s_2}\leftrightarrow ..{\leftrightarrow }_t^{s_t},$计算蝶形单元顺序为：$r_1,r_2,..,r_t,s=\underset{i=1}{\overset{t}{\Sigma }}{s}_i;$包括以下步骤：

步骤一、设计计数器：当级数为1～s₁时，采用的蝶形单元为基-r₁，设计 的计数器为：即该计数器由s位进制数表示，顺 序从最高位到最低位的进制数分别为s₁-1位r₁进制数，s₂位r₂进制数，s₃位r₃进制数，…，s_t位r_t进制数，1位r₁进制数；

当级数为s₁+1～s₁+s₂时，采用的蝶形单元为基-r₂，设计的计数器为： 顺序从最高位到最低位的进制数分别为s₁位r₁进制 数，s₂-1位r₂进制数，s₃位r₃进制数，…，s_t位r_t进制数，1位r₂进制数；

当级数为时，采用的蝶形单元为基-r_j，设计的计数器为： 顺序从最高位到最低位的进制数分别为s₁位r₁进制数，s₂-1位r₂进制数，s₃位r₃进制数，…，s_j-1位r_j进制数，…，s_t位r_t进制数，1位r_j进制数；

步骤二、根据步骤一得到的每级的计数器，将其映射到操作数的访问地址， 即当级数为1～s₁时，计数器为：对应的操作数地 址为：当级数为1时，将计数器最低位r₁移位到最高 位的左端；当级数为2时，将计数器最低位r₁移位到最高位的后1位；当级数 为3时，将计数器最低位r₁移位到最高位的后2位；….；当级数为i(i≤s₁)时， 将计数器最低位r₁移位到最高位的后i-1位；

当级数为s₁+1～s₁+s₂时，计数器为：对应 的操作数地址为：当级数为s₁+1时，将计数器最低位r₂移 位到s₂-1位r₂进制数左端；当级数为s₁+2时，将计数器最低位r₂移位到s₂-1位 r₂进制数的后1位；当级数为3时，将计数器最低位r₂移位到s₂-1位r₂进制数 后2位；….；当级数为i(s₁<i≤s₁+s₂)时，将计数器最低位r₂移位到s₂-1位r₂进 制数后i-s₁位；依次类推其他级数由计数器映射到对应的操作数地址；

步骤三、根据步骤一得到的计数器，给出生成旋转因子地址的中间值的映 射，设为β：

第一级，无需映射，β=0；

当级数为即i-1位r₁进制数，后面补s-i个 零，其中s₁-i个r₁进制零，s₂个r₂进制零，…，s_t个r_t进制零；

当级数为即s₁位r₁进制数，i-s₁-1 位r₂进制数，后面补s-i个零，其中s₁+s₂-i个r₂进制零，s₃个r₃进制零，…， s_t个r_t进制零；其他级数以此类推；

β得到后，即得到基-r′的r′个旋转因子地址，r′=r_j，j＝1，2，…，t：

${\mathrm{Addr}}_{\mathrm{twi}}\left(i\right)=\left(\begin{array}{c}0,\\ \beta \left(i\right)\\ 2\beta \left(i\right)\\ ...\\ (r^{\text{'}}-1)\beta \left(i\right),\end{array}\right)$

上面得到的操作数和旋转因子的访问地址即为地址控制单元，选择器Mux 设置为：当Mux=0时，表示进入RAM中的数据为外界输入数据；当Mux=1时， 表示进入RAM中的数据为由蝶形单元计算按照原位算法存储的数据。

本发明的有益效果：

本发明是一种低复杂度的通用混合基FFT设计，对比已有技术，在实现中 去除取模操作，达到一种简单的通用混合基FFT实现方案。

附图说明

图1为原位存储结构FFT框图。

具体实施方式

下面结合附图对本发明方法的实施方式做详细说明。

一种低复杂度的通用混合基FFT设计方法，其具体步骤包括：

设FFT点数满足设计算蝶形单元顺序为： $r_1,r_2,...,r_t,s=\underset{i=1}{\overset{t}{\Sigma }}{s}_i;$

步骤一、设计计数器：

由于不同级数采用的计数器是不一样的，因此每级计数器设计如表1所示。 说明：

表1

当级数为1～s₁时，采用的蝶形单元为基-r₁，设计的计数器为： 即该计数器由s位进制数表示，顺序从最高位到最低位 的进制数分别为s₁-1位r₁进制数，s₂位r₂进制数，s₃位r₃进制数，…，s_t位r_t进 制数，1位r₁进制数。

当级数为s₁+1～s₁+s₂时，采用的蝶形单元为基-r₂，设计的计数器为： 顺序从最高位到最低位的进制数分别为s₁位r₁进制数， s₂-1位r₂进制数，s₃位r₃进制数，…，s_t位r_t进制数，1位r₂进制数。

当级数为时，采用的蝶形单元为基-r_j，设计的计数器为： 顺序从最高位到最低位的进制数分别为s₁位r₁进制 数，s₂-1位r₂进制数，s₃位r₃进制数，…，s_j-1位r_j进制数，…，s_t位r_t进制 数，1位r_j进制数。其他级数按表1以此类推。

步骤二、将该计数器映射到操作数的访问地址：

根据步骤一得到的每级的计数器，将其映射到操作数的访问地址，地址生 成如表2所示。

表2

可以看出，虽然每级的计数器不同，但是每级对应的操作数访问地址是相 同的。映射说明：

当级数为1～s₁时，计数器为：对应的操作数地址为： 详细说明：当级数为1时，将计数器最低位r₁移位到最 高位的左端；当级数为2时，将计数器最低位r₁移位到最高位的后1位；当级 数为3时，将计数器最低位r₁移位到最高位的后2位；….；当级数为i(i≤s₁)时， 将计数器最低位r₁移位到最高位的后i-1位。

当级数为s₁+1～s₁+s₂时，计数器为：对应的操作 数地址为：详细说明：当级数为s₁+1时，将计数器最低 位r₂移位到s₂-1位r₂进制数左端；当级数为s₁+2时，将计数器最低位r₂移位到 s₂-1位r₂进制数的后1位；当级数为3时，将计数器最低位r₂移位到s₂-1位r₂ 进制数后2位；….；当级数为i(s₁<i≤s₁+s₂)时，将计数器最低位r₂移位到s₂-1 位r₂进制数后i-s₁位。

依次类推其他级数由计数器映射到对应的操作数地址。

步骤三、将该计数器映射到旋转因子的访问地址：

根据步骤一得到的计数器，首先给出生成旋转因子地址的中间值的映射， 设为β，如表3。

表3

映射说明：

第一级，无需映射，β=0。

当级数为即i-1位r₁进制数，后面补s-i个零， 其中s₁-i个r₁进制零，s₂个r₂进制零，…，s_t个r_t进制零。

当级数为i即s₁位r₁进制数，i-s₁-1位r₂进制数，后面补s-i个零，其中s₁+s₂-i个r₂进制零，s₃个r₃进制零，…，s_t个 r₁进制零。

其他级数以此类推。注意：不管补零的个数是多少，进制数的个数分配原 则是：β是由s-1位进制数组成，映射到β时，对应级数的计数器最低位不考 虑，其他位上不同进制数的个数同β一致。

β得到后，由式(1)即可得到基-r′的r′(r′=r_j，j=1，2，…，t)个旋转因子地址：

${\mathrm{Addr}}_{\mathrm{twi}}\left(i\right)=\left(\begin{array}{c}0,\\ \beta \left(i\right)\\ 2\beta \left(i\right)\\ ...\\ (r^{\text{'}}-1)\beta \left(i\right),\end{array}\right)$   式(1)

上面得到的操作数和旋转因子的访问地址即为图1中地址控制单元，选择 器Mux设置为：当Mux=0时，表示进入RAM中的数据为外界输入数据；当Mux=1 时，表示进入RAM中的数据为由蝶形单元计算按照原位算法存储的数据。蝶形 运算单元有两部分输入，一是从RAM中读出的所需操作数，一是从R0M中读出 的所需旋转因子，采用的蝶形单元根据不同的级数采用不同的蝶形。当做到最 后一级，通过地址控制，从RAM中读出的即为输出数据。

综上所述，本发明基于原位存储结构的一种低复杂度的通用混合基FFT设 计，通过该方案能够将地址控制单元简单地由计数器映射到硬件平台。

自此，就完成了一种低复杂度的通用混合基FFT设计。

虽然结合了附图描述了本发明的实施方式，但是对于本领域技术人员来 说，在不脱离本发明原理的前提下，还可以做出若干改进，这些也应视为属于 本发明的保护范围。