【DSP】DSP5509A的FFT算法实现（附：完整代码及疑点解惑）

灰太狼 2022-04-17 06:37 301阅读 0赞

## 傅里叶变换及FFT原理 ##

说起傅里叶变换，每个人第一反应都是从时域转换到频域的手段，如下图所示：

![20181128142126993.jpg][]

但除了这一点之外呢？原理呢，推导呢？大概都是一头雾水……

**而FFT并不是一种新的变换，它是离散傅立叶变换（DFT）的一种快速算法。**

DFT的算法速度：

由于我们在计算DFT时一次复数乘法需用四次实数乘法和二次实数加法；一次复数加法则需二次实数加法。每运算一个 X（k）需要 4N 次复数乘法及2N+2（N-1）=2（2N-1）次实数加法。所以整个DFT运算总共需要4N^2次实数乘法和 N\*2(2N-1)=2N(2N-1)次实数加法。如此一来，计算时乘法次数和加法次数都是和N^2成正比的，当N很大时，运算量是可观的，因而需要改进对 DFT 的算法减少运算速度。

根据傅立叶变换的对称性和周期性，我们可以将DFT运算中有些项合并。

FFT的算法速度：

我们先设序列长度为N=2^L，L 为整数。将N=2^L的序列 x(n)(n=0,1,……，N-1)，按N的奇偶分成两组，也就是说我们将一个N点的DFT分解成两个N/2点的DFT，他们又重新组合成一个如下式所表达的N点DFT：一般来说，输入被假定为连续的。当输入为纯粹的实数的时候，我们就可以利用左右对称的特性更好的计算FFT。

**“FFT其实是很难的东西，即使常年在这个领域下打拼的科学家也未必能很好的写出FFT的算法。”**所以，也不需要很头疼这个算法究竟什么意思，这个算法怎么手写，能用就行了。

关于傅里叶变换的原理和计算过程，比较复杂，如果想要深入理解，可以参考文章：[从头到尾彻底理解傅里叶变换算法][Link 1]。本文由于文章篇幅就不展开讲述了。

## DSP5509A的FFT算法实现 ##

下列FFT算法中的变量说明：

**输入的信号为INPUT数组，FFT输出的信号为DATA数组，进行的是128点的FFT运算：**

#include "myapp.h"
    #include "csedu.h"
    #include "scancode.h"
    #include <math.h>
    
    #define PI 3.1415926
    #define SAMPLENUMBER 128
    
    void InitForFFT();
    void MakeWave();
    
    int INPUT[SAMPLENUMBER],DATA[SAMPLENUMBER];
    float fWaveR[SAMPLENUMBER],fWaveI[SAMPLENUMBER],w[SAMPLENUMBER];
    float sin_tab[SAMPLENUMBER],cos_tab[SAMPLENUMBER];
    
    main()
    {
        int i;
        
        InitForFFT();
        MakeWave();
        for ( i=0;i<SAMPLENUMBER;i++ )
        {
            fWaveR[i]=INPUT[i];
            fWaveI[i]=0.0f;
            w[i]=0.0f;
        }
        FFT(fWaveR,fWaveI);
        for ( i=0;i<SAMPLENUMBER;i++ )
        {
            DATA[i]=w[i];
        }
        while ( 1 );    // break point
    }
    
    void FFT(float dataR[SAMPLENUMBER],float dataI[SAMPLENUMBER])
    {
        int x0,x1,x2,x3,x4,x5,x6,xx;
        int i,j,k,b,p,L;
        float TR,TI,temp;
        
        /********** following code invert sequence ************/
        for ( i=0;i<SAMPLENUMBER;i++ )
        {
            x0=x1=x2=x3=x4=x5=x6=0;
            x0=i&0x01; x1=(i/2)&0x01; x2=(i/4)&0x01; x3=(i/8)&0x01;x4=(i/16)&0x01; x5=(i/32)&0x01; x6=(i/64)&0x01;
            xx=x0*64+x1*32+x2*16+x3*8+x4*4+x5*2+x6;
            dataI[xx]=dataR[i];
        }
        for ( i=0;i<SAMPLENUMBER;i++ )
        {
            dataR[i]=dataI[i]; dataI[i]=0; 
        }
    
        /************** following code FFT *******************/
        for ( L=1;L<=7;L++ )
        { /* for(1) */
            b=1; i=L-1;
            while ( i>0 ) 
            {
                b=b*2; i--;
            } /* b= 2^(L-1) */
            for ( j=0;j<=b-1;j++ ) /* for (2) */
            {
                p=1; i=7-L;
                while ( i>0 ) /* p=pow(2,7-L)*j; */
                {
                    p=p*2; i--;
                }
                p=p*j;
                for ( k=j;k<128;k=k+2*b ) /* for (3) */
                {
                    TR=dataR[k]; TI=dataI[k]; temp=dataR[k+b];
                    dataR[k]=dataR[k]+dataR[k+b]*cos_tab[p]+dataI[k+b]*sin_tab[p];
                    dataI[k]=dataI[k]-dataR[k+b]*sin_tab[p]+dataI[k+b]*cos_tab[p];
                    dataR[k+b]=TR-dataR[k+b]*cos_tab[p]-dataI[k+b]*sin_tab[p];
                    dataI[k+b]=TI+temp*sin_tab[p]-dataI[k+b]*cos_tab[p];
                } /* END for (3) */
            } /* END for (2) */
        } /* END for (1) */
        for ( i=0;i<SAMPLENUMBER/2;i++ )
        { 
            w[i]=sqrt(dataR[i]*dataR[i]+dataI[i]*dataI[i]);
        }
    } /* END FFT */
    
    
    void InitForFFT()
    {
        int i;
        
        for ( i=0;i<SAMPLENUMBER;i++ )
        {
            sin_tab[i]=sin(PI*2*i/SAMPLENUMBER);
            cos_tab[i]=cos(PI*2*i/SAMPLENUMBER);
        }
    }
    
    void MakeWave()
    {
        int i;
        
        for ( i=0;i<SAMPLENUMBER;i++ )
        {
            INPUT[i]=sin(PI*2*i/SAMPLENUMBER*3)*1024;
        }
    }

## FFT算法实现的验证 ##

启动调试，打开Tools->Graph，分别创建两个Singal Time（一个是原始的正选波形，一个是程序FFT得出的波形）和一个FFT Magnitude（CCS软件用FFT得出的波形），然后对比程序得出的和CCS帮得出的是否一致，就可以检查程序有没有问题。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEwNzMw_size_16_color_FFFFFF_t_70][]

**显示FFT算法实现的结果**，设置如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEwNzMw_size_16_color_FFFFFF_t_70 1][]

**显示INPUT的输入波形（时域）**，设置如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEwNzMw_size_16_color_FFFFFF_t_70 2][]

**显示INPUT的输入波形（频域）**，设置如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEwNzMw_size_16_color_FFFFFF_t_70 3][]

最终得出的波形图如下（从上到下分别为FFT算法实现的结果、输入INPUT的时域波形、输入INPUT的频域波形）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEwNzMw_size_16_color_FFFFFF_t_70 4][]

我们从程序代码中看出，输入波形INPUT的表达式为：

INPUT[i]=sin(PI*2*i/SAMPLENUMBER*3)*1024;

**它的周期是：42.6666667，幅值是：1024。这与第二幅图的波形是保持一致的。**

**由于周期是42.6666667，所以它的频率是0.0234375，这与第三幅图的横坐标保持一致的。但是纵坐标却不一致！**

**再看第一幅图，除了只有一个峰，表示只有一种频率存在，峰的横纵坐标更加都是乱七八糟的！！**

这是不是代表我们的FFT算法是错误的呢？

## FFT算法实现的解惑 ##

### 解惑一：FFT变换之后，横纵坐标的意义是什么。 ###

先看一下结论：

*  **横坐标的变换：假设采样频率为Fs，采样点数为N，那么横坐标第n个点代表的频率 X(n) = （Fs/N）\* n。**
 *  **纵坐标的变换：假设原始信号的赋值为A，采样点数为N，那么纵坐标第n个点的幅值应该为 X(n) = （N/2）\* A。**

对照一下上面的程序，采样频率为1（作图的时候设置里面默认为1），采样点数为128，峰值的赋值为1024，那么有：

第三幅图的横坐标为3，可得到频率为3/128=0.0234375；纵坐标大约为65000，可得到原始幅值为65000/64=1015.625，与1024相差不大。

而输入INPUT的频域波形，由于CCS内部的机制不太清楚，所以不能确定有没有已经对横纵坐标进行了变换。

参考文章：[FFT变换后，坐标单位是什么？][FFT]

### 疑惑二：上面的算法是128点的FFT计算，要是想要其他点数的FFT计算，怎么修改呢？ ###

先说一个办法：

#define SAMPLENUMBER 128

修改这里的128成为自己想要的FFT的点数。这是不行的！

原因：这里的128表示的样本的长度，并不是FFT的点数，点数是在FFT算法中x0-x6来表示的。也就是说，直接修改128是不能改变自己想要的FFT点数的。那怎么办？

可以参考文章：[FFT算法的DSP实现][FFT_DSP]（与本文同样的思路）、[FFT算法的完整DSP实现][FFT_DSP 1]（另外的算法思路）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEwNzMw_size_16_color_FFFFFF_t_70 5][]

[20181128142126993.jpg]: /images/20220417/46760e5261d4407d8ec2cd2c1c0cfaf1.png
[Link 1]: https://blog.csdn.net/v_JULY_v/article/details/6196862
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEwNzMw_size_16_color_FFFFFF_t_70]: /images/20220417/6935f8471f9149b49e9c3ccde77b37dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEwNzMw_size_16_color_FFFFFF_t_70 1]: /images/20220417/8085d35a7ce64f768f3b40db9c3dba22.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEwNzMw_size_16_color_FFFFFF_t_70 2]: /images/20220417/a001ea6f09654abc8ab462efea8a9e0d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEwNzMw_size_16_color_FFFFFF_t_70 3]: /images/20220417/514953ab1dde4ea6945ecbaf7300b9f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEwNzMw_size_16_color_FFFFFF_t_70 4]: /images/20220417/3ce1a6d414944c1190936bf32134acab.png
[FFT]: https://blog.csdn.net/wangkeyen/article/details/50117439
[FFT_DSP]: https://blog.csdn.net/dreamandxiaochouyu/article/details/45392723
[FFT_DSP 1]: https://blog.csdn.net/xiahouzuoxin/article/details/9790455#
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEwNzMw_size_16_color_FFFFFF_t_70 5]: /images/20220417/e539eeb77ab84773b62c1bda5c0364c1.png