关键字 |
| 快速傅立叶变换(FFT)， FPGA，新分布式算法(NEDA)，基数-4，改进的CSLA |
介绍 |
| 今天的电子系统大多靠电池运行，从而使设计具有硬件效率和电源效率。应用领域，如数字信号处理，通信等采用数字系统执行复杂的功能。这些系统最需要的是硬件高效和节能的体系结构，以实现最大的性能。 |
| 傅里叶分析是以法国数学家、物理学家让·巴蒂斯特·约瑟夫·傅里叶(1768 - 1830)的名字命名的。约瑟夫·傅立叶在19世纪早期研究热的传播时，提出了调和级数的概念，它可以描述任何周期运动，而不管其复杂性如何。后来，傅里叶变换(FT)取代了傅里叶分析(Fourier analysis)，并由傅里叶变换(FT)衍生出许多方法。一般来说，傅里叶变换是将被测信号与其频率含量联系起来的数学过程。 |
| 傅里叶变换是分析信号的几种数学工具之一。它涉及到信号在频域的正弦或协正弦分量的分解。下面给出了连续FT (CFT)的数学定义。 |
 |
| 式中x(t)为原始信号，x(ω)为信号在频域的表示，j为虚数，ω为角频率，t为时间指数。连续傅里叶变换(ICFT)的逆函数定义为; |
 |
| 连续时间周期信号和有限能量非周期信号可以用傅立叶级数表示来定义。此外，在实际应用中，离散时间信号可以在有限时间内表示。对于有限长度的信号，另一种变换称为离散傅里叶变换(DFT)，它在频率上是离散的。离散时间信号的频率范围是在-π到π的区间内定义的。由N个采样点组成的周期数字信号，是通过分频域将频率分量分成2π/N弧度的区间。然后，离散时间信号的傅立叶级数表示将由Kuo等人(2001)的N个频率分量组成。周期信号(x(n))的一般傅立叶级数表示为: |
 |
| 其中N是与指数函数(e jk(2n/N) N)有关的谐波指数，k= 0,1，…，N-1, ck是傅立叶级数的系数。系数ck的计算公式为: |
 |
| 傅立叶级数的系数ck是基周期为n的周期序列的形式，周期信号的时域频谱可以用DFT表示为周期序列。离散周期信号(sin(nt)和cos(nt))的频率分析涉及时域信号的傅里叶变换。DFT定义为N个样本x(N)与N个离散频率的乘积。这些样本在离散频率下采集(ωk=2πk/N)，其中k=0,1，…N-1，在0≤ω≤2π之间。这意味着X(ω)在连续的样本中由等间隔的频率计算。X(ω)如下所示。 |
 |
| DFT是时域N个样本x(N)到频域N个样本x(ω)的映射。这为计算周期信号和有限长度信号的DFT提供了机会。利用离散傅里叶反变换(IDFT)可以将周期序列的频域频谱重新得到为周期信号。IDFT可以用X(k)的频率样本来定义。如下所示。 |
 |
| IDFT通过将X(k)的频谱变换回X(n)的原始时间序列，表明不存在损失信息。 |
| DFT已经在许多领域得到了广泛的应用;下面我们只列举了几个例子(也可参阅文章末尾的参考资料)。DFT的所有应用都依赖于一种快速算法的可用性来计算离散傅里叶变换及其逆，即快速傅里叶变换。 |
| 由于FFT在现代电子系统中的应用能力提高，更高基数的FFT如基数- 4，基数- 8，基数- 2K，分割基数等被设计用于改进计时和减少硬件。这些方法的基本区别在于它们的蝴蝶单元的结构。 |
NEDA |
| 在许多数字信号处理(DSP)系统中，采用分布式算法(DA)来实现乘加(MAC)单元。DA消除了用作MAC单元一部分的乘法器的需要。它通过预计算所有可能的产品并使用只读存储器(ROM)存储它们来实现MAC单元。如果一组输入有一个固定的值，ROM就可以消除。这可以通过将系数分配到单元的输入来实现。这种方法被称为新分布式算法(NEDA)。因此，使用NEDA，任何类似MAC的单元都可以通过使用加法器和移位器来实现。体系结构设计采用DA方法或CORDIC单元方法实现FFT，其中ROM作为设计的基本单元。所提出的方法是基于NEDA，它不需要任何ROM，从而使设计减少了硬件。系数的分布是最优的，以进一步减少冗余硬件单元。新的分布式算法(NEDA)技术正在许多需要MAC单元的数字信号处理系统中得到应用。 Transforms such as FFT, DCT, etc. have many multiplications that in turn require a number of multipliers. Implementation of such transforms using NEDA improves performance of the system in terms of speed, power and area. The mathematical derivation of NEDA is discussed as follows. Inner product calculation of two sequences may be represented as |
 |
| 式(7)的矩阵表示形式为 |
 |
| 考虑到“词”和“喜”都是2的补体形式，可以用“式”表示 |
 |
| 其中Ci= 0或1,k=N,N+1，…，M, Ci M是符号位，Ci N是最低有效位。将式(9)代入式(8)得到如下矩阵乘积，根据所需设计建模。 |
 |
| 包含Cik的矩阵是一个稀疏矩阵，这意味着值不是0就是1。C矩阵的行数决定了固定系数的精度。将式(10)重新排列如下所示。 |
 |
 |
| W矩阵由输入的和组成，取决于每一行的系数值。下面将讨论一个展示NEDA操作的示例。考虑计算式(12)的值。 |
 |
| 式(13)可以用式(10)表示，如式(14)所示。 |
 |
| 式(14)可改写为 |
 |
| 应用精确移位，将式(15)改写为 |
 |
| 因此，与实现式(15)相比，实现式(16)进一步减少了加法器的数量。通过移位器可以实现与2i, i属于Z+的乘法。在式(16)中，X矩阵的第一行右移1位，第二行右移2位，以此类推。更准确地说，所进行的移位是算术右移。如果我们需要偏积，输出Y可以实现为一个列矩阵。因此，与传统的MAC单元相比，基于NEDA的架构设计具有更少的关键路径。 |
提出了基4算法 |
| 在数字信号处理的许多应用中，离散傅里叶变换(DFT)起着重要的作用。DFT已广泛应用于线性滤波、频谱分析、数字视频广播和正交频率解调复用(OFDM)等领域。快速增长的基于OFDM的应用需求，包括局域网等现代无线通信，需要快速傅里叶变换算法的实时高速计算。这使得FFT处理器的设计成为未来无线技术的关键要求。 |
| 随着这一需求的出现，高性能VLSI FFT架构的研究也变得越来越重要。为了实现FFT算法，已经提出了许多不同的硬件架构。设计方法的主要关注点是功率和建筑尺寸。在各种FFT算法中，基于Cooley-Turkey算法的基数-2 FFT因其高效地利用了对称性而备受欢迎。为了进一步降低计算复杂度，在Cooley- Turkey算法的基础上，提出了多种架构，包括基4、基2和分裂基。该快速傅里叶变换算法采用分治法递归划分计算量，然后提取尽可能多的公共旋转因子。所需要的实际加法和乘法的数量通常用来比较不同的FFT算法的效率。在乘法比较方面，分裂基FFT在计算上优于所有其他算法，因为它有大多数平凡的乘法。最终，该算法由于结构不规则而存在缺陷，不适合在数字信号处理器上实现。在专用芯片(如ASIC(应用专用集成芯片))上实现FFT算法时，结构的规律性也很重要。 Hence, radix-2 and radix-4 FFT algorithm are preferable in terms of speed and accuracy. |
| 本文提出了一种基于基-4的16点复FFT算法。利用NEDA实现了该过程中需要的复杂乘法运算。根据基数-4算法，实现16点FFT需要8个基数-4蝴蝶。四个基-4蝴蝶在第一阶段使用，其他四个在第二/最后阶段使用。输入按正序进行，输出按位反转顺序进行。 |
| 每个基数为4的蝴蝶的输出乘以各自的旋转因子。在所示的方框图中，第一阶段由四只基4蝴蝶组成。蝴蝶的输入是s(n)， s(n+4)， s(n+8)， s(n+12)其中第一个蝴蝶的n为0，第二个蝴蝶为1，第三个蝴蝶为2，最后一个蝴蝶为3，都是第一阶段。旋转因子由w160, w16q, w162q, w163q给出，其中第一个蝴蝶的q为0，第二个蝴蝶的q为1，第三个蝴蝶的q为2，最后一个蝴蝶的q为3，都是第一阶段。第一阶段的输出与相应的旋转因子相乘，并作为第二阶段的输入。在我们的设计中 |
| 在16点FFT处理器的第一级输出中需要NEDA块。在第二阶段，使用了4个以上的基-4蝴蝶块。第二阶段中的第一根-4蝴蝶取第一阶段中使用的4根-4蝴蝶块的第一输出。第二阶段中的第二个基数-4蝴蝶获得4个基数-4蝴蝶块的第二个输出，然后是NEDA块(如果需要)。这一过程继续到第二阶段的其余基-4蝴蝶块。在第二阶段之后不需要使用任何NEDA块，因为旋转因子W16 0等于1乘以第二阶段的输出。最终输出以位反转的顺序出现。采用基数-4算法的优点是保留了基数-2算法的简单性，并给出了复杂度较低的输出。所提出的框图中所示的NEDA块对第一阶段的输出和各自的旋转因子进行复杂的乘法运算。这里使用的旋转因子值如下。 |
 |
| 基4蝴蝶的基本结构如图2所示。它有四个输入和四个输出。 |
Neda使用进位选择加法器和修改进位选择加法器 |
| 在NEDA部分中，进位选择加法器用于加法。在超大规模集成电路(VLSI)系统设计中，面积和功率效率高的高速数据路径逻辑系统的设计是最重要的研究领域之一。在数字加法器中，加法的速度受进位运算在加法器中传播所需时间的限制。初等加法器中每个位位置的和仅在前一个位位置被求和并且进位传播到下一个位置之后才按顺序生成。 |
| CSLA在许多计算系统中都是通过独立生成多个载波，然后选择一个载波生成和来缓解载波传播时延的问题。然而，CSLA的面积效率不高，因为它使用多对Ripple进位加法器(RCA)，通过考虑进位输入Cin=0和Cin=1来生成部分和和和进位，然后由多路复用器(mux)选择最终的和和进位。 |
| 16-b正则CSLA结构如图3所示。它有五组不同大小的RCA。 |
| 在常规CSLA中，使用二进制到超1转换器(BEC)来代替Cin=1的RCA，以实现更低的面积和功耗。这种BEC逻辑的主要优势在于，与n位全加法器(FA)结构相比，逻辑门的数量较少。 |
| 利用BEC for RCA (Cin=1)优化面积和功率的16-b CSLA结构如图4所示 |
结果与讨论 |
| 从Xilinx ISE 13.2获得的不同Virtex FPGA的综合报告如下表所示。表i给出了使用CSLA进行NEDA FFT的Virtex 6 FPGA和使用改进CSLA进行NEDA FFT的Virtex 6 FPGA的设备利用率摘要。使用修改后的CSLA, NEDA的设备利用率更低。 |
| 表格II给出了使用CSLA进行NEDA FFT和使用改进CSLA进行NEDA FFT的Virtex 6 FPGA的功率和延迟。与使用CSLA的NEDA相比，使用改进的CSLA的NEDA使用更少的功率。 |
| 表格III给出了Virtex 5 FPGA用于使用CSLA的NEDA FFT和使用Modified CSLA的NEDA FFT的设备利用率摘要。 |
| 表格IV给出了Virtex 5 FPGA的功率和时延，用于使用CSLA的NEDA FFT和使用改进CSLA的NEDA FFT。 |
| 表格V给出了Virtex 4 FPGA的设备利用率摘要，用于使用CSLA的NEDA FFT和使用Modified CSLA的NEDA FFT。 |
| 表格VI给出了Virtex 4 FPGA的功率和时延，用于使用CSLA的NEDA FFT和使用改进的CSLA的NEDA FFT。 |
结论 |
| 设计了基于NEDA和改进CSLA的radiad4复合16点FFT内核。这是一种无rom和无乘数的方法。所提出的设计在硬件和功耗方面是高效的。快速傅里叶变换(FFT)是一种计算离散傅里叶变换及其逆的有效算法。DFT将一组值分解为不同频率的分量。这个运算在很多领域都很有用，但是直接从定义来计算它通常太慢而不实用。 |
| 使用NEDA，任何类似MAC的单元都可以通过使用加法器和移位器实现。现有的体系结构设计采用DA方法或CORDIC单元方法实现FFT，其中ROM作为设计的基本单元。所提出的方法基于NEDA，不需要任何ROM，从而使设计减少了硬件。系数的分布是最优的，以进一步减少冗余硬件单元，从而减少硬件。系数的分布是最优的，以进一步减少冗余硬件单元。新的分布式算法(NEDA)技术正在许多需要MAC单元的数字信号处理系统中得到应用。FFT、DCT等变换有许多乘法，而这些乘法又需要许多乘法器。使用NEDA实现这种转换可以提高系统在速度、功率和面积方面的性能。本文采用ModelSim进行仿真，Xilinx ISE项目导航器进行综合。综合结果表明，采用该方法计算16点FFT在面积和功率方面都是有效的。 |
表格一览 |
|
|
|
数字一览 |
|
|
|
参考文献 |
- C. González-Concejero, V. Rodellar，“FFT算法的便携式硬件设计”，拉丁美洲应用研究，37:78-82,2007。
- AsmithaHaveliya, Amity大学勒克诺，印度“32点FFT的设计与仿真使用基数-2算法的fpga实现”第二届国际先进计算与通信技术会议，2012
- B. Ramkumar和Harish M Kittur，“低功耗和区域效率进位选择加法器”，IEEE超大规模集成系统汇刊，VOL。2,没有。2,页。371 - 375年,Feb.2012。
- 陈纳图切里，“一种减小FFT实现面积和功率的新方法”，中华人民大学学报(自然科学版)。电气，电子和仪器工程高级研究，卷。2,页130 - 138。
- Alban Ferizi,BernhardHoeher, Melanie Jung, Georg Fischer，和Alexander Koelpin，“无线传感器网络中本地定位优化的定点基- 4FFT的设计和实现”，国际。Multi-Conf。系统。信号与设备，第1 - 4页，2012年3月。
- 李文琪，王轩，孙祥然，“高性能FFT处理器的设计”，国际。参看。Edu。技术与计算，卷。5，第139 - 143页，2010年6月。
- M. Hasan, T. Arshan，和J.S. Thomson，“一种基于系数排序的低功率流水线基-4 FFT处理器的无线局域网应用”，IEEE Trans。消费电子:128-134,2003。
- Stanley A. white，“分布式算法在数字信号处理中的应用:教程回顾”，IEEE ASSP杂志，第6卷，第1期。3页。4 - 19。
|
菜单
