fft.rar_fft_算法复杂度资源-CSDN文库

共1个文件

doc：1个

版权申诉

fft

算法复杂度

147 浏览量 2022-09-14 20:01:56 上传评论收藏 561KB RAR 举报

资源详情

资源评论

资源推荐

收起资源包目录

fft.rar （1个子文件）

fft.doc 1.09MB

第四章快速傅里叶变换

4．1 引言

4．2 直接计算 DFT 的问题及改进的途径

一．DFT 的计算量

两者的差别仅在指数的符号和因子 1/N。

一个 X(k)的值的计算量,如 X(1)

通常 x(n)和都是复数,所以计算一个 X(k)的值需要 N 次复数乘法运算,

和 N-1 次复数加法运算.那么,所有的 X(k)就要 N2 次复数乘法运算,N(N-1)次复

数加法运算.当 N 很大时,运算量将是惊人的,如 N=1024,则要完成 1048576 次(一

百多万次)运算.这样,难以做到实时处理.

二.改进的途径

的对称性和周期性

对称性：

( )

nk nk

N N

W W

周期性：

( ) ( )nk n N k n k N

N N N

W W W

+ +

= =

得：

( ) ( ) 2 ( )

( 1)

n N k N n k nk Nk Nn k n

N N N N N

W W W W W e

- - - -

= = = = =Q

1,,1,0,)()(

��

�

NkWnxkX

�

��

1,,1,0,)(

)(

NnWkX

nx �

1210

)1()2()1()0()1(

�

��

NNNN

WNxWxWxWxX �

/ 2

1( 1)

N j

N N

W W e

= - = = -Q

( / 2)k N k

N N

W W

= -

利用上述特性,可以将有些项合并,并将 DFT 分解为短序列,从而降低运算次

数,提高运算速度.1965 年,库利(cooley)和图基(Tukey)首先提出 FFT 算法.对

于 N 点 DFT,仅需(N/2)log2N 次复数乘法运算.例如 N=1024=210 时，需要

(1024/2)log2 210 =512*10=5120 次。

5120/1048576=4.88% ,速度提高 20 倍

4．3 按时间抽选(DIT)的基-2 FFT 算法（库利-图基算法）

一．算法原理(基 2FFT)

(一)N/2 点 DFT

1．将

( )x n

按 n 的奇偶分为两组作 DFT,设 N=2L ,不足时,可补些零。这样有:

n 为偶数时:

(2 ) ( ), 0,1, , 1

x r x r r= = -L

n 为奇数时:

(2 1) ( ), 0,1, , 1

x r x r r+ = = -L

因此：

( ) [ ( )] ( )

X k DFT x n x n W

= =

1 1

0 0

( ) ( ) ( ) ( ) ( )

N N

nk nk

N N

n n

X k x n W n x n W n

- -

= =

= +

å å

为偶数时为奇数时

2 2

1 1

2 (2 1)

0 0

(2 ) (2 1)

N N

rk r k

N N

r r

x r W x r W

- -

= =

= + +

å å

2 2

1 1

2 2

1 2

0 0

( )( ) ( )( )

N N

rk k rk

N N N

r r

x r W W x r W

- -

= =

= +

å å

由于：

2 /( )

W e e W

- *

= = =

所以，上式可表示为：

2 2

1 1

1 2 1 2

0 0

( ) ( ) ( ) ( ) ( )

N N

rk k rk k

N N

r r

X k x r W W x r W X k W X k

- -

= =

= + = +

å å

其中：

2 2

1 1

0 0

( ) ( ) (2 )

N N

rk rk

r r

X k x r W x r W

- -

= =

å å

2 2

1 1

2 2

0 0

( ) ( ) (2 1)

N N

rk rk

r r

X k x r W x r W

- -

= =

= = +

å å

2．两点结论:

(1) X (k),X (k)均为 N/2 点的 DFT。

(2) X(k)=X (k)+W X (k)只能确定出 X(k)的 k=

0,1, , 1

-L

个；即前一半的

结果。

3．X(k)的后一半的确定由于

2 2

( )

N N

r k

W W

（周期性）,

所以:

2 2

1 1

( )

1 1 1 1

0 0

( ) ( ) ( ) ( )

N N

r k

r r

X k x r W x r W X k

- -

= =

+ = = =

å å

同理：

2 2

( ) ( )

X k X k+ =

这就是说 ,X1(k),X2(k) 的

后一半,分别等于其前一半的值。

又由于

2 2

( )

N N

k k

N N N N

W W W W

= = -

所以：

1 2

( ) ( ) ( )

2 2 2

N N N

X k X k W X k

+ = + + +

1 2

( ) ( ), 0,1, , 1

X k W X k k= - = -L

可见 ,X(k)

的后一半，也完全由 X1(k), X2 (k)的前一半所确定。

*N 点的 DFT 可由两个 N/2 点的 DFT 来计算。

4.蝶形运算

由 X1(k)、X 2(k)表示 X(k)的运算是一种特殊的运算-碟形运算（N/2 个蝶形）

1 2

( ) ( ) ( )

X k X k W X k= +

前一半

( 0,1, , 1)

k = -L

1 2

( ) ( ) ( )

X k X k W X k= -

后一半

( , , 1)

k N= -L

5.计算工作量分析

按奇、偶分组后的计算量：

(1)N/2 点的 DFT 运算量：复乘次数：

( )

2 4

N N

复加次数：

( 1)

2 2

N N

(2)两个 N/2 点的 DFT 运算量：复乘次数：

复加次数：

( 1)

N -

(3)N/2 个蝶形运算的运算量：复乘次数：

复加次数：

N× =

*但是,N 点 DFT 的复乘为 N2 ;复加 N(N-1);与分解后相比可知,计算工作点差不

多减少一半。

例如 N=8 时的 DFT,可以分解为两个 N/2=4 点的 DFT.具体方法如下:

(1)n 为偶数时,即

(0), (2), (4), (6);x x x x

分别记作:

(0) (0),x x=

(1) (2),x x=

(2) (4),x x=

(3) (6);x x=

/ 2 4 ( )N DFT X k=进行点的，得

3 3

1 1 4 4

0 0

( ) ( ) (2 )

rk rk

r r

X k x r W x r W

= =

å å

0,1, 2,3k =

(2)n 为奇数时,

分别记作:

(1) (3),x x=

(2) (5),x x=

(3) (7);x x=

/ 2 4 ( )N DFT X k=进行点的，得

3 3

2 2 4 4

0 0

( ) ( ) (2 1)

rk rk

r r

X k x r W x r W

= =

= = +

å å

0,1, 2,3k =

1 2

( ) ( ) ( )

X k X k W X k= +

1 2

( 4) ( ) ( ), 0,1,2,3

X k X k W X k k+ = - =

(3)对 X (k)和 X (k)进行蝶形运算,前半部为 X(0) X(3),后半部分为 X(4) X(7)

整个过程如下图所示:

评论收藏

内容反馈

版权申诉

我虽横行却不霸道

粉丝: 72
资源: 1万+

fft.rar_fft_算法复杂度

评论0

最新资源

fft.rar_fft_算法复杂度

评论0

FFT.rar_4 3 2 1_fft 4_fft 基4_基2 FFT

pmf-fft-acq.zip_FFT伪码捕获_PMF_FFT_acq_伪码 捕获_伪码捕获

FFT.rar_FFT MSP430_MSP430 fft_fft_msp430 f_基于msp430 波形

FFT.zip_FFT.h FFt.cpp_ccsZX_FFT.H文件_fft_fft.h_fft文件

fft.rar_16点FFT_32点 fft_4 FFT 256_8点dit-fft_fft-4

STM32F4-DSP-FFT-Libraries.rar_STM32F4-DSP-FFT-LIB_dsp FFT_fft ds

256fft.rar.gz_CLB VHDL_fft 256 fpga_fft and VHDL_fft fpga_radix-

MPEG4.rar_MPEG4 标准_MPEG4 音频_faac_faac.h_fft.h

fft_2d_test.rar_2d fft级数展开_fft 雷达_lfmcw回波_速度距离维_雷达FFT

cf_fft_1024_8.rar_Verilog FFT_Verilog 算法_fft_verilog fft

FFT.rar_fft_fft.c

FFT.rar_FFT算法_FFT算法C_c fft_fft_fft C#

FFT.rar_DFT VC_FFT算法_VC++ FFT_fft_vc fft

fft_int.rar_FFT 单片机_fft_single_单片机 fft_单片机FFT

Xilinx_FPGA_FFT_应用笔记.rar_FFT笔记_FPGA FFT_Xilinx fft_fft_算法笔记

fft.rar_I AM_fft_vhdl_fft

Fft.rar_The Show_fft.c

fft.rar_FFT算法_fft_vhdl_fft

FFT算法和STFT算法比较20041215.rar_fft matlab_fft和stft_stft和fft_stft和fft

冰河的渗透实战笔记-冰河.pdf

大灰狼远控2021最新版，解压密码222

J-LINK V10 V11固件.rar

ISO21434.pdf

Web安全漏洞扫描工具-AWVS14

CTF 竞赛入门指南（ctf-all-in-one）.pdf

Web中间件常见漏洞总结.pdf

stm32f103 adc采样+dma传输+fft处理 频率计_fft处理_stm32_ADCFFT_频率计_ADC采样_

jts-1.14.zip

CobaltStrike4.4.zip

最新资源

pmf-fft-acq.zip_FFT伪码捕获_PMF_FFT_acq_伪码捕获_伪码捕获

stm32f103 adc采样+dma传输+fft处理频率计_fft处理_stm32_ADCFFT_频率计_ADC采样_