傅里叶变换 - Fourier Transform

2024-03-19 18:08

本文主要是介绍傅里叶变换 - Fourier Transform,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

傅里叶级数

傅里叶在他的专著《热的解析理论》中提出,任何一个周期函数都可以表示为若干个正弦函数的和,即:
\[f(t)=a_0+\sum_{n=1}^{\infty}(a_ncos(n\omega t)+b_nsin(n\omega t))\]其中\(\omega=\dfrac{2\pi}{T}\)\(T\)为函数的周期。\(a_n/b_n\)\(n\)分别控制了正弦波的振幅与频率。这就是傅里叶级数的三角形式
我们还可以用复指数形式1积分2来表示傅里叶级数:
\[ f(t)=\sum_{n=-\infty}^{\infty}F_ne^{in\omega t} \] \[ F_n=\frac{1}{T}\int_0^T f(t)e^{-in\omega t} dt \]其中\(F\)就是周期函数\(f\)傅里叶级数(Fourier Series, FS)
如果说\(f\)是某段信号在时域上的表现,\(F\)就是其在频域上的表现。傅里叶变换实现的就是从时域到频域的变换。
这里写图片描述

傅里叶变换

对于非周期函数,我们可以将其视为一个以\((-\infty,\infty)\)为一个周期的周期函数。
经过数学推导,得到:
\[ F(\omega)=\int_{-\infty}^\infty f(t)e^{-i\omega t} dt\] \[ f(t)=\frac{1}{2\pi}\int_{-\infty}^\infty F(\omega)e^{i\omega t} d\omega \] 这叫做傅里叶变换(Fouier Transform, FT)傅里叶逆变换(IFT)
注意,其结果都可能是复数。
这时,\(F\)不再是离散的级数,而是一个连续的函数了。
与傅里叶级数的比较:

  • 傅里叶级数:周期信号,离散频率,频率分量的值
  • 傅里叶变换:非周期信号,连续频率,频率分量的密度

卷积定理

卷积定理有两个:
\[ FT[f_1(t)*f_2(t)]=FT[f_1(t)]\cdot FT[f_2(t)] \] \[ IFT[F_1(\omega)*F_2(\omega)]=\frac{1}{2\pi}IFT[F_1(\omega)]\cdot IFT[F_2(\omega)] \] 分别称为时域卷积定理频域卷积定理

下面对时域卷积定理进行证明。
\[ \begin{align*} FT[f_1(t)*f_2(t)] &= FT[\int_{-\infty}^\infty f_1(\tau)f_2(t-\tau) d\tau] \\ &= \int_{-\infty}^\infty[\int_{-\infty}^\infty f_1(\tau)f_2(t-\tau) d\tau]e^{-i\omega t} dt \\ &= \int_{-\infty}^\infty f_1(\tau)[\int_{-\infty}^\infty f_2(t-\tau)e^{-i\omega t} dt]d\tau \\ &= \int_{-\infty}^\infty f_1(\tau)[\int_{-\infty}^\infty f_2(t)e^{-i\omega (t+\tau)} dt]d\tau \\ &= \int_{-\infty}^\infty f_1(\tau)e^{-i\omega\tau}[\int_{-\infty}^\infty f_2(t)e^{-i\omega t} dt]d\tau \\ &= \int_{-\infty}^\infty f_1(\tau)e^{-i\omega\tau}F_2(\omega) d\tau \\ &= F_2(\omega) \int_{-\infty}^\infty f_1(\tau)e^{-i\omega\tau} d\tau \\ &= F_1(\omega)F_2(\omega) \end{align*} \] 其实基本上就是直接展开啦。频域卷积定理的证明也是类似的。
可以观察到,在一个域上进行卷积,相当于在另一个域上进行点积。这启发我们用复杂度低的点积运算来代替复杂度高的卷积运算。

离散时间傅里叶变换

以上的内容都是针对连续信息/连续函数的。但是,计算机是无法存储连续的信息的,只能每隔时间\(T\)对信息进行采样。也就是说,计算机把连续的函数转化为了离散的序列。对于这样一个序列进行的傅里叶变换就称为离散时间傅里叶变换(Discrete Time Fouier Transform, DTFT)
\[ F(\omega)=\sum_{n=-\infty}^\infty f(nT)e^{-i\omega nT } \] 我们其实是用离散的采样点\(nT\)代替了FT中连续的时间\(t\)。进一步,由于采样的结果本质上是一个序列,那么我们可以把序列中连续两项的间隔,也就是采样频率\(T\)看做单位“1”。我们用\(x(n)\)表示采样结果序列,那么有:
\[ X(\omega)=\sum_{n=-\infty}^\infty x(n)e^{-i\omega n} \] 事实上,这个将\(T\)转化为“1”的过程,就是模拟信号转化为数字信号的过程。
其逆变换IDTFT的表达式为:
\[ x(n)=\int_{-\pi}^\pi X(\omega)e^{i\omega n} d\omega\]

离散傅里叶变换

通过DTFT,我们已经能够处理离散的采样信号了。但由于采样结果序列依然是无限长的,计算机还是无法进行处理。从DTFT的式子中可以看出,\(X(\omega)\)是以\(2\pi\)为周期的,那么解决的方法很简单:我们只从时域\((0,2\pi)\)上均匀地取\(N\)个点,用这\(N\)个点计算出频域上的\(N\)个点,这\(N\)个点就可以作为频域上的一个周期。
\[ X(k)=\sum_{n=0}^{N-1}x(n)W_N^{nk} \quad (k=0,1,2...,N-1)\] 其中\(W_N=e^{-i\frac{2\pi}{N}}\),也就是n次单位根。
其实DFT就是将DTFT中的对\(\omega\)积分替换为对\(\frac{2k\pi}{N}\)求和3
这样,我们就得到了一个\(N\)点信号到\(N\)点频域的离散变换,这个变换就叫做离散傅里叶变换(Discrete Fourier Transform, DFT)
其逆变换的表达式为:
\[ x(n)=\frac{1}{N} \sum_{k=0}^{N-1}X(k)W_N^{-nk} \quad (n=0,1,2...,N-1)\]

FS, FT, DTFT, DFT的比较

变换特点
傅里叶级数FS周期信号,离散频率,频率分量的值
傅里叶变换FT非周期信号,连续频率,频率分量的密度
离散时间傅里叶变换DTFT非周期采样信号,连续频率,频率分量的密度
离散傅里叶变换DFT有限长度非周期采样信号,离散频率,对于DTFT频谱频率分量的密度

快速傅里叶变换

朴素进行DFT的复杂度是\(O(n^2)\),这可以从其表达式中看出。事实上我们有一种利用分治进行DFT的\(O(nlogn)\)算法,这就是常常被应用在OI中的快速傅里叶变换(Fast Fourier Transform, FFT)
为了方便,以下若不做特殊说明,\(N\)均是\(2\)的整数次幂,这可以通过在原来的序列后补若干个\(0\)至有\(2\)的整数次幂项来实现。
\[ \begin{align} X(k) &= \sum_{n=0}^{N-1}x(n)W_N^{nk} \\ &= \sum_{n=0,n+=2}^{N-2}x(n)W_N^{nk} + \sum_{n=1,n+=2}^{N-1}x(n)W_N^{nk} \\ &= \sum_{n=0}^{\frac{N}{2}-1}x(2n)W_N^{2nk} + \sum_{n=0}^{\frac{N}{2}-1}x(2n+1)W_N^{(2n+1)k} \\ &= \sum_{n=0}^{\frac{N}{2}-1}x(2n)W_{\frac{N}{2}}^{nk} + W_N\sum_{n=0}^{\frac{N}{2}-1}x(2n+1)W_{\frac{N}{2}}^{nk} \end{align} \] 通过以上变形,原问题变成了两个规模减半的子问题。合并两个子问题的复杂度是\(O(1)\),分治层数为\(O(logn)\),所以计算一项的复杂度是\(O(logn)\),计算\(n\)项的复杂度是\(O(nlogn)\)

例题:多项式乘法

\(n\)次多项式\(f_1(x)=\sum_{i=0}^{n}a_ix^i\)\(m\)次多项式\(f_2(x)=\sum_{i=0}^{m}b_ix^i\)的积为\(n+m\)次多项式\(f_3(x)=\sum_{i=0}^{n+m}c_ix^i\)。给出序列\(a,b\),求序列\(c\)

容易知道\(c_k=\sum_{i=0}^{k}a_ib_{k-i}\),事实上序列\(c\)就是序列\(a\)和序列\(b\)离散卷积
那么根据卷积定理,\(c_k=IDFT[DFT[c_k]]=IDFT[DFT[a_k*b_k]]=IDFT[DFT[a_k]\cdot DFT[b_k]]\)
所以我们只要将序列\(a\)\(b\)DTFT到频域,点积后再IDTFT回时域,就可以得到序列\(c\)啦。

时间复杂度\(O((n+m)log(n+m))\)

快速数论变换

在我们进行DTFT的过程中,使用的是复数。如果精度要求很高(比如求方案数),用复数来进行FFT就会出现误差。所以我们需要找到一个与复数单位根有相似性质的替代。
注意到FFT能够进行的根本因素就是复数单位根具有\(W_N^2=W_{\frac{N}{2}}\)这一性质。事实上,模意义域下的原根4就是复数单位根的一个很好的替代。
定义\(W_N=g^{\frac{P-1}{N}}(mod \ P)\),则有:
\[ X(k)=\sum_{n=0}^{N-1}x(n)W_N^{nk} \quad (mod \ P)\] 这就是快速数论变换(Number Theory Transform, NTT)
进行NTT时,最常用的模数就是998244353,其原根\(g=3\)

Code

UOJ34 - 多项式乘法


  1. \(e^{i\theta}=cos\theta+isin\theta\)

  2. \(\int_a^b f(x)dx\)表示对\(x\in(a,b)\)\(f(x)\)进行积分。↩

  3. 把这个式子转化成类似DTFT的形式:
    \[ X(k)=\sum_{n=0}^{N-1}x(n)W_N^{nk}=\sum_{n=0}^{N-1} x(n)e^{-i \frac{2k\pi}{N}n} \] \(\frac{2k\pi}{N}\)代替的就是DTFT中\(\omega\)的位置。↩

  4. \(P\)的原根\(g\)定义为使得\(g^0,g^1,...,g^{P-2} \ (mod \ P)\)互不相同的数。↩

转载于:https://www.cnblogs.com/VisJiao/p/8483338.html

这篇关于傅里叶变换 - Fourier Transform的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Verybot之OpenCV应用二:霍夫变换查找圆

其实我是想通过这个程序来测试一下,OpenCV在Verybot上跑得怎么样,霍夫变换的原理就不多说了,下面是程序: #include "cv.h"#include "highgui.h"#include "stdio.h"int main(int argc, char** argv){cvNamedWindow("vedio",0);CvCapture* capture;i

css-transform对position:fixed影响

在betterScroll尝试使用position:fixed固定首列,然而并不能实现固定。因为 bscroll / iscroll 是基于 transform 属性实现滚动的, 所以 iscroll 会通过实时修改元素的 transform 属性以达到滚动的效果。父元素如果存在 transform 属性,子元素的 position: fixed 属性无效。betterScroll有个 useTr

【数字信号处理】一文讲清FFT(快速傅里叶变换)

目录 快速傅里叶变换(Fast Fourier Transform,FFT)FFT的背景快速傅里叶变换(Fast Fourier Transform,FFT)DFT的数学表达实际计算重要性和应用频谱泄露、频谱混叠奈奎斯特采样定理参考链接 快速傅里叶变换(Fast Fourier Transform,FFT) FFT的背景 1、为什么要时域→频域频率?50Hz+频率120Hz

CSS-transform【上】(2D转换)【看这一篇就够了!!!】

目录 transform属性 transform的2D变换函数 transform的3D转换属性值 2D转换 translate位移 translate(x,y) x,y为px长度单位 x,y为%百分比 y值不写,默认为0 translateX(x)与translateY(y) translate与绝对定位结合实现元素水平垂直居中 scale(x,y) 百分比单位 sc

傅里叶变换家族

禹晶、肖创柏、廖庆敏《数字图像处理(面向新工科的电工电子信息基础课程系列教材)》 禹晶、肖创柏、廖庆敏《数字图像处理》资源二维码

齐次变换矩阵的原理与应用

齐次变换矩阵的原理与应用 通过齐次变换矩阵,可以描述机械臂末端执行器(法兰)在三维空间中的平移和旋转操作。该矩阵结合了旋转和平移信息,用于坐标变换。 1. 齐次变换矩阵的基本形式 一个齐次变换矩阵 T是一个 4x4 矩阵,表示刚体的旋转和平移: T = [ R t 0 1 ] = [ r 11 r 12 r 13 x r 21 r 22 r 23 y r 31 r 32 r 33 z 0

MATLAB分析图像的离散余弦变换(DCT)

1. MATLAB的介绍以及所需函数的说明:  1.1 MATLAB  MATLAB是matrix&laboratory两个词的组合,意为矩阵工厂(矩阵实验室)。是由美国mathworks 公司发布的主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中,为科学研究、工程设

PyTorch Demo-4 : 数据变换Transforms

Transforms的函数有很多,每次都是直接copy已有的代码,但是不知道具体是什么样子,在这里记录一下 Transforms常用方法的具体说明参考链接1,链接2,或者官方文档。 原始图像采用图像处理经典的Lena: Python代码 from PIL import Imagefrom torchvision import transforms as tfimport ma

【Get深一度】小波变换通俗解释 -算法与数学之美

链接:http://www.zhihu.com/question/22864189/answer/40772083 文章推荐人:杨晓东 从傅里叶变换到小波变换,并不是一个完全抽象的东西,可以讲得很形象。小波变换有着明确的物理意义,如果我们从它的提出时所面对的问题看起,可以整理出非常清晰的思路。     下面就按照傅里叶-->短时傅里叶变换-->小波变换的顺序,讲一下为什么会出现小波这个东

【Get深一度】信号处理(二)——傅里叶变换与傅里叶级数的区别与联系

1.傅里叶级数和傅里叶变换:  傅里叶级数对周期性现象做数学上的分析 傅里叶变换可以看作傅里叶级数的极限形式,也可以看作是对周期现象进行数学上的分析。 除此之外,傅里叶变换还是处理信号领域的一种很重要的算法。要想理解傅里叶变换算法的内涵,首先要了解傅里叶原理的内涵。 傅里叶原理表明:对于任何连续测量的数字信号,都可以用不同频率的正弦波信号的无限叠加来表示。     傅里叶变