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

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
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。

上一篇:IFFT的计算方法
下一篇:DFT的计算量

关注eeworld公众号 快捷获取更多信息
关注eeworld公众号
快捷获取更多信息
关注eeworld服务号 享受更多官方福利
关注eeworld服务号
享受更多官方福利
推荐阅读
全部
蝶形
变址
计算
计算方法

小广播

独家专题更多

TI车载信息娱乐系统的音视频解决方案
TI车载信息娱乐系统的音视频解决方案
汇总了TI汽车信息娱乐系统方案、优质音频解决方案、汽车娱乐系统和仪表盘参考设计相关的文档、视频等资源
迎接创新的黄金时代 无创想,不奇迹
迎接创新的黄金时代 无创想,不奇迹
​TE工程师帮助将不可能变成可能,通过技术突破,使世界更加清洁、安全和美好。
TTI携TE传感器样片与你相见,一起传感未来
TTI携TE传感器样片与你相见,一起传感未来
TTI携TE传感器样片与你相见,一起传感未来
电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2017 EEWORLD.com.cn, Inc. All rights reserved