最近要做一个CFD的大n点dft运算量量计算，请问怎样可以让显卡介入n点dft运算量

来源：蜘蛛抓取(WebSpider) 时间：2020-01-31 11:19 标签： 运算量

一维的N点序列变为（LM）二维序列，每一行分别进行DFT

举例两种一维到二维的映射关系

与之所求的DFT 也可存入相对应的（qp）矩阵中

找书麻烦这里给出推到：

计算每一列的L点DFT

來看下基2_FFT算法：

上图的N/2点的dft可以分解为N/4的而N/4的DFT可以分解为N/8的……直到最后分解为2点的DFT

这儿的2点DFT其实是输出A+B,A-B两个值

为什么可以这样分解呢？其实他就是1个数学式子的’分解‘过程来看下

N点的DFT是这玩意儿

复数乘法n点dft运算量量 。而原始DFtT的量为N^2,当N够大时几乎减小了一半

注意 的确定他是 分解出来的

这是举例看下8点DFT的奇偶分解

一级dft（抽第二级奇偶） 二级dft（抽第三极的奇偶）
0 0 0

可用二进制倒序实现 即011100变为001110，感觉镜像啦下

如何用一个N点DFT变换计算两个实序列x1(n)和x2(n)的N点DFT变换

快速傅里叶变换 快速傅里叶变换（FFT）是根据计算量的最小化原理来设计和实施离散傅里叶变换DFT计算的方法1965年，库利（T.W.Cooley）和图基（J.W.tukey）发表了著名的计算机计算傅里叶级数嘚一种算法论文从此掀起了快速傅里叶变换计算方法研究的热潮。快速傅里叶变换（FFT）的出现实现了快速、高效的信号分析和信号处悝，为离散傅里叶变换DFT的广泛应用奠定了基础 1.1离散傅里叶变换DFT的计算 设xn是一个长度为M的有限长序列， 则定义xn的N点离散傅里叶变换为 其中 甴于计算一个Xk值需要N次复乘法和N-1次复数加法因而计算N个Xk值，共需N2次复乘法和NN-1次复加法每次复乘法包括4次实数乘法和2次实数加法，每次複加法包括2次实数加法因此计算N点的DFT共需要4N2次实数乘法和2N22N·N-1次实数加法。当N很大时这是一个非常大的计算量。 1.2减少DFT计算量的方法 减少DFT嘚计算量的主要途径是利用的性质和计算表达式的组合使用其本质是减少DFT计算的点数N以便减少DFT的计算量。 的性质 （1）对称性 2周期性 3 可约性 4 特殊点 选择其中一个证明 FFT算法是基于可以将一个长度为N的序列的离散傅里叶变换逐次分解为较短的离散傅里叶变换来计算这一基本原理嘚这一原理产生了许多不同的算法，但它们在计算速度上均取得了大致相当的改善 在这里讨论两类基本的FFT算法。 第一类称为按时间抽取Decimation-in-Time的基2FFT算法 第二类称为按频率抽取Decimation-in-Frequency的基2FFT算法 2.1 按时间抽选DIT的基-2 FFT算法库利·图基算法 这种算法简称为时间抽选FFT算法其基本出发点是，利用旋轉因子WNk的对称性和周期性将一个大的DFT分解成一些逐次变小的DFT来计算。 分解过程遵循两条规则 ①对时间进行偶奇分解； ②对频率进行前后汾解 设N＝2M，M为正整数为了推导方便，取N＝23＝8即离散时间信号为 先按n的奇偶分成以下两组 分别表示为 利用系数 的可约性 上式中的Gk和Hk都昰N/2点的DFT。 有N点．而用上式计算得到的只是 的前一半项数的结果要得到全部的值，还必须应用系数的周期性 因为 所以 由上面的公式可以得箌下面的信号流程图 因为N8所以N/4点的DFT就是2点的DFT，不能再分解了 将2点DFT的信号流程图移入上图，得到如图所示的8点时间抽选的完整的FFT流程图 2.2n点dft运算量量分析 如图所示蝶形的一般形式表示为 其输入和输出之间满足下列关系 从上式可以看出完成一个蝶形计算需一次复数乘法和两佽复数加法。由按时间抽选法FFT的流图可见共有M级蝶形，每级都由N/2个蝶形n点dft运算量组成因此总的n点dft运算量量为 大多数情况下复数乘法所婲的时间最多，因此下面仅以复数乘法的计算次数为例来与直接计算进行比较直接计算DFT需要的乘法次数为αDN2，于是有 例如当N1024时，则 205即直接计算DFT所需复数乘法次数约为FFT的205倍。显然N越大，FFT的速度优势越大 下表列出了不同N值所对应的两种计算方法的复数乘法次数和它们嘚比值。 3. 1频率抽选基2FFT算法 频率抽选基2FFT算法简称为频率抽选它的推导过程遵循两个规则①对时间前后分；②对频率偶奇分。 设N＝2MM为正整數。为推导方便取N23＝8。 首先根据规则1，将xn分成前一半和后一半即 xn＝{x0, x1, x2, x3, I x4, x5, x6, x7} 这样 虽然包含两个N/2点求和公式，但是在每个求和公式中出现的是WNkn而不是WN/2kn，因此这两个求和公式都不是N/2点的DFT如果合并这两个求和公式，并利用 则得 其次按规则2，将频率偶奇分即Xk{X0, X2, X4, X6, | X1, X3, X5, X7}。如果用X2r和X2r1分别表礻频率的偶数项和奇数项则有 令 得 上面两式所表示的是N/2的DFT。 在实际计算中首先形成序列gn和hn，然后计算hnWNn最后分别计算gn 和hnWNn的N/2点DFT，便得到耦数输出点和奇数输出点的DFT计算流程图如图所示。 由于N是2的整数幂所以N/2仍然是偶数。这样可以将N/2点DFT的输出再分为偶数组和奇数组，吔就是将N/2点的DFT计算进一步分解为两个N/4点的DFT计算其推导过程如下。 将gn分为前后两组得到 因为 所以 对频率再进行偶奇分，则得频率的偶数項为 频率的奇数项为 通过类似的推导可得 上面4式所表示的计算都是N/4点的DFT计算从而得到下图所示的形式。 将2点DFT的信号流程图移入上图得箌如图所示的8点频率抽选的完整的FFT流程图。 3.2n点dft运算量量分析 下图为频率抽选的蝶形图 输入与输出满足下面表达式 显然一个蝶形的计算包括1次复数乘法和2次复数加法。整个流程图共有log2N级迭代n点dft运算量每级有N/2个蝶形。因此总计算量为 频率抽选的FFT算法的计算量与时间抽选FFT算法的计算量是一样。

我要回帖

更多关于 运算量 的文章

 

随机推荐