蝶形、同址和变址计算方法及公式

2011-08-11 10:51:50来源: 互联网

1.  蝶形计算
    任何一个N为2的整数幂(即N=2M)的DFT,都可以通过M次分解,最后成为2点的 DFT来计算。M次分解构成了从x(n)到X(k)的M级迭代计算,每级由N/2个蝶形组成。图3.20表示了蝶形的一般形式表示。
其输入和输出之间满足下列关系:

大多数情况下复数乘法所花的时间最多,因此下面仅以复数乘法的计算次数为例来与直接计算进行比较。
直接计算DFT需要的乘法次数为αD=N2,于是有例如,当N=1024时,则:   205,即直接计算DFT所需复数乘法次数约为FFT的205倍。显然,N越大,FFT的速度优势越大。

同址(原位)计算
图3. 19包含log2N级迭代运算,每级由N/2个蝶形计算构成。蝶形计算的优点是可以进行所谓同址或原位计算。
现在来考察第一级的计算规律。设将输入x(0),x(4),x(2),x(6), x(1),x(5),x(3),x(7)分别存入计算机的存储单元M(1), M(2), M(3),…,M(7)和M(8)中。首先,存储单元M(1)和M(2)中的数据x(0)和x(4)进入运算器并进行蝶形运算,流图中各蝶形的输入量或输出量是互不相重的,任何一个蝶形的二个输入量经蝶形运算后,便失去了利用价值,不再需要保存。这样,蝶形运算后的结果便可以送到M(1)和M(2)存储起来。类似地,M(3)和M(4)中的x(2)和x(6)进入运算器进行蝶形运算后的结果也被送回 到M(3)和M(4)保存,等等。第二级运算与第一级类似,不过,M(1)和M(3)存储单元中的数 据进行蝶形运算后的结果被送回M(1)和M(3)保存,M(2)和M(4)中的数据进行蝶形运算 后送回M(2)和M(4)保存,等等。这样一直到最后一级的最后一个蝶形运算完成。

蝶形运算的特点是,首先每一个蝶形运算都需要两个输入数据,计算结果也是两个数据,与其它结点的数据无关,其它蝶形运算也与这两结点的数据无关、因此,一个蝶形 运算一旦计算完毕,原输入数据便失效了。这就意味着输出数据可以立即使用原输 人数据结点所占用的内存。原来的数据也就消失了。输出、输人数据利用同一内存单 元的这种蝶形计算称为同位(址)计算。
可以看出, 每一级的蝶形的输入与输出在运算前后可以存储在同一地址(原来位置上)的存储单元中,这种同址运算的优点是可以节省存储单元,从而降低对计算机存储量的要求或降低硬件实现的成本。

3.变址计算
从图3. 19所示的流程图看出,同址计算要求输入x(n)是“混序”排列的。所谓输入为“混 序”,并不是说输入是杂乱无章的,实际上它是有规律的。如果输入x(n)的序号用二进制码来 表示,就可以发现输入的顺序恰好是正序输入的“码位倒置”,表3. 3列出了这种规律。

在实际运算中,按码位倒置顺序输入数据x(n),特别当N较大时,是很不方便的。因此,数据总是按自然顺序输入存储,然后通过“变址”运算将自然顺序转换成码位倒置顺序存储。实现这种转换的程序可用图3. 21来说明。

图中用n表示自然顺序的标号,用l表示码位倒置的标号。当l=n时,x(n)和x(l)不必互相调换。当l≠n时, 必须将x(l)和x(n)互相调换,但只能调换一次,为此必须规定每当l>n时,要将x(l)和x(n)相互调换,即把原来存放x(n)的存储单元中的数据调入存储x(l)的存储单元中,而把原来存储x(l)的存储单元中的数据调入到存储x(n)的存储单元中。
这样,按自然序输入的数据x(n)经过变址计算后变成了码位倒置的排列顺序,便可进入第一级的蝶形运算。
最后介绍一下时间抽选FFT算法的另外一些形式的流程图。对于任何流程图,只要保持 各节点所连支路及其传输系数不变,则不论节点位置怎样排列,所得到的流程图总是等效的,因而都能得到DFT的正确结果,只是数据的提取和存储次序不同而已。
把图3. 19中与x(4)水平相邻的所有节点和与x(1)水平相邻的所有节点交换,把与x(6)水平相邻的所有节点和与 x(3)水平相邻的所有节点交换,而与x(2)、x(5)和x(7)水平相邻各节点位置不变,就可以从图3. 19得到图3.22。图3.22与图3.19的区别只是节点的排列不同,而支路传输比,即WN的 各次幂保持不变。显然图3.22所示流程图的输入是正序(自然顺序)排列的,输出是码位倒置 排列的,所以输出要进行变址计算。图3. 22所示的流程图相当于最初由库利和图基给出的时 间抽选算法。

另一种形式的流程图是将节点排列成输入 和输出两者都是正序排列,但这类流程图不能进行同址计算,因而需要两列 长度为N的复数存储器。

关键字:蝶形  变址  计算  计算方法

编辑:eeleader 引用地址:http://www.eeworld.com.cn/gykz/2011/0811/article_7986.html
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。
论坛活动 E手掌握
微信扫一扫加关注
论坛活动 E手掌握
芯片资讯 锐利解读
微信扫一扫加关注
芯片资讯 锐利解读
推荐阅读
全部
蝶形
变址
计算
计算方法

小广播

独家专题更多

富士通铁电随机存储器FRAM主题展馆
富士通铁电随机存储器FRAM主题展馆
馆内包含了 纵览FRAM、独立FRAM存储器专区、FRAM内置LSI专区三大部分内容。 
走,跟Molex一起去看《中国电子消费品趋势》!
走,跟Molex一起去看《中国电子消费品趋势》!
 
带你走进LED王国——Microchip LED应用专题
带你走进LED王国——Microchip LED应用专题
 
电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2016 EEWORLD.com.cn, Inc. All rights reserved