基于TS101的DFT输出子集算法研究及软件实现

摘要

自从库利-图基FFT算法出现以来，各种不同类型的FFT算法相继出现，但是这些快速傅立叶变换的算法一般基于这样一种假设，即假定输入和输出长度是相等的。在大部分应用场合这是一个合理的假设，但是仍然有一些应用场合输入和输出点数明显不同，比如说矩阵处理计算本征值的高分辨率谱或者在滤波器设计中计算转换域(通带和阻带之间)的响应。另外FFT固有的频率分辨率与计算量之间的矛盾从某种程度上也限制了它的应用,因为要提高FFT的频率分辨率，就要增加采样点数及计算量。而当数据足够长时，有时又不需要频域的全部频点，而只要得到频谱中某一频带或一部分频点的值即可，那么对无关频点的计算就是多余的，找到能够有效的计算DFT部分输出点(输出子集)的算法一直是学者们所关注的。
　　本文首先介绍了Goertzel算法、FFTPruning算法和变换分解法等DFT输出子集应用的算法，推导了它们的理论算法复杂度公式，并根据算法复杂度公式对各种算法的运算量进行了初步的对比。
　　然后结合分裂基算法和Goertzel算法改进了变换分解法，进一步提高了变换分解法的运算效率。之后，本文介绍了相关算法的软件设计方法，并在VisualDSP++5.0上以TS101为目标处理器仿真运行得到相关数据，验证了理论推导的结果。结果表明变换分解法可以较大程度的提高DFT输出子集应用的计算效率，而且适用性较高。并讨论了P的取值对变换分解法总运算量的影响。考虑了实际的寻址运算所需操作之后，推导得到了最优P值的求取公式。对于1024点变换16点输出的DFT，在P取得最优值时，改进后的变换分解法可以比基-2FFT算法减少大约36％的运算时间。
　　文章的最后讨论了实输入情况下的输出子集算法，使用实输入分裂基算法进一步优化了经过改进的变换分解法。

目录

基于TS101的DFT输出子集算法研究及软件实现

THE ALGORITHM OF DFT WITH A SUBSET OF OUTPUT POINTS BASED ON TS101 AND ITS SOFTWARE IMPLEMENTATION

摘要

Abstract

绪论

1.1 课题的研究背景与意义

1.2 国内外发展现状

1.2.1 DFT输出子集算法研究现状

1.2.2 FFT处理器发展现状

1.3 本课题研究的主要内容

1.4 本文的结构安排

第2章 DFT输出子集算法概述

2.1 引言

2.2 Goertzel算法概述

2.3 FFT Pruning算法概述

2.3.1 FFT Pruning算法原理

2.3.2 FFTPruning算法的算法复杂度

2.4 变换分解法概述

2.4.1 变换分解法原理

2.4.2 变换分解法算法复杂度

2.5 算法的理论复杂度对比

2.6 本章小结

第3章 改进的变换分解法

3.1 引言

3.2 分裂基算法概述

3.2.1 分裂基算法原理

3.2.2 分裂基算法的算法复杂度

3.3 改进的变换分解法

3.3.1 改进的TD算法原理

3.3.2 改进后算法的复杂度

3.3.3 P的取值对总运算量的影响

3.4 本章小结

第4章 算法的软件实现及仿真分析

4.1 软件开发环境简述

4.1.1 ADSP-TS101的结构和特点

4.1.2 软件开发平台（Visual DSP++）简介

4.2 算法的软件实现

4.2.1 基-2 FFT算法的软件实现

4.2.2 Goertzel算法的软件实现

4.2.3 FFT Pruning算法的软件实现

4.2.4 分裂基算法的软件实现

4.2.5 变换分解法的软件实现

4.3 仿真结果分析

4.3.1 算法的运算量对比

4.3.2 变换分解法中P的取值对总运算量的影响

4.4 本章小结

第5章 输入为实数时的输出子集算法

5.1 引言

5.2 实输入DFT的计算方法

5.3 实输入变换分解法

5.3.1 实输入变换分解法的实现

5.3.2 算法复杂度分析

5.3.3 仿真结果分析

5.4 程序的优化编译

5.5 本章小结

结论

参考文献

攻读学位期间发表的学术论文

哈尔滨工业大学硕士学位论文原创性声明

哈尔滨工业大学硕士学位论文使用授权书

致谢