基2×K并行FFT架构的地址映射方法及系统

摘要

本发明公开了一种基2×K并行FFT架构的地址映射方法及系统，其特征是采用定常结构的基2FFT运算流图；包含K个基2碟算单元，K为2的整数幂；以2K个双端口数据存储器为共用存储器，分别与两组2K个单端口数据存储器构成两个存储器组；K个基2碟算单元将FFT运算操作数从一个存储器组并行读出，将运算结果操作数并行写入另一个存储器组；旋转因子存放在K个旋转因子存储器中；FFT运算操作数存放算法，确定输入FFT运算操作数在存储器组中的地址；并行读/写地址产生算法，确定FFT运算操作数读/写地址。按照本发明设计的并行FFT处理器架构，避免了在操作数交换部件中使用多级查找表电路，同时简化了操作数并行读/写地址产生部件电路。

说明书

技术领域

本发明涉及FFT处理器，更具体地说是涉及一种并行FFT处理器的地址映射方法及系统。

背景技术

离散傅里叶变换DFT是描述离散信号时域和频域关系的重要数学工具，随着快速计算技 术FFT的出现，它在数字信号处理和图像信号处理等方面得到了广泛的应用，是许多系统的 核心运算。FFT运算结构特殊，在一些对FFT运算速度有较高要求的应用场合，需要采用FFT 处理器。

FFT处理器的目标是蝶形运算单元的流水执行，这就要求蝶形运算单元的多个操作数能 够并行读入或写出。并行FFT处理器使多个蝶形运算单元并行流水执行，运算速度更快，同 时要求多个蝶算单元的众多操作数并行读入或写出，因此存在FFT运算操作数的存储安排以 及并行无冲突访问问题。直到2008年，上述问题才获得系统解决。D.Reisis和N.Vlassopoulos 在文章《Conflict-Free Parallel Memory Accessing Techniques for FFT Architectures》 （发表在IEEE Transactions on circuits and systems Ⅰ，Vol.55,No.11,p3438-3447） 中采用原址运算的FFT算法提出了一种并行FFT处理器架构。该架构使用多级查找表电路对 蝶算单元的输入和输出数据排序，构成所述FFT运算操作数交换部件，以实现FFT运算操作 数存储器的并行无冲突访问。尽管该方案解决了FFT运算操作数的存储安排以及并行无冲突 访问问题，并且需要的数据存储器容量最小，但由于使用多级查找表电路，造成了操作数交 换部件电路复杂。此外，该方案扩展性较差，若需要增加并行FFT处理器中包含的碟算单元 数量，就需要重新设计查找表电路。

发明内容

本发明为避免上述现有技术所存在的不足之处，提供一种基2×K并行FFT架构的地址映 射方法及系统，采用定常结构的基2FFT运算流图，利用FFT运算操作数存放算法以及并行 读/写地址产生算法，避免在操作数交换部件中使用多级查找表电路，同时使操作数并行读/ 写地址产生部件电路更加简单。

本发明为解决技术问题采用如下技术方案：

本发明基2×K并行FFT架构的地址映射方法的特点是：

采用定常结构的基2FFT运算流图，并行FFT架构包含K个基2碟算单元，K为2的整 数幂；

以2K个双端口数据存储器为共用存储器，所述2K个双端口数据存储器与第一组2K个单 端口数据存储器构成一个存储器组，并以所述2K个双端口数据存储器与第二组2K个单端口 数据存储器构成另一个存储器组；

K个基2碟算单元将FFT运算操作数从一个存储器组并行读出，并将FFT运算结果操作 数并行写入另一个存储器组；

旋转因子存放在K个旋转因子存储器中；

所述基2×K并行FFT架构的地址映射方法是按如下步骤进行：

a、确定所述FFT运算操作数在存储器组中的存放方法：

设N为所述FFT运算操作数的数量；k为操作数的标号，k=0,1,…,N-1；操作数k存 放在体标号为B(k)，体内地址为A(k)的存储器组中；

当时，操作数k存放在存储器组的双端口数据存储器中，并有：

当操作数k存放在存储器组的单端口数据存储器中，并有：

其中$p\left(k\right)=\left(\begin{array}{cc}0,& k\mathrm{mod}2=1\\ 2,& k\mathrm{mod}2=0\end{array}\right),$为向下取整数，mod为取余数；

b、确定所述FFT运算操作数的读地址；

设m为所述基2碟算单元标号，m=0,1,…,K-1；基2碟算单元m包括两个读端口 BFI(m,0)和BFI(m,1)；以MBFI(m,0)和MBFI(m,1)分别表示读端口BFI(m,0)和 BFI(m,1)读入的FFT运算操作数；以cntr表示完成一层FFT运算需要的并行读操作次数，

$\mathrm{cntr}=\mathrm{0,1},···,\frac{N}{2K}-1;$

所述FFT运算操作数MBFI(m,0)来自存储器组的双端口数据存储器，读地址为

所述FFT运算操作数MBFI(m,1)来自存储器组的单端口数据存储器，读地址为

c、确定所述FFT运算操作数的写地址；

基2碟算单元m包括两个写端口BFO(m,0)和BFO(m，1)；以MBFO(m,0)和 MBFO(m,1)分别表示写端口BFO(m,0)和BFO(m，1)写入的FFT运算操作数；以cntw表示 完成一层FFT运算需要的并行写操作次数，

当所述FFT运算操作数MBFO(m,0)和MBFO(m,1)均写入存储器组的双端 口数据存储器中，写地址为：

$\left(\begin{array}{c}B\left(\mathrm{MBFO}(m,0)\right)=2m\\ B\left(\mathrm{MBFO}(m,1)\right)=2m+1\\ A\left(\mathrm{MBFO}(m,0)\right)=A\left(\mathrm{MBFO}(m,1)\right)=\mathrm{cntw}\end{array}\right)---\left(4\right);$

当所述FFT运算操作数MBFO(m,0)和MBFO(m,1)均写入存储器组的单端 口数据存储器中，写地址为：

$\left(\begin{array}{c}B\left(\mathrm{MBFO}(m,0)\right)=2K-2-2m\\ B\left(\mathrm{MBFO}(m,1)\right)=2K-1-2m\\ A\left(\mathrm{MBFO}(m,0)\right)=A\left(\mathrm{MBFO}(m,1)\right)=\mathrm{cntw}-\frac{N}{4K}\end{array}\right)---\left(5\right);$

d、确定旋转因子在所述旋转因子存储器中的存放方法：

所述K个旋转因子存储器的存储内容相同，均按地址递增顺序存放指数为w的旋转因子， w取值范围为[0,N-1]；

e、确定旋转因子读地址：

以cnt表示完成一层FFT运算并行读旋转因子的次数，N=2^L为 所述FFT运算操作数的数量；n为FFT运算级数，n=1,2,…,L；则蝶算单元m在第n级FFT 运算时旋转因子的读地址P(m,n)为：

$P(m,n)=\left(\begin{array}{cc}0,& n=1\\ \mathrm{rev}\left((m+K\times \mathrm{cnt})\mathrm{mod}{2}^{n-1}\right),& n\ne 1\end{array}\right)---\left(6\right)$

其中rev()，表示位倒序操作。

本发明基2×K并行FFT架构的地址映射系统的特点是所述系统构成包括：

系统控制部件，用于系统控制和同步；

基2蝶形运算部件，在每个周期内完成一个基2蝶形运算，所述的基2蝶形运算部件为 K个；

2K个双端口数据存储器，用于存储所述FFT运算操作数并支持并行读写操作；

4K个单端口数据存储器，用于存储所述FFT运算操作数并支持写入或读出操作；

旋转因子存储器，用于存储旋转因子并仅支持读出操作，所述旋转因子存储器为K个独 立的只读存储器；

操作数并行读/写地址产生部件，用于在FFT运算过程中产生FFT运算操作数在存储器组 中的地址；

操作数交换部件，用于双端口数据存储器及单端口数据存储器与所述K个基2蝶形运算 部件之间交换所述FFT运算操作数；

操作数初始地址产生部件，在将外部输入的所述FFT运算操作数存入所述存储器组过程 中，产生存储器组地址；

旋转因子地址产生部件，用于生成旋转因子存储器的地址。

与已有技术相比，本发明有益效果体现在：

1、本发明通过采用定常结构的基2FFT运算流图，利用FFT运算操作数存放算法以及并 行读/写地址产生算法，使并行FFT处理器的操作数交换部件电路简单，避免了多级查找表电 路的使用，同时简化了FFT运算操作数并行读/写地址产生部件；

2、本发明包含不同基2碟算单元数量的并行FFT处理器，其FFT运算操作数并行读/写 地址产生及交换部件结构相同，因此增加基2碟算单元并不需要重新设计电路，可扩展性好。

附图说明

图1是本发明中基2×K并行FFT处理器结构框图；

图2是本发明中定常结构FFT运算流图（N=16）；

图3是本发明中所述存储器组的组织方式；

图4是本发明中存储器组中操作数送入K个基2碟算单元经过的操作数交换部件；

图5是本发明中K个基2碟算单元产生的操作数送入存储器组经过的操作数交换部件；

图6是本发明中操作数并行读地址产生部件；

图7是本发明中操作数并行写地址产生部件。

具体实施方式

本实施例中基2×K并行FFT架构的地址映射方法是：

采用定常结构的基2FFT运算流图，并行FFT架构包含K个基2碟算单元，K为2的整数 幂；

以2K个双端口数据存储器为共用存储器，所述2K个双端口数据存储器与第一组2K个单 端口数据存储器构成一个存储器组，并以所述2K个双端口数据存储器与第二组2K个单端口 数据存储器构成另一个存储器组；

K个基2碟算单元将FFT运算操作数从一个存储器组并行读出，并将FFT运算结果操作 数并行写入另一个存储器组；

旋转因子存放在K个旋转因子存储器中；

所述基2×K并行FFT架构的地址映射方法是按如下步骤进行：

a、确定所述FFT运算操作数在存储器组中的存放方法：

设N为所述FFT运算操作数的数量；k为所述FFT操作数的标号，k=0,1,…,N-1；操 作数k存放在体标号为B(k)，体内地址为A(k)的所述存储器组中。

当时，操作数k存放在所述存储器组的双端口数据存储器中，并有：

当操作数k存放在所述存储器组的单端口数据存储器中，并有：

其中$p\left(k\right)=\left(\begin{array}{cc}0,& k\mathrm{mod}2=1\\ 2,& k\mathrm{mod}2=0\end{array}\right),$为向下取整数，mod为取余数。

b、确定所述FFT运算操作数的读地址；

设m为所述基2碟算单元标号，m=0,1,…,K-1；基2碟算单元m包括两个读端口 BFI(m,0)和BFI(m,1)；以MBFI(m,0)和MBFI(m,1)分别表示读端口BFI(m,0)和 BFI(m,1)读入的FFT运算操作数；以cntr表示完成一层FFT运算需要的并行读操作次数，

$\mathrm{cntr}=\mathrm{0,1},···,\frac{N}{2K}-1;$

所述FFT运算操作数MBFI(m,0)来自所述存储器组的双端口数据存储器，读地址为

所述FFT运算操作数MBFI(m,1)来自所述存储器组的单端口数据存储器，读地址为

c、确定所述FFT运算操作数的写地址；

基2碟算单元m包括两个写端口BFO(m,0)和BFO(m，1)；以MBFO(m,0)和 MBFO(m,1)分别表示写端口BFO(m,0)和BFO(m，1)写入的FFT运算操作数；以cntw表示 完成一层FFT运算需要的并行写操作次数，

当所述FFT运算操作数MBFO(m,0)和MBFO(m,1)均写入所述存储器组的 双端口数据存储器中，写地址为：

$\left(\begin{array}{c}B\left(\mathrm{MBFO}(m,0)\right)=2m\\ B\left(\mathrm{MBFO}(m,1)\right)=2m+1\\ A\left(\mathrm{MBFO}(m,0)\right)=A\left(\mathrm{MBFO}(m,1)\right)=\mathrm{cntw}\end{array}\right)---\left(4\right);$

当所述FFT运算操作数MBFO(m,0)和MBFO(m,1)均写入所述存储器组的 单端口数据存储器中，写地址为：

$\left(\begin{array}{c}B\left(\mathrm{MBFO}(m,0)\right)=2K-2-2m\\ B\left(\mathrm{MBFO}(m,1)\right)=2K-1-2m\\ A\left(\mathrm{MBFO}(m,0)\right)=A\left(\mathrm{MBFO}(m,1)\right)=\mathrm{cntw}-\frac{N}{4K}\end{array}\right)---\left(5\right);$

d、确定旋转因子在所述旋转因子存储器中的存放方法：

所述K个旋转因子存储器的存储内容相同，均按地址递增顺序存放指数为w的旋转因子， w取值范围为[0,N-1]；

e、确定旋转因子读地址：

以cnt表示完成一层FFT运算并行读旋转因子的次数，N=2^L为 所述FFT运算操作数的数量；n为FFT运算级数，n=1,2,…,L；则蝶算单元m在第n级FFT 运算时旋转因子的读地址P(m,n)为：

$P(m,n)=\left(\begin{array}{cc}0,& n=1\\ \mathrm{rev}\left((m+K\times \mathrm{cnt})\mathrm{mod}{2}^{n-1}\right),& n\ne 1\end{array}\right)---\left(6\right)$

其中rev()，表示位倒序操作。

本实施例中基2×K并行FFT架构的地址映射系统的构成包括：

系统控制部件，用于系统的控制和同步；

基2蝶形运算部件，在每个周期内完成一个基2蝶形运算，基2蝶形运算部件为K个；

2K个双端口数据存储器，用于存储FFT运算操作数并支持并行读写操作；

4K个单端口数据存储器，用于存储FFT运算操作数并支持写入或读出操作；

旋转因子存储器，用于存储旋转因子并仅支持读出操作，旋转因子存储器为K个独立的 只读存储器；

操作数并行读/写地址产生部件，用于在FFT运算过程中，产生FFT运算操作数在存储器 组中的地址；

操作数交换部件，用于双端口数据存储器及单端口数据存储器与所述K个基2蝶形运算 部件之间的交换所述FFT运算操作数。

操作数初始地址产生部件，在将外部输入的所述FFT运算操作数存入所述存储器组过程 中，产生存储器组地址；

旋转因子地址产生部件，用于生成旋转因子存储器的地址；

图1示出了基2×K并行FFT处理器结构框图，主要组成部分为：系统控制部件，用于处 理器的控制和同步；蝶形运算部件，在每个周期内完成一个基2蝶形运算，共K个；双端口 数据存储器，用于存储FFT运算操作数并支持并行读写操作，共2K个；单端口数据存储器， 用于存储FFT运算操作数并支持写入或读出操作，共4K个；4K个单端口数据存储器等分为 两部分，每部分包含2K个单端口数据存储器；以2K个双端口数据存储器为共用；2K个单 端口数据存储器与2K个双端口数据存储器组成存储器组，一共可以组成两个存储器组；旋转 因子存储器，用于存储旋转因子并仅支持读出操作，共K个；操作数并行读/写地址产生部件， 用于生成所述FFT运算操作数在所述存储器组中的地址；操作数交换部件，用于双端口数据 存储器及单端口数据存储器与所述K个基2蝶形运算部件之间的交换所述FFT运算操作数； 操作数初始地址产生部件，在将外部输入的所述FFT运算操作数存入所述存储器组过程中， 产生存储器组地址；旋转因子地址产生部件，用于生成旋转因子存储器的地址；操作数通讯 接口部件，用于将待处理的FFT运算操作数读入并行FFT处理器，或将并行FFT处理器运算 得到的操作数送出。

并行FFT处理器启动后，操作数通讯接口部件将外部待运算的N个FFT运算操作数送入 所述的一个存储器组，并由操作数初始地址产生部件决定外部操作数在存储器组中的地址。 在外部待计算FFT操作数全部写入上述存储器组后，系统控制部件协调控制并行FFT处理器 各部件开始运算。根据操作数并行读地址产生部件（见图4）产生的地址，2K个所述FFT运 算操作数从上述存储器组中读出，经过由所述存储器组到所述基2碟算单元的操作数交换部 件（见图6）送入K个基2碟算单元。同时旋转因子地址产生部件产生所述旋转因子存储器 的地址，K个旋转因子从所述旋转因子存储器中读出，也被送入K个基2碟算单元。K个基2 碟算单元开始运算，并在下一周期将计算得到的2K个操作数结果经过由所述基2碟算单元到 所述存储器组的操作数交换部件（见图7）后，写入所述的另外一个存储器组。上述计算得 到的2K个操作数在该存储器组中的地址，由操作数并行写地址产生部件（见图5）产生。上 面所述步骤重复进行次后，共N个FFT操作数已经全部由初始存储器组读出，并经过基 2碟算单元运算后写入了另一个存储器组。至此，处理器完成了FFT的一次单层运算。对于N 个操作数的FFT运算，共需要重复log₂N次上述FFT单层运算。所有运算次数的控制均由系 统控制部件完成。

下面依次具体说明定常结构的基2FFT运算流图、所述存储器组的组织方式、所述FFT 操作数的地址组成、操作数并行读地址产生部件、操作数并行写地址产生部件以及操作数交 换部件。基2×K并行FFT处理器结构框图中的其余部件容易设计，不做解释。

本发明基2×K并行FFT处理器采用如图2所示定常结构FFT运算流图（以N=16为例）， 并且对于N=2^L个操作数的定常结构FFT运算流图有如下结论：操作数k与级数n无关，即 FFT流图中每级具有相同的结构；任意一级FFT运算包含个碟式运算，碟式运算的两个输 入端操作数标号统一表示为u和两个输出端操作数标号统一表示为2u和2u+1，其中 设为第m个碟式运算在第n级的旋转因子，则有

$P_{(m,n)}=\left(\begin{array}{cc}0,& n=1\\ \mathrm{rev}\left(m\mathrm{mod}{2}^{n-1}\right),& n\ne 1\end{array}\right)---\left(7\right)$

其中n=1,2,…,L；m=0,1,…,2^L-1；rev()表示位倒序操作，例A的二进制表示为A=1011b， 则rev(A)=1101b。

所述存储器组的组织方式见图3。所述FFT处理器共有2个存储器组，每个存储器组包 括所述2K个双端口存储器和所述2K个单端口存储器。2个存储器组共用所述2K个双端口存 储器。

所述FFT操作数k在存储器组中的地址由三部分组成：存储器类型，体标号B(k)和体内 地址A(k)。所述存储器类型表示操作数k所在存储器是双端口存储器还是单端口存储器。体 标号B(k)表示操作数k所在存储器标号，取值范围为B(k)=0,1,…,2K-1。体内地址A(k)表 示存储器内部存储单元的地址，取值范围为A(k)=0,1,…,H，其中图3直观说明 了体标号B(k)和体内地址A(k)所表示的含义。

操作数并行读地址产生部件的设计由权利1.b中的公式（2）（3）中A(MBFI(m，0))和 A(MBFI(m，1))确定，且与所述基2碟算单元的标号无关。由于所述FFT操作数数量N和所 述基2蝶算单元个数K均为2的幂，可得L=log₂N和r=log₂K。并行读地址产生部件结构 见图4，其中AddrGen_R表示送入存储器组的地址，取L-r-1位计数器Count_0的高L-r-2 位。

操作数并行写地址产生部件的设计由权利1.c中的公式（4）（5）中A(MBFO(m，0))和 A(MBFO(m，1))确定，且与所述基2碟算单元的标号无关。由于所述FFT操作数数量N和所 述基2蝶算单元个数K均为2的幂，可得L=log₂N和r=log₂K。并行写地址产生部件结构 见图5，其中AddrGen_W表示送入存储器组的地址，取L-r-1位计数器Count_1的低L-r-2 位。由于所述K个基2碟算单元完成一次计算需要1个周期，因此计数器Count_1由所述计 数器Count_0寄存一个周期得到。

操作数交换部件完成所述K个基2碟算单元与所述存储器组的数据交换，因此按照数据 方向不同，分为由存储器组到碟算单元经过的交换部件和由碟算单元到存储器组经过的交换 部件，共两部分。

由存储器组到碟算单元经过的交换部件的设计由权利1.b中的公式（2）（3）中的 B(MBFI(m,0))和B(MBFI(m，1))确定。而B(MBFI(m，0))和B(MBFI(m，1))固定取两个值中 的一个，且仅与所述基2碟算单元的标号m有关。因此，所述由存储器组到碟算单元经过的 交换部件的结构见图6，由2K个利用二选一多路选择器实现，且这些多路选择器的选择端相 同，为图4中计数器Count_0的最低位B₀。

由碟算单元到存储器组经过的交换部件的设计由权利1.c中的公式（4）（5）中的 B(MBFO(m,0))和B(MBFO(m,1))确定。而B(MBFO(m,0))和B(MBFO(m,1))固定取两个 值中的一个，且仅与所述基2碟算单元的标号m有关。因此，所述由碟算单元到存储器组经 过的交换部件见图7，由2K个利用二选一多路选择器实现，且这些多路选择器的选择端相同， 为图5中计数器Count_1的最高位B_L-r-2。