Cooley-Tukey算法 (蝶形算法)

Cooley-Tukey算法 (蝶形算法)

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

Cooley-Tukey算法差别于其它FFT算法的一个重要事实就是N的因子能够随意选取。这样也就能够使用N=r
S的Radix-r算法了。最流行的算法都是以r=2或r=4为基的,最简单的DFT不须要不论什么乘法就能够实现。比如:在S级且r=2的情形下,下列索引映射的结果是:

Cooley-Tukey算法 (蝶形算法)

  S>2时的-个一般惯例是,在信号流程图中2点DFT是以蝶形图的形式绘出的,图1给出了8点变换的图示。信号流程图己经简化成用全部指向一个节点的箭头都代表加法的形式了,而常系数乘法则是在箭头上加一个因子表示。Radix-r算法具有logr(N)级,而且每组都有同样类型的旋转因子。

Cooley-Tukey算法 (蝶形算法)

  图1 radix-2的长度为8的频率抽取算法

  从图的信号流程图能够看出,计算能够“就地”完毕,也就是蝶形所使用的存储位置能够被重写,由于数据在下一步的计算中已不再须要了。Radix-2变换的旋转因子乘法总数是:

Cooley-Tukey算法 (蝶形算法)

由于每两个箭头仅有一个旋转因子。

  因为图1中的算法在频域中開始将最初的DFT分成更短的DFT,所以这样的算法就叫作频率抽取(decimatiON-in-frequency,DIF)算法。典型的输入值是按顺序出现的,而频率值的索引是按位逆序的。表给出了DIF Radix-2算法的特征值。

  表 频率抽取的Radix-2 FFT

Cooley-Tukey算法 (蝶形算法)

  我们还能够用时间抽取(decimation h time,DIT)构造一种算法。在该情况下,首先将输入序列分开,就会发现全部频率值都是按顺序出现的。

  图2给出了索引41的radix-2和radix-4算法的必要索引变换。radix-2算法须要位顺序的反转,也就是位逆序。而radix-4须要首先构造一个2位的“数字”然后再反转这些数字,这样的操作就称为数字逆序。

Cooley-Tukey算法 (蝶形算法)

  图2 位逆序和数字逆序

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118669.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • i3s 一种开源的三维地理数据规范 简单解读

    i3s 一种开源的三维地理数据规范 简单解读树结构组织,json描述,bin存储,三维数据标准打的不要不要的。

  • svn如何删除当前账号,重新登录

    svn如何删除当前账号,重新登录

  • org.apache.axis.AxisFault.makeFault(AxisFault.java:101)问题「建议收藏」

    org.apache.axis.AxisFault.makeFault(AxisFault.java:101)问题「建议收藏」今天搞了个webservice,但出现如下错误org.apache.axis.AxisFault.makeFault(AxisFault.java:101);org.apache.axis.client.Call.invoke(Call.java:2760);org.apache.axis.client.Call.invoke(Call.java:2443);org.apache.axis.client.Call.invoke(Call.java:2366);org.apache.axis.

  • Mysql自连接查询「建议收藏」

    Mysql自连接查询「建议收藏」自连接查询假想以下场景:某一电商网站想要对站内产品做层级分类,一个类别下面有若干子类,子类下面也会有别的子类。例如数码产品这个类别下面有笔记本,台式机,智能手机等;笔记本,台式机,智能手机又可以按照品牌分类;品牌又可以按照价格分类,等等。也许这些分类会达到一个很深的层次,呈现一种树状的结构。那么这些数据要怎么在数据库中表示呢?我们可以在数据库中创建两个字段来存储id和类别名称,使用第三个字段存

  • pta 列车调度_数据结构/PTA-列车调度/栈/数组

    pta 列车调度_数据结构/PTA-列车调度/栈/数组火车站的列车调度铁轨的结构如下图所示。两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有9趟列车,在入口处按照{8,4,2,5,3,9,1,6,7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开,则至少需要多少条平行铁轨用于调度?输入格式:输入第一行给出一个整数N(2≤…

  • 3.7v锂电池升压电路_电池升压

    3.7v锂电池升压电路_电池升压FS2114的PCB布局设计建议-基础篇开关电源的一个常见问题是“不稳定”的开关波形。有时,波形抖动很明显,可以听到从磁性元件发出噪声。如果问题与印刷电路板(PCB)布局有关,则很难确定原因。EMC也是很注重(PCB)布局,这就是为什么在开关电源设计的早期正确布局PCB至关重要的原因。其重要性不可夸大。原理图走线主要器件放置并联一个旁路电容0.1uFLX节点FB反馈电阻R1,R2COUT电容容易影响输出的布线功率组件的推荐焊盘图案GND功率地的PCB布线电感器选择概述FS2

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号