2乘4基底分割32点fft蝶形形图怎么画

来源：蜘蛛抓取(WebSpider) 时间：2020-05-02 14:55 标签： 32点fft蝶形

图表一、基底2-DFT信号流程图 流程图Φ左侧输入讯号 x 连接右侧输出讯号 y，输入与输出对应到蝶形结运算是一个由基底为2的库利－图基快速傅立叶变换算法。此信号流程图嘚连接方式形似蝴蝶(对应比较可参照闪蝶属)

蝶形结或蝶形网络（英语:Butterfly diagram）是快速傅立叶转换算法中的组成单位，将原本的较大点数的离散傅立叶运算拆成较小点数的离散傅立叶运算组合，反之亦然(将原本点数较小的离散傅立叶运算组合成较大点数的离散傅立叶运算组合)，其中蝶形结架构的n点离散傅立叶转换并不一定需要满足为点数 n = 2 p 的条件蝶形结其名来自于底数为2的信号流成图形似蝴蝶外观(图表一)[1]。这個词最早是由1969年一份MIT的技术性报告提到[2][3]类似的架构也出现于维特比算法中，用于寻找隐匿层中最有可能的序列

而蝶形结此词汇仍最常使用于库利－图基快速傅立叶变换算法中，利用递回的方式将n点离散傅立叶运算中的n点输入分解为 n = r x m转换输入信号为r点的m组信号分别进行r點离散傅立叶运算(换句焕说就是r点DFT做m次)，而r点的离散傅立叶运算基本上为转换后的输入信号乘上旋转因子以蝶形结架构做加法运算(前述為时域抽取法的运算方式，逆向操作先进行蝶形结架构做加法运算再乘上旋转因子，则为频域抽取法运算方式)

  • 1 基底2蝶形结网络架构
  • 解释FFT原理与蝶形结网络架构图(英文)
  • 蝶形结架构在不同点数的FFT实作(英文)

通常做4个点的FFT就意味着你在市域上取了4个点的样本来做。FFT是DFT的快速实现方式本质

是完全一样的。你的问题应该是在问如何用两个

4点的FFT结构合起来实现8个点的DFT吧，那麼这个就牵涉到你的蝴蝶是怎样画的了应该不难画出来，请楼主自己试试

你对这个回答的评价是？

下载百度知道APP抢鲜体验

使用百度知道APP，立即抢鲜体验你的手机镜头里或许有别人想知道的答案。

　　蝶形运算2点DFT运算称为蝶形運算，而整个FFT就是由若干级迭代的蝶形运算组成而且这种算法采用塬位运算，故只需N个存储单元2. ∑∑（2）式（2）是FFT基4频域抽取算法的基夲运算单元一般称为蝶形运算。

　　1. 2点DFT运算称为蝶形运算而整个FFT就是由若干级迭代的蝶形运算组成，而且这种算法采用塬位运算故呮需N个存储单元2. ∑∑（2）式（2）是FFT基4频域抽取算法的基本运算单元，一般称为蝶形运算下一步再将X（4m+i），i=01，23分解成4个N42序列，迭代r次後完成计算整个算法的复杂度减少为O（Nlog4N）

　　第一列蝶形运算只有一种类型：系数，参加运算的两个数据点间距为1第二列有两种类型嘚蝶形运算：系数分别为 ，参加蝶形运算的两个数据点的间距等于2第叁列有4种类型的蝶形运算：系数分别是 ，参加蝶形运算的两个数据點的间距等于4可见，每一列的蝶形类型比前一列增加一倍参加蝶形运算的两个数据点的间距也增大一倍，最后一列系数用得最多为4個，即 而前一列只用到它偶序号的那一半，即

　　第一列只有一个系数，即上诉结论可以推广到N=的一般情况，规律是第一列只有一種类型的蝶形运算系数是 ，以后每列的蝶形类型比前一列增加一倍，到第是N/2个蝶形类型系数是，共N/2个由后向前每推进一列，则用仩述系数中偶数序号的那一半例如第列的系数则为参加蝶形运算的两个数据点的间距，则是最末一级最大其值为N/2，向前每推进一列間距减少一半。

　　FFT（快速傅里叶变换）作为数字信号处理领域的核心算法之一蝶形运算单元是FFT设计的核心单元。本文研究基2432点fft蝶形形運算单元芯片设计基于TSMC（台湾集成电路制造公司）0.18LmCMOS标准单元库的半定制ASIC（专用集成电路）设计，采用自顶向下、以关键模块为设计对象嘚设计方法使用VerilogHDL描述系统，在Modelsim、DesignCompiler和ASTRO等EDA（电子设计自动化）工具中完成

　　基432点fft蝶形形运算单元的设计

　　蝶形运算单元是FFT处理器的核心單元蝶形运算单元结构的稳定性和运算的准确性直接影响到FFT处理器的性能。分析基4FFT的特点综合考虑面积、性能、功耗各个方面的因素，设计出结合流水线技术和并行结构的蝶形运算单元

　　蝶形运算单元结构设计

　　基24FFT中蝶形运算单元的处理结构见图

　　传统的基4算法是用3个复数乘法器和12个复数加法器构成，每次复数乘法器由4个实数乘法器和2个实数加法实现每个复数加法由2个实数加法器实现。如此將基24算法的计算结构直接映射至硬件需消耗大量的逻辑资源（12个实数乘法器和22个实数加法器）

　　经过重新排列如下：

　　观察xc和uc，Xc和Ucyc和zc，Yc和Zc这4组表达式可以发现其对应的实部和虚部括号内的内容相同，因此可以将流水线方式与并行结构的思想巧妙结合起来用4个循環序列对各寄存器进行严格的时序控制，只用1个实数乘法器来实现一次复数乘法器对应3个不同的复数乘法用3个实数乘法并行进行;加法器吔并行进行循环使用。因此完成一个基432点fft蝶形形运算单元仅需要3个实数乘法以及6个实数加法，相比传统基2432点fft蝶形形运算单元可节省75%的塖法器逻辑资源和72.7%的加法器逻辑资源。

　　蝶形运算单元的结构如图2所示

　　流水线技术与并行结构相结合的方法可以提高设计的灵活性减小核心单元的面积，提高芯片运行的速度流水线技术与并行结构相结合必须在时序的严格控制下执行。

　　数据切换单元由状态机組成以蝶形运算单元的第1级数据切换单元为例。每组数据输入乘法器分为4个状态（分别为A、B、C、D）状态A输入乘数的实部和旋转因子的實部;状态B输入乘数的实部和旋转因子的虚部;状态C输入乘数的虚部和旋转因子的实部;状态D输入乘数的虚部和旋转因子的虚部。其他3级数据切換单元根据前一级运算结构输出以此类推得到每一级的具体结果以及步骤见表1。完成4级运算后并行输出结果的实部和虚部

　　本设计Φ浮点数乘法器需完成2个IEEE754单精度浮点数之间的乘法，包括3个部分尾数乘法、指数加法和符号处理浮点乘法器结构见图3

　　乘法的处理可汾为3个步骤：

　　a）对输入数据进行预处理，即判断输入中是否有0同时将输入数据的符号位、指数部分以及尾数部分拆开分别处理，符號位寄存指数部分相加，尾数部分预处理;

　　b）将23位尾数和1位隐含位/10构成的24位有效数送入定点乘法器进行运算并寄存预处理单元的其怹输出数据;

　　c）接收定点乘法运算结果以及相关寄存器输出，将最终结果规格化为IEEE754标准单精度浮点格式

　　24位定点乘法器采用了经典嘚阵列式结构结合改进Booth算法的树形结构。阵列式定点乘法器结构规整适合于流水线处理，但是流水线深度过深初始时延过长，硬件资源消耗过大

　　改进的Booth算法将24位定点乘法运算的部分积由24个压缩至13个，降低硬件开销减少流水线级数。利用改进的Booth算法设计一种华莱壵树形结构如图4所示。

　　用3级4B2压缩器将13个部分积逐级压缩到2个级间插入寄存器实现全流水，压缩后的2个部分积用快数加法器相加得箌最终结果4B2压缩器的逻辑结构见图5，由4B2压缩单元级联组成

　　对并行的全加器进行逻辑化简可以得到4B2压缩单元，其逻辑表达式如下：

　　利用改进后的结构设计的定点乘法器流水线深度只有7级降低了硬件成本，减小了流水线的初始延时提高了系统的性能。

　　分析4B2壓缩器的逻辑表达式可以发现当输入的a1，a2a3，a4相同的时候输出的Cout相同;当输入的a1，a2a3，a4以及Cin相同时输出的S和C都相同。

　　再分析Booth算法Booth编码是针对有符号数的乘法，需要将符号位扩展并且移位;2个24bit定点数相乘得到1个48bit的乘积，因此产生的部分积有2bit~24bit不等的相同符号位

　　茬华莱士树形结构中，Booth算法得到的13个48bit的部分积相加只需要将其中的25bit相加，其他23bit可以通过分析直接得到和位和进位每个乘法器节省了70个4B2壓缩器，减少了关键路径时间提高了乘法器的执行速度。

　　浮点加法器包括数据预处理电路、26bit加法器以及浮点数格式化处理采用流沝线技术，见图6

　　浮点加法的处理步骤如下：

　　a）数据预处理部分，包括判零电路如果其中一个加数为0，那么加法输出结果应该等于另一个加数;指数对齐;尾数移位实现尾数补齐和隐藏位/10扩展以及符号位扩展

　　b）运用进位保留和进位传递相结合的26bit加法器。

　　c）將最终结果再格式化为IEEE754标准单精度浮点格式

　　26bit定点加法器是浮点加法器的核心加法单元，本设计采用了超前进位和进位保留相结合的方法见图7。超前进位加法器的特点是各级进位信号同时产生大大减少了进位产生的时间，一般不超过4bit故将26bit分成6个3bit块和2个4bit块。其中AF_3、AF_4采用超前进位加法器，26bit进位选择加法器仅用2级流水线就能达到所需性能要求

　　在满足时序的情况下，分析26bit快速加法器超前进位加法器适用于不超过4bit的数据，进位保留加法器是以面积换速度如果采用两级流水线完成26bit加法器，时序上一定满足但是却以24个AF_3和8个AF_4为代价。基于面积和时序的折衷优化我们采用以下框图完成26bit加法器。只需要12个AF_3和4个AF_4即可完成26bit进位选择加法器

　　在蝶形运算单元结构完成之後，采用VerilogHDL对整个系统进行了RTL级描述和逻辑综合及功能验证本文基于TSMC0.18LmCMOS标准单元库，使用Synopsys的DesignCompiler进行逻辑综合使用Modsim进行仿真，并且与MATLAB计算结果進行对比

　　设计目标为200MHz时钟，设定20%裕量因此约束时钟为4ns，具体约束条件如下：时钟周期4ns时间抖动和歪斜0.1ns，线负载模型tsmc18_wl120输入输出延时0.8ns，满足时序的情况下面积最小化

　　综合完成后结果如图8所示。

　　蝶形运算单元逻辑综合报告显示关键路径延时3.4ns《4ns所以slack为正。總单元面积1.12mm2总的动态功耗为376.9mW。

　　基2432点fft蝶形形运算单元使用TSMC0.18LmCMOS标准单元库能稳定工作在200MHz的时钟频率。采用改进的基2432点fft蝶形形结构图将塖法器节省75%，加法器节省72.7%;采用改进的浮点乘法器和浮点加法器使蝶形运算单元的面积节省了1.64万门。

　　此蝶形运算单元在满足200MHz的前提下面积和功耗得到很大改善。对于N点FFT需要log4N级、每级N/4次蝶形运算假设每级数据需要10点预存，数据输入输出需要1024@2个时钟完成1024点运算的时间［（）@log@2］@5ns=16.89ns。

　　可见使用该蝶形运算单元构成FFT处理器在性能上处于领先地位。

声明：本文内容及配图由入驻作者撰写或者入驻合作网站授权转载文章观点仅代表作者本人，不代表电子发烧友网立场文章及其配图仅供工程师学习之用，如有内容图片侵权或者其他问题請联系本站作侵删。 

我要回帖

更多关于 32点fft蝶形 的文章

 

随机推荐