英语原文共 5 页，剩余内容已隐藏，支付完成后下载完整资料
为MIMO处理双数据流的正规I/O编序基2 FFT架构
作者：
摘要：如今，许多应用要求在正规编序下对多重独立快速傅里叶变换运算及其输出的同时计算。本简报介绍了一种针对双独立数据流FFT运算的新型流水线FFT处理器。提出的结构是基于多路径延迟换向器FFT结构。它分别按时间FFT和频率FFT抽取N/2的点去处理来自两组数据流的奇数和偶数样本。该结构的主要特点是位反转操作由其自身执行，所以输出生成于正规编序而没有用到任何专用位反转电路。位反转的操作是由FFT结构中的移位寄存器糅合数据完成的。因此，该结构需要更少的寄存器却有高输出量。
关键词：位反转，位逆序，快速傅里叶变换（FFT），多路径延迟换向FFT，正规编序
Ⅰ.介绍
FFT是无线通信应用中最通用的操作之一，例如正交频分复用访问，超宽带，地面数字视频广播，信号处理应用等等。[1]中讨论了一组流水线FFT结构，其中单路径延迟反馈和多路径延迟换向器最为热门。许多应用需要处理多组数据流，例如图像处理，阵列信号处理，多输入多输出正交频分复用技术等等。因此在正规编序下生成输出需要同时多路FFT操作和专用位反转电路。
参考文献[2]-[5]中的FFT结构可以处理多组独立数据流。然而，在[2]和[5]中是通过单FFT处理器处理所有数据流。[5]中四组数据流逐一处理，相似的，在[2]中八组数据流在两个域中被处理。从而在平行下多数据流的输出并不可用。为了同时处理数据流，需要使用多个FFT处理器。[3]中则使用多数据路径去处理1到4组数据流以服务于无线本地局域网络应用。在[4]中不同数据流中的数据被交织以便同时处理。不过[2]-[4]中的结构没有用到任何专用位反转电路。
参考文献[6]-[9]中提出以一定的电路重新排序位反转FFT的输出至正规编序。[8]中位反转电路是对于不同的根。[9]中提出一个服务于可变长度FFT的寄存器复杂度为N的相似结构。这些电路适用于将流水线FFT结构中的数据位反转。然而[8]和[9]中只提到了位反转结构体。[6]中位反转电路被整合到FFT结构中，结果是寄存器的需求量从5N/2下降到2N。[10]中提到了按频率抽取二,四,八平行流水线式基2k前馈FFT结构，而且需要额外N个寄存器去生成在正规编序下的输出。此外二,四,八平行FFT结构分别只在样本x(n N/2)，x(n 3N/4)和x(n 7N/8)到来时运作。因此，硬件为充分利用且需要附加寄存器去存储第一个N/2，3N/4，和7N/8样本。
参考文献[7]中提出一个修改的带有新数据调度方式的多路径延时换向器FFT，还有抛弃[10]中缺点的重排结构。[2]-[6]以及[8]-[10]中的结构以传入采样率的频率运行，但是[7]中的结构仅以一半的时钟频率运行生成和[2]-[4]，[6]，[8]-[10]中相同的输出量。从而如果所有结构运行在相同的速度下，[7]中的结构会产生翻倍的输出量。同样地，[11]中提出了一种具有正规编序I/O的单路径延时换向器SDF-FFT结构，其中位反转操作仅需N/2个寄存器。然而它的输出量很低，并且所需寄存器数量较大。在[12]中提出了低复杂度的FFT结构，但这些结构仅能处理实值信号（信号仅有实部）。此外，他们在每个时钟周期产生两个输出，且输出不符合正规编序。因此近来大部分结构都需要位反转结构体去生成正规编序下的输出。
该文提出的结构设计为以更少的硬件需求量来同时处理两个独立的数据流。先将正规编序下的奇数输入位反转，再用周期FFT中抽取的N/2点对奇数输入进行处理。均匀样本直接被DIF-FFT的N/2点处理，因此输出是位逆序的。因此DIF-FFT的N/2点的输出是位反转的。两个N/2点FFT的输出被两个平行蝶进一步处理以正规编序产生n点FFT的输出。完成位反转操作的调度寄存器实际是用来为蝶形操作延时样本。从而该FFT结构不需要专用电路来将数据位反转。因而该FFT结构设计比先前的FFT结构需要更少的寄存器。
提议的结构会在第Ⅱ节中详细地解释。在第Ⅲ节中会将该结构的结果与已有的设计进行比较。结论将会写在第Ⅳ节中。
Ⅱ.流水线式FFT结构
用两个N/2点FFT操作以及蝶形操作的一阶段来计算N点FFT的想法展现在Fig.1中，虽然不是精确的结构但也提供了方法。Fig.1中的重新排序块存在就是为了说明N/2奇数样本（x（2n 1））在N/2时域采样点FFT操作之前重新排序，N/2偶数样本（x（2n））在N/2频率采样点操作之后重新排序。为了从两个N/2点FFT的输出中计算N点DIT FFT，对两个FFT的结果执行额外的一个阶段的蝶形操作。因此，产生的产出通过额外的蝴形阶段是正规编序的。
Fig.1
简便起见，提出的16点FFT结构已在Fig.2中解释。它有两个8点MDC-FFT结构来处理两组数据流。在SW1左侧存在的延迟换向器单元分离了奇数和偶数样本。延迟换向器单元中接收输入的移位寄存器，用于位反转奇数输入样本。这些移位寄存器被称为重新排序移位寄存器（RSR）。RSR在最后阶段存储8点D IF- FFT的输出，并位反转它们，BF2在RSR的位反转数据之间进行双并行蝶操作，并从八点DIT FFT输出。因此上下的BF2按正规编序在最后阶段生成第一和第二数据流的FFT输出。将来自SW2的两条数据路径组合在一起，因此最后阶段数据路径的字长为两倍，所以使用如此粗的线条来表示数据路径和寄存器。
A：结构的运行
Table.1
Fig.2
Fig.2中的FFT结构被分为（L1，L2，L3，M1，M2，M3）六个层次。L1和M1中的RSR将奇数输入数据重新排序，L3和M3中的RSR将部分处理的偶数数据重新排序。8点DIF和DIT FFT操作分别在L2和M2中执行。L1和M1的数据在SW1的帮助下分别前递给L2和M2，反向亦然。同样地，L2和M2的数据在SW2的帮助下分别前递给L3和M3，反向亦然。SW1和SW2有两个开关用来交换数据路径或者扩散数据到其它层。在正常模式下，开关（SW1，SW2）会把u1,u2,u3和u4的数据分别传送到v1,v2,v3和v4。在交换模式下，开关（SW1，SW2）会把u1,u2,u3和u4的数据分别传送到v3,v4,v1和v2。SW1在前N/2个时钟周期处于交换模式，在第N/2 1到第N个周期处于正常模式。而SW2在前N/2个时钟周期处于正常模式，在第N/2 1到第N个周期处于交换模式。因此SW1和SW2在任何时间都处于不同的模式，且都是每N/2个周期改变工作模式。此外，如果在Ly和Ly 1或者My和My 1（y只能是1或2）之间有数据过渡，开关（SW1或SW2）随后便工作在正常模式，如果在Ly和My 1或者My和Ly 1（y只能是1或2）之间有数据过渡，开关（SW1或SW2）随后便工作在交换模式。就像该设计中的其他控制信号，开关（SW1和SW2）的控制信号由外部提供且在每N/2个时钟周期进行交换。
输入到FFT处理器的两组数据流显示为X1和X2。两组数据流的奇数和偶数样本被L1和M1的延时换向器单元解离了（X1被分解为{E1（i，j）和O1（i，j）}，而X2被分解成{E2（i，j）和O2（i，j）}）。在这些表示中，i定义了数据的性质，j定义了数据的数值，规定了什么FFT需要被计算。输入数据的偶数组[X（0），X（2），X（4）...]被限定为E（1，j）的形式，输入数据的偶数组[X（1），X（3），X（5）...]被限定为O（1，j）的形式。E（2，j）/O（2，j）是一组预定的或者规定的偶数比奇数的数值，并准备好馈送给8点DIT/DIF FFT。8点DIT/DIF FFT的输出定义为E（3，j）/O（3，j），并馈送给第三级用于16点FFT计算。表格Ⅰ解释了FFT的运作方式和不同级之间的数据传播。
- X1的首八个样本被载入到L1的寄存器中（延时换向器单元上下臂的4D）。八个时钟周期后，开关SW1被置为正常模式，X2中的首八个样本被载入到M1的寄存器中（4D）。E1（1,1）（X1的奇数样本）由L1递送到L2作为E1（2,1）去执行8点FFT操作。X1和X2的偶数样本分别被L1和L2的RSR位反转。位反转的操作在第Ⅱ节B部分中作解释。
- 经过八个时钟周期，开关SW1和开关SW2分别被置为交换模式和正常模式。X1的奇数样本O1（1,1）从L1前递到M2成为O1（2,1），X2的偶数样本E2（1,1）从M1前递到L2成为E2（2,1）。同时E1（2,1）从L2前递到L3并完成重新排序。
- 又经过八个时钟周期，开关SW1和SW2分别被置为正常模式和交换模式。X2的奇数样本O2（1,1）被从M1前递到M2成为O2（2,1），并将O1（2，1）从M2前递到L3成为O1（3,1），并在L3执行相当于数据流X1最后阶段的与E1（3,1）的蝶形操作。同时，从L2的E2（2，1）被前递到M3，作为E2（3，1），并在RSR中进行重新排序。同时将E2（2，1）从L2前递到M3成为E2（3，1），并在RSR中完成重新排序。
- 经过八个时钟周期后，开关SW2被置为正常模式以允许部分处理的奇数样本（O2（3，1）从M2到M3，并执行数据流X2最后阶段的与E1（3，1）的蝴蝶操作。
除了基数-2FFT，如图Fig.2所示，任何更高的基数FFT结构都可以使用。在图Fig.3中采用两个基数23 64点FFT实现128点FFT，其乘法器复杂度为4（log8（N/2）-.5），工作和16点FFT完全一样。N点基数k FFT算法的乘法器复杂度为4（logk（N/2）-.5）。
Fig.3
Fig.4
Table.2
Table.3
B：位反转
所提出的结构受启发于[7]中的结构，其中第一个蝴蝶单元之前的N/2数据调度寄存器被用来从偶数样本中分离奇数样本和延迟它们并行生成x（N）和x（N/2）。在提出的结构中，该数据调度寄存器被重复使用来位反转奇数样本。同样，在最后一个蝴蝶单元之前的N/2数据调度寄存器用来存储部分处理的偶数样本，直到[7]中的奇数样本到达，在这里这些寄存器是重复使用来位反转部分处理的偶数样本（D IF FFT输出的）。在[8]中，提出了使用复用器和移位寄存器进行位反转的电路。.根据[8]，如果N是r的偶数幂，则位反转N数据所需的寄存器数为。如果N是r的奇数幂，则位反转N数据所需的寄存器数为，r是FFT算法的基数。提出的结构中，这些位反转电路被包含在数据调度寄存器中，以承担双重角色。
在16点FFT和64点FFT架构中使用的RSR如图所示分别为Fig.4（a）和（b）。实际上，这些结构存在于标有RSR的移位寄存器的位置。广泛用于N点的RSR呈现在Fig.4（c）其中c0是或者。c0中这些寄存器不涉及重新排序。RSR中多路复用器的控制信号被适当的变化，以交织数据。如果log2N是偶数，则需要log2N-2复用器，否则需要log2N乘法器来进行位反转。关于位反转的更多细节，可以参考[8]。
在所提出的FFT结构中，第一个N/4和下一个N/4输入到DIF FFT的奇数数据被分别被位反转，因为它们需要并行。因此，N/4点位反转算法就足够了，位反转N/4数据所需的寄存器数要么是，要么是取决于两个数据的幂。在图Fig.2中M1的RSR（R1-R4）位反转首N/4奇数输入数据[X（1）、X（5）、X（3）和X（7）]，并将它们存储在R5-R8[X（1）、X（5）、X（3）和X（7）]中。在此之后，下一个N/4奇数输入数据[X（9）、X（13）、X（11）和X（15）]在R1-R4[X（9）、X（13）、X（11）和X（15）]中被反转，如表TableⅡ所示。L1和M1中的延迟换向器单元将位反转的奇数输入样本分别馈送到u1和u2，以及u3和u4（在SW1中）。同样，在M3中RSR（R9-R12）位反转第一个DIT FFT N/4输出数据[X（0）、X（2）、X（4）和X（6）]，RSR（R13-R16）位反转下一个DIT FFT N/4输出数据[X（8）、X（10）、X（12）和X（14）]，具体解释见表TableⅢ。因此，L3和M3中的RSR分别反转了v1和v2、v3和v4（SW2的）的部分处理的偶数数据样本，并（通过O1和O2）馈送到BF2。
Ⅲ.对比
虽然[2]-[5]中提出了几种处理多个独立数据流的结构，但同时每个数据流并不是由单个FFT处理器处理的。此外，[5]中的体系结构存在缺点，如每个数据流的通量低，需要复杂的双端口RAM。表四中列出的结构[5]的计算复杂性对应于两个流当两个流被提出的结构处理。如果[6]、[7]中的单流结构需要处理两个或多个流，则需要并行使用两个或多个这样的结构。
虽然[10]中的四并行结构并行生成四个输出，但其硬件利用率仅25%，需要额外的3N/4寄存器才能在实时应用中保存第一个3N/4数据。 在[8]和[9]中，只针对SDF和MDC结构提出了重新排序电路，因此在表四中，加法器和内部寄存器的复杂性与MDC和SDF结构保持不变。表四有两种类型的寄存器，即内部寄存器（Int 寄存器，用于执行FFT操作）和重新排序寄存器（Reo寄存器，用于按正常编重新排序FFT输出）。NS是处理的独立数据流的数目。在FFT计算单个数据集时使用架构的程度称为利用率，它等于Toperation/（Toperation Tidle）。Toperation和Tidle分别是结构运行和空闲的时间段。其中NPlt;
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[240957]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
