首先说明：采用的是基2时域抽取法（Decimation-In-Time FFT 简称DIT-FFT）。
FFT实际上是对DFT的一种快速实现算法，实质上就是对DFT抽取，以8点DFT为例：可以分解为两个4点DFT，在继续分解为4个两点DFT，从而缩小DFT运算量，提高运算效率。（因此首先需要理解DFT算法和它的一些基本性质（周期性等））。
注意：FFT需要的采样点数要是个，若采样点数不够则需要补零处理。
具体算法推导过程如下：
最终得到的蝶形流图如下：
（1）原位计算：简单理解就是每一级蝶形运算计算的结果存储到原来的存储单元就行，这样可以节省内存，降低成本。
（2）旋转因子规律
首先需要明确FFT一定是对个点进行FFT。下面以N=8为例寻找规律。根据鲽形流图，可以将
分为M级蝶形运算。具体推导如下：
下面是一个16点的蝶形流图，可以用来验证一下
（3）蝶形运算规律
已经知道旋转因子的规律了，接下来需要推导蝶形运算的规律。首先需要有一个跨度的概念（这里用B表示跨度），观察上面的8点，16点的流图，我们可以发现如下规律：
当L=1时：进行蝶形运算的两点跨度（距离）为1，这里记作B=1。
当L=2时：进行蝶形运算的两点跨度（距离）为2，这里记作B=2。
当L=3时：进行蝶形运算的两点跨度（距离）为4，这里记作B=4。
当L=4时：进行蝶形运算的两点跨度（距离）为8，这里记作B=8。
依次类推：则第L级跨度为：。
因此最终得到如下蝶形运算形式：
（5）序列的倒序
上面所进行的所有操作都是在对采样点进行重新排序之后进行的，在进行上述操作前需要对序列进行重新排序（倒序）以N=8为例输入为x(0),x(1),x(2),x(3),x(4),x(5),x(6),x(7)。需要重新排序为x(0),x(4),x(2),x(6),x(1),x(5),x(3),x(7)。这个操作就叫做倒序。首先观察下面16点的正序和倒序的二进制图如下：
i相对容易，每一行只需要加1就可以，j如果从左往右看其实本质上也是加1，因此问题难点实质上在于右边如何从8到4到12等等。这里关键是权重的概念，讲起来可能相对困难，这里大家可以结合下面的代码，调试观察，尝试几组数据之后相信一定可以理解。
框图：
#include<stdio.h>
int main()
{
int N;
printf("请输入需要倒序的个数：");
scanf("%d",&N);
int a[N];
int i=0;
//原始数据赋值
for(i=0;i<N;i++)
a[i]=i;
printf("原始数据值为");
for(i=0;i<N;i++)
printf("%-4d",a[i]);
printf("\n");
int lh=N/2,j=lh,n1=N-2;
int index,k;
//重新排序部分
for(i=1;i<n1;i++){
if(i<j){
index=a[j];
a[j]=a[i];
a[i]=index;
}
k=lh;
while(j>=k){
j=j-k;
k=k/2;
}
j=j+k;
}
printf("倒序数据值为");
for(i=0;i<N;i++)
printf("%-4d",a[i]);
return 0;
}（6）最终程序框图
到这里，需要明确对于个点，共有M级，每一级需要进行N/2此蝶形运算。第L级有
个旋转因子。可以带入到前文的流图中进性验证。具体框图入下（重点和难理解的是第三层循环，可以代入值进去理解）：
（7）关于旋转旋转因子的c语言处理思路
同时需要说明：fft进行的运算都是复数运算，因此进行的加减乘除都是复数的加减乘除。但一般在硬件上输入信号都是由ADC采集的实数信号，因此我们见到的大部分输入都是数值，但其实也可以是复数输入。
（8）完整程序放在这里，大家可以免费下载参考。
（9）matlab验证
参考华东理工大学大学万永菁老师讲的数字信号处理。想要详细学习的可以取找视频学习。
所写内容都是自己下学习fft的过程，其中可能有一些错误，如发现 还望大家指正。
我正在寻找执行以下操作的正确语法(在Perl、Shell或Ruby中):#variabletoaccessthedatalinesappendedasafileEND_OF_SCRIPT_MARKERrawdatastartshereanditcontinues. 最佳答案 Perl用__DATA__做这个:#!/usr/bin/perlusestrict;usewarnings;while(){print;}__DATA__Texttoprintgoeshere 关于ruby-如何将脚
几个月前，我读了一篇关于rubygem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：
?博客主页：https://xiaoy.blog.csdn.net?本文由呆呆敲代码的小Y原创，首发于CSDN??学习专栏推荐：Unity系统学习专栏?游戏制作专栏推荐：游戏制作?Unity实战100例专栏推荐：Unity实战100例教程?欢迎点赞?收藏⭐留言?如有错误敬请指正！?未来很长，值得我们全力奔赴更美好的生活✨------------------❤️分割线❤️-------------------------
嗨~大家好，这里是可莉！今天给大家带来的是7个C语言的经典基础代码~那一起往下看下去把【程序一】打印100到200之间的素数#includeintmain(){ inti; for(i=100;i 【程序二】输出乘法口诀表#includeintmain(){inti;for(i=1;i 【程序三】判断1000年---2000年之间的闰年#includeintmain(){intyear;for(year=1000;year 【程序四】给定两个整形变量的值，将两个值的内容进行交换。这里提供两种方法来进行交换，第一种为创建临时变量来进行交换，第二种是不创建临时变量而直接进行交换。1.创建临时变量来
网络编程套接字网络编程基础知识理解源`IP`地址和目的`IP`地址理解源MAC地址和目的MAC地址认识端口号理解端口号和进程ID理解源端口号和目的端口号认识`TCP`协议认识`UDP`协议网络字节序socket编程接口`sockaddr``UDP`网络程序服务器端代码逻辑：需要用到的接口服务器端代码`udp`客户端代码逻辑`udp`客户端代码`TCP`网络程序服务器代码逻辑多个版本服务器单进程版本多进程版本多线程版本线程池版本服务器端代码客户端代码逻辑客户端代码TCP协议通讯流程TCP协议的客户端/服务器程序流程三次握手（建立连接）数据传输四次挥手（断开连接）TCP和UDP对比网络编程基础知识
我完全不是程序员，正在学习使用Ruby和Rails框架进行编程。我目前正在使用Ruby1.8.7和Rails3.0.3，但我想知道我是否应该升级到Ruby1.9，因为我真的没有任何升级的“遗留”成本。缺点是什么？我是否会遇到与普通gem的兼容性问题，或者甚至其他我不太了解甚至无法预料的问题？ 最佳答案 你应该升级。不要坚持从1.8.7开始。如果您发现不支持1.9.2的gem，请避免使用它们(因为它们很可能不被维护)。如果您对gem是否兼容1.9.2有任何疑问，您可以在以下位置查看:http://www.railsplugins.or
我创建了一个由于“在运行时执行的单例元类定义”而无法编码的对象(这段代码的描述是否正确？)。这是通过以下代码执行的:#defineclassXthatmyusesingletonclassmetaprogrammingfeatures#throughcallofmethod:break_marshalling!classXdefbreak_marshalling!meta_class=class我该怎么做才能使对象编码正确？是否可以从对象instance_of_x的classX中“移除”单例组件？我真的需要一个建议，因为我们的一些对象需要通过Marshal.dump序列化机制进行缓存。
我正在查看Ruby日志记录库Logging.logger方法并从sourceatgithub提出问题与这段代码有关:logger=::Logging::Logger.new(name)logger.add_appendersappenderlogger.additive=falseclass我知道类 最佳答案 这实际上删除了方法(当它实际被执行时)。这是确保close不会被调用两次的保障措施。看起来好像有嵌套的“class 关于Ruby元编程问题，我们在StackOverflow上找到一
使用Paperclip，我想从这样的URL抓取图像:require'open-uri'user.photo=open(url)问题是我最后得到一个像“open-uri20110915-4852-1o7k5uw”这样的文件名。有什么方法可以更改user.photo上的文件名？作为一个额外的变化，Paperclip将我的文件存储在S3上，所以如果我可以在初始分配中设置我想要的文件名就更好了，这样图像就会上传到正确的S3key。像这样:user.photo=open(url),:filename=>URI.parse(url).path 最佳答案
我正在开发一个xcode自动构建系统。在执行一些预构建验证时，我想检查指定的证书文件是否已被撤销。我了解securityverify-cert验证其他证书属性但不验证吊销。我如何检查撤销？我正在用Ruby编写构建系统，但我对任何语言的想法都持开放态度。我阅读了这个答案(Openssl-Howtocheckifacertificateisrevokedornot)，但指向底部的链接(DoesOpenSSLautomaticallyhandleCRLs(CertificateRevocationLists)now?)进入的Material对我的目的来说有点过于复杂(用户上传已撤销的证书是一