基于DSP的频率抽取基4FFT算法实现.pdf

-1- 基于 DSP的频率抽取基 4FFT算法实现 王靖琰 中国科学院上海应用物理研究所，上海 (201800) E-mail：wjycas@ 摘 要：首先介绍了频率抽取基 4FFT 算法的快速有效的原理及实现方法，提出了一种在 DSP上实现此算法的方法并且在 TMS320C6713B浮点型 DSP上实现了频率抽取基 4FFT算 法，最后对语音信号进行了基 4FFT变换和反变换的实验，实验结果表明本程序能正确、高 效地实现基 4FFT变换与逆变换的算法。 关键词：频率抽取 FFT；基 4FFT；TMS320C6713B 1．引言 傅里叶变换是一种将信号从时域变换到频域的变换形式。是声学、图像、电信和信号处 理等领域中一种重要的分析工具[1]。其中，离散傅里叶变换(DFT)更是数字信号处理领域不 可缺少的工具之一，特别是快速傅里叶变换(FFT)的出现使得DFT在实际应用中得到了广泛 的应用。FFT算法就是不断地把长序列的DFT逐次分解为几个短序列的DFT，并利用的周期 性和对称性来减少DFT的运算次数这一基本原理来加快运算速度的。 一般高基数FFT算法要比低基数FFT算法运算量要小，计算速度要快，但需要具有更强 大的数据并行处理能力的器件支持且编程难度也增大了。基4 FFT算法在各个点数的乘法次 数均小于基2 FFT的乘法次数。当运算点数很大的时候.这种优势越是明显。加法的次数基本 相等。由于实时处理对高速运算和大点数运算的要求，基4 FFT算法越来越受到重视。要获 得基4算法理论上的优越性，必须要有高速且并行性极好的数字信号处理器的支持。 TI公司的TMS320C6713B芯片具有强大的数据并处理能力。满足该算法要进行大量的实 时算术运算的要求因此选用TMS320C6713B这一款高性能DSP来实现基4 FFT算法。 2．频率抽取基4- FFT算法介绍 2.1 频率抽取基 4 FFT 算法原理 对于 N=4L点 DFT 可按照如下方法做频率抽取[2]： 31 1 1 14 2 4 30 4 2 4 ( ) ( ) ( ) ( ) ( ) (1) N N N N nk nk nk nk N N N N N N Nn n n n X k x n W x n W x n W x n W ? ? ? ? = = = = = + + +∑ ∑ ∑ ∑ 即 13 4 0 0 ( ) (4 ) (2) N lk nk N N l n X k W x n l W ? = = = +∑ ∑ 分别另 k=4r，k=4r+2，k=4r+1，k=4r+3，而 r=0,1,……,N/4，于是有 1 4 / 4 0 (4 ) ( ( ) ( )) ( ( ) ( 3 )) (3) 2 4 4 N nk N n N N NX r x n x n x n x n W ? = ? ?= + + + + + +? ?? ? ∑ 1 4 2 / 4 0 (4 2) ( ( ) ( )) ( ( ) ( 3 )) (4) 2 4 4 N n nk N N n N N NX r x n x n x n x n W W ? = ? ?+ = + + ? + + +? ?? ? ∑ -2- 1 4 / 4 0 (4 1) ( ( ) ( )) ( ( ) ( 3 )) (5) 2 4 4 N n nk N N n N N NX r x n x n j x n x n W W ? = ? ?+ = ? + ? + ? +? ?? ? ∑ 1 4 3 / 4 0 (4 3) ( ( ) ( )) ( ( ) ( 3 )) (6) 2 4 4 N n nk N N n N N NX r x n x n j x n x n W W ? = ? ?+ = ? + + + ? +? ?? ? ∑ 这样就把一个 N 点 DFT 转换为一个基本碟形运算和 4 个 N/4 点 DFT 运算，如频率抽取 基 4FFT 一级分解框图所示： 图 1 频率抽取基 4FFT 一级分解框图 对框图中每个 N/4 点 DFT 继续进行同样的分解，直到只有最基本的 4 点 DFT 为止，就 得到了频率抽取基 4FFT。由于频率抽取，造成了输出数据的四进制倒序，实际上也是二进 制倒序。 2.2 频率抽取基 4 FFT 变换的运算量 下面讨论基 4FFT 的运算次数[3]。每个基本的 4 点 FFT 都不需要乘法，算法中只有旋转 因子才需要复乘法，而没个 4 点 DFT 只有 3 次乘旋转因子，而每一级有 N/4 个 4 点 DFT， 所以每级共需要3 / 4N× 次复数乘法，由于 4LN = ，则共有 L 级，因而总