摘 要

近十余年数字信号处理技术同计算机技术和大规模集成电路等高新技术一样，有了突飞猛进的发展，已经发展成一门具有巨大研究应用价值的技术科学。在数字信号处理中离散傅里叶变换(Discrete Fourier Transform，DFT)是常用的变换方法，在信号处理和分析中得到很好的应用。而快速傅里叶变换〔Fast Fourier Transform，FFT〕是一种进行傅里叶变换时减少计算量快速有效的算法。

本文研究的基于C 的自适应基底的快速傅里叶变换，它是利用不同基底对不同长度的离散时间信号进行快速傅里叶变换，通过研究其效率和实用性找到对一定范围长度的离散时间信号效率最高实用性最好的基底，最后利用该结果完成对已知长度的离散信号自适应基底的快速傅里叶变换，提高运算效率。

本文是使用VC 6.0软件进行基于C 不同基2基4基8快速傅里叶研究，同时研究其处理的速度以及适用长度，找到不同长度的最佳基底并完成自适应基底的功能实现。

实验研究表明：不同基底对同一长度的处理速度有很大的差异，其中基8的快速傅里叶变换效率最高但对长度要求较为苛刻，相反基2的快速傅里叶变换效率较低但对信号长度要求较低，基4的快速傅里叶变换在二者之间。

关键词：离散时间信号处理；快速傅里叶变换；基底

Abstract

Nearly ten years of digital signal processing technology with computer technology and large scale integrated circuit technology, has been rapid development, has become a great research and application value of science and technology. In digital signal processing, discrete Fourier transform (Discrete Fourier Transform DFT) is a commonly used method of transformation, and has been well applied in signal processing and analysis. Fast Fourier transform [Fast Fourier Transform FFT] is a fast and efficient algorithm for reducing the amount of computation in Fourier transform.

Fast Fourier transform adaptive base based on C is studied in this paper, it is the use of different substrate discrete time signals for different lengths of Fast Fourier transform, discrete time signal to find a range of the length of the highest efficiency real through the research of the efficiency and practicability of the best base, Fast Fourier transform finally complete discrete signal adaptive base the known length of the use of the results, and improve operational efficiency.

This paper is based on C based on 2 different base 4 base 8 Fast Fourier transform using VC 6.0 software, and the processing speed and length of study, the best to find the different length of basal and complete adaptive base functions.

The experimental study shows that the processing speed of different substrates on the same length have great differences, the base 8 of the Fast Fourier transform efficiency is the highest but the length requirements are more demanding, instead based Fast Fourier transform efficiency of 2 is low but the signal length is low, the base 4 of the Fast Fourier transform between the two.

Keywords：Discrete-time signal processing; Fast Fourier transform; radix

目录

第1章 绪论 1

1.1研究背景及意义 1

1.2 国内外发展现状 2

1.3 本文的结构 3

第2章 快速傅里叶变换原理 5

2.1 DFT的计算问题 5

2.2 常用FFT算法介绍 6

2.2.1 素因子算法（PFA） 6

2.2.2 维诺格兰算法（WFTA） 6

2.2.3蝶形算法 6

2.3 8点的时间抽取的几种FFT算法 7

2.3.1 以8点为例进行一次按奇偶分解算法 7

2.3.2以8点为例进行两次按奇偶分解算法 8

2.3.3以8点为例进行三次按奇偶分解算法 8

2.3.4以8点为例子FFT算法特点 9

2.4 本章小结 10

第3章 三种基底的FFT以及运算量的研究 12

3.1 基2FFT 12

3.1.1基本原理 12

3.1.2 程序测试 14

3.1.3 算法理论运算量分析 14

3.2基4FFT 15

3.2.1基本原理 15

3.2.2 程序测试 17

3.2.3 算法理论运算量分析 18

3.3基8FFT 18

3.3.1 基本原理 18

3.3.2 程序测试 19

3.3.3 算法理论运算量分析 20

3.4 基2、基4和基8算法优缺点点分析 20

3.4.1 基2、基4和基8算法的运算量 21

3.4.2 基2、基4和基8算法对信号长度适应性分析 22

3.4.3 基2、基4和基8算法精度及存储器访问次数分析 22

3.5 本章小结 23

第4章 自适应基底快速傅里叶变换设计实现 25

4.1快速傅里叶变换基底自适应的实现过程 25

4.1.1 实现方案与选择 25

4.1.2 实现过程 26

4.2 实际待处理信号处理过程 28

4.2.1 对1024点信号的处理 28

4.2.2 对4096点信号的处理 29

第5章 总结与展望 31

5.1 总结 31

5.2 展望 31

参考文献 33

致谢 34

附录 35

绪论

1.1研究背景及意义

离散傅里叶变换在数字信号处理中的作用可谓是举足轻重，在对信号分析和处理实际应用中它也是最常用的的处理方法之一。法国物理学家、数学家傅里叶傅里叶在200余年前提出傅里叶级数之后，经过人们实际实验发现其变换对于信号处理分析十分有用，后来人们越来越接受使用DFT这种工具来进行信号分析的做法^[1]。

伴随着计算机技术的高速发展，离散傅里叶变换在实际应用中到了一个新的阶段^[2]。在信号处理的实际应用中，傅里叶变换的作用可谓是举足轻重，利用快速傅里叶变换来实现信号的相关、滤波和谱估计都是十分必要的，但是由于采集的信号越来越复杂，计算量变的越来越大。找到一种能够有效提高傅里叶变换速率，减少运算量的算法才能提高快速傅里叶变换的实际应用价值。于是 于1965年Tooley-Tukey发表了快速傅里叶比变换FFT论文，快速傅里叶算法运运而生^[3]。