精华内容
下载资源
问答
  • cosx傅里叶变换

    万次阅读 2020-03-20 11:06:53
    我们知道,直流信号的傅里叶变换是2πδ(ω)。 根据频移性质可得exp(jω0t)的傅里叶变换是2πδ(ω-ω0)。 再根据线性性质,可得: cosω0t=[exp(jω0t)+exp(-jω0t)]/2的傅里叶变换是πδ(ω-ω0)+πδ(ω+ω0)。 ...

    根据欧拉公式,cosω0t=[exp(jω0t)+exp(-jω0t)]/2。
    我们知道,直流信号的傅里叶变换是2πδ(ω)。
    根据频移性质可得exp(jω0t)的傅里叶变换是2πδ(ω-ω0)。
    再根据线性性质,可得:
    cosω0t=[exp(jω0t)+exp(-jω0t)]/2的傅里叶变换是πδ(ω-ω0)+πδ(ω+ω0)。

    展开全文
  • 十分简明易懂的FFT(快速傅里叶变换

    万次阅读 多人点赞 2018-08-07 11:38:56
    快速傅里叶变换 (fast Fourier transform),即利用计算机计算离散傅里叶变换(DFT)的高效、快速计算方法的统称,简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶...

    FFT前言

    快速傅里叶变换 (fast Fourier transform),即利用计算机计算离散傅里叶变换(DFT)的高效、快速计算方法的统称,简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少,特别是被变换的抽样点数N越多,FFT算法计算量的节省就越显著。

    FFT(Fast Fourier Transformation) 是离散傅氏变换(DFT)的快速算法。即为快速傅氏变换。它是根据离散傅氏变换的奇、偶、虚、实等特性,对离散傅立叶变换的算法进行改进获得的。

    ——百度百科

    FFT(Fast Fourier Transformation),中文名快速傅里叶变换,用来加速多项式乘法
    朴素高精度乘法时间 O ( n 2 ) O(n^2) O(n2),但 F F T FFT FFT O ( n log ⁡ 2 n ) O(n\log_2 n) O(nlog2n)的时间解决
    F F T FFT FFT名字逼格高,也难懂,其他教程写得让人看不太懂,于是自己随便写一下

    • 建议对复数三角函数相关知识有所耳闻 (不会也无所谓)

    • 下面难懂的点我会从网上盗


    多项式的系数表示法和点值表示法

    • F F T FFT FFT其实是一个用 O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n)的时间将一个用系数表示的多项式转换成它的点值表示的算法

    • 多项式的系数表示和点值表示可以互相转换

    系数表示法

    一个n-1次n项多项式 f ( x ) f(x) f(x)可以表示为 f ( x ) = ∑ i = 0 n − 1 a i x i f(x)=\sum^{n-1}_{i=0}a_ix^i f(x)=i=0n1aixi
    也可以用每一项的系数来表示 f ( x ) f(x) f(x),即 f ( x ) = { a 0 , a 1 , a 2 , . . . , a n − 1 } f(x)=\{a_0,a_1,a_2,...,a_{n-1} \} f(x)={a0,a1,a2,...,an1}
    这就是系数表示法,也就是平时数学课上用的方法

    点值表示法

    • 把多项式放到平面直角坐标系里面,看成一个函数

    • n n n个不同的 x x x代入,会得出 n n n个不同的 y y y,在坐标系内就是 n n n个不同的点

    • 那么这 n n n个点唯一确定该多项式,也就是有且仅有一个多项式满足 ∀ k , f ( x k ) = y k ∀k,f(x_k)=y_k k,f(xk)=yk

    • 理由很简单,把 n n n条式子联立起来成为一个有n条方程的n元方程组,每一项的系数都可以解出来

    那么 f ( x ) f(x) f(x)还可以用 f ( x ) = { ( x 0 , f ( x 0 ) ) , ( x 1 , f ( x 1 ) ) , ( x 2 , f ( x 2 ) ) , . . . , ( x n − 1 , f ( x n − 1 ) ) } f(x)=\{(x_0,f(x_0)),(x_1,f(x_1)),(x_2,f(x_2)),...,(x_{n-1},f(x_{n-1}))\} f(x)={(x0,f(x0)),(x1,f(x1)),(x2,f(x2)),...,(xn1,f(xn1))}来表示
    这就是点值表示法


    高精度乘法下两种多项式表示法的区别

    对于两个用系数表示的多项式,我们把它们相乘
    设两个多项式分别为 A ( x ) , B ( x ) A(x),B(x) A(x),B(x)
    我们要枚举 A A A每一位的系数与 B B B每一位的系数相乘
    那么系数表示法做多项式乘法时间复杂度 O ( n 2 ) O(n^2) O(n2)

    但两个用点值表示的多项式相乘,只需要 O ( n ) O(n) O(n)的时间

    什么意思呢?

    设两个点值多项式分别为 f ( x ) = { ( x 0 , f ( x 0 ) ) , ( x 1 , f ( x 1 ) ) , ( x 2 , f ( x 2 ) ) , . . . , ( x n − 1 , f ( x n − 1 ) ) } f(x)=\{(x_0,f(x_0)),(x_1,f(x_1)),(x_2,f(x_2)),...,(x_{n-1},f(x_{n-1}))\} f(x)={(x0,f(x0)),(x1,f(x1)),(x2,f(x2)),...,(xn1,f(xn1))} g ( x ) = { ( x 0 , g ( x 0 ) ) , ( x 1 , g ( x 1 ) ) , ( x 2 , g ( x 2 ) ) , . . . , ( x n − 1 , g ( x n − 1 ) ) } g(x)=\{(x_0,g(x_0)),(x_1,g(x_1)),(x_2,g(x_2)),...,(x_{n-1},g(x_{n-1}))\} g(x)={(x0,g(x0)),(x1,g(x1)),(x2,g(x2)),...,(xn1,g(xn1))}
    设它们的乘积是 h ( x ) h(x) h(x),那么 h ( x ) = { ( x 0 , f ( x 0 ) ⋅ g ( x 0 ) ) , ( x 1 , f ( x 1 ) ⋅ g ( x 1 ) ) , . . . , ( x n − 1 , f ( x n − 1 ) ⋅ g ( x n − 1 ) ) } h(x)=\{(x_0,f(x_0)·g(x_0)),(x_1,f(x_1)·g(x_1)),...,(x_{n-1},f(x_{n-1})·g(x_{n-1}))\} h(x)={(x0,f(x0)g(x0)),(x1,f(x1)g(x1)),...,(xn1,f(xn1)g(xn1))}

    所以这里的时间复杂度只有一个枚举的 O ( n ) O(n) O(n)

    • 突然感觉高精度乘法能 O ( n ) O(n) O(n)暴艹一堆题?

    • 但是朴素的系数表示法转点值表示法的算法还是 O ( n 2 ) O(n^2) O(n2)的,逆操作类似

    • 朴素系数转点值的算法叫DFT(离散傅里叶变换),点值转系数叫IDFT(离散傅里叶逆变换)

    • 难道高精度乘法只能 O ( n 2 ) O(n^2) O(n2)了吗?


    DFT前置知识&技能

    复数

    毕竟高中有所以不多说

    我们把形如a+bi(a,b均为实数)的数称为复数,其中a称为实部,b称为虚部,i称为虚数单位。当虚部等于零时,这个复数可以视为实数;当z的虚部不等于零时,实部等于零时,常称z为纯虚数。复数域是实数域的代数闭包,也即任何复系数多项式在复数域中总有根。 复数是由意大利米兰学者卡当在十六世纪首次引入,经过达朗贝尔、棣莫弗、欧拉、高斯等人的工作,此概念逐渐为数学家所接受。
    ——百度百科

    初中数学老师会告诉你没有 − 1 \sqrt{-1} 1 ,但仅限 R R R
    扩展至复数集 C C C,定义 i 2 = − 1 i^2=-1 i2=1,一个复数 z z z可以表示为 z = a + b i ( a , b ∈ R ) z=a+bi(a,b\in R) z=a+bi(a,bR)
    其中 a a a称为实部 b b b称为虚部 i i i称为虚数单位

    • 在复数集中就可以用 i i i表示负数的平方根,如 − 7 = 7 i \sqrt{-7}=\sqrt{7}i 7 =7 i

    还可以把复数看成平面直角坐标系上的一个点,比如下面


    x x x轴就是实数集中的坐标轴, y y y轴就是虚数单位 i i i

    这个点 ( 2 , 3 ) (2,3) (2,3)表示的复数就是 2 + 3 i 2+3i 2+3i,或者想象它代表的向量 ( 2 , 3 ) (2,3) (2,3)
    其实我们还可以自己想象 (其实没有这种表达方式) 它可以表示为 ( 13 , θ ) (\sqrt{13},\theta) (13 ,θ)
    一个复数 z z z定义为它到原点的距离,记为 ∣ z ∣ = a 2 + b 2 |z|=\sqrt{a^2+b^2} z=a2+b2
    一个复数 z = a + b i z=a+bi z=a+bi共轭复数 a − b i a-bi abi(虚部取反),记为 z ‾ = a − b i \overline{z}=a-bi z=abi

    复数的运算

    复数不像点或向量,它和实数一样可以进行四则运算
    设两个复数分别为 z 1 = a + b i , z 2 = c + d i z_1=a+bi,z_2=c+di z1=a+bi,z2=c+di,那么
    z 1 + z 2 = ( a + c ) + ( b + d ) i z_1+z_2=(a+c)+(b+d)i z1+z2=(a+c)+(b+d)i z 1 z 2 = ( a c − b d ) + ( a d + b c ) i z_1z_2=(ac−bd)+(ad+bc)i z1z2=(acbd)+(ad+bc)i

    复数相加也满足平行四边形法则


    这张是从网上盗的

    A B + A D = A C AB+AD=AC AB+AD=AC

    复数相乘还有一个值得注意的小性质
    ( a 1 , θ 1 ) ∗ ( a 2 , θ 2 ) = ( a 1 a 2 , θ 1 + θ 2 ) (a_1,\theta_1)*(a_2,\theta_2)=(a_1a_2,\theta_1+\theta_2) (a1,θ1)(a2,θ2)=(a1a2,θ1+θ2)
    模长相乘,极角相加


    DFT(离散傅里叶变换)

    • 一定注意从这里开始所有的 n n n都默认为 2 2 2的整数次幂

    对于任意系数多项式转点值,当然可以随便取任意 n n n x x x值代入计算
    但是暴力计算 x k 0 , x k 1 , . . . , x k n − 1 ( k ∈ [ 0 , n ) ) x_k^0,x_k^1,...,x_k^{n-1}(k\in[0,n)) xk0,xk1,...,xkn1(k[0,n))当然是 O ( n 2 ) O(n^2) O(n2)的时间
    其实可以代入一组神奇 x x x,代入以后不用做那么多的次方运算
    这些 x x x当然不是乱取的,而且取这些 x x x值应该就是 傅里叶 的主意了

    考虑一下,如果我们代入一些 x x x,使每个 x x x若干次方等于 1 1 1,我们就不用做全部的次方运算了
    ± 1 ±1 ±1是可以的,考虑虚数的话 ± i ±i ±i也可以,但只有这四个数远远不够

    • 傅里叶说:这个圆圈上面的点都可以做到

    以原点为圆心,画一个半径为 1 1 1单位圆
    那么单位圆上所有的点都可以经过若干次次方得到 1 1 1
    傅里叶说还要把它给 n n n等分了,比如此时 n = 8 n=8 n=8

    橙色点即为 n = 8 n=8 n=8时要取的点,从 ( 1 , 0 ) (1,0) (1,0)点开始,逆时针从 0 0 0号开始标号,标到 7 7 7
    记编号为 k k k的点代表的复数值为 ω n k \omega_n^k ωnk,那么由模长相乘,极角相加可知 ( ω n 1 ) k = ω n k (\omega_n^1)^k=\omega_n^k (ωn1)k=ωnk
    其中 ω n 1 \omega_n^1 ωn1称为 n n n次单位根,而且每一个 ω \omega ω都可以求出 (我三角函数不好)
    ω n k = cos ⁡ k n 2 π + i sin ⁡ k n 2 π \omega_n^k=\cos{k\over n}2π+i\sin{k\over n} 2π ωnk=cosnk2π+isinnk2π

    或者说也可以这样解释这条式子


    注意 s i n 2 θ + c o s 2 θ = 1 sin^2\theta+cos^2\theta=1 sin2θ+cos2θ=1什么的,就容易理解了

    那么 ω n 0 , ω n 1 , . . . , ω n n − 1 \omega^0_n,\omega^1_n,...,\omega^{n-1}_n ωn0,ωn1,...,ωnn1即为我们要代入的 x 0 , x 1 , . . . , x n − 1 x_0,x_1,...,x_{n-1} x0,x1,...,xn1


    单位根的一些性质

    F F T FFT FFT的过程中需要用到 ω \omega ω的一些性质

    ω n k = ω 2 n 2 k \omega^k_n=\omega^{2k}_{2n} ωnk=ω2n2k

    • 它们表示的点(或向量)表示的复数是相同的

    • 证明

    • ω n k = c o s k n 2 π + i s i n k n 2 π = c o s 2 k 2 n 2 π + i s i n 2 k 2 n 2 π = ω 2 n 2 k \omega^k_n=cos{k\over n}2π+isin{k\over n} 2π=cos{2k\over 2n}2π+isin{2k\over 2n} 2π=\omega^{2k}_{2n} ωnk=cosnk2π+isinnk2π=cos2n2k2π+isin2n2k2π=ω2n2k

    ω n k + n 2 = − ω n k \omega^{k+{n \over 2}}_n=-\omega_n^k ωnk+2n=ωnk

    • 它们表示的点关于原点对称,所表示的复数实部相反,所表示的向量等大反向

    • 证明

    • ω n n 2 = c o s n 2 n 2 π + i s i n n 2 n 2 π = c o s π + i s i n π = − 1 \omega^{n\over 2}_n=cos{{n\over 2}\over n}2\pi+isin{{n\over 2}\over n}2\pi=cos\pi+isin\pi=-1 ωn2n=cosn2n2π+isinn2n2π=cosπ+isinπ=1

    • (这个东西和 e i x = c o s x + i s i n x e^{ix}=cosx+isinx eix=cosx+isinx e i π + 1 = 0 e^{i\pi}+1=0 eiπ+1=0有点关系,我不会就不讲了

    ω n 0 = ω n n \omega^0_n=\omega^n_n ωn0=ωnn

    • 都等于 1 1 1,或 1 + 0 i 1+0i 1+0i

    FFT(快速傅里叶变换)

    虽然 D F T DFT DFT搞出来一堆很牛逼 ω \omega ω作为代入多项式的 x x x
    但只是代入这类特殊 x x x值法的变换叫做 D F T DFT DFT而已,还是要代入单位根暴力计算

    • DFT还是暴力 O ( n 2 ) O(n^2) O(n2)

    D F T DFT DFT可以分治来做,于是 FFT(快速傅里叶变换) 就出来了
    首先设一个多项式 A ( x ) A(x) A(x)
    A ( x ) = ∑ i = 0 n − 1 a i x i = a 0 + a 1 x + a 2 x 2 + . . . + a n − 1 x n − 1 A(x)=\sum^{n-1}_{i=0}a_ix^i=a_0+a_1x+a_2x^2+...+a_{n-1}x^{n-1} A(x)=i=0n1aixi=a0+a1x+a2x2+...+an1xn1

    A ( x ) A(x) A(x)下标的奇偶性 A ( x ) A(x) A(x)分成两半,右边再提一个 x x x

    A ( x ) = ( a 0 + a 2 x 2 + . . . + a n − 2 x n − 2 ) + ( a 1 x + a 3 x 3 + . . . + a n − 1 x n − 1 ) A(x)=(a_0+a_2x^2+...+a_{n-2}x^{n-2})+(a_1x+a_3x^3+...+a_{n-1}x^{n-1}) A(x)=(a0+a2x2+...+an2xn2)+(a1x+a3x3+...+an1xn1)

    = ( a 0 + a 2 x 2 + . . . + a n − 2 x n − 2 ) + x ( a 1 + a 3 x 2 + . . . + a n − 1 x n − 2 ) =(a_0+a_2x^2+...+a_{n-2}x^{n-2})+x(a_1+a_3x^2+...+a_{n-1}x^{n-2}) =(a0+a2x2+...+an2xn2)+x(a1+a3x2+...+an1xn2)

    两边好像非常相似,于是再设两个多项式 A 1 ( x ) , A 2 ( x ) A_1(x),A_2(x) A1(x),A2(x),令

    A 1 ( x ) = a 0 + a 2 x + a 4 x 2 + . . . + a n − 2 x n 2 − 1 A_1(x)=a_0+a_2x+a_4x^2+...+a_{n-2}x^{{n\over 2}-1} A1(x)=a0+a2x+a4x2+...+an2x2n1 A 2 ( x ) = a 1 + a 3 x + a 5 x 2 + . . . + a n − 1 x n 2 − 1 A_2(x)=a_1+a_3x+a_5x^2+...+a_{n-1}x^{{n \over 2}-1} A2(x)=a1+a3x+a5x2+...+an1x2n1

    比较明显得出
    A ( x ) = A 1 ( x 2 ) + x A 2 ( x 2 ) A(x)=A_1(x^2)+xA_2(x^2) A(x)=A1(x2)+xA2(x2)

    再设 k &lt; n 2 k&lt;{n\over 2} k<2n,把 ω n k \omega^k_n ωnk作为 x x x代入 A ( x ) A(x) A(x)(接下来几步变换要多想想单位根的性质)

    A ( ω n k ) = A 1 ( ( ω n k ) 2 ) + ω n k A 2 ( ( ω n k ) 2 ) A(\omega^k_n)=A_1((\omega^k_n)^2)+\omega^k_nA_2((\omega^k_n)^2) A(ωnk)=A1((ωnk)2)+ωnkA2((ωnk)2) = A 1 ( ω n 2 k ) + ω n k A 2 ( ω n 2 k ) = A 1 ( ω n 2 k ) + ω n k A 2 ( ω n 2 k ) =A_1(\omega^{2k}_n)+\omega^k_nA_2(\omega^{2k}_n)=A_1(\omega^k_{n\over2})+\omega^k_nA_2(\omega^k_{n\over 2}) =A1(ωn2k)+ωnkA2(ωn2k)=A1(ω2nk)+ωnkA2(ω2nk)

    那么对于 A ( ω n k + n 2 ) A(\omega^{k+{n\over2}}_n) A(ωnk+2n)的话,代入 ω n k + n 2 \omega^{k+{n \over 2}}_n ωnk+2n
    A ( ω n k + n 2 ) = A 1 ( ω n 2 k + n ) + ω n k + n 2 A 2 ( ω n 2 k + n ) A(\omega^{k+{n\over 2}}_n)=A_1(\omega^{2k+n}_n)+\omega^{k+{n\over 2}}_nA_2(\omega^{2k+n}_n) A(ωnk+2n)=A1(ωn2k+n)+ωnk+2nA2(ωn2k+n) = A 1 ( ω n 2 k ω n n ) − ω n k A 2 ( ω n 2 k ω n n ) =A_1(\omega^{2k}_n\omega^n_n)-\omega^k_nA_2(\omega^{2k}_n\omega^n_n) =A1(ωn2kωnn)ωnkA2(ωn2kωnn) = A 1 ( ω n 2 k ) − ω n k A 2 ( ω n 2 k ) = A 1 ( ω n 2 k ) − ω n k A 2 ( ω n 2 k ) =A_1(\omega^{2k}_n)-\omega^k_nA_2(\omega^{2k}_n)=A_1(\omega^k_{n\over2})-\omega^k_nA_2(\omega^k_{n\over2}) =A1(ωn2k)ωnkA2(ωn2k)=A1(ω2nk)ωnkA2(ω2nk)

    • 发现了什么?

    A ( ω n k ) A(\omega^k_n) A(ωnk) A ( ω n k + n 2 ) A(\omega^{k+{n\over2}}_n) A(ωnk+2n)两个多项式后面一坨东西只有符号不同
    就是说,如果已知 A 1 ( ω n 2 k ) A_1(\omega^k_{n\over 2}) A1(ω2nk) A 2 ( ω n 2 k ) A_2(\omega^k_{n\over 2}) A2(ω2nk)的值,我们就可以同时知道 A ( ω n k ) A(\omega^k_n) A(ωnk) A ( ω n k + n 2 ) A(\omega^{k+{n\over2}}_n) A(ωnk+2n)的值
    现在我们就可以递归分治来搞 F F T FFT FFT

    每一次回溯时只扫当前前面一半的序列,即可得出后面一半序列的答案
    n = = 1 n==1 n==1时只有一个常数项,直接 r e t u r n return return
    时间复杂度 O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n)


    IFFT(快速傅里叶逆变换)

    想一下,我们不仅要会 F F T FFT FFT,还要会IFFT(快速傅里叶逆变换)
    我们把两个多项式相乘 (也叫求卷积),做完两遍 F F T FFT FFT也知道了积的多项式的点值表示
    可我们平时用系数表示的多项式,点值表示没有意义

    • 怎么把点值表示的多项式快速转回系数表示法?

    • I D F T IDFT IDFT暴力 O ( n 2 ) O(n^2) O(n2)做?其实也可以用 F F T FFT FFT O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n)的时间搞

    你有没有想过为什么傅里叶是把 ω n k \omega^k_n ωnk作为 x x x代入而不是别的什么数?
    原因是有的但是有我也看不懂
    由于我是沙雕所以只用记住一个结论

    • 一个多项式在分治的过程中乘上单位根的共轭复数,分治完的每一项除以 n n n即为原多项式的每一项系数

    意思就是说 F F T FFT FFT I F F T IFFT IFFT可以一起搞


    朴素版FFT板子

    c + + c++ c++有自带的复数模板 c o m p l e x complex complex
    a . r e a l ( ) a.real() a.real()即表示复数 a a a的实部

    #include<complex>
    #define cp complex<double>
    
    void fft(cp *a,int n,int inv)//inv是取共轭复数的符号
    {
        if (n==1)return;
        int mid=n/2;
        static cp b[MAXN];
        fo(i,0,mid-1)b[i]=a[i*2],b[i+mid]=a[i*2+1];
        fo(i,0,n-1)a[i]=b[i];
        fft(a,mid,inv),fft(a+mid,mid,inv);//分治
        fo(i,0,mid-1)
        {
            cp x(cos(2*pi*i/n),inv*sin(2*pi*i/n));//inv取决是否取共轭复数
            b[i]=a[i]+x*a[i+mid],b[i+mid]=a[i]-x*a[i+mid];
        }
        fo(i,0,n-1)a[i]=b[i];
    }
    

    两个多项式 a , b a,b a,b相乘再转系数多项式 c c c,通常只用打这么一小段

    	cp a[MAXN],b[MAXN];
    	int c[MAXN];
    	fft(a,n,1),fft(b,n,1);//1系数转点值
    	fo(i,0,n-1)a[i]*=b[i];
    	fft(a,n,-1);//-1点值转系数
    	fo(i,0,n-1)c[i]=(int)(a[i].real()/n+0.5);//注意精度
    

    很明显,FFT只能处理 n n n 2 2 2的整数次幂的多项式
    所以在 F F T FFT FFT前一定要把 n n n调到 2 2 2的次幂

    这个板子看着好像很优美,但是

    递归常数太大,要考虑优化…


    FFTの优化——迭代版FFT

    这个图也是盗的

    这个很容易发现点什么吧?

    • 每个位置分治后的最终位置为其二进制翻转后得到的位置

    这样的话我们可以先把原序列变换好,把每个数放在最终的位置上,再一步一步向上合并
    一句话就可以 O ( n ) O(n) O(n)预处理第 i i i位最终的位置 r e v [ i ] rev[i] rev[i]

    fo(i,0,n-1)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
    

    至于蝴蝶变换它死了其实是我不会


    真·FFT板子

    void fft(cp *a,int n,int inv)
    {
        int bit=0;
        while ((1<<bit)<n)bit++;
        fo(i,0,n-1)
        {
            rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
            if (i<rev[i])swap(a[i],a[rev[i]]);//不加这条if会交换两次(就是没交换)
        }
        for (int mid=1;mid<n;mid*=2)//mid是准备合并序列的长度的二分之一
        {
        	cp temp(cos(pi/mid),inv*sin(pi/mid));//单位根,pi的系数2已经约掉了
            for (int i=0;i<n;i+=mid*2)//mid*2是准备合并序列的长度,i是合并到了哪一位
    		{
                cp omega(1,0);
                for (int j=0;j<mid;j++,omega*=temp)//只扫左半部分,得到右半部分的答案
                {
                    cp x=a[i+j],y=omega*a[i+j+mid];
                    a[i+j]=x+y,a[i+j+mid]=x-y;//这个就是蝴蝶变换什么的
                }
            }
        }
    }
    

    这个板子好像不是那么好背
    至少这个板子已经很优美


    FFT后记

    本人版权意识薄弱……

    N T T NTT NTT我来了

    展开全文
  • 傅里叶变换 一维离散傅里叶变换

    万次阅读 热门讨论 2019-11-06 21:08:43
    DFT:(Discrete Fourier Transform)离散傅里叶变换傅里叶变换在时域和频域上都呈离散的形式,将信号的时域采样变换为其DTFT的频域采样。在形式上,变换两端(时域和频域上)的序列是有限长的,而实际上这两组序列...

    1、介绍。

            DFT:(Discrete Fourier Transform)离散傅里叶变换是傅里叶变换在时域和频域上都呈离散的形式,将信号的时域采样变换为其DTFT的频域采样。在形式上,变换两端(时域和频域上)的序列是有限长的,而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT,也应当将其看作其周期延拓的变换。实际应用的时候,都是使用快速傅里叶变换的,因为运算速度快。


    1)、欧拉公式:

    \LARGE \dpi{100} \LARGE e^{\theta i}=cos \theta +(sin \theta )i,其中i是虚数,即i的平方为-1。

     

    2)、一维离散傅里叶变换DFT公式:

            

    展开全文
  • DFT:(Discrete Fourier Transform)离散傅里叶变换傅里叶变换在时域和频域上都呈离散的形式,将信号的时域采样变换为其DTFT的频域采样。在形式上,变换两端(时域和频域上)的序列是有限长的,而实际上这两组序列...

    一、介绍

    1、一维离散傅里叶变换DFT。

            DFT:(Discrete Fourier Transform)离散傅里叶变换是傅里叶变换在时域和频域上都呈离散的形式,将信号的时域采样变换为其DTFT的频域采样。在形式上,变换两端(时域和频域上)的序列是有限长的,而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT,也应当将其看作其周期延拓的变换。

            根据欧拉公式e^{\theta i}=cos \theta +(sin \theta )i,其中W_{N}^k=e^{-\frac{2\pi k }{N}i}=cos(\frac{2\pi k }{N})-sin(\frac{2\pi k }{N})i,i为虚数单位,即i^2=-1

            公式

    展开全文
  • 傅里叶变换 二维离散傅里叶变换

    万次阅读 热门讨论 2019-11-07 15:41:28
    DFT:(Discrete Fourier Transform)离散傅里叶变换傅里叶变换在时域和频域上都呈离散的形式,将信号的时域采样变换为其DTFT的频域采样。在形式上,变换两端(时域和频域上)的序列是有限长的,而实际上这两组序列...
  • 一、基于傅里叶变换的图像校正 由于拍照时,图像被旋转,为方便观看或使用,需要对旋转图像进行校正。 旋转图像矫正流程 思路借鉴 http://johnhany.net/2013/11/dft-based-text-rotation-correction/ 获取图像...
  • 图像傅里叶变换

    千次阅读 2018-04-27 16:14:26
    1. 图像的傅里叶变换傅里叶变换可以看成是时域和频域的转换。一维图像傅里叶变换公式(空间域-&gt;频域):一维傅里叶变换变换公式(频域-&gt;空间域):M×N图像的二维离散傅里叶变换:M×N图像的傅里叶...
  • 二维离散傅里叶变换(代码和性能的优化) 的写法,相结合的话,就可以很容易得出二维FFT的写法。   2、复数类。 package com.zxj.reptile.utils.number; public class Complex { private double real;...
  • 傅里叶级数和傅里叶变换基本定理三角函数的正交性欧拉公式傅里叶级数三角形式指数形式傅里叶变换傅里叶积分定理 最近在做音频处理相关的内容,所以打算对傅里叶的相关内容做一个小结。大学本科时学过复变函数,不过...
  • 傅里叶变换的由来及复数下的傅里叶变换公式证明 1、 考虑到一个函数可以展开成一个多项式的和,可惜多项式并不能直观的表示周期函数,由于正余弦函数是周期函数,可以考虑任意一个周期函数能否表示成为一系列正...
  • 目录傅里叶变换一维连续傅里叶变换一维离散傅里叶变换傅里叶矩阵Matlab中``函数的含义 傅里叶变换 傅立叶变换,表示能将满足一定条件的某个函数表示成三角函数(正弦和/或余弦函数)或者它们的积分的线性组合。在...
  • * 一维离散傅里叶变换DFT和一维逆离散傅里叶变换IDFT计算过程 * * @param array 复数数组 * @param minus 正负值,DFT=-1,IDFT=1 */ private static Complex[] dftProgress(Complex[] array, int minus) { ...
  • 傅里叶变换

    千次阅读 2016-06-29 17:59:39
    基观点理解傅里叶变换
  • 傅里叶变换详解

    2016-12-19 19:43:00
    1. 傅里叶变换的基本结论 (1)三角形式:任何函数都可以用三角形式(无穷多个累加,从1到无穷多个)来表达 (2)复数形式:三角函数和复数之间有一个关系:cosx=(e^ix+e^-ix)/2 sinx=(e^ix-e^-ix)/2 (欧拉公式)...
  • 傅里叶变换推导

    万次阅读 2019-01-11 21:18:58
    图像傅里叶变换 1.周期函数的分解猜想 &amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;数学家总是非常伟大的,数学家拉格朗日大家从小到大在数学课本里面都能见到他的身影,他和一些数学家发现:一些...
  • 傅里叶级数到傅里叶变换

    千次阅读 2017-10-12 16:01:03
    写在前面傅里叶变换这个东东是一块心病,记得刚接触计算机视觉那会儿,最先看的是冈萨雷斯的《数字图像处理》。当看到频率域滤波那章节的时候,首先就是傅里叶变换,当时看了两三遍愣是没懂。无奈之下,去问老师,...
  • 主要参考自 DR_CAN 的B站教程 纯干货傅里叶变换。 0x01 三角函数系的正交性与傅里叶级数 我们首先看一下这个定理: 组成三角级数的函数系 0(sin0x),1(cos0x),sinx,cosx,sin2x,cos2x,…,sinnx,cosnx \begin{aligned} 0...
  • 谈谈傅里叶级数和傅里叶变换 前言 ​ 作为工科大学生,相信很多人都避免不了要学习傅里叶变换傅里叶级数,我是属于每次用到都查询资料代入公式,所以对于它的理解只停留在了科普层面,没有真正理解其中奥秘,所以...
  • 傅里叶级数与傅里叶变换

    千次阅读 2017-06-09 15:15:28
    它是一种特殊形式的函数展开,将一个函数展开,用1,cosxcosx​, sinx​sinx​等基底函数表示。任意两个基底函数在[0,2π]​[0,2\pi]​上是正交的,正交的意思就是积分为0.傅里叶级数一般表示f(x)f(x)为周期函数: ...
  • FFTFFTFFT :快速傅里叶变换的英文缩写,快速傅里叶变换是对离散傅里叶变换 DFTDFTDFT 的优化,用来解决多项式上的操作如 卷积 等问题。 多项式: 系数表示法: 一般在 初中 数学上,表示一个多项式我们用的是系数...
  • 傅里叶变换的推导

    千次阅读 2019-12-29 14:19:49
    首先,隆重推出傅里叶级数的公式,不过这个东西属于“文物”级别的,诞生于19 世纪初,因为傅里叶...一打开《信号与系统》、《锁相环原理》等书籍,动不动就跳出一个“傅里叶级数”或“傅里叶变换”,弄一长串公式,...
  • 高维数据因为其计算代价昂贵(纬度高计算必然昂贵)和建立索引结构的困难(空间索引结构往往面临着“维度灾”),因此有对其进行数据压缩的需求,即对高维数据进行降维,傅里叶变换和小波变换都可以用来做这件事 ...
  • 系统学习傅里叶变换

    2021-08-19 14:05:00
    本篇内容主要记录一下自己学习傅里叶变换的资料,方便回顾。也给要学习傅里叶变换的小伙伴整理一条系统点的路径。可以先学习链接,再看我的笔记,如果有不对的地方请多多指正。 1.直观理解傅里叶变换 ...
  • 通过快速傅里叶变换得到三角插值多项式 一、题目 编程实现快速傅里叶变换算法,使用快速傅里叶变换确定函数f(x)在[-π, π ]上的16次三角插值多项式。 f(x)=x2cosx.f(x) = x^2cosx.f(x)=x2cosx. 二、快速傅里叶变换...
  • 浅谈傅里叶级数到傅里叶变换

    千次阅读 2017-11-10 13:43:53
    约瑟夫·傅里叶男爵(法语:Joseph Fourier,1768年3月21日-1830年5月16日),法国数学家、物理学家,提出傅里叶级数,并将其应用于热传导理论与振动理论,傅里叶变换也以他命名。他被归功为温室效应的发现者。 ...
  • [音频处理]傅里叶变换去噪

    千次阅读 2020-05-31 21:12:50
    写在前面 不是科研狗,基础理论薄弱,写的比较匆忙,有理解有误的地方还请理解和指正。...3 离散傅里叶变换处理音频的C语言代码及讲解 背景 最近接触音视频处理比较多,就遇到了采集的音频数据有噪音的情况。可不可以用

空空如也

空空如也

1 2 3 4 5 ... 15
收藏数 281
精华内容 112
关键字:

cosx的傅里叶变换