基于位倒序寻址方222.ppt

基于位倒序寻址方式的FFT现 制作者魏俊 基于位倒序寻址方式的FFT现 摘要 数字信号处理在许多领域中有重要的意义 数字信号处理目的是对数字信号进行处理和转换 它采用运算的方法来处理数字信号 由于傅里叶变换和z变换在计算机上实现很不方便 所以引入了离散傅里叶变换 它在数字信号处理中有着重要的地位 面对大量的数据运算 为了提高运算速度 人们对离散傅里叶变换进行了改进 离散傅里叶运算效率大大提高 这种快速傅里叶算法的出现 在数字信号处理中发挥了巨大的作用 本文介绍了有关离散傅里叶变换和快速傅里叶变换性质 算法原理和应用举例 并用c语言编程实现快速傅里叶转换 关键词 离散傅里叶转换 快速傅里叶转换 c语言编程 第一章绪论 1 1数字信号处理的基本概念1 2数字信号处理的特点1 3数字信号处理的应用 1 1数字信号处理的基本概念 信号是信息的物理表现形式 信息是信号的具体内容 根据信息的载体不同 信号可以是电的 磁的 光的 声的 热的和机械的等不同种类的信号 信号通常是一个或几个自变量的函数 如果只有一个自变量 则称为一维信号 如果是两个或以上自变量 则称为多维信号 信号的自变量可以是时间 距离 电压 温度等不同形式 本书一般把信号看做时间的函数 1 2数字信号处理的特点 1 灵活性高2精度高3易于大规模集成4性能指标高 1 3数字信号处理的应用 1通用DSP 数字滤波 卷积 相关 FFT2语音 语音通信 语言编码 识别 3图像图形 机器人视觉 图像传输和压缩 等 4控制 磁盘控制器 机器人控制 激光打印机 电机控制 5军事 雷达 保密通信 声纳 导航 传感器融合等 6电讯 调制解调器 蜂窝电话 视频会议等 7汽车 自动驾驶控制 故障分析 导航 汽车音响等 8消费 数字音响 数字电视 MP3播放器 数码相机等 第二章离散傅里叶变换 DFT 2 1 傅里叶变换的几种可能形式及离散傅里叶变换定义2 2DFT的性质 2 1傅里叶变换的几种可能的形式及离散傅里叶变换的定义 1连续时间 连续频率 傅里叶变换 2连续时间 离散频率 傅里叶级数 3离散时间 连续频域 序列的傅里叶变换 4离散时间 离散频率 离散傅里叶变换 由于 所以 2 1 1DFS的性质 1线性DFS 其中a b为任意常数所得到的频域序列也是周期序列 周期为N 2序列的时域移位 3序列的频域移位 4周期卷积如果 则 5对偶性 2 2DFT的性质 2 2 1线性性质如果和是两个有限长序列 长度分别 若 式中 为任意常数 2 2 2圆周移位性质 2 2 3对偶性 2 3 1用DFT对信号进行谱分析 2 3离散傅里叶的应用 用DFT对连续信号进行谱分析 先对xa t 进行时域采样 得到时域离散信号x n xa nT 对x n 进行DFT 得到的X k 是x n 的傅里叶变换X ejw 在区间 0 2 上的N点等间隔采样 x n 和X k 均是有限长序列 傅里叶变换理论信号持续时间有限长 其频谱是无限宽 信号的频谱有限长 在时域中 该信号的持续时间无限长 上述两种情况 在时域或频域中进行采样 得到的序列都是无限长序列 不满足DFT的变换条件 采用的处理方法 在频域中用滤波器滤除高于折叠频率的高频分量 在时域中则是截取有限点进行DFT 第三章快速傅里叶变换 3 1改进计算的方法3 2按时间抽取的FFT算法3 2 1算法原理3 2 2按时间抽取的FFT算法的运算量与运算特点3 3按频率抽取的FFT算法3 3 1算法原理与运算特点3 3 2按时间抽取与按频率抽取的同异 离散傅里叶的计算工作量 通常X k 都是复数 所以计算一个X k 的值需要N次复数乘法运算 和N 1次复数加法运算 那么所有的X k 就要NxN复数乘法运算 N N 1 复数加法运算 当N很大时 计算量就相当惊人 如果当N 1024时 则要完成1048576次运算这样难易做到实时处理 改进途径 利用的周期性和对称性 3 2按时间抽取的FFT算法 3 2 1算法原理一 算法原理基于 2FFT N 2点的DFT 先将x n 按n的奇偶分成两组DFT 不足时补零这样就有 N为偶数时 N为奇数时 由于所以可表示为 X k 的后一半的确定 蝶形运算 蝶形运算 前半部为X 0 X 3 后半部分为X 4 X 7 整个过程如下图所示 有图可知一个N点分解为两个N 2点DFT后 如果直接计算N 2点DFT 则每一个N 2点DFT只需要 4次复数乘法N 2 N 2 1 次复数加法 两个N 2点DFT共需 2次复数乘法和N N 2 1 次复数加法 此外 把两个N 2点DFT合成N点DFT时 有N 2个碟形运算 需要N 2次复数乘法及N次复数加法 因此通过进一步分解后 这样分解后运算量减少了一半 3 2 2FFT的运算量和运算特点 1 位倒序 造成位倒序的原因是输入按标号的奇偶的不断分组而造成的 如果用二进制数表示为第一次分组 为偶数上半部分 为奇数在下半部分 这样观察的二进制数的最低位则序列值对应于偶数抽样 则序列值对应于奇数抽样 下一次则根据次低位的0 1来分偶奇 这种不断分成偶数子序列和基数子序列的过程如下图的二进制树状图来描述 这就是的算法输入序列的序数成为位倒序的原因 2 位倒序的实现如果输入序列的序号n用二进制数表示 如 则位倒序二进制数用N表示为当n N时 不必调换当nN时 说明已经换过了最终得到一致的 3 蝶形运算两节点的距离 其中 m表示第m列 且m 1 L例如N 8 第一级 列 距离为 1 第二级 列 距离为 2第三级 列 距离为 4 4 存储单元存输入序列x n n 0 1 N 1 计N个单元 存放系数 r 0 1 N 2 1 需N 2个存储单元 共计 N N 2 个存储单元 3 3按频率抽取的FFT算法 一 算法原理 k为偶数时 k为奇数时 蝶形运算 3 3 2按时间抽取与按频率抽取的同异相同点 1 进行原位运算 2 运算量相同不同点 1 蝶形运算不同 2 DIT输入为倒位序 输出为自然顺序 DIF正好与此相反 但DIT也有输入为自然顺序 输出为倒位序的情况 3 两种蝶形运算的关系互为转置 综上可得 如果将DIT的基本碟形运算加以转置 就得到DIF的基本碟形 反过来 将的DIF基本碟形加以转置就得到DIT的基本碟形 因而法与法的基本碟形是互为转置的 按照转置定理 两个信号流图的输入输出特性必然相同 转置就是将流图的所有之路方向都反向 并且交换输入输出 但节点变量值不交换 因而对每一种按时序抽取的FFT流图都存在一个按频率抽取的FFT流图 第四章FFT的编程 4 1FFT的软件实现4 2用c语言实现FFT 用C语言实现FFT的流程图 如下示 2用c语言实现毕业论文设计上有 这里就省了 结论 由此我们可以得出结论 快速傅里叶转换只是离散傅里叶转换的一种方法 它的出现从根本上改变了傅里叶变换的地位 它可以将一个信号变换到频域 有些信号在时域上很难看出什么特征来 但变换到频域后 就很容易看看出特征 通过对快速傅里叶的深刻理解和对c语言的掌握 这次用c语言来实现基于位倒序方式的FFT是完全可行的 该方法具有运算速度快 精确度高 实现简单 可用于各种关于离散傅里叶的计算中 它可以把复杂的计算问题简单化 具有良好的学术价值和良好的应用前景 致谢 本次设计是在廖老师的悉心指导下完成的 在整个过程中 导师给予了大量指导 并提供了很多与课题相关的重要信息 培养了我们对科学研究的严谨态度和创新精神 对我影响深远 不仅我掌握了基本的科学研究方法 还使我明白了许多待人接物与人处事的道理 这非常有利于我今后的学习和工作 本论文从最初选题到最终完成 每一步都是在导师的指导下完成的 倾注了导师大量的精力 在此 谨向导师表示衷心的感谢和至高的敬意 参考文献 刘明 徐洪波 数字信号处理 原理与算法实现 清华大学出版社赵健 李勇 数字信号处理 清华大学出版社张立材 吴冬梅