基于DSP实现的移动场景的相位配准(7)

Void DSP_fft16x16_imre(
short *w, int nx, short *x, short *y)   16 bits 复输入输出数据，复数按先虚部/后实部交织存放；
除最后一级外，每级的结果右移 1并四舍五入
void DSP_fft16x16r(
int nx, short *x, short *w, short *y，int radix, int offset, int n_max)   16 bits 复输入输出数据，复数按先实部/后虚部交织存放；除最后一级外，每级的结果右移 1并四舍五入；针对比较小的 Cache优化；
void DSP_fft16x32(
short *w, int nx, int *x, int *y)   32 bits 复输入输出数据，复数按先实部/后虚部交织存放；
void DSP_fft32x32(
int *w, int nx, int *x, int *y)   32 bits 复输入输出数据，复数按先实部/后虚部交织存放；
32 bits旋转因子
void DSP_fft32x32s(
int *w, int nx, int *x, int *y)   32 bits 复输入输出数据，复数按先实部/后虚部交织存放；
32 bits旋转因子；
除最后一级外，每级的结果右移 1；
void DSP_ifft16x16(
short *w, int nx, short *x, short *y)   16 bits 复输入输出数据，复数按先实部/后虚部交织存放；
除最后一级外，每级的结果右移 1并四舍五入
Void DSP_ifft16x16_imre(
short *w, int nx, short *x, short *y)   16 bits 复输入输出数据，复数按先虚部/后实部交织存放；
除最后一级外，每级的结果右移 1并四舍五入
void DSP_ifft16x32(
short *w, int nx, int *x, int *y)   32 bits 复输入输出数据，复数按先实部/后虚部交织存放
void DSP_ifft32x32(
int *w, int nx, int *x, int *y)   32 bits 复输入输出数据，复数按先实部/后虚部交织存放；
32 bits旋转因子
下图说明了DSP的FFT函数命名规则：

所有函数都按混合基FFT实现。除最后一级外，都是基 4运算，最后一级可能是基2或基4。FFT点数要求是2或4的整数次方，且16≤nx≤65536。输入数据是实部虚部交织存放。输出数据是经过排序后的数据。FFT蝶形运算可以直接在输入数组x[]上执行，但比特反转的结果必须存放的另一数组，所以最终输出结果要求存放的另一个数组y[]。也就是说函数中的*x和*y不能对应同一地址。
在第一部分介绍的普通FFT实现里，对旋转因子表的访问不是连续的。为了利用cache的特点，旋转因子表被按如下所示的方式重排，以使它能被连续访问。
对每个基4蝶，第一个旋转因子都是，它不需要被存储，只有其它三个需要存储。所以，第一级只用 3N/4个旋转因子。在下一级，运算被分成四个小FFT，每个小FFT使用相同的旋转因子，所以第二级只用3N/16个旋转因子。以此类推，总共需要的旋转因子的个数为：
3N/4 + 3N/16 + 3N/64 + … =N
所以，旋转因子表的大小也是N。
下面的代码产生用于DSP_fft16x16函数的优化的旋转因子表:
int gen_twiddle_fft16x16(short *w, int n)
{
int i, j, k;
float M = 32767;
float PI = 3.14159265358979323846;

for (j = 1, k = 0; j < n >> 2; j = j << 2)
{
    for (i = 0; i < n >> 2; i += j << 1)
    {
      /*twiddle factor for the second output of first butterfly*/
      w[k + 1] = M * cos(2.0 * PI * (i    ) / n);
      w[k + 0] = M * sin(2.0 * PI * (i    ) / n);

      /*twiddle factor for the second output of second butterfly*/ 基于DSP实现的移动场景的相位配准(7):http://www.youerw.com/wuli/lunwen_1614.html