摘要当今的无线通信、图像处理和频谱分析等众多工程领域，快速傅里叶变换占有很重要的地位。针对某些特殊序列，研究其更高效的算法就更加具有意义。

本文在研究和原理的基础上，针对具有共轭对称性的输入序列，通过观察它的蝶形结构以及每级输入输出间的特殊关系，推导出蝶形运算、共轭赋值等一系列变量的通式，在此基础上用编写出比传统算法减少一半运算量的算法程序。然后，采用原位运算进而实现一种可以再减少一半存储空间的进一步优化算法，推导改写后，编写出优化后的算法程序。调用库中的传统函数，比较三种算法运行时间、占用空间等参数，验证两种改进算法的正确性与优越性。最后，讨论了相应的其他几种特殊输入序列的改进算法，拓展了思路。80590

毕业论文关键词      共轭对称  算法优化

毕业设计说明书外文摘要

Title   DFT and FFT algorithms of conjugate symmetric data   

Abstract Nowadays, in wireless communications, image processing, spectral analysis and many other engineering fields, fast Fourier transform takes a very important position。 For some special sequences, it is more meaningful to study a more efficient algorithm。

Based on the study of principle of DFT and FFT, for the input sequence with conjugate symmetry, the paper derives the general formula of a series of variables, such as butterfly and conjugated assignment by observing its butterfly structure and  special relationship between input and output of each stage 。On this base ,we write the algorithm program with MATLAB which can reduce half amount of computation compared with the traditional method。 Then, the paper proposes a more optimized algorithm to further reduce half the storage space。 After derivation and rewriting, the optimized algorithm program is written。 By transferring traditional function of FFT in the storehouse of MATLAB, we compare the running time, space and other parameters of three algorithms to verify the correctness and superiority of two improved algorithms。 Finally, the paper discusses corresponding improvement on FFT algorithm of several other special input sequence which expands the idea。

Keywords  FFT  Conjugate symmetric  algorithm optimization

目次

1  绪论 1

1。1  课题研究背景及意义 1

1。2  FFT算法研究状况及国内外现状 2

1。3  本论文主要研究的内容 3

2  FFT算法原理 4

2。1  离散傅里叶变换 4

2。2  快速傅里叶变换 5

2。2。1  按时间抽取的基2FFT算法 6

2。2。2  按频率抽取的基2FFT算法 10

2。2。3  Bruun FFT算法 14

2。3  本章小结 15

3  两种改进FFT算法的MATLAB实现 16

3。1  共轭对称数据FFT算法 16

3。2  进一步改进的FFT算法 20

3。3  本章小结 25

4  结果及分析