优雅的FFT算法

TsinghuaJoking 2022-05-30 22:24

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

01 Python算法

  天下午的信号与系统, 给同学们介绍了离散傅里叶变换的基本应用, 并且介绍了快速傅里叶变换(FFT)的主要思想与算法。FFT算法因其优异的性能和广泛的应用, 堪称信息处理领域的原子武器。实现FFT编程语言很多, 比较来比较去, 利用Python语音所描述的该算法最为简明和优雅。

1.1 FFT算法代码

  下面的代码是在  The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?  视频中给出的 FFT 递归算法形式, 最大精度反映了FFT算法核心。

  这个代码实现了DIF(时域抽取快速傅里叶变换), 利用递归定义,将FFT核心算法中的分而治之体现的淋漓尽致, 突出了递归核心中的核心思想。

def FFT(P):
    n = len(P)
    if n * 1return P

    ye = FFT(P[0::2])
    yo = FFT(P[1::2])

    y = [0]*n
    w = exp(-1j*2*pi/n)
    for j in range(n//2):
        yow = w**j * array(yo)
        y[j] = ye[j] + yow[j]
        y[j+n//2] = ye[j] - yow[j]

    return y

  利用Python语音中对于数组切片操作语法, 还可以将上面FFT算法中的循环部分都替换成关于数组的操作, 使得实际运算速度得到提高。

def FFT1(P):
    n = len(P)
    if n * 1return P

    ye = FFT(P[0::2])
    yo = FFT(P[1::2])

    w = exp(-1j*2*pi/n)**array(list(range(n//2)))
    yow = w*yo

    y = [0]*n
    y[:n//2] = ye + yow
    y[n//2:] = ye - yow

    return y

1.2 FFT 算法测试

  为了测试算法的有效性, 下面对于一个方波信号计算对应的FFT结果。

  测试算法代码如下:

LEN = 1024
oneLEN=10
p1 = [1]*oneLEN+[0]*(LEN-oneLEN)

y = FFT(p1)
plt.plot(abs(array(y)), label='abs(FFT)')
plt.plot(p1, label='Data')

plt.xlabel("y")
plt.ylabel("abs(FFT(y))")
plt.grid(True)
plt.legend(loc='upper right')
plt.tight_layout()
plt.show()

  下面是测试利用Python语言实现的FFT算法计算结果。

▲ 图1.2.1 利用Python语音实现的FFT算法测试结果

02 它语言FFT

  FFT算法贵在计算效率,前面使用Python实现FFT,虽然形式上优雅,但实际执行效率不高。提高执行效率,还是需要使用编译语言。

2.1 Fortran FFT算法

  在我上大学期间所学的编程语言为Fortran, 估计现在没有多少同学学习这个算法语言。下面给出了利用Fortran语言实现的FFT算法程序。

  算法整体上包括有两个阶段:

  • 第一个阶段实现了对输入数据进行倒读顺序排列;
  • 第二阶段利用三重循环实现了分组蝶形运算。

  当然了,时过三十年再看Fortran感觉十分酸爽, 但它简练语言和执行高效还是让我们回忆起当年编程时所感觉到的快乐。

▲ 图 Fortran 语言实现的FFT算法

2.2 C语言FFT算法

  下面是在网络上博文 C++ Program to Compute Discrete Fourier Transform using Fast Fourier Transform Approach[1]  给出的FFT算法, 没有对其功能进行测试。相比于前面利用Python,Fortran来看, C语言实现FFT就显得非常啰嗦了。

#include 
#include 
#include 
#include 
using namespace std;
unsigned int bitReverse(unsigned int x, int log2n) {
    int n = 0;
    int mask = 0x1;
    for (int i = 0; i < log2n; i++) {
        n <<= 1;
        n |= (x & 1);
        x >>= 1;
    }
    return n;
}
const double PI = 3.1415926536;
template<class Iter_T>
void fft(Iter_T a, Iter_T b, int log2n) {
    typedef typename iterator_traits<iter_t>:
:value_type complex;
    const complex J(01);
    int n = 1 << log2n;
    for (unsigned int i = 0; i < n; ++i) {
        b[bitReverse(i, log2n)] = a[i];
    }
 
    for (int s = 1; s <= log2n; ++s)  {
        int m = 1 << s;
        int m2 = m >> 1;
        complex w(10);
        complex wm = exp(-J * (PI / m2));
        for (int j = 0; j < m2; ++j) {
            for (int k = j; k < n; k += m) {
                complex t = w * b[k + m2];
                complex u = b[k];
                b[k] = u + t;
                b[k + m2] = u - t;
            }
            w *= wm;
        }
    }
}

 结 ※

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

参考资料

[1]

C++ Program to Compute Discrete Fourier Transform using Fast Fourier Transform Approach: https://www.sanfoundry.com/cpp-program-compute-discrete-fourier-transform-using-fast-fourier-transform-approach/




“喜盈门”杯

第六届福建省大学生智能汽车竞赛胜利闭幕







TsinghuaJoking 这是一个公众号,它不端、不装,与你同游在课下、课上。 卓晴博士,清华大学中央主楼 626A。010-62773349, 13501115467,zhuoqing@tsinghua.edu.cn
评论
  • 习学习笔记&记录学习学习笔记&记录学习学习笔记&记录学习学习笔记&记录学习笔记&记录学习习笔记&记学习学习笔记&记录学习学习笔记&记录学习习笔记&记录学习学习笔记&记录学习学习笔记记录学习学习笔记&记录学习学习笔记&记录学习学习笔记&记录学习学习笔记&记录学习学习笔记&记录学习习笔记&记录学习学习笔记&记录学习学习笔记&记录学习学习笔记&记录学习学习笔记&记录学习学习笔记&记录学习学习笔记&记录学习学习笔记&学习学习笔记&记录学习学习笔记&记录学习学习笔记&记录学习学习笔记&记录学习学习笔记&记
    youyeye 2024-12-10 16:13 105浏览
  • 时源芯微——RE超标整机定位与解决详细流程一、 初步测量与问题确认使用专业的电磁辐射测量设备,对整机的辐射发射进行精确测量。确认是否存在RE超标问题,并记录超标频段和幅度。二、电缆检查与处理若存在信号电缆:步骤一:拔掉所有信号电缆,仅保留电源线,再次测量整机的辐射发射。若测量合格:判定问题出在信号电缆上,可能是电缆的共模电流导致。逐一连接信号电缆,每次连接后测量,定位具体哪根电缆或接口导致超标。对问题电缆进行处理,如加共模扼流圈、滤波器,或优化电缆布局和屏蔽。重新连接所有电缆,再次测量
    时源芯微 2024-12-11 17:11 68浏览
  • 一、SAE J1939协议概述SAE J1939协议是由美国汽车工程师协会(SAE,Society of Automotive Engineers)定义的一种用于重型车辆和工业设备中的通信协议,主要应用于车辆和设备之间的实时数据交换。J1939基于CAN(Controller Area Network)总线技术,使用29bit的扩展标识符和扩展数据帧,CAN通信速率为250Kbps,用于车载电子控制单元(ECU)之间的通信和控制。小北同学在之前也对J1939协议做过扫盲科普【科普系列】SAE J
    北汇信息 2024-12-11 15:45 73浏览
  • 我的一台很多年前人家不要了的九十年代SONY台式组合音响,接手时只有CD功能不行了,因为不需要,也就没修,只使用收音机、磁带机和外接信号功能就够了。最近五年在外地,就断电闲置,没使用了。今年9月回到家里,就一个劲儿地忙着收拾家当,忙了一个多月,太多事啦!修了电气,清理了闲置不用了的电器和电子,就是一个劲儿地扔扔扔!几十年的“工匠式”收留收藏,只能断舍离,拆解不过来的了。一天,忽然感觉室内有股臭味,用鼻子的嗅觉功能朝着臭味重的方向寻找,觉得应该就是这台组合音响?怎么会呢?这无机物的东西不会腐臭吧?
    自做自受 2024-12-10 16:34 136浏览
  • 本文介绍Linux系统(Ubuntu/Debian通用)挂载exfat格式U盘的方法,触觉智能RK3562开发板演示,搭载4核A53处理器,主频高达2.0GHz;内置独立1Tops算力NPU,可应用于物联网网关、平板电脑、智能家居、教育电子、工业显示与控制等行业。修改对应的内核配置文件# 进入sdk目录cdrk3562_linux# 编辑内核配置文件vi./kernel-5.10/arch/arm64/configs/rockchip_linux_defconfig注:不清楚内核使用哪个defc
    Industio_触觉智能 2024-12-10 09:44 90浏览
  •         在有电流流过的导线周围会感生出磁场,再用霍尔器件检测由电流感生的磁场,即可测出产生这个磁场的电流的量值。由此就可以构成霍尔电流、电压传感器。因为霍尔器件的输出电压与加在它上面的磁感应强度以及流过其中的工作电流的乘积成比例,是一个具有乘法器功能的器件,并且可与各种逻辑电路直接接口,还可以直接驱动各种性质的负载。因为霍尔器件的应用原理简单,信号处理方便,器件本身又具有一系列的du特优点,所以在变频器中也发挥了非常重要的作用。  &nb
    锦正茂科技 2024-12-10 12:57 76浏览
  •         霍尔传感器是根据霍尔效应制作的一种磁场传感器。霍尔效应是磁电效应的一种,这一现象是霍尔(A.H.Hall,1855—1938)于1879年在研究金属的导电机构时发现的。后来发现半导体、导电流体等也有这种效应,而半导体的霍尔效应比金属强得多,利用这现象制成的各种霍尔元件,广泛地应用于工业自动化技术、检测技术及信息处理等方面。霍尔效应是研究半导体材料性能的基本方法。通过霍尔效应实验测定的霍尔系数,能够判断半导体材料的导电类型、载流子浓度及载流子
    锦正茂科技 2024-12-10 11:07 64浏览
  • 肖特基具有很多的应用场景, 可以做同步整流,防止电流倒灌和电源反接等,但是随着电源电流的增大,肖特基导通正向压降0.3~0.7v的劣势也越发明显,产生了很多的热,对于工程师的散热设计是个考验,增加了工程师的设计难度和产品成本,目前一种新的理想二极管及其控制器,目前正在得到越来越广泛的应用- BMS,无人机,PLC,安防,家电,电动工具,汽车等都在快速普及理想二极管有三种架构,内置电荷泵的类似无锡明芯微MX5050T这种,驱动能力会弱点,静态功耗200uA,外置电荷泵MX74700T的这种驱动能力
    王萌 2024-12-10 08:51 85浏览
  • RK3506 是瑞芯微推出的MPU产品,芯片制程为22nm,定位于轻量级、低成本解决方案。该MPU具有低功耗、外设接口丰富、实时性高的特点,适合用多种工商业场景。本文将基于RK3506的设计特点,为大家分析其应用场景。RK3506核心板主要分为三个型号,各型号间的区别如下图:​图 1  RK3506核心板处理器型号场景1:显示HMIRK3506核心板显示接口支持RGB、MIPI、QSPI输出,且支持2D图形加速,轻松运行QT、LVGL等GUI,最快3S内开
    万象奥科 2024-12-11 15:42 66浏览
  • 近日,搭载紫光展锐W517芯片平台的INMO GO2由影目科技正式推出。作为全球首款专为商务场景设计的智能翻译眼镜,INMO GO2 以“快、准、稳”三大核心优势,突破传统翻译产品局限,为全球商务人士带来高效、自然、稳定的跨语言交流体验。 INMO GO2内置的W517芯片,是紫光展锐4G旗舰级智能穿戴平台,采用四核处理器,具有高性能、低功耗的优势,内置超微高集成技术,采用先进工艺,计算能力相比同档位竞品提升4倍,强大的性能提供更加多样化的应用场景。【视频见P盘链接】 依托“
    紫光展锐 2024-12-11 11:50 44浏览
  • 智能汽车可替换LED前照灯控制运行的原理涉及多个方面,包括自适应前照灯系统(AFS)的工作原理、传感器的应用、步进电机的控制以及模糊控制策略等。当下时代的智能汽车灯光控制系统通过车载网关控制单元集中控制,表现特殊点的有特斯拉,仅通过前车身控制器,整个系统就包括了灯光旋转开关、车灯变光开关、左LED前照灯总成、右LED前照灯总成、转向柱电子控制单元、CAN数据总线接口、组合仪表控制单元、车载网关控制单元等器件。变光开关、转向开关和辅助操作系统一般连为一体,开关之间通过内部线束和转向柱装置连接为多,
    lauguo2013 2024-12-10 15:53 78浏览
  • 概述 通过前面的研究学习,已经可以在CycloneVGX器件中成功实现完整的TDC(或者说完整的TDL,即延时线),测试结果也比较满足,解决了超大BIN尺寸以及大量0尺寸BIN的问题,但是还是存在一些之前系列器件还未遇到的问题,这些问题将在本文中进行详细描述介绍。 在五代Cyclone器件内部系统时钟受限的情况下,意味着大量逻辑资源将被浪费在于实现较大长度的TDL上面。是否可以找到方法可以对此前TDL的长度进行优化呢?本文还将探讨这个问题。TDC前段BIN颗粒堵塞问题分析 将延时链在逻辑中实现后
    coyoo 2024-12-10 13:28 101浏览
  • 【萤火工场CEM5826-M11测评】OLED显示雷达数据本文结合之前关于串口打印雷达监测数据的研究,进一步扩展至 OLED 屏幕显示。该项目整体分为两部分: 一、框架显示; 二、数据采集与填充显示。为了减小 MCU 负担,采用 局部刷新 的方案。1. 显示框架所需库函数 Wire.h 、Adafruit_GFX.h 、Adafruit_SSD1306.h . 代码#include #include #include #include "logo_128x64.h"#include "logo_
    无垠的广袤 2024-12-10 14:03 69浏览
  • 天问Block和Mixly是两个不同的编程工具,分别在单片机开发和教育编程领域有各自的应用。以下是对它们的详细比较: 基本定义 天问Block:天问Block是一个基于区块链技术的数字身份验证和数据交换平台。它的目标是为用户提供一个安全、去中心化、可信任的数字身份验证和数据交换解决方案。 Mixly:Mixly是一款由北京师范大学教育学部创客教育实验室开发的图形化编程软件,旨在为初学者提供一个易于学习和使用的Arduino编程环境。 主要功能 天问Block:支持STC全系列8位单片机,32位
    丙丁先生 2024-12-11 13:15 45浏览
  • 全球知名半导体制造商ROHM Co., Ltd.(以下简称“罗姆”)宣布与Taiwan Semiconductor Manufacturing Company Limited(以下简称“台积公司”)就车载氮化镓功率器件的开发和量产事宜建立战略合作伙伴关系。通过该合作关系,双方将致力于将罗姆的氮化镓器件开发技术与台积公司业界先进的GaN-on-Silicon工艺技术优势结合起来,满足市场对高耐压和高频特性优异的功率元器件日益增长的需求。氮化镓功率器件目前主要被用于AC适配器和服务器电源等消费电子和
    电子资讯报 2024-12-10 17:09 84浏览
我要评论
0
点击右上角,分享到朋友圈 我知道啦
请使用浏览器分享功能 我知道啦