File content as of revision 2:dbe2cc9e3b23:

// --------------------------------------------------------------------------------------------------------
//
//  September 2018
//  Author: Valeria Toffoli, Rohan Gurav 
// --------------------------------------------------------------------------------------------------------
//
//  FFT.h
//
// --------------------------------------------------------------------------------------------------------
// 
//  This library provides all the functions necessary to obtain the FFT form an analog ADXL connected with   
//  EV-COG-AD3029 or EV-COG-AD4050 Board. 
//
//  Permission is hereby granted, free of charge, to any person obtaining
//  a copy of this software and associated documentation files (the
//  "Software"), to deal in the Software without restriction, including
//  without limitation the rights to use, copy, modify, merge, publish,
//  distribute, sublicense, and/or sell copies of the Software, and to
//  permit persons to whom the Software is furnished to do so, subject to
//  the following conditions:
//
//  The above copyright notice and this permission notice shall be
//  included in all copies or substantial portions of the Software.
//
//  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
//  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
//  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
//  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
//  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
//  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
//  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
// --------------------------------------------------------------------------------------------------------



#include <stdint.h>
#include <math.h>
#include <complex>
#include "mbed.h"
#include "FFT.h"


int FFT::log2(int N)    //funzione per calcolare il logaritmo in base 2 di un intero
{
  int k = N, i = 0;
  while(k) {
    k >>= 1;
    i++;
  }
  return i - 1;
}

int FFT::check(int n)    //usato per controllare se il numero di componenti del vettore di input è una potenza di 2
{
  return n > 0 && (n & (n - 1)) == 0;
}

int FFT::reverse(int N, int n)    //calcola il reverse number di ogni intero n rispetto al numero massimo N
{
  int j, p = 0;
  for(j = 1; j <= log2(N); j++) {
    if(n & (1 << (log2(N) - j)))
      p |= 1 << (j - 1);
  }
  return p;
}

void FFT::order(complex<double>* f1, int N)     //dispone gli elementi del vettore ordinandoli per reverse order
{
  complex<double> f2[N];
  for(int i = 0; i < N; i++)
    f2[i] = f1[reverse(N, i)];
  for(int j = 0; j < N; j++)
    f1[j] = f2[j];
}

void FFT::transform(complex<double>* f, int N)     //calcola il vettore trasformato
{
  order(f, N);    //dapprima lo ordina col reverse order
  complex<double> W[N / 2]; //vettore degli zeri dell'unità.
                            //Prima N/2-1 ma genera errore con ciclo for successivo
                           //in quanto prova a copiare in una zona non allocata "W[N/2-1]"
  W[1] = polar(1., -2. * M_PI / N);
  W[0] = 1;
  for(int i = 2; i < N / 2; i++)
    W[i] = pow(W[1], i);
  int n = 1;
  int a = N / 2;
  for(int j = 0; j < log2(N); j++) {
    for(int i = 0; i < N; i++) {
      if(!(i & n)) {
        /*ad ogni step di raddoppiamento di n, vengono utilizzati gli indici */
        /*'i' presi alternativamente a gruppetti di n, una volta si e una no.*/
        complex<double> temp = f[i];
        complex<double> Temp = W[(i * a) % (n * a)] * f[i + n];
        f[i] = temp + Temp;
        f[i + n] = temp - Temp;
      }
    }
    n *= 2;
    a = a / 2;
  }
}

void FFT::fourier(complex<double>* f, int N, double d)
{
  transform(f, N);
  for(int i = 0; i < N; i++)
    f[i] *= d; //moltiplica il vettore per il passo in modo da avere il vettore trasformato effettivo
}