从零开始学习FFT(快速傅里叶变换) 这也是我学习dft算法的心得,谢谢各位

本文主要是介绍从零开始学习FFT(快速傅里叶变换) 这也是我学习dft算法的心得,谢谢各位,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 本文是从最基础的知识开始讲解,力求用最通俗易懂的文字将问题将的通俗易懂,大神勿喷,多多指教啊,虽然说是从零学习FFT,但是基本的数学知识还是要有的,sincos,等。

       FFT(快速傅里叶变换)其本质就是DFT,只不过可以快速的计算出DFT结果,要弄懂FFT,必须先弄懂DFTDFT(DiscreteFourier Transform) 离散傅里叶变换的缩写,咱们先来详细讨论DFT,因为DFT懂了之后,FFT就容易的多了

DFT(FFT)的作用:可以将信号从时域变换到频域,而且时域和频域都是离散的,通俗的说,可以求出一个信号由哪些正弦波叠加而成,求出的结果就是这些正弦波的幅度和相位,我们音乐播放器上面显示的就是音乐fft之后不同频率正弦波的幅度,就像下面这张图片:

里面的柱状高度就是正弦波的幅度

     那么为什么可以求出正弦波的幅度呢,这里就要说一下信号的相关性了,我们也可以利用信号的相关性检测信号波中是否含有某个频率的信号波:把一个待检测信号波乘以另一个信号波,个新的信号波,再把这个新的信号波所有的点进行相加,从相加的结果就可以判断出这两个信号的相似程度,比如下图:

 

        上图中a,b图是待检测信号,cd3个周期的正弦信号,很显然a图含有正弦波,e=a*c,将e图的各点相加,很显然值是正的,这就说明a图含频率为3的正弦波,f=b*d,显然将f图中各点相加结果约等于0了,说明b图不含有周期为3的正弦波,这就是dft的原理,也就是离散傅里叶变换的原理,其实就是这么简单,只不过dft将待检测信号和很多不同频率的正弦波和余弦波相乘,也就是进行了信号相关性检测,从而可以计算出信号中含有的正弦波的幅度,若含有此频率的正弦波,那么幅值不为0,若不含有此正弦波,那么幅值为0,那么幅值是如何计算出来的呢,幅值就是上面e图和f图各点之和(若是连续信号的话就是两信号乘积求积分了,。。额,不说积分,抽象了)

下面来看个具体的例子:


上面图一即为待检测信号,也就是将进行DFT变换的信号,将它分成16个离散的点,图2是一个频率为1的正弦波,也分成16个点,将对应的点相乘,得到图3,再将图3的各个点的幅值相加,结果为10.06,也就是说图1中的图像含有图2的正弦波,此时用到的dft点数就为16,10/(N/2)=10/8=1.25,含有的频率为1的正弦波的幅度就是1.25,以此类推,若要求是否含有频率为2的正弦波,将图1和频率为2的正弦波相乘再求和,。。。。

至于为什么要除以N/2,数字信号处理里面有讲,我就不多说了

     接下来就是dft的实现了:                   

    DFT的公式:

   

   其中X(k)表示DFT变换后的数据,x(n)为采样的模拟信号,公式中的x(n)可以为复信号,实际当中x(n)都是实信号,即虚部为0,此时公式可以展开为:

     从这个公式可以看出,变换后的数据就是原信号对cos和sin的相关操作,即进行相乘求和(连续信号即为积分),为什么我要将n\N写在2k*pi后面呢?因为我觉得在对cos和sin进行相关操作时,k代表和频率为多少的正弦相关,而n和N则是在一个正弦周期内采样N个点,采样间隔为2*pi\N,,n用来步进,一次步进2*pi\N,最后进行累加求和,就得出了X(k),《实用数字信号处理》这本书的DFT章节详细的解释了此公式,并且还进行了举例,看了以后明白了不少,另外,DFT之后的数据是对称的,具体原因还是在那本书上面有,在FFT的章节。比如做8DFT,采样信号为x(n),DFT之后的数据为X(k),那么X(0)为直流信号,X(1), X(2), X(3), X(5), X(6), X(7),关于X(4)对称,X(1)=X(7), X(2)=X(6),X(3)=X(5),如下图,是对1+sin(2*PI)进行DFT变换,具体的幅值先不关心,只要知道它是对称的就行了。

接下来就是对公式写程序了,先将公式展开:

在计算机中可以这样展开:

里面有个j,不用管它,我们用两个数组,一个保存sin相关,一个保存cos相关,由于cos为实部,sin为虚部,可以定义以下两个数组:

float real[N];//用来保存cos相关。

float imag[N];//用来保存sin相关。

可以得到如下程序:

[cpp]  view plain copy
  1. for(k=0;k<N;k++)  
  2. {  
  3.   for(n=0;n<N;n++)  
  4.   {  
  5.     real[k] = real[k] + x[n] * cos(2*PI*k*n/N) ;  
  6.     imag[k] = imag[k] – x[n] * sin(2*PI*k*n/N);  
  7.   }  
  8. }  

Real就是cos相关的幅值,imag就是sin相关的幅值

最后将sincos合成一个sin

就完了。。。

这篇关于从零开始学习FFT(快速傅里叶变换) 这也是我学习dft算法的心得,谢谢各位的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/427226

相关文章

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

Win32下C++实现快速获取硬盘分区信息

《Win32下C++实现快速获取硬盘分区信息》这篇文章主要为大家详细介绍了Win32下C++如何实现快速获取硬盘分区信息,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 实现代码CDiskDriveUtils.h#pragma once #include <wtypesbase

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Spring AI与DeepSeek实战一之快速打造智能对话应用

《SpringAI与DeepSeek实战一之快速打造智能对话应用》本文详细介绍了如何通过SpringAI框架集成DeepSeek大模型,实现普通对话和流式对话功能,步骤包括申请API-KEY、项目搭... 目录一、概述二、申请DeepSeek的API-KEY三、项目搭建3.1. 开发环境要求3.2. mav

Python如何快速下载依赖

《Python如何快速下载依赖》本文介绍了四种在Python中快速下载依赖的方法,包括使用国内镜像源、开启pip并发下载功能、使用pipreqs批量下载项目依赖以及使用conda管理依赖,通过这些方法... 目录python快速下载依赖1. 使用国内镜像源临时使用镜像源永久配置镜像源2. 使用 pip 的并