当前位置：文档之家 › 快速FFT变换-公式展开过程

快速FFT变换-公式展开过程

  • 格式：doc
  • 大小：2.32 MB
  • 文档页数：4

以16点序列做FFT变换：

倒序：

0000,1000,0100,1100,0010,1010,0110,1110,0001,1001,0101,1101,0011,1011,0111,1111

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

mkNNmmkWxX10 1 , ,2 ,1 ,0Nk NjNeW2, 1)sin()cos(222/jeeWjNNjNN

kmNNmmmkNNmmkWxWxX)12(12/012212/02,

mkNNmmkNmkNNmmkWxWWxX212/012212/02,

mkNNmmkNmkNNmmkWxWWxX2/12/0122/12/02, 2/222/NjNNeWW

)()12(2/14/01)12(2)2(2/14/01)2(2)12(2/14/0)12(2)2(2/14/0)2(2kmNNmmkmNNmmkNkmNNmmkmNNmmkWxWxWWxWxX,

)(22/14/0342/22/14/01422/14/0242/22/14/04mkNNmmkNmkNNmmkNmkNNmmkNmkNNmmkWxWWxWWxWWxX,

)(4/14/0342/4/14/0144/14/0242/4/14/04mkNNmmkNmkNNmmkNmkNNmmkNmkNNmmkWxWWxWWxWWxX, 4/2422/4/NjNNNeWWW

)()12(4/18/02)12(4)2(4/18/02)2(42/)12(4/18/0)12(4)2(4/18/0)2(4kmNNmmkmNNmmkNkmNNmmkmNNmmkWxWxWWxWxX

)]([)12(4/18/03)12(4)2(4/18/03)2(42/)12(4/18/01)12(4)2(4/18/01)2(4kmNNmmkmNNmmkNkmNNmmkmNNmmkNWxWxWWxWxW

)(24/18/0684/24/18/0282/24/18/0484/24/18/08mkNNmmkNmkNNmmkNmkNNmmkNmkNNmmkWxWWxWWxWWxX

)]([24/18/0784/24/18/0382/24/18/0584/24/18/018mkNNmmkNmkNNmmkNmkNNmmkNmkNNmmkNWxWWxWWxWWxW，

)(8/18/0684/8/18/0282/8/18/0484/8/18/08mkNNmmkNmkNNmmkNmkNNmmkNmkNNmmkWxWWxWWxWWxX

)]([8/18/0784/8/18/0382/8/18/0584/8/18/018mkNNmmkNmkNNmmkNmkNNmmkNmkNNmmkNWxWWxWWxWWxW， 8/288/NjNNeWW

)()12(8/116/04)12(8)2(8/116/04)2(84/)12(8/116/0)12(8)2(8/116/0)2(8kmNNmmkmNNmmkNkmNNmmkmNNmmkWxWxWWxWxX

)]([)12(8/116/06)12(8)2(8/116/06)2(84/)12(8/116/02)12(8)2(8/116/02)2(82/kmNNmmkmNNmmkNkmNNmmkmNNmmkNWxWxWWxWxW

)({)12(8/116/05)12(8)2(8/116/05)2(84/)12(8/116/01)12(8)2(8/116/01)2(8kmNNmmkmNNmmkNkmNNmmkmNNmmkNWxWxWWxWxW

)]}([)12(8/116/07)12(8)2(8/116/07)2(84/)12(8/116/03)12(8)2(8/116/03)2(82/kmNNmmkmNNmmkNkmNNmmkmNNmmkNWxWxWWxWxW,

)(28/116/012168/28/116/04164/28/116/08168/28/116/016mkNNmmkNmkNNmmkNmkNNmmkNmkNNmmkWxWWxWWxWWxX

)]([28/116/014168/28/116/06164/28/116/010168/28/116/02162/mkNNmmkNmkNNmmkNmkNNmmkNmkNNmmkNWxWWxWWxWWxW

)({28/116/013168/28/116/05164/28/116/09168/28/116/0116mkNNmmkNmkNNmmkNmkNNmmkNmkNNmmkNWxWWxWWxWWxW

)]}([28/116/015168/28/116/07164/28/116/011168/28/116/03162/mkNNmmkNmkNNmmkNmkNNmmkNmkNNmmkNWxWWxWWxWWxW,

)(16/116/012168/16/116/04164/16/116/08168/16/116/016mkNNmmkNmkNNmmkNmkNNmmkNmkNNmmkWxWWxWWxWWxX

)]([16/116/014168/16/116/06164/16/116/010168/16/116/02162/mkNNmmkNmkNNmmkNmkNNmmkNmkNNmmkNWxWWxWWxWWxW

)({16/116/013168/16/116/05164/16/116/09168/16/116/0116mkNNmmkNmkNNmmkNmkNNmmkNmkNNmmkNWxWWxWWxWWxW

)]}([16/116/015168/16/116/07164/16/116/011168/16/116/03162/mkNNmmkNmkNNmmkNmkNNmmkNmkNNmmkNWxWWxWWxWWxW, 16/21616/NjNNeWW

0000,1000,0100,1100,0010,1010,0110,1110,0001,1001,0101,1101,0011,1011,0111,1111

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

16点序列做FFT变换公式：

)]([)(148/64/108/22/128/44/88/0xWxWxWxWxWxWxWxXkNkNkNkNkNkNkNk

)]}([)({158/74/118/32/138/54/98/1xWxWxWxWxWxWxWxWkNkNkNkNkNkNkNkN,

)]([)(1408/604/1008/202/1208/404/808/00xWxWxWxWxWxWxWxXNNNNNNN

)]}([)({1508/704/1108/302/1308/504/908/10xWxWxWxWxWxWxWxWNNNNNNNN

)]([)(1418/614/1018/212/1218/414/818/01xWxWxWxWxWxWxWxXNNNNNNN

)]}([)({1518/714/1118/312/1318/514/918/11xWxWxWxWxWxWxWxWNNNNNNNN

)]([)(1428/624/1028/222/1228/424/828/02xWxWxWxWxWxWxWxXNNNNNNN

)]}([)({1528/724/1128/322/1328/524/928/12xWxWxWxWxWxWxWxWNNNNNNNN

)]([)(1438/634/1038/232/1238/434/838/03xWxWxWxWxWxWxWxXNNNNNNN

)]}([)({1538/734/1138/332/1338/534/938/13xWxWxWxWxWxWxWxWNNNNNNNN

)]([)(1448/644/1048/242/1248/444/848/04xWxWxWxWxWxWxWxXNNNNNNN

)]}([)({1548/744/1148/342/1348/544/948/14xWxWxWxWxWxWxWxWNNNNNNNN

)]([)(1458/654/1058/252/1258/454/858/05xWxWxWxWxWxWxWxXNNNNNNN

)]}([)({1558/754/1158/352/1358/554/958/15xWxWxWxWxWxWxWxWNNNNNNNN

)]([)(1468/664/1068/262/1268/464/868/06xWxWxWxWxWxWxWxXNNNNNNN

)]}([)({1568/764/1168/362/1368/564/968/16xWxWxWxWxWxWxWxWNNNNNNNN

)]([)(1478/674/1078/272/1278/474/878/07xWxWxWxWxWxWxWxXNNNNNNN

)]}([)({1578/774/1178/372/1378/574/978/17xWxWxWxWxWxWxWxWNNNNNNNN

)]([)(1488/684/1088/282/1288/484/888/08xWxWxWxWxWxWxWxXNNNNNNN

)]}([)({1588/784/1188/382/1388/584/988/18xWxWxWxWxWxWxWxWNNNNNNNN

合集下载

快速傅里叶变换（FFT）详解

快速傅里叶变换（FFT）详解

快速傅⾥叶变换（FFT）详解

本⽂只讨论FFT在信息学奥赛中的应⽤

⽂中内容均为个⼈理解，如有错误请指出，不胜感激

前⾔

先解释⼏个⽐较容易混淆的缩写吧

DFT：离散傅⾥叶变换—>O(n2)计算多项式乘法

FFT：快速傅⾥叶变换—>O(n∗log(n)计算多项式乘法

FNTT/NTT：快速傅⾥叶变换的优化版—>优化常数及误差

FWT：快速沃尔什变换—>利⽤类似FFT的东西解决⼀类卷积问题

MTT：⽑爷爷的FFT—>⾮常nb/任意模数

FMT 快速莫⽐乌斯变化—>感谢stump提供多项式

系数表⽰法

设A(x)表⽰⼀个n−1次多项式

则A(x)=∑ni=0ai∗xi

例如：A(3)=2+3∗x+x2

利⽤这种⽅法计算多项式乘法复杂度为O(n2)

（第⼀个多项式中每个系数都需要与第⼆个多项式的每个系数相乘）

点值表⽰法

将n互不相同的x带⼊多项式，会得到n个不同的取值y

则该多项式被这n个点(x1,y1),(x2,y2),…,(xn,yn)唯⼀确定

其中yi=∑n−1j=0aj∗xji例如：上⾯的例⼦⽤点值表⽰法可以为(0,2),(1,6),(2,12)

利⽤这种⽅法计算多项式乘法的时间复杂度仍然为O(n2)

（选点O(n)，每次计算O(n)）

我们可以看到，两种⽅法的时间复杂度都为O(n2)，我们考虑对其进⾏优化

对于第⼀种⽅法，由于每个点的系数都是固定的，想要优化⽐较困难

对于第⼆种⽅法，貌似也没有什么好的优化⽅法，不过当你看完下⾯的知识，或许就不这么想了

复数

在介绍复数之前，⾸先介绍⼀些可能会⽤到的东西

向量

同时具有⼤⼩和⽅向的量

在⼏何中通常⽤带有箭头的线段表⽰

圆的弧度制

等于半径长的圆弧所对的叫做1的⾓，⽤符号rad表⽰，读作弧度。⽤弧度作单位来度量⾓的制度叫做弧度制

公式:

1∘=π180rad180∘=πrad

平⾏四边形定则

(好像画的不是很标准。。)

平⾏四边形定则：AB+AD=AC

复数定义

设a,b为实数，i2=−1，形如a+bi的数叫复数，其中i被称为虚数单位，复数域是⽬前已知最⼤的域

离散傅里叶变换及其快速算法

离散傅里叶变换及其快速算法

第五章离散傅里叶变换及其快速算法1离散傅里叶变换(DFT)的推导

(1)时域抽样：

目的：解决信号的离散化问题。

效果：连续信号离散化使得信号的频谱被周期延拓。⑵时域截断： 原因：工程上无法处理时间无限信号。

方法：通过窗函数(一般用矩形窗)对信号进行逐段截取。结果：时域 乘以矩形脉冲信号，频域相当于和抽样函数卷积。

(3) 时域周期延拓：

目的：要使频率离散，就要使时域变成周期信号。

方法：周期延拓中的搬移通过与 、：(t_nTs)的卷积来实现。

表示：延拓后的波形在数学上可表示为原始波形与冲激串序列的卷积。

结果：周期延拓后的周期函数具有离散谱。

经抽样、截断和延拓后，信号时域和频域都是离散、周期的。过程见图

▲

t

載曲后

ft \ \ t \ f

0 .............. ►

t ---------------- r f

i 0/

1 L L 紹后 -7

i

i t

7 V

0 0 亍延拓

・V普义PFT

「州 -PTT nh

图1 DFT推导过程示意图

〜 00 ”N 4

处理后信号的连续时间傅里叶变换：|~⑴虫ls h(nT2o n=0 「忆飞

n/N -kfo) (i) l~(f)是离散函数，仅在离散频率点f二kf。k —处存在冲激，强度为ak，其

To NTs

余各点为0。

〜 N N 1

(ii) H(f)是周期函数，周期为Nfo == I，每个周期内有N个不同的幅值。

To NTs Ts

(iii) 时域的离散时间间隔(或周期)与频域的周期(或离散间隔)互为倒数。

2 DFT及IDFT的定义

(1) DFT定义：设hnTs是连续函数h(t)的N个抽样值J，这N个点的宽度为

N 的 DFT 为:DFTN h(nTs)]=A h(nTs)ej 2ffi/N =H ——J (k =0,1,..., N_1)

7 lNTs 丿

IDFT定义：设H上是连续频率函数吧的N个抽样值k亠，…• N J，这N个点(NTs丿 的宽度为N的IDFT为：

离散傅里叶变换和快速傅里叶变换的区别

离散傅里叶变换和快速傅里叶变换的区别

离散傅里叶变换和快速傅里叶变换的区别

离散傅里叶变换（Discrete Fourier Transform，DFT）和快速傅里叶变换（Fast Fourier Transform，FFT）都是数字信号处理中常用的算法，用于将时域信号转换为频域信号。虽然它们都是傅里叶变换的变种，但它们之间有很大的区别。

DFT是一种直接计算傅里叶变换的方法，它将N个时域采样点转换为N个频域采样点。DFT的计算复杂度为O(N^2)，因此对于大规模的信号处理任务来说，计算时间会非常长。而FFT是一种基于分治思想的算法，它将DFT的计算复杂度降低到O(NlogN)，因此计算速度非常快，特别适合于大规模信号处理任务。

DFT和FFT的计算方式也有所不同。DFT的计算公式为：

X[k] = sum(x[n] * exp(-j*2*pi*k*n/N))

其中，x[n]表示时域采样点，X[k]表示频域采样点，N表示采样点数，k和n分别表示频域和时域的索引。这个公式需要进行N^2次复数乘法和加法运算，因此计算复杂度很高。

FFT的计算方式则是将DFT的计算过程分解为多个子问题，然后递归地求解这些子问题。具体来说，FFT将N个采样点分为两个子序列，分别进行DFT计算，然后将它们合并起来得到整个序列的DFT结果。这个过程可以递归地进行下去，直到只剩下一个采样点为止。由于FFT采用了分治思想，它的计算复杂度为O(NlogN)，比DFT快得多。

DFT和FFT的应用场景也有所不同。由于DFT的计算复杂度较高，因此它适合于小规模的信号处理任务，例如音频信号的处理。而FFT则适合于大规模的信号处理任务，例如图像处理和视频处理。此外，FFT还可以用于信号压缩、滤波和频域分析等领域。

离散傅里叶变换和快速傅里叶变换虽然都是傅里叶变换的变种，但它们之间有很大的区别。DFT是一种直接计算傅里叶变换的方法，计算复杂度较高，适合于小规模的信号处理任务；而FFT是一种基于分治思想的算法，计算速度非常快，适合于大规模的信号处理任务。

fft(x,n)实例解释

fft(x,n)实例解释

FFT（Fast Fourier Transform，快速傅里叶变换）是一种高效的计算离散傅里叶变换（DFT）及其逆变换的算法。在信号处理、图像处理等领域有着广泛的应用。下面通过一个简单的实例来解释FFT（x，n）的计算过程。

假设我们有一个长度为8的离散信号x，其值为：

x = [1, 2, 3, 4, 5, 6, 7, 8]

我们希望计算该信号的离散傅里叶变换，并求得其频率分量。首先，我们需要确定信号的长度n和采样频率。在这个例子中，n=8，采样频率为1。

接下来，我们将信号x分成两个长度相等的子序列：x_even和x_odd。这两个子序列分别包含偶数下标和奇数下标的元素。在本例中，x_even = [1, 3, 5, 7]，x_odd = [2, 4, 6, 8]。

然后，我们分别对这两个子序列进行FFT计算。对于x_even，其DFT为：

X_even(k) = FFT([1, 3, 5, 7]) = [10 + 0j, -2 + 2j, -2 + 0j, -2 - 2j]

对于x_odd，其DFT为：

X_odd(k) = FFT([2, 4, 6, 8]) = [-2 + 0j, -2 - 2j, -2 + 2j, 10 + 0j]

最后，我们将这两个子序列的DFT结果合并起来，得到原始信号x的DFT：

X(k) = X_even(k) + X_odd(k) = [10 + 0j, -2 + 2j, -2 + 0j, -2 - 2j] + [-2 + 0j,

-2 - 2j, -2 + 2j, 10 + 0j] = [8 + 0j, -4 + 4j, -4 + 0j, -4 - 4j]

至此，我们已经完成了FFT（x，n）的计算过程。从结果可以看出，原始信号x的频率分量分别为8Hz、4Hz、4Hz和-4Hz。这些频率分量可以用于信号分析、滤波等应用。