一种基于二维FFT处理器的行转置架构设计方法

摘要

本发明公开了一种二维FFT处理器的行转置架构，具有以下特点：FFT处理器包含片上行转置存储器，用于保存图像行变换结果。当行变换结果超过该片上存储器容量时，每行变换结果的前2k个数据写入片上行转置存储器，剩余数据写入片外SDRAM，k根据行变换结果和片上行转置存储器容量计算得到。此时，将片上行转置存储器一分为二，记为存储器A、B，用于保存行变换部分结果以及暂存片外SDRAM读出数据。在从存储器A或B逐列读出数据进行FFT列变换的同时，采用行突发方式访问SDRAM，并将数据轮流写入被读空的存储器A或B。这样A和B乒乓切换，循环往复，直到读空SDRAM。采用这种行转置架构，能够显著降低SDRAM的跨行访问次数，提高二维FFT执行速度。

说明书

技术领域

本发明属于数字信号处理领域，更具体地，涉及一种基于二维FFT处理器的行转置架构设计方法，适用于流水线架构的FFT内核，能满足星载雷达成像系统对FFT的速度等性能要求。

背景技术

FFT变换广泛应用于图像处理、无线通信、语音识别、频谱分析、雷达处理、遥感遥测和地质勘探等多个领域。在一维信号处理中，各种高效的FFT算法相继被提出，对于2的整数次幂的点数处理，可以通过Cooley-Tukey算法、Sander-Tukey算法、分裂基算法等算法来实现。而对于非2的整数次幂的点数处理，可以采用Good-Thomas素因子算法、Winograd嵌套算法等算法来实现。而在二维信号处理中，主要通过行列分解算法以及矢量基算法来实现。

矢量基算法是直接将二维阵列当成一维序列处理的，通过将N×N点数据分解为多个独立的小点数单元，对蝶形操作数进行并行存取，只用了一个矢量基2×2蝶形运算硬件单元实现了2D-FFT。相比于传统行列分解方法极大地节省了硬件资源，同时提高了计算速度。它对于小规模数据阵列时可以有效减少计算量，但对于大规模数据阵列就显得力不从心，比如说8192×8192规模的二维FFT计算，数据控制流程复杂，并且对于片上存储器的要求很高。

相对于矢量基算法，行列分解算法应用得更为广泛和成熟，行列分解算法主要是在一维FFT算法基础上，先将二维阵列中每一行进行FFT计算，得到的二维阵列中间结果；在列方向，再将每一列进行FFT计算，所有列 都计算完成得到的结果就是最后的二维FFT结果。将二维阵列的FFT计算分解为多次一维FFT计算，不仅简化数据流图，而且在片上降低存储器的容量，有利于VLSI设计实现和缩小硅片面积。本发明专利的实施例就是采用的行列分解算法。

目前大规模数据阵列的行转置主要有两种方法实现：第一种是采用转置存储器的方法，对采用的存储器进行硬件操作，即对行变换后的二维阵列结果所存放的处理模块进行行列变换，对存储器的读取方式进行变换；第二种是将行变换后的二维阵列结果按照转置地址写入存储器，之后顺序地址依次读出即可。

其中转置存储器来实现图像转置的方法主要有输入输出平衡法、矩阵分块法、行进列出法、两页式或三页式转置法。其中实现FFT的行变换结果转置的方法主要是行进列出法以及矩阵分块法。行进列出法主要是将二维行变换后的数据按行方向连续地存入片外SDRAM，在列方向连续地读出一列数据，最坏的情况是每取一个列数据就要进行行激活，需要耗费若干时钟周期，降低对片外SDRAM的访问效率；而矩阵分块法方法略好于行进列出法，主要是将二维数据按行分段存储到片外SDRAM，即将二维数据中的一行存到片外SDRAM的区域块中，这样分块存储，列数据虽然不是连续存放在SDRAM中的同一行，但是SDRAM中的一行总会有若干同列数据，因此对其只需要通过地址变换就可以读取了。避免行激活的额外开销，提高了对片外SDRAM的访问效率。本发明专利中行转置架构充分利用片上存储器，转置操作都在片上进行；从片外SDRAM读取行变换后的数据都是采用突发读取SDRAM中一行数据到片上存储器，跨行的情况比矩阵分块法方法还少，片外SDRAM的访问效率也就相对更高。

发明内容

针对现有技术的以上缺陷或改进需求，本发明提供了一种基于二维FFT处理器的行转置架构设计，其目的在于结合硬件实现速度快、并行执行、 存储资源有限等特点实现二维行变换结果的转置功能，由此解决访问外部SDRAM效率过低的技术问题。

为了实现上述目的，本发明提供了一种基于二维FFT处理器的行转置架构设计方法，包括以下步骤：

S1、根据行变换后的二维阵列行列数大小，判断是否需要片外SDRAM协同工作：行变换后的二维阵列的大小为M*N，其中M是行数，N是列数，片上存储器的存储单元有s个；若M*N＞s，则执行步骤S2；若M*N≤s，则执行步骤S3；其中需要大于行变换后的图像数据的最大行数M；

S2、片上存储器与片外SDRAM协同工作完成行转置功能：包括如下子步骤：

(S2a)将片上的存储器一分为二，其中每一份的存储单元都有个，分别记为A与B；

(S2b)将行变换后的结果串行写入存储器，将其中一行前k个数据，按照顺序依次存放到存储器A，然后将该行接下来的k个数据顺序写入B，最后将该行剩下的(N-2k)个数据写入片外SDRAM；这样将行变换后的二维结果中的一行完整地写入存储器A，B以及片外SDRAM中，重复该操作，直到将所有行的数据全部顺序地存放在存储器A，B以及SDRAM中；其中k是一个取整的数；

(S2c)在步骤(S2b)中写完存储器A后，按照转置地址来读取存储器A中数据，每次读出M个数据送到FFT内核进行列变换，直到读空存储器A；

(S2d)按照(S2c)的步骤，按照转置地址读取存储器B中数据，每次读出M个数据送到FFT内核进行列变换；同时并行执行从SDRAM突发读数据到存储器A，按照顺序突发方式读取一行的前X数据存到存储器A；循环执行，直到将SDRAM中行变换后的矩阵的前X列数据全部写到存储器A；其 中X的大小为：

$X=\left(\begin{array}{cc}k;when& k<N-(n+1)k\\ N-(n+1)k;when& k\ge N-(n+1)k\end{array}\right)$

其中n是指第n次从片外SDRAM读取数据到片上存储器；

(S2e)当存储器A写满时，存储器B肯定早已读空，这时需要进行交替处理；将(S2d)步骤中的执行对象颠倒过来，在按照转置地址读取存储器A中数据的同时，并行执行从SDRAM突发读数据到存储器B中，按步骤(S2d)的方法同时执行读存储器A和写存储器B的操作，直到A读空B写满,再替换执行对象；这样重复操作，直到第n₁次从片外SDRAM读取数据到片上存储器时(其中n₁满足)，将最后剩余的N-(n₁+1)*k列数据突发读出来，读空SDRAM；

S3、只在片上存储器中实现行转置的功能；

将二维行变换后的结果串行写入存储器A，B中，将其中每行的前个数据缓存到存储器A，后个数据缓存到存储器B，共缓存M行；

在进行读操作时，按照转置地址读取存储器A中数据，每次读出M个数据送至FFT内核进行列变换；当读空存储器A后，再按照相同的方式读存储器B，直到将B也读空。

所述步骤S1中，根据行变换后的图像数据M*N以及片上存储器的存储容量s之间的大小关系，采用不同方式来实现行转置的功能，具体情况如下：

(1)若M*N＜s，只用片上存储器就可以完成行转置功能；

(2)若M*N≥s，需要片上存储器与片外SDRAM协同工作完成行转置的功能。

所述步骤(S2b)中，对于行变换后图像数据M*N大于片上存储器的存储容量s的情况，将片上存储器一分为二，其写操作按以下方式进行：

二维行变换后生成的阵列数据M*N串行写入片上存储器与片外SDRAM中，将其中一行的前k个数据按顺序依次写入片上存储器A，再把该行接下来的k个数据按顺序依次写入片上存储器B，最后把该行剩下的N-2k个数据按顺序依次写入片外SDRAM；这样把行变换输出结果的M行按上述步骤分别写入片上存储器与片外SDRAM，其中M*2k的图像像素存储在片上，后M*(N-2k)的图像像素存储在片外SDRAM中。

所述步骤(S2c)中对于行变换后图像数据M*N大于片上存储器的存储容量s的情况，其按转置地址读出存储器A与B中数据的实现方式：

在存储器A或B写满后，先从存储器中读出第一个数据，然后每隔k个地址处再读出存储器中的一个数据，这样重复M次，读出行变换后生成的二维数据的第一列送到FFT内核中进行列变换；再从存储器中读出第二个数据，然后每隔k个地址读出存储器中的一个数据，也重复M次，这样读出第二列数据，并将其送到FFT内核中进行列变换；依次类推，直到将存储器读空为止；当最后一次从片外SDRAM读出数据到片上存储器，将片外SDRAM最后剩下的N-(n₁+1)*k列数据全部写到片上存储器，这时就应该间隔N-(n₁+1)*k个数据读出一列，其它操作相同。

所述步骤(S2c)中对于行变换后的二维数据M*N大于片上存储器的存储容量s的情况，其按照顺序突发方式读出片外SDRAM中数据存到片上存储器的实现方式：

存储器A读空后，在读取存储器B的数据到FFT内核进行列变换时，需要并行执行从片外SDRAM读取数据到存储器A；当第一次从SDRAM中读取数据时，先从开始的位置按顺序依次读取k个数据存放在片上存储器A，然后在间隔最后读出数据的位置后的N-3k处，再按顺序依次读取k个数据存放在存储器A，之后又一次在间隔N-3k处读取k个数据存放在存储器A， 这样重复M次，直到将M*k个数据全部写到存储器A；同样地，当第q次从SDRAM中读取数据时，从距离开头(q-1)k处按顺序依次读取k个数据存放在存储器A，然后在间隔最后读出数据的位置后的N-3k处，再按顺序依次读取k个数据，这样突发读取M次，将M*k个数据到存储器A；

当第q₁次从片外SDRAM突发读取数据到片上存储器时，此时q₁满足：这也是最后一次从片外SDRAM读取数据到片上存储器中；按顺序的方式从距离开头(q₁-1)*k处读取N-(q₁+1)*k个数据，然后在间隔最后读出数据的位置后的(q₁-1)*k处，再按顺序依次读取N-(q₁+1)k个数据存放在片上存储器，接着还是在间隔(q₁-1)*k处按顺序依次读取N-(q₁+1)*k个数据存放在片上存储器，这样突发读取M次，此时SDRAM中的行变换结果就全部读空了。

所述步骤(S2e)，对于行变换后的图像数据M*N大于片上存储器的存储容量s的情况，当按照转置地址读取某一片上存储器的数据时，比如存储器A，每次读出M个数据送到FFT内核进行列变换，同时并行执行从SDRAM按顺序突发读数据到存储器B中；由于读取SDRAM中的数据总会存在跨行读取的情况，因此需要几个时钟周期来激活，这样在存储器A读空时，B存储器还没有填满，这时需要等待存储器B填满，才能交换执行对象。

附图说明

图1为本发明设计的硬件结构简图；

图2为行变换结果存储示意图；

图3为片上存储器存放数据示意图；

图4为片外SDRAM存放数据示意图；

图5为片上存储器读取数据示意图；

图6为片外SDRAM读取数据示意图；

图7为写RAM逻辑控制1状态机示意图；

图8为写RAM逻辑控制2状态机示意图；

图9为读RAM控制逻辑状态机示意图；

图10为EMIF读写控制逻辑状态机示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。

如图1所示，本实施例中二维FFT处理器行转置架构主要包括FFT行变换结果的接收控制逻辑、采用乒乓缓存的的片上存储器、用于缓存写入SDRAM数据的FIFO、控制片外存储器SDRAM读写的片外存储器扩展接口EMIF以及其读写控制逻辑以及针对片上存储器的读写控制逻辑。

其中片上存储器的总容量是8192*15*64bits，采用乒乓缓存结构，分为存储器A和存储器B，每部分的存储器容量由7片64*8192bits的RASP和1片64*4096bits的RASP组成，并采用统一寻址方式控制；用于缓存写入SDRAM数据的FIFO是采用的128*64bit的双端口RFTP；写RAM控制逻辑1的功能是将FFT行变换的部分结果写入片上存储器；写RAM控制逻辑2的功能是将FFT缓存到SDRAM的行变换结果读入到片上存储器；读RAM的控制逻辑用来将RAM中的行变换结果转置输出。

如图2、图3与图4所示，接收控制逻辑负责从FFT内核输出端接受行变换结果，然后由写RAM控制逻辑1和EMIF读写控制逻辑负责给片上存储器与片外SDRAM写入行变换结果。将前2k列数据缓存在片上，后(N－2k)列数据缓存到片外，其中前k列数据缓存到存储器A中，后k列数据缓存到存储器B中。如图7中状态机所示，描述的是写RAM逻辑控制1将前2k列数据缓存在片上的方式。其中CntCol是一个计数器，记录输入数据的个 数，k是输入数据每行中写入片上存储器的数据个数。CntRow记录写入片上存储器的行数。

如图6，EMIF读写控制逻辑负责从片外SDRAM读出数据，写RAM控制逻辑2负责将读出的数据写入到片上存储器中。当第一次从片外SDRAM读出数据时，按顺序的方式从开始的位置读取k个数据，并依次将其写入片上存储器，然后在间隔最后读出数据的位置后的N－3k处，按顺序依次读取k个数据存放在片上存储器，接着还是在间隔N－3k处按顺序依次读取k个数据存放在片上存储器，这样重复M次才算完成一次从片外SDRAM读数据到片上存储器。当第q次从片外SDRAM读出数据，按顺序的方式从距离开头(q－1)*k处读取k个数据，并依次将其写入片上存储器，然后在间隔最后读出数据的位置后的N－3k处，按顺序依次读取k个数据存放在片上存储器，接着还是在间隔N－3k处按顺序依次读取k个数据存放在片上存储器，这样重复M次再结束。

当第q₁次从片外SDRAM突发读取数据到片上存储器时，此时q₁满足：k≥N-(q₁+1)k，这也是最后一次从片外SDRAM读取数据到片上存储器中。按顺序的方式从距离开头(q₁－1)*k处读取N－(q₁+1)*k个数据，然后在间隔最后读出数据的位置后的(q₁－1)*k处，按顺序依次读取N－(q₁+1)*k个数据存放在片上存储器，接着还是在间隔(q₁－1)*k处按顺序依次读取N－(q₁+1)*k个数据存放在片上存储器，这样重复M次再结束，此时SDRAM中的行变换结果就全部读空了。

其具体实现的状态机示意图如图8、图10所示，EMIF读写控制逻辑负责从片外SDRAM读出数据，写RAM控制逻辑2负责将读出的数据写入到片上存储器相对应的乒乓结构。图8中，SD＿W＿REQ是写RAM控制逻辑2向EMIF的读写控制逻辑发送的请求读的信号，SD＿W＿ACK是EMIF的读写控制逻辑向写RAM控制逻辑2发送的握手响应信号。当EMIF的读写控制逻辑检测到写RAM控制逻辑2的请求信号，并且此时检测到存储器A空标志时， 开始从SDRAM中按上述方式读出数据写到A，当写满A，设置A的满标志位，且检测到存储器B的空的标志位就开始按上述方式从SDRAM中读出数据写到B，当B写满，就设置B的满标志。然后再检测存储器A的空标志，开始存储器A的写操作，以空标志为每次写存储器的起始信号交替写存储器A和存储器B。另外，当最后读空SDRAM，设置正在写入数据的片上存储器满标志；写存储器的地址是连续的。

图10中，EMIF在上电复位撤销后首先要配置SDRAM，然后接收前级FIFO写入的数据，以接收到帧起始为开始写标志，将数据按照顺序地址写入SDRAM，CNT是计数器用来记录写入数据的个数，接收完毕就等待写RAM控制逻辑2产生的读请求，在接收到请求信号后就开始应答，从SDRAM中读数据并且输出到片上存储器A或存储器B，读地址如上所述。

如图5，读RAM控制逻辑负责将片上存储器的行变换结果转置输出。当需要读取储存器时，先读出第一个数据，然后每隔k个地址再读出存储器中的一个数据，这样重复M次，读出行变换后的二维数据的第一列进行列变换；再从存储器中读出第二个数据，然后每隔k个地址读出存储器中的一个数据，也重复M次，将读出数据进行列变换；依次类推，重复k次，将存储器的k列数据进行列变换。这里的片上存储器是指的存储器A或B中的任意一个。

当最后一次从片外SDRAM读取数据到片上存储器，将SDRAM中的行变换结果全部写到片上存储器后，其读出储存器方式如下：先读出第一个数据，然后每隔N－(q₁+1)*k个地址再读出存储器中的一个数据，这样重复M次，读出行变换后的二维数据的一列送到FFT内核进行列变换；再从存储器中读出第二个数据，然后每隔N－(q₁+1)*k个地址读出存储器中的一个数据，也重复M次，将读出数据进行列变换，依次类推，重复N－(q₁+1)次，将存储器的N－(q₁+1)*k列数据全部送到FFT内核进行列变换。

其具体实现的状态机示意图如图9所示，其中Read＿req是片外输入 的请求读数据的信号，存储器A和存储器B各设置一个满标志位，每次检测该位为高电平，就开始读该存储器。存储器读是按照转置地址进行读的，其方式如上所讲。

上面都是讲述的行变换后的图像数据M*N大于片上存储器的存储容量的情况，而对于行变换后的图像数据M*N小于片上存储器的存储容量时，不需要用到片外SDRAM，所以也无需启动EMIF读写控制逻辑，相对比较简单，易于实现。

本实施例中所设计的FFT内核处理速度可以达到一个时钟周期处理一个数据，那么提高FFT处理器速度的关键是如何提高行转置的速度。转置处理需要先将一帧图像进行完整缓存然后再读出，并且该图像大小范围变化很大，片上存储器远远不能满足存储的需求，采用存储容量比较大的片外SDRAM存储器，能有效地降低设计成本。但是由于SDRAM的行激活预充电刷新的时间要求特性，从行激活指令有效到有效的读写指令，该行必须满足tRCD的时间延迟参数要求，而如果从SDRAM存储器按照列地址进行读操作，送入SDRAM的地址是不连续的，这样就造成在读一列数据时，SDRAM需要进行多次行激活操作，从而使SDRAM的读速率非常低，造成FFT列变换速率的降低。而采用本发明设计的二维FFT处理器行转置架构，充分利用片上存储器，转置操作都在片上进行，片外SDRAM的数据仅需要读到片上存储器进行缓存，然后按照转置地址读片上存储器，这样片外SDRAM就可以连续突发读取，跨行读取的情况大大降低了，FFT列变换速率也相应的提高了。

行转置的最理想的情况是每个时钟周期处理一个数据，这样才能匹配FFT内核的处理速度，本设计的转置速度与理想情况对比：假设SDRAM的每次跨行需要耗费t个时钟周期进行行激活以及预充电操作，本设计与理想情况下对比多出时间就是跨行读的时间，以转置一个512*512的图像为例，片上存储器可以缓存的列数L为240列，片外为272列，根据上文提到的 参数q₁＝3次，也就是需要3次从SDRAM中读取数据到片上存储器才算完成一帧图像的转置。其中SDRAM每个bank的列数设为1024，那么缓存到SDRAM占行数是136行。与理想情况比较，耗费的时间为136*3*t为408t，假设t为16个时钟周期，耗费的时间为6528个周期，相较于理想情况整个转置周期512*512*2为524288个周期，多出了1.2％的时钟周期，与理想情况是很接近的。

尽管本发明的内容已经通过上述实施例作了比较详细介绍，但应当认识到上述描述不应被认为是对本发明的限制。本领域技术人员阅读上述内容后，本发明的多种修改和替代都将是显而易见的，因此，本发明的保护范围应由所附的权利要求的限定。