Implementation of FFT array

Question

I have a problem when implementing a FFT algorithm in Android. Let´s say that I have a wav file of 8.000 bytes length. I am aware that you have to select a size of the FFT algorithm (and also has to be a power of 2). My problem is that I am not really sure about how to further proceed from now on. Lets say that I have chosen a size of the FFT of N=1024. I have basically to options on my mind: 1) Apply the FFT algorithm directly to the whole array of 8.000 bytes 2) Divide the 8000 byte array wav file in chunks of 1024 bytes (and fill with 0´s the last chunk untill having 8 exact chunks), then apply the fft to each of this chunks and finally collate all the different chunks again to have one single byte array to represent. 8000*2*1 sec = 8192

I think it´s the option 2 but I am not completely sure.

Here is the fft array thaT I am using:

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

I think that you can use the entire array with the FFT. There is not problem with that, you can use 2^13 = 8192 and complete the array with zeros, this processing is also called zero padding and is used in more than one implementation of the FFT. If your procedure works well there is not problem with run the entire array, but if you use section of size 1024 for compute the FFT, then you will have a segmented Fourier transform that not describe well the entire spectrum of the signal, because the FFT use all the positions in the array to compute each value in the new transformed array, then you not get the correct answer in the position one for example if you don't use the entire array of the signal.

This is my analysis of your question I am not hundred percent sure but my knowledge about Fourier series tell me that this is almost that is going to do if you compute a segmented form of the Fourier Transform instead the entire serie.