title: How to calculate Frequency with Fast Fourier Transformation
body: <p>i am working on a pulse sensor project. I get data from the sensor like this:
  <a href="https://i.stack.imgur.com/L6RZw.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/L6RZw.jpg" alt="voltage without artifacts"></a></p>
  
  <p>Now i would like to use this code:</p>
  
  <pre><code>  #include &lt;complex&gt;
  #include &lt;iostream&gt;
  #include &lt;valarray&gt;
  
  const double PI = 3.141592653589793238460;
  
  typedef std::complex&lt;double&gt; Complex;
  typedef std::valarray&lt;Complex&gt; CArray;
  
  // Cooley–Tukey FFT (in-place, divide-and-conquer)
  // Higher memory requirements and redundancy although more intuitive
  void fft(CArray&amp; x)
  {
      const size_t N = x.size();
      if (N &lt;= 1) return;
  
      // divide
      CArray even = x[std::slice(0, N/2, 2)];
      CArray  odd = x[std::slice(1, N/2, 2)];
  
      // conquer
      fft(even);
      fft(odd);
  
      // combine
      for (size_t k = 0; k &lt; N/2; ++k)
      {
          Complex t = std::polar(1.0, -2 * PI * k / N) * odd[k];
          x[k    ] = even[k] + t;
          x[k+N/2] = even[k] - t;
      }
  }
  
  // Cooley-Tukey FFT (in-place, breadth-first, decimation-in-frequency)
  // Better optimized but less intuitive
  // !!! Warning : in some cases this code make result different from not optimased version above (need to fix bug)
  // The bug is now fixed @2017/05/30 
  void fft(CArray &amp;x)
  {
      // DFT
      unsigned int N = x.size(), k = N, n;
      double thetaT = 3.14159265358979323846264338328L / N;
      Complex phiT = Complex(cos(thetaT), -sin(thetaT)), T;
      while (k &gt; 1)
      {
          n = k;
          k &gt;&gt;= 1;
          phiT = phiT * phiT;
          T = 1.0L;
          for (unsigned int l = 0; l &lt; k; l++)
          {
              for (unsigned int a = l; a &lt; N; a += n)
              {
                  unsigned int b = a + k;
                  Complex t = x[a] - x[b];
                  x[a] += x[b];
                  x[b] = t * T;
              }
              T *= phiT;
          }
      }
      // Decimate
      unsigned int m = (unsigned int)log2(N);
      for (unsigned int a = 0; a &lt; N; a++)
      {
          unsigned int b = a;
          // Reverse bits
          b = (((b &amp; 0xaaaaaaaa) &gt;&gt; 1) | ((b &amp; 0x55555555) &lt;&lt; 1));
          b = (((b &amp; 0xcccccccc) &gt;&gt; 2) | ((b &amp; 0x33333333) &lt;&lt; 2));
          b = (((b &amp; 0xf0f0f0f0) &gt;&gt; 4) | ((b &amp; 0x0f0f0f0f) &lt;&lt; 4));
          b = (((b &amp; 0xff00ff00) &gt;&gt; 8) | ((b &amp; 0x00ff00ff) &lt;&lt; 8));
          b = ((b &gt;&gt; 16) | (b &lt;&lt; 16)) &gt;&gt; (32 - m);
          if (b &gt; a)
          {
              Complex t = x[a];
              x[a] = x[b];
              x[b] = t;
          }
      }
      //// Normalize (This section make it not working correctly)
      //Complex f = 1.0 / sqrt(N);
      //for (unsigned int i = 0; i &lt; N; i++)
      //  x[i] *= f;
  }
  
  
  int main()
  {
      const Complex test[] = { 1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0 };
      CArray data(test, 8);
  
      // forward fft
      fft(data);
  
      std::cout &lt;&lt; "fft" &lt;&lt; std::endl;
      for (int i = 0; i &lt; 8; ++i)
      {
          std::cout &lt;&lt; data[i] &lt;&lt; std::endl;
      }
  
      }
      return 0;
  }
  </code></pre>
  
  <p>To calculate the frequency of my heartbeat. The problem i have right now is making sense of the output i get:
  fft
  (4,0)
  (1,-2.41421)
  (0,0)
  (1,-0.414214)
  (0,0)
  (1,0.414214)
  (0,0)
  (1,2.41421)</p>
  
  <p>What is this? I think it is the Amplitude and the phase, but i dont know how to calculate from that the frequency. </p>
  
  <p>The frequency of a pulse is around 0.33 Hz to 3 Hz. Is the resolution of this code good enough? I never had to work with fourier transformation</p>
  
  <p>Thanks for the help. I look forward to your answers. </p>