FFT浮点的DSP实现精

FFT 算法的 DSP 实现

对于离散傅里叶变换（DFT）的数字计算，FFT是一种有效的方法。一般假定输入序列是 复数。当实际输入是实数时，利用对称性质可以使计算 DFT 非常有效。

一个优化的实数FFT算法是一个组合以后的算法。原始的2N个点的实输入序列组合成 一个 N 点的复序列， 之后对复序列进行 N 点的 FFT 运算， 最后再由 N 点的复数输出拆散成 2N点的复数序列，这 2 N点的复数序列与原始的 2N点的实数输入序列的 DFT输出一致。

使用这种方法， 在组合输入和拆散输出的操作中， FFT 运算量减半。 这样利用实数 FFT 算法来计算实输入序列的 DFT的速度几乎是一般 FFT算法的两倍。下面用这种方法来实现 一个 256 点实数 FFT（2N=256 ）运算。

1. 实数 FFT 运算序列的存储分配

如何利用有限的 DSP 系统资源，合理的安排好算法使用的存储器是一个比较重要的问 题。本文中，程序代码安排在 0x3000 开始的存储器中，其中 0x3000~0x3080 存放中断向量 表，FFT程序使用的正弦表和余弦表数据 （.data段）安排在OxcOO开始的地方，变量（.bss段定

义 ） 存放在 0x80 开始的地址中。另外，本文中 256 点实数 FFT 程序的数据缓冲位

Ox23OO~Ox23ff , FFT 变换后功率谱的计算结果存放在 Ox22OO~Ox22ff 中。连续定位 .cmd 文件 程序如下：

MEMORY {

PAGE O: IPROG: origin = Ox3O8O,len=Ox1F8O

VECT: lorigin=Ox3OOO,len=Ox8O

EPROG: origin=Ox38OOO,len=Ox8OOO

PAGE 1: USERREGS: origin=Ox6O,len=Ox1c

BIOSREGS: origin=Ox7c,len=Ox4

1 快速傅立叶变换（FFT）的实现

一、实验目的

1.了解FFT的原理及算法；

2.了解DSP中FFT的设计及编程方法；

3.熟悉FFT的调试方法；

二、实验原理

FFT是一种高效实现离散付立叶变换的算法，把信号从时域变换到频域，在频域分析处理信息。

对于长度为N的有限长序列x(n)，它的离散傅里叶变换为：

(2/)jNnkNWe，称为旋转因子，或蝶形因子。

在x(n)为复数序列的情况下，计算X(k)：

对某个k值，需要N次复数乘法、(N-1)次复数加法；

对所有N个k值，需要2N次复数乘法和N(N-1)次复数加法。对于N相当大时（如1024）来说，直接计算它的DFT所作的计算量是很大的，

FFT的基本思想在于：

利用2()jnkNNWe的周期性即：kNkNNWW

对称性：/2kkNNNWW

将原有的N点序列分成两个较短的序列，这些序列的DFT可以很简单的组合起来得到原序列的DFT。按时间抽取的FFT——DIT FFT信号流图如图5.1所示：

图5.1 时间抽取的FFT—DIT FFT信号流图

FFT算法主要分为以下四步。

第一步 输入数据的组合和位倒序 10 )()(NnnkNWnxkX 2 把输入序列作位倒序是为了在整个运算最后的输出中得到的序列是自然顺序。

第二步 实现N点复数FFT

第一级蝶形运算；第二级蝶形运算；第三级至log2N级蝶形运算；

FFT运算中的旋转因子NW是一个复数，可表示：

为了实现旋转因子NW的运算，在存储空间分别建立正弦表和余弦表，每个表对应从0度到180度，采用循环寻址来对正弦表和余弦表进行寻址。

第三步 功率谱的计算

X(k)是由实部()RXk和虚部()IXk组成的复数：()()()RIXkXkjXk；计算功率谱时只需将FFT变换好的数据，按照实部()RXk和虚部()IXk求它们的平方和，然后对平方和进行开平方运算。

STM32官方DSP的FFT库使用

STMicroelectronics提供了用于STM32系列微控制器的官方DSP库，其中包括了快速傅里叶变换（FFT）的实现。FFT是一种将时域信号转换为频域信号的算法，常用于音频处理、图像处理、通信系统等领域。

使用STM32官方DSP库中的FFT功能，需要以下几个步骤：

2. 配置工程：在工程的编译选项中，确保已启用浮点运算支持。这可以通过设置编译器选项“-u _printf_float”来实现。

3.初始化FFT配置：在使用FFT之前，需要初始化FFT的配置，包括长度、窗函数、比例缩放系数等。

例如，对于一个长度为N的FFT，可以使用arm_cfft_radix4_init_f32函数来初始化：

```

arm_cfft_radix4_instance_f32 S;

arm_cfft_radix4_init_f32(&S, N, 0, 1);

```

4.执行FFT变换：在进行FFT变换之前，需要准备好输入缓冲区，并确保输出缓冲区具有足够的大小来存储FFT的结果。

例如，如果要对一个长度为N的实数序列进行FFT变换，可以使用arm_cfft_radix4_f32函数：

``` float32_t input[N];

float32_t output[N*2];

//将输入数据复制到输入缓冲区

arm_cfft_radix4_f32(&S, input);

//处理输出数据

```

注意，为了存储FFT结果中的实部和虚部，输出缓冲区的大小应为FFT长度的两倍（N*2）。

5.访问FFT结果：FFT变换的结果保存在输出缓冲区中。对于每个频率分量，实部和虚部分别存储在相邻的位置上。

例如，要获取第n个频率分量的实部和虚部，可以使用以下代码：

```

float32_t re = output[2*n];

float32_t im = output[2*n+1];

Ｃｈｉｎａ　Ｉｎｔｅｇｒａｔｅｄ　Ｃｉｒｃｕｉｔ　１　Ｉ…Ｈ【ｌ】国集成电路　Ｊ　■●＿　’　

一种实序列ＦＦＴ算法改进　

及其在ＤＳＰ上的实现　

鲍华，王昊　

（华东电子工程研究所，　安徽合肥，２　３００８８）　

摘要：ＦＦＴ是数字信号处理最重要的算法之一，论文分析了常规的２Ｎ点按时间抽选的实序列ＦＦＴ运算　的基本原理，介绍了一种改进的算法，算法将奇数序列和偶数序列部分开计算，并提取旋转因子的公因　

子，大大减少了计算过程中的加法和乘法的个数和旋转因子的引用次数，并在实际的ＤＳＰ平台上进行了　实现，实验数据表明，该算法在运算效率和复杂度上都较传统ＦＦＴ算法有较大的改进。　

关键词：快速傅里叶变换；实序列快速傅里叶变换；ＤＳＰ　

文献标识码：Ａ　中图分类号：ＴＰ３０１．６　

Ａ　Ｋｉｎｄ　ｏｆ　Ｉｍｐｒｏｖｅｄ　Ｒｅａｌ－Ｖａｌｕｅｄ　Ｆａｓｔ　Ｆｏｕｒｉｅｒ　

Ｔｒａｎｓｆｏｒｍ（ＦＦＴ）ａｎｄ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｎ　ＤＳＰ　

ＢＡＯ　Ｈｕａ，ＷＡＮＧ　Ｈａｏ　

（Ｅａｓｔ　Ｃｈｉｎａ　Ｒｅｓｅａｒｃｈ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｅｌｅｃｔｒｏｎｉｃ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｈｅｆｅｉ，Ｃｈｉｎａ，２３００３　１）　

Ａｂｓｔｒａｃｔ：Ｆａｓｔ　Ｆｏｕｒｉｅｒ　Ｔｒａｎｓｆｏｒｍ（ＦＦｒＩ１）ｉｓ　ｏｎｅ　ｏｆ　ｍｏｓｔ　ｉｍｐｏｒｔａｎｔ　ｄｉｇｉｔａｌ　ｓｉｇｎａｌ　ｐｒｏｃｅｓｓｉｎｇ　ａｌｇｏｒｉｔｈｍｓ．Ｔｈｅ　ｎｏｒｍａｌ　

Ｆｒｒ　ｔｈｅｏｒｙ　ｏｆ　ｔｈｅ　２Ｎ　ｒｅａｌ—ｖａｌｕｅｄ　ｉｓ　ａｎａｌｙｚｅｄ　ａｎｄ　ａ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍｓ　ｉｓ　ｉｎｔｒｏｄｕｃｅｄ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ．Ｔｈｅ　ａｌｇｏｒｉｔｈｍｓ　

ｃｏｍｐｕｔｅｒ　ｔｈｅ　ｏｄｄ　ｎｕｍｂｅｒ　ａｎｄ　ｅｖｅｎ　ｎｕｍｂｅｒ　ｓｅｑｕｅｎｃｅ　ｓｅｐａｒａｔｅｌｙ，ｔｈｅ　ｃｏｍｍｏｎ　ｆａｃｔｏｒ　ｏｆ　ｔｈｅ　ｔｗｉｄｄｌｅ　ｆａｃｔｏｒｓ　ｉｓ　ｅｘｔｒａｃｔｅｄ，