快速傅立叶变换阵列的实现

Question

我在Android中实现FFT算法时遇到了一个问题。假设我有一个8.000字节长的wav文件。我知道你必须选择FFT算法的大小(也必须是2的幂)。我的问题是，我真的不确定从现在开始如何进一步进行。假设我选择了N=1024的快速傅立叶变换的大小。我的脑海中基本上有很多选择: 1)将FFT算法直接应用于8.000字节的整个数组；2)将8000byte数组wav文件分成1024字节的块(并用0填充最后的块，直到有8个精确的块)，然后将fft应用到这些块中的每一个，最后再次整理所有不同的块，以便有一个单字节数组来表示。8000*2*1秒= 8192

我认为这是第二种选择，但我不完全确定。

下面是我使用的快速傅立叶变换数组thaT：

package com.example.acoustics;

public class FFT {

  int n, m;

  // Lookup tables. Only need to recompute when size of FFT changes.
  double[] cos;
  double[] sin;

  public FFT(int n) {
      this.n = n;
      this.m = (int) (Math.log(n) / Math.log(2));

      // Make sure n is a power of 2
      if (n != (1 << m))
          throw new RuntimeException("FFT length must be power of 2");

      // precompute tables
      cos = new double[n / 2];
      sin = new double[n / 2];

      for (int i = 0; i < n / 2; i++) {
          cos[i] = Math.cos(-2 * Math.PI * i / n);
          sin[i] = Math.sin(-2 * Math.PI * i / n);
      }

  }

  /***************************************************************
     * fft.c
     * Douglas L. Jones 
     * University of Illinois at Urbana-Champaign 
     * January 19, 1992 
     * http://cnx.rice.edu/content/m12016/latest/
     * 
     *   fft: in-place radix-2 DIT DFT of a complex input 
     * 
     *   input: 
     * n: length of FFT: must be a power of two 
     * m: n = 2**m 
     *   input/output 
     * x: double array of length n with real part of data 
     * y: double array of length n with imag part of data 
     * 
     *   Permission to copy and use this program is granted 
     *   as long as this header is included. 
     ****************************************************************/

  public void fft(double[] x, double[] y) {
      int i, j, k, n1, n2, a;
      double c, s, t1, t2;

      // Bit-reverse
      j = 0;
      n2 = n / 2;
      for (i = 1; i < n - 1; i++) {
          n1 = n2;
          while (j >= n1) {
              j = j - n1;
              n1 = n1 / 2;
          }
          j = j + n1;

          if (i < j) {
              t1 = x[i];
              x[i] = x[j];
              x[j] = t1;
              t1 = y[i];
              y[i] = y[j];
              y[j] = t1;
          }
      }

      // FFT
      n1 = 0;
      n2 = 1;

      for (i = 0; i < m; i++) {
          n1 = n2;
          n2 = n2 + n2;
          a = 0;

          for (j = 0; j < n1; j++) {
              c = cos[a];
              s = sin[a];
              a += 1 << (m - i - 1);

              for (k = j; k < n; k = k + n2) {
                  t1 = c * x[k + n1] - s * y[k + n1];
                  t2 = s * x[k + n1] + c * y[k + n1];
                  x[k + n1] = x[k] - t1;
                  y[k + n1] = y[k] - t2;
                  x[k] = x[k] + t1;
                  y[k] = y[k] + t2;
              }
          }
      }
  }
}

Answer 1

我认为你可以在FFT中使用整个数组。这是没有问题的，你可以使用2^13 = 8192并用零来完成数组，这种处理也称为补零，并用于FFT的多个实现中。如果你的程序运行得很好，运行整个数组是没有问题的，但是如果你使用大小为1024的部分来计算FFT，那么你将有一个分段傅立叶变换，它不能很好地描述信号的整个频谱，因为FFT使用数组中的所有位置来计算新变换的数组中的每个值，那么你在位置1中不会得到正确的答案，例如，如果你没有使用信号的整个数组。

这是我对你的问题的分析，我不是百分之百确定，但我对傅里叶级数的了解告诉我，如果你计算傅立叶变换的分段形式，而不是整个级数，这几乎就可以做到。