FFT算法的C语言实现

article/2025/10/18 22:17:00

FFT算法的C语言实现

:数字信号处理


需要注意的几个点

整体实现
比特逆序
旋转因子
三大循环

算法原理

X ( k ) = ∑ n = 0 N − 1 x ( n ) × e − j 2 π N k n X(k) = \sum_{n=0}^{N-1} x(n)\times e^{-j\frac{2\pi}{N}kn} \\ X(k)=n=0N1x(n)×ejN2πkn
在将信号进行补零,变为偶数序列的时候
0 < = k < = N / 2 X ( k ) = X 1 ( k ) + W n k × X 2 ( k ) 0<=k<=N/2 \\ X(k) = X_1(k) + W_n^k\times X_2(k) 0<=k<=N/2X(k)=X1(k)+Wnk×X2(k)
再利用 W N k W_N^k WNk的可约性质,可以得到
0 < = k < = N / 2 X ( k + N 2 ) = X 1 ( k ) − W n k × X 2 ( k ) 0<=k<=N/2 \\ X(k+\frac{N}{2}) = X_1(k) - W_n^k\times X_2(k) 0<=k<=N/2X(k+2N)=X1(k)Wnk×X2(k)

一些重要的关系

关于蝶群和蝶形运算
fft.jpg-1217.9kB

对于图中表的红色方框的就是一个蝶群,可以看到一个蝶群中可能包含有多个蝶形,左边第一个蝶群中就是包含了一个蝶形,而右边包含了两个蝶形。
经过分析可以知道,如果以左边的输入序列为第0级,而最右边为第M级(假设序列的长度为2的M次幂),则可以知道第M级只有一个蝶群,这个蝶群中含有 2 ( m − 1 ) 2^(m-1) 2(m1)个蝶形和旋转因子。
经过分析可以看到第i级,有 2 M − i 2^{M-i} 2Mi个蝶群,比如以上图为例,第一级有 2 3 − 1 = 4 2^{3-1}=4 231=4个蝶群。

关于旋转因子的分析

我们知道对于每一级分解之后,关于$W_N^k$中的N的值是不断变化的,从最后一级来分析。

N = 2 M W N k = e − j 2 π 2 M n k N = 2^M \\ W_N^k = e^{-j\frac{2\pi}{2^M}nk} N=2MWNk=ej2M2πnk
对于倒数第二级
N = 2 ( M − 1 ) W N k = e − j 2 π 2 ( M − 1 ) n k N = 2^(M-1) \\ W_N^k = e^{-j\frac{2\pi}{2^(M-1)}nk} N=2(M1)WNk=ej2(M1)2πnk

对于第i级
N = 2 ( M − ( M − i ) ) W N k = e − j 2 π 2 ( M ( M − i ) ) n k = e − j 2 π 2 i N = 2^(M-(M-i)) \\ W_N^k = e^{-j\frac{2\pi}{2^(M(M-i))}nk} \\ = e^{-j\frac{2\pi}{2^i}} N=2(M(Mi))WNk=ej2(M(Mi))2πnk=ej2i2π

于是可以得到一个普遍的规律,对于第i级的旋转因子为
W N k = e − j 2 π 2 i W_N^k = e^{-j\frac{2\pi}{2^i}} WNk=ej2i2π

编程主要使用到了三大循环

最外层的循环:级数的循环
中间的循环:旋转因子的个数(也是每一个蝶群中,蝶形的个数)
最内层的循环:一个旋转因子需要给多少个蝶群使用。

void fft(complexNumber* sequence, int order, int length, complexNumber * result)
{
int i, j, k;
copyComplex(sequence, length, result);
//THE FIRST LOOP 
for(i=0; i<order; i++)
{int total_factors;complexNumber u = {1, 0};total_factors = pow(2, i);factor = getFactor(i+1);//printf("The %d's level loop\n", i);//THE NUMBER OF DIFFERENT FACTORS = THE LENGTH OF TWO GROUPSfor(j=0; j<total_factors; j++){int total_groups, index;total_groups = pow(2, order-i-1);	//THE NUMBER OF DIFFERENT GROUPSfor(index=0, k=j; index<total_groups;k+=total_factors*2, index++) {//COMPUTER THE DFTresult[k] = complex_add(*(sequence+k) ,complex_mul(u, *(sequence+k+total_factors)));result[k+total_factors] = complex_add(*(sequence+k) , reverse_complex(complex_mul(u, *(sequence+k+total_factors))));}//printf("The value of u is: \n");//showComplex(u);u = complex_mul(u, factor);}copyComplex(result, length, sequence);
}

}

这里仍然有很多需要注意的细节,比如关于逆序的时候,我们需要首先判断需要使用多少位宽的空间来存放数据,然后才能进行逆序,如果直接使用一个固定的位宽来进行逆序,那么除非你将所有的输入的序列继续补零到固定的值,然后再对这个整体的数据进行逆序,否则就是错误的,但是如果补零到固定的个数,那么就对造成浪费,而且fft的点数也就确定了。
**还有一个需要注意的点是,相邻两个蝶群的距离是多少,为什么需要这个参数呢?因为只有得到这个参数之后,我们才能知道同一个旋转因子,下一次需要的位置, 2 i 2^i 2i,就是总共旋转因子个数(一个蝶群中蝶形的个数)的二倍。

结果展示

无标题.png-28.7kB

使用matlab的标准结果
无标题.png-4.9kB

源码,在上传的资源中。有任何问题欢迎交流。
源码地址


http://chatgpt.dhexx.cn/article/pX1F2W3n.shtml

相关文章

优雅的FFT算法

简 介&#xff1a; 利用FFT算法实现快速傅里叶变换&#xff0c; 在理论、工程中具有非常广泛的应用。 除了能够在合适的计算平台完成FFT算法&#xff0c;同时还需要注意到它在频谱分析中可能带来的频率混叠以及频率泄露等问题。 关键词&#xff1a; FFT&#xff0c;算法实现 #m…

STM32 FFT算法实现

DSP 库运行环境搭建 在 MDK 里面搭建 STM32F4 的 DSP 运行环境(使用.lib 方式)是很简单的&#xff0c;分为 3 个步骤&#xff1a; 1&#xff0c; 添加文件。 首先&#xff0c;我们在例程工程目录下新建&#xff1a;DSP_LIB 文件夹&#xff0c;存放我们将要添加的文件&#xff…

FFT算法解析

问题描述 两个n次多项式相乘,其时间复杂度为 O(n2) ,通过FFT来减小其问题的复杂度。 分析过程 FFT的基本思路是:我知道一个多项式表达式可以根据其表达式算出结果,同理我们也可以根据其结果算出表达式。对于A,B两个n次多项式,一共所有又2n+1个参数需要求解,我们至少需要…

FFT算法再学以及终于理解

前言 人生如逆旅&#xff0c;我亦是行人。 一、FFT FFT&#xff08;Fast Fourier Transformation&#xff09;&#xff0c;中文名快速傅里叶变换&#xff0c;用来 加速多项式乘法 &#xff0c;就是用来降低算法的时间复杂度的&#xff0c;将时间复杂度由原来的 O(n^2) 变为了O…

十分简明易懂的FFT(快速傅里叶变换)

FFT前言 快速傅里叶变换 (fast Fourier transform),即利用计算机计算离散傅里叶变换&#xff08;DFT)的高效、快速计算方法的统称&#xff0c;简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少&…

第四章快速傅里叶变换FFT

一、基2FFT算法 1.直接计算DFT的特点 对于N点DFT的乘法和加法运算次数均为N^2(运算量较大)减少运算量的基本途径&#xff1a;将N点DFT分解成多个较短的DFT旋转因子具有 周期性&#xff1a; 对称性&#xff1a;或又或者 2.时域抽取法基2FFT基本原理 分类&#xff1a;基2FFT分…

数学专题小结:FFT算法

快速傅里叶变换(FFT,Fast Fourier Transform)是信号处理的常用手段,可以把时域信号变成频域信号,时域的卷积运算对应于频域就成了简单的乘法运算。由于两个多项式的乘积,其系数的运算实际上也是一种卷积运算,因此可以用FFT来计算多项式的乘法。网上关于FFT算法的讲解大多…

转:fft算法(快速傅里叶变换算法)

FFT (Fast Fourier Transform) 是一种快速傅里叶变换算法。它是用来将一个信号从时域转换到频域的算法。这个算法通过分治策略&#xff0c;将一个长度为 N 的复数序列分解成 N/2 个长度为 2 的复数序列&#xff0c;然后对这些小的序列分别进行 FFT 计算。 最简单的 FFT 算法是暴…

快速傅里叶变换(FFT)算法学习

前言 人生如逆旅&#xff0c;我亦是行人。 一、介绍 算法的世界多么广大&#xff0c;我们可以将算法大致分为两类&#xff1a; 第一类是较为有用的算法&#xff1a;比如一些经典的图算法&#xff0c;像 DFS 和 BFS&#xff08;深度 / 广度优先算法&#xff09;&#xff0c;这些…

FFT算法讲解——麻麻我终于会FFT了!

FFT——快速傅里叶变换 这块不写东西空荡荡的&#xff0c;我决定还是把FFT的定义给贴上吧 FFT&#xff08;Fast Fourier Transformation&#xff09;是离散傅氏变换&#xff08;DFT&#xff09;的快速算法。即为快速傅氏变换。它是根据离散傅氏变换的奇、偶、虚、实等特性&…

怎么计算网站流量?

如何计算网站的流量呢&#xff1f;在这华仔给大家分享一个如何计算流量的算法&#xff1a; 举个栗子&#xff1a;1G1024M&#xff0c;10G就是101024M10240M. 一个1M的文件被下载1000次的流量约为1G;被下载10000次的流量约为10G. 假如你每月的网站流量为10G&#xff0c;那10G的流…

CDN流量是什么,怎么计算?

CDN流量通俗来讲就是使用CDN加速时&#xff0c;网络加速会产生一个数据使用量&#xff0c;到达某一个时段&#xff0c;统计出这个时段使用的量&#xff0c;也就是CDN流量&#xff0c;和网站流量的使用很像。 随着互联网的发展&#xff0c;用户在使用网络时对网站的浏览速度和…

流量计算器

为所做的工作处于初始开发的阶段&#xff0c;所以数据一直在变化&#xff0c;导致1s的流量大小一直也在变化。每次都需要手动根据新的参数进行计算&#xff0c;真的好烦。 所以呢&#xff0c;作为一个程序员&#xff0c;能让程序做的事情&#xff0c;自己就不要动手了呀&#x…

Flink1.14相关-3.数据流量计算

1. 前言 使用环境 Flink1.14.6Centos7.9Java8 Flink1.14.6安装部署测试参考&#xff1a;参考链接 2 .数据采集 2.1 信号监听 需要监听文件夹下的新文件产生&#xff0c;并且数据库中的值未更新时才发送消息通知后续模块开始采集数据。【后面需要重新搭建监听部分和判断部分…

适应多场景的客流量统计-人流量统计算法

在商场、展厅、景区等受人流量影响较大的场所&#xff0c;流量统计算法可以快速获取流量数据和动态趋势&#xff0c;辅助评估店铺和部分活动的效果&#xff0c;帮助商业决策。另外&#xff0c;在地铁站、火车站、机场等公共场所。实时检测人数可以及时预警高密度人群&#xff0…

网站的服务器带宽计算,服务器带宽和流量计算方式

服务器带宽和流量计算方式。网站流量和带宽该怎么计算&#xff0c;给一些参照数据信息&#xff0c;由于不清楚流量和带宽是怎么计算的&#xff0c;因此不清楚用多宽的带宽更有效、更节省资产! 网站服务器上最好是安装流量统计手机软件(强烈推荐应用DUMeter)&#xff0c;假如流量…

博途1200/1500PLC累计流量计算FB(SCL算法详解+优化)

在编写这篇博客之前其实已经写过一篇SMART S7-200PLC的流量累计的应用文章,由于很多朋友咨询博途PLC下的流量累计实现算法。今天我们以博途PLC的开发环境为例详细讲解算法的实现原理和注意事项同时给出算法的优化方法。受水平和能力所限,文中难免出现错误和不足之处,诚恳的欢…

阿里云轻量应用服务器流量计算方法

阿里云轻量应用服务器套餐有峰值带宽限制每月流量的&#xff0c;还有固定带宽的&#xff0c;阿里云轻量应用服务器流量是怎么计算的&#xff1f;阿里云轻量应用服务器来说说不同套餐下轻量服务器流量计算方法&#xff1a; 轻量应用服务器带宽套餐和流量套餐 阿里云轻量应用服…

物联网GPRS模块流量计算

物联网GPRS模块流量计算 MQTT(消息队列遥测传输) 是ISO 标准下一个基于TCP/IP的消息发布/订阅传输协议。 一、TCP消耗流量计算 以太网数据包结构&#xff1a; 以太网首部 IP首部 TCP首部 APPL首部 用户数据 以太网尾部 以太网首部为14个字节 IP首部为20个字节 TCP首部…

恒容容器放气的瞬时流量的计算

有时候&#xff0c;你会遇到一个问题&#xff0c;该问题的描述如下&#xff1a; 你有一个已知体积的容器&#xff0c;设容器体积为&#xff0c;里面装有一定压力(初始压力)的气体&#xff0c;如空气或氢气等&#xff0c;设初始压力为&#xff0c;容器出口连接着一个阀门开关&am…