FFT原理(基2DIT-FFT)及C语言编程思路及实现

这篇具有很好参考价值的文章主要介绍了FFT原理(基2DIT-FFT)及C语言编程思路及实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.FFT原理(fast Fourier transform)

首先说明:采用的是基2时域抽取法(Decimation-In-Time FFT 简称DIT-FFT)。

        FFT实际上是对DFT的一种快速实现算法,实质上就是对DFT抽取,以8点DFT为例:可以分解为两个4点DFT,在继续分解为4个两点DFT,从而缩小DFT运算量,提高运算效率。(因此首先需要理解DFT算法和它的一些基本性质(周期性等))。

注意:FFT需要的采样点数要是个,若采样点数不够则需要补零处理。

具体算法推导过程如下:

FFT原理(基2DIT-FFT)及C语言编程思路及实现

FFT原理(基2DIT-FFT)及C语言编程思路及实现

FFT原理(基2DIT-FFT)及C语言编程思路及实现

FFT原理(基2DIT-FFT)及C语言编程思路及实现 最终得到的蝶形流图如下:

FFT原理(基2DIT-FFT)及C语言编程思路及实现

 2.c语言算法实现

(1)原位计算:简单理解就是每一级蝶形运算计算的结果存储到原来的存储单元就行,这样可以节省内存,降低成本。

(2)旋转因子规律

        首先需要明确FFT一定是对个点进行FFT。下面以N=8为例寻找规律。根据鲽形流图,可以将分为M级蝶形运算。具体推导如下:

FFT原理(基2DIT-FFT)及C语言编程思路及实现

FFT原理(基2DIT-FFT)及C语言编程思路及实现

 下面是一个16点的蝶形流图,可以用来验证一下

FFT原理(基2DIT-FFT)及C语言编程思路及实现

(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级跨度为:。

因此最终得到如下蝶形运算形式:

FFT原理(基2DIT-FFT)及C语言编程思路及实现

(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点的正序和倒序的二进制图如下:

FFT原理(基2DIT-FFT)及C语言编程思路及实现

         i相对容易,每一行只需要加1就可以,j如果从左往右看其实本质上也是加1,因此问题难点实质上在于右边如何从8到4到12等等。这里关键是权重的概念,讲起来可能相对困难,这里大家可以结合下面的代码,调试观察,尝试几组数据之后相信一定可以理解。

框图:

FFT原理(基2DIT-FFT)及C语言编程思路及实现

#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级有个旋转因子。可以带入到前文的流图中进性验证。具体框图入下(重点和难理解的是第三层循环,可以代入值进去理解):

FFT原理(基2DIT-FFT)及C语言编程思路及实现

(7)关于旋转旋转因子的c语言处理思路

FFT原理(基2DIT-FFT)及C语言编程思路及实现         同时需要说明:fft进行的运算都是复数运算,因此进行的加减乘除都是复数的加减乘除。但一般在硬件上输入信号都是由ADC采集的实数信号,因此我们见到的大部分输入都是数值,但其实也可以是复数输入。

(8)完整程序放在这里,大家可以免费下载参考。

DIT-FFT算法c语言实现-C文档类资源-CSDN下载

(9)matlab验证

FFT原理(基2DIT-FFT)及C语言编程思路及实现

 FFT原理(基2DIT-FFT)及C语言编程思路及实现FFT原理(基2DIT-FFT)及C语言编程思路及实现

 FFT原理(基2DIT-FFT)及C语言编程思路及实现

 3.Reference

 参考华东理工大学大学万永菁老师讲的数字信号处理。想要详细学习的可以取找视频学习。

所写内容都是自己下学习fft的过程,其中可能有一些错误,如发现 还望大家指正。文章来源地址https://www.toymoban.com/news/detail-409323.html

到了这里,关于FFT原理(基2DIT-FFT)及C语言编程思路及实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Go语言网络编程:HTTP服务端之底层原理与源码分析——http.HandleFunc()、http.ListenAndServe()

    在 Golang只需要几行代码便能启动一个 http 服务,在上述代码中,完成了两件事: 调用 http.HandleFunc 方法,注册了对应于请求路径 /ping 的 handler 函数 调用 http.ListenAndServe,启动了一个端口为 8999 的 http 服务 2.1 server 结构 Addr :表示服务器监听的地址。如\\\":8080\\\"表示服务器在本地

    2024年02月08日
    浏览(61)
  • 基于Verilog HDL的FFT算法硬件实现(8点,三级流水线,DIT-FFT)

    关于fft的相关知识,在之前的文章中,有过介绍,这里不再具体介绍,可以参考学习。 从傅里叶级数(FS)到傅里叶变换(FT)最后到离散傅里叶变换(DFT)_小张爱学习哦的博客-CSDN博客_fs傅里叶级数 FFT原理(基2DIT-FFT)及C语言编程思路及实现_小张爱学习哦的博客-CSDN博客_c语言

    2024年02月14日
    浏览(37)
  • GO编程语言:简洁、高效、强大的开源编程语言

    在现代软件开发领域,随着应用复杂度的不断提升,开发人员对编程语言的需求也日益增长。GO编程语言,作为一种简洁、高效且具备强大并发能力的新型开源编程语言,逐渐成为了许多开发者的首选。本文将详细介绍GO语言在哪些项目开发中表现出色,以及为什么许多开发者

    2024年02月02日
    浏览(102)
  • 【编程】C++语言编程规范-2

    结合C++ Effective系列参考树、尤其是工程经验教训的总结。 并发 除非必要,尽量少用线程。 多线程编程要守护好内存,使用atomic、mutex、condition variable、future、semaphore、latch、barrier等同步机制避免数据竞争。 尽量缩小临界区,临界区指独占的资源,禁止其他线程访问变量的代

    2024年02月21日
    浏览(51)
  • Go语言网络编程(socket编程)http编程

    Web服务器的工作原理可以简单地归纳为 客户机通过TCP/IP协议建立到服务器的TCP连接 客户端向服务器发送HTTP协议请求包,请求服务器里的资源文档 服务器向客户机发送HTTP协议应答包,如果请求的资源包含有动态语言的内容,那么服务器会调用动态语言的解释引擎负责处理“

    2024年02月09日
    浏览(67)
  • Go语言网络编程(socket编程)WebSocket编程

    WebSocket是一种在单个TCP连接上进行全双工通信的协议 WebSocket使得客户端和服务器之间的数据交换变得更加简单,允许服务端主动向客户端推送数据 在WebSocket API中,浏览器和服务器只需要完成一次握手,两者之间就直接可以创建持久性的连接,并进行双向数据传输 需要安装第

    2024年02月09日
    浏览(73)
  • 自然语言编程系列(二):自然语言处理(NLP)、编程语言处理(PPL)和GitHub Copilot X

           编程语言处理的核心是计算机如何理解和执行预定义的人工语言(编程语言),而自然语言处理则是研究如何使计算机理解并生成非正式、多样化的自然语言。GPT-4.0作为自然语言处理技术的最新迭代,其编程语言处理能力相较于前代模型有了显著提升。Copilot X 构建于

    2024年02月20日
    浏览(67)
  • 模拟计算器编程教程,中文编程开发语言工具编程实例

    模拟计算器编程教程,中文编程开发语言工具编程实例 中文编程系统化教程,不需英语基础。学习链接 ​​​​​​https://edu.csdn.net/course/detail/39036 课程安排:初级1 1  初级概述 2  熟悉构件取值赋值 3 折叠式菜单滑动面板编程 4 自定义图形窗口自定义标题栏编程 5 多行文本

    2024年02月08日
    浏览(65)
  • 【编程语言 · C语言 · 函数指针】

    由于指针可以指向任何存储器位置中的地址,因此它们也可以指向可执行代码的开头。 函数指针或函数指针指向内存中函数的可执行代码。函数指针可以存储在数组中,也可以作为参数传递给其他函数。 函数指针声明使用 * 就像使用任何指针一样: (*func_name)  周围的括号很

    2024年02月10日
    浏览(55)
  • 介绍一些编程语言—C语言

    C 语言是一门 面向过程 的计算机编程语言,与 C++、C#、Java 等面向对象编程语言有所不同。C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、仅产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。 C语言描述问题比汇编语言迅速、工作量小

    2024年02月13日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包