利用低功耗微控制器开发FFT应用

获取采样

FFT算法假定采样是以固定的取样频率获得的。在为FFT获取采样时如果不加小心将会产生一些问题。例如，采样间隔的抖动就会给FFT结果引入误差，应尽力减小之。

ADC采样循环中的判决语句会造成采样间隔的抖动。例如，我们的系统从ADC读取带符号的8位采样，并将其存储在一组16位变量中。在下面的程序清单1中给出了两种伪码算法，执行这种ADC读取-存储功能。算法1给出的方法会造成采样间隔的抖动，因为负采样比正采样需要更多的时间来读取并存储。  

清单1. 两种ADC采样伪码算法。第二种算法避免了第一种的问题——采样间隔抖动。  

// ALGORITHM 1: INCONSISTENT SAMPLING FREQUENCY - BAD!
// sample[] is an array of 16-bit va
riables
for i = 0 to (N-1)
begin
doADCSampleConversion() // Instruct ADC to sample Vin
sample[ i] = read8BitSampleFromADC() // Read 8-bit sample from ADC

if (sample[ i] & 0x0080) // If the 8-bit sample was negative
sample[ i] = sample[ i] + 0xFF00 // Make the 16-bit word negative
end

// ALGORITHM 2: FIXED SAMPLING FREQUENCY - GOOD!
// sample[] is an array of 16-bit variables
for i = 0 to (N-1)
begin
doADCSampleConversion() // Instruct ADC to sample Vin
sample[ i] = read8BitSampleFromADC() // Read 8-bit sample from ADC
end

for i = 0 to (N-1)
begin
if (sample[ i] & 0x0080) // If the 8-bit sample was negative
sample[ i] = sample[ i] + 0xFF00 // Make the 16-bit word negative
end

三角函数表

本FFT算法通过查表(LUT)而非计算得到正弦或余弦函数值。程序清单2给出了对于正弦和余弦LUT的申明。实际固件的注释中包含了自动生成这些LUT的源代码，可由程序调用。两个LUT均含有N / 2分量，因为旋转因子的索引号变化范围为从0至N / 2 - 1 (见图2)。
清单2. 正弦和余弦函数LUT。  

const int cosLUT[N/2] = {+128,+127,+127, ... ,-127,-127,-127};
const int sinLUT[N/2] = {+0 ,+3 , +6, ... ,+9 , +6, +3};

这些LUT中的数组被声明为const，强制编译器将它们存储于代码空间而非数据空间。由于LUT数值须采用Q8.7表示法，它们由正弦和余弦的实际值乘以27后得到。

位反转

位反转排序(N已知)可在运行时通过计算、查表或直接利用展开循环编写。所有这些方法都需要在源代码的尺寸和运行速度间进行折衷。本FFT应用利用展开循环进行位反转，其源代码较长，但运行速度快。程序清单3显示了该展开循环的实现。本应用固件的注释中包含了用于程序自动生成展开循环的源代码。
清单3. 用于实现N = 256的位反转的展开循环。  

i=x_n_re[ 1]; x_n_re[ 1]=x_n_re[128]; x_n_re[128]=i;
i=x_n_re[ 2]; x_n_re[ 2]=x_n_re[ 64]; x_n_re[ 64]=i;
i=x_n_re[ 3]; x_n_re[ 3]=x_n_re[192]; x_n_re[192]=i;
i=x_n_re[ 4]; x_n_re[ 4]=x_n_re[ 32]; x_n_re[ 32]=i;
...
i=x_n_re[207]; x_n_re[207]=x_n_re[243]; x_n_re[243]=i;
i=x_n_re[215]; x_n_re[215]=x_n_re[235]; x_n_re[235]=i;
i=x_n_re[223]; x_n_re[223]=x_n_re[251]; x_n_re[251]=i;
i=x_n_re[239]; x_n_re[239]=x_n_re[247]; x_n_re[247]=i;

Radix-2 FFT算法

采样按照位反转方式重新排序后就可进行FFT运算了。本radix-2 FFT应用的固件通过三个主循环执行图2所示的蝶型运算。外循环计数log2(N)级FFT运算。内循环执行每一级的蝶型运算。

FFT 算法的核心部分是执行蝶型运算的一小块代码。程序清单4给出了这一块代码，遗憾的是，它是本应用中唯一“不可移植”的固件。宏MUL_1和MUL_2利用μC的硬件乘法器执行单指令周期乘法运算。这些宏的内容专用于MAXQ2000，可在实际固件中全部看到。

清单4. 用C编写的蝶型运算。  

/* (1) Macro MUL_1(A,B,C): C="A"*B (result in Q8.7)*/
/* (2) Macro MUL_2(A,C) : C="A"*last_B (result in Q8.7)*/
MUL_1(cosLUT[tf],x_n_re[ b],resultMulReCos);
MUL_2(sinLUT[tf],resultMulReSin);
MUL_1(cosLUT[tf],x_n_im[ b],resultMulImCos);
MUL_2(sinLUT[tf],resultMulImSin);

x_n_re[ b] = x_n_re[a]-resultMulReCos+resultMulImSin;
x_n_im[ b] = x_n_im[a]-resultMulReSin-resultMulImCos;
x_n_re[a] = x_n_re[a]+resultMulReCos-resultMulImSin;
x_n_im[a] = x_n_im[a]+resultMulReSin+resultMulImCos;