一种实现混合基FFT末级重排序的映射迭代算法

摘要

本发明属数字集成电路与系统技术领域，具体涉及实现混合基FFT末级重排序的映射迭代算法。FFT的末级重排序模块是保证采用DIF-FFT情况下实现队列顺序输出的必要环节。以往对于这一问题的处理普遍采用bit-reversal算法，但其受限于输入点数必须满足

说明书

技术领域

本发明属数字集成电路与系统技术领域，具体涉及实现混合基FFT末级重排序的映射迭代算法。

背景技术

FFT（快速傅里叶变换）的末级重排序模块是保证采用DIF-FFT（频域快速傅里叶变换）情况下实现队列顺序输出的必要环节。当采用DIF-FFT（频域抽取方式的FFT）时，末级重排序模块确保了最终的序列以自然顺序输出，实现了FIFO（顺序输入、顺序输出），为前后级之间数据的读写提供了便捷。但以往对于末级重排序模块的设计，都是基于bit-reversal的算法，这一算法顾名思义就是将输入的序列的序号以二进制的形式来表示，之后只要对每个序号进行“位反”操作即可，而基-                                                FFT算法本身决定了输出序列排列规律恰好都是由自然顺序的序列进行“位反”操作得到的，因此对于基-FFT的末级重排序模块只要采用bit-reversal的算法就必定能够得到自然顺序的输出序列。前人基于这一算法作了大量的研究以及改进工作：最著名且最高效的bit-reversal算法自从B.Gold和C.M.Rader于1969年在Digital Processing of Signals上提出改进的Cooley-Turkey DFT起已经被广泛地使用了；1991年，Angelo A.Yong在IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS——II:ANALOG AND DIGITAL SIGNAL PROCESSING上发表的论文“A Better FFT Bit-Reversal Algorithm Without Tables”中指出，相比于传统的BRCA(Bit-reversal Counter Algorithm)，其算法将循环次数由原先的N-1减少到N/4，设I是由0~N-1按自然顺序排列的数，基本思想是假设存在4组数（I,J）、（I+1，J+N/2）、（I+N/2，J+1）、（I+1+N/2,J+1+N/2），暂且认为I是偶数且I<N/2，而J对应了I的bit-reversal的值，则显然J+N/2是I+1的bit-reversal的值。

因为I是偶数，因此其最低位是0，则J的最高位必然是0，也就意味着J<N/2；同样因为I是偶数，则I+1必然是奇数，且I<N/2，则；I+1+N/2与J+1+N/2的大小判断相当于是在I、J上各加了一个常数，因此只需判断I、J大小即可决定是否需要做bit-reversal操作。因此，Angelo A.Yong的算法的提出相当于可以根据所有输入的N个点中的前N/2个点来决定所有N个点中哪些需要做bit-reversal操作。

Angelo A.Yong确实针对以往的bit-reversal算法作了改进，使得计算N个输入值的时候循环次数由原先的N-1减少到N/4，提升了系统的运算速度，但这仅仅是针对特定的输入值而言的，即改进后算法的优势仅体现在输入点数为2的整数次幂时、采用基-来实现FFT末级重排序的情况。这明显存在局限性，不能满足一般需求。

发明内容

本发明的目的在于提出一种输入点数是任意合数情况下的FFT末级的重排序算法，以简化输入点数为大点数情况下的繁琐的人工重排序的工作，确保设计的可靠性。 

本发明提供的FFT末级的重排序算法，原始输入序列（下文中统一称其为“参考序列”）的排布方式由变换点数N和两个分解因子、共同决定，具体推导过程如下：

令：           [1]

[2]。

通过以上的推导，可以看出当为参量时，输入变量与输出变量之间的组点DFT，的序列值为。乘以旋转因子后成为新的。分解得到组点DFT，参考序列的排列方式由最终的组点DFT的输出排列方式决定。如表2所示，为了清晰地表示一一对应的关系，左列为由0到N-1按自然数排列的序号，右列为与之对应的参考序列。其中，参数m满足下不等式：

,               [3]。

考虑到m是整数，因此可以得到：

              [4]。

由于具体硬件实现时，每次输入的N点的次序都是恒定的，即每次末级重排序模块接受的输入序列的次序恒定，因此映射迭代函数的建立基于第一组N点的逆序输出。则相邻两组N点输入经过FFT变换后的输出向量组之间可以建立起如下关系式：

，    [5]。

由于相邻两向量组之间的元素之间的映射关系满足单一对应，因此变换矩阵是一个由N个变换函数构成的对角阵，其中变换函数可以由如下表达式给出：

      [6]。

假设经过n-1次迭代之后，得到向量组，即：

 [7]

再经过第n次迭代之后得到:

 [8]。

即回到向量组的初态，则基于当前映射迭代的关系收敛于n。本发明的映射迭代算法中含有3个参量：N、、，当三者确定之后，迭代的过程等价于有限域上的取余运算，因此必然有迭代严格收敛于。

    本发明在给出映射迭代算法后，同样致力于硬件实现。为了使系统的吞吐率尽可能地大，FFT的设计采用了“并行+流水”的结构实现。在流水线处理中，首先要明确的就是系统的延迟，即从第一组数据输入直至有效数据开始输出所经历的时间。假设FFT变换后的输出序列为X(k)，则经过重排序后第一组输出的向量组为，则关键路径取决于获得X(p-1)所需的时间间隔，即在当前的架构下，系统的延迟可由下式决定：

  [9]。

其中，p表示“并行路数”，由上式可知：当X(p-1)到来的时刻起，每隔一个时钟周期就会有一组含有p个元素的向量组输出，同时伴随相应的p个下一周期的输入元素来填入空缺位置，填补好的元素也就是下一轮映射迭代的初值，这也就形成了输入、输出元素之间动态平衡的过程，因此，基于流水线结构的设计决定了本发明对于存储空间的需求恰好为N。

表1为当输入点数为32、按照的混合基方式分解时，以本发明的映射迭代算法实现FFT末级重排序的向量组变换举例。

表2为初始参考序列中的元素排布规律。

具体实施方式

以下结合实施例进一步描述本发明。

按照本发明中的映射迭代算法，当FFT的输入点数满足是非零自然数的混合基的方式分解时，均能保证在变换函数满足如下关系：；

以为例，输入FFT末级重排序模块的初始向量组如表1中的（1）列所示，其对应了采用的混合基分解方式时32点FFT的最后一个环节：4组8点DFT的输出。由参考序列起，经过5轮循环迭代后，最终向量组以自然顺序输出，如（5）列所示，第6轮迭代开始后，向量组以顺序方式读取，而输出则又回归到的混合基分解方式，如（1）列所示。

如表1所示，设为一个时钟周期，则若要对X(0)~X(3)进行输出必须经过的最短时间间隔分别为：1、3、5、7，而为了提高系统吞吐率，当前的FFT变换采用的是“4路并行+流水线”的架构，即第一组输出的向量组为，因此完成第一组向量组的输出的延迟取决于：   [10]。

由表1可以看到，参考序列采用的是的分解，在变换过程中依次经历了、、、最后又回归的分解的情形。显然，对于设计者而言，初始的分解过程可以是任意的，而任意一种分解方式的选取都势必遍历且仅遍历上述种分解情形，符合上文中论证的按照（是非零自然数）的混合基的方式分解，则无论的取值如何，都能满足映射向量组的个数。

表1

表2

自然序列参考序列………………………………