蝶形运算，2点DFT运算称为蝶形运算，整个FFT由多次迭代的蝶形运算组成，而这种算法采用的是高原运算，所以只需要n个存储单元。2.(2)公式(2)是FFT基-4频域提取算法的基本运算单元，一般称为蝶形运算。
1.2点DFT运算称为蝶形运算，整个FFT由若干次迭代的蝶形运算组成，而这种算法采用的是高原运算，所以只需要n个存储单元。2.(2)公式(2)是FFT基-4频域提取算法的基本运算单元，一般称为蝶形运算。接下来，将X(4m i)，i=0，1，2，3分解成四个N42序列，经过R次迭代完成计算。整个算法的复杂度降低到O(Nlog4N)。
第一列只有一种蝶形运算：系数，参与运算的两个数据点之间的距离为1。第二列蝶形运算有两种：系数分别为，参与蝶形运算的两个数据点之间的距离等于2。第三列有四种蝶形运算：系数是参与蝶形运算的两个数据点之间的距离等于4。可以看到，每一列的蝶形比前一列增大了一倍，参与蝶形运算的两个数据点之间的距离也增大了一倍。最后一列的系数用的最多，是4，也就是前一列只用了其偶数序号的一半，也就是说，
第一列只有一个系数，即。上诉结论可以推广到N=的一般情况，规则是第一列蝴蝶运算只有一种类型，系数是每列蝴蝶类型将从前一列加倍为N/2个蝴蝶类型，系数为N/2。对于从后向前推进的每一列，使用上述系数的偶数一半。比如第一列的系数是参与蝶形运算的两个数据点之间的距离，在最后一级最大，其值为N/2。每向前推进一列，距离就减少一半。
FFT(快速傅立叶变换)是数字信号处理领域的核心算法之一。蝶形运算单元是FFT设计的核心单元。本文研究了基于24FFT的蝶形运算单元芯片的设计。基于TSMC(***集成电路制造公司)0.18LmCMOS标准单元库的半定制ASIC(专用集成电路)设计，采用自顶向下的设计方法和VerilogHDL描述体系，在Modelsim、DesignCompiler、ASTRO等EDA(电子设计自动化)工具中完成。
FFT蝶形运算器的设计是FFT处理器的核心单元。蝶形运算器结构的稳定性和运算的准确性直接影响FFT处理器的性能。分析了基4FFT的特点，综合考虑面积、性能和功耗等因素，设计了一种结合流水线技术和并行结构的蝶形运算单元。
蝶形运算单元结构设计基础24蝶形运算单元在24FFT中的处理结构如图所示。
传统的基4算法由3个复数乘法器和12个复数加法器组成。每个复数乘法器由4个实数乘法器和2个实数加法器实现，每个复数加法器由2个实数加法器实现。将radix-24算法的计算结构直接映射到硬件需要大量的逻辑资源(12个实数乘法器和22个实数加法器)。
重新排列后，如下所示：
观察四组表达式xc和uc，Xc和Uc，yc和zc，Yc和Zc，可以发现，它们对应的实部和虚部的括号内的内容是相同的。因此，我们可以巧妙地将流水线的思想与并行结构结合起来，用四个循环序列严格控制每个寄存器的时序，只用一个实数乘法器实现一个复数乘法器，三个不同的复数乘法并行进行。加法器也被并行回收。因此，完成一个基-4FFT蝶形运算单元只需要3次实数乘法和6次实数加法，与传统的基-24FFT蝶形运算单元相比，可以节省75%的乘法器逻辑资源和72.7%的加法器逻辑资源。
结构
数据交换单元由状态机组成，以蝶形运算单元的一级数据交换单元为例。每组数据输入乘法器分为四种状态(分别为A、B、C和D)。状态A输入乘数的实部和旋转因子的实部；状态b输入乘数的实部和旋转因子的虚部；状态c输入乘数的虚部和旋转因子的实部；状态d输入乘数的虚部和旋转因子的虚部。其他三级数据交换单元根据前一级运算结构的输出类推得到。每一级的具体结果和步骤如表1所示。完成四级运算后，并行输出结果的实部和虚部。
浮点乘法器的设计在本设计中，浮点乘法器需要完成两个IEEE754单精度浮点数之间的乘法，包括三个部分尾数的乘法、指数加法和符号处理。浮点乘法器结构如图3所示。
乘法的处理可以分为三步：a)对输入数据进行预处理，即判断输入中是否有零，同时对输入数据的符号位、指数部分和尾数部分进行分解并分别处理，对符号位进行注册，对指数部分进行加法运算，对尾数部分进行预处理；
b)将23位尾数和由1位隐含位/10组成的24位有效数送到定点乘法器进行运算，并寄存预处理单元的其他输出数据；
c)接收定点乘法运算的结果和相关寄存器的输出，并将最终结果归一化为IEEE754标准的单精度浮点格式。
24位定点乘法器采用经典的数组结构结合改进的Booth算法的树结构。阵列定点乘法器结构规则，适合流水线处理，但流水线深度太深，初始延迟太长，硬件资源消耗太大。
改进的Booth算法将24位定点乘法的部分积从24个减少到13个，减少了硬件开销和流水线级数。使用改进的Booth算法设计了一个Wallace树结构，如图4所示。
13个部分积被3级4B2压缩器压缩成两个，整个流水线通过在级间插入寄存器来实现。压缩后的两个部分积通过快速加法器相加得到最终结果。4B2压缩机的逻辑结构如图5所示，由4B2压缩单元级联而成。
4B2压缩单元可以通过对并行全加器进行逻辑简化得到，其逻辑表达式如下：
利用改进结构设计的定点乘法器的流水线深度只有7级，降低了硬件成本，减少了流水线的初始延迟，提高了系统的性能。
浮点乘法器的改进通过分析4B2压缩器的逻辑表达式可以发现，当输入a1、a2、a3、a4相同时，输出Cout也相同。当输入a1、a2、a3、a4和Cin相同时，输出S和C也相同。
然后分析布斯算法。布斯编码针对的是有符号数的乘法，需要对符号位进行扩展和移位；将两个24位定点相乘得到一个48位乘积，因此得到的部分乘积具有相同的符号位，范围从2位到24位。
在Wallace树结构中，将Booth算法得到的13个48位部分积相加，只需要将其中的25位相加，另外23位可以直接通过分析得到。每个乘法器节省了70个4B2压缩器，减少了关键路径时间，提高了乘法器的执行速度。
浮点加法器的设计浮点加法器包括数据预处理电路、26位加法器和浮点数格式化处理，采用流水线技术，如图6所示。
浮点加法的处理步骤如下：a)数据预处理部分，包括零判断电路，如果一个加数为0，加法的输出结果要等于另一个加数；指数排列；尾数移位实现尾数补全、隐藏位/10扩展和符号位扩展。
b)使用组合了进位保留和进位传送的26位加法器。
c)将最终结果重新格式化为IEEE754标准单精度浮点格式。
26位定点加法器是cor
浮点加法器的改进分析了26位快速加法器在满足时序的情况下。超前进位加法器适用于不超过4位的数据，预留进位加法器按区变速。如果用两级流水线来完成26位加法器，时序必须满足，但代价是24个AF_3和8个AF_4。基于面积和时序的折衷优化，我们使用下面的框图来完成26位加法器。完成26位进位选择加法器只需要12个AF_3和4个AF_4。
逻辑综合在蝶形运算单元结构完成后，用VerilogHDL对整个系统进行RTL级描述、逻辑综合和功能验证。基于TSMC0.18LmCMOS标准单元库，使用Synopsys的DesignCompiler进行逻辑综合，使用Modsim进行仿真，并与MATLAB计算结果进行比较。
逻辑综合
设计目标是200MHz时钟，设置了20%的余量，因此约束时钟为4ns。具体约束如下：时钟周期4ns，时间抖动和偏斜0.1ns，线负载型号tsmc18_wl120，输入输出延时0.8ns，在满足时序的情况下面积最小化。
合成后的结果如图8所示。
蝶形逻辑综合报告显示关键路径延迟为3.4 ns \4 ns，因此slack为正。总单位面积1.12mm2，总动态功耗376.9mW。
基24FFT蝶形运算单元采用TSMC0.18LmCMOS标准单元库，可以稳定工作在200MHz的时钟频率。采用改进的基-24FFT蝶形结构图，乘法器节省75%，加法器节省72.7%。使用改进的浮点乘法器和浮点加法器，蝶形运算单元的面积节省了16400门。
在200MHz的前提下，这个蝶形运算单元的面积和功耗都有了很大的提升。对于N点FFT，它需要log4N级和每级N/4次蝶形运算。假设每一级数据需要预存10个点，数据输入输出需要1024@2个时钟，完成1024个点运算的时间[(1024/410)@ log 41024 1024 @ 2]@ 5 ns=16.89 ns。
可以看出，这种蝶形运算单元构成的FFT处理器在性能上处于领先地位。