EasyFFT – Biblioteca FFT Confiável para Projetos Arduino

Componentes e Materiais

Componente	Quantidade
Arduino Nano R3	1

Aplicativos e Serviços Online

• Arduino IDE

Sobre o Projeto

A medição de frequência a partir de um sinal capturado pode ser uma tarefa difícil, especialmente no Arduino, que tem menor poder computacional. Existem métodos para capturar cruzamento por zero, onde a frequência é capturada verificando quantas vezes o sinal cruza a linha zero em um determinado tempo. Tal método pode não funcionar quando o sinal é uma combinação de várias frequências.

Isso é de alguma forma difícil de codificar se você não tem esse conhecimento. Mas, sendo um entusiasta, este código pode ser altamente útil para vários projetos relacionados a música, análise de sinais. O objetivo deste projeto foi preparar um código fácil de implementar no Arduino sem entrar nos detalhes matemáticos.

Este projeto não explica o funcionamento da FFT, mas explica a aplicação da função FFT. O mesmo processo também é explicado no vídeo anexado.

Se você está interessado apenas na aplicação do código e não na explicação, pode pular diretamente para o passo 3.

Se precisar realizar FFT com alta velocidade (3x) com pequeno comprometimento na precisão (cerca de 5%), consulte meu outro artigo sobre ApproxFFT: ApproxFFT – Função FFT mais rápida para Arduino.

Passo 1: Transformada Rápida de Fourier

Para tornar o cálculo da DFT mais rápido, o algoritmo FFT foi desenvolvido por James Cooley e John Tukey. Este algoritmo é considerado um dos mais importantes do século XX. Ele divide um sinal em partes de sequência ímpar e par, o que reduz o número de cálculos necessários. Ao usá-lo, o total de multiplicações complexas necessárias pode ser reduzido para NlogN, uma melhoria significativa. A DFT típica requer N*N multiplicações complexas para resultados, enquanto a FFT requer apenas N*logN. Isso é uma vantagem significativa quando o número de amostras é alto.

Você pode consultar as referências abaixo que usei ao escrever o código para uma compreensão detalhada da matemática por trás da FFT:

1. Derivação da FFT
2. Entendendo a FFT
3. FFT no CNX
4. Wikipédia: Fast Fourier Transform

Passo 2: Explicação do Código

1. Seno e Cosseno Rápidos

O cálculo da FFT requer valores de vários senos e cossenos múltiplas vezes. A função nativa do Arduino não é rápida o suficiente e leva um bom tempo para fornecer o valor necessário, o que torna o código significativamente mais lento (dobra o tempo para 64 amostras). Para contornar isso, o valor do seno para 0 a 90 graus é armazenado como múltiplo de 255. Isso elimina a necessidade de armazenar números como float e podemos armazená-los como byte, que ocupa 1/4 do espaço no Arduino. O array sine_data[] precisa ser colado no topo do código para declará-lo como variável global.

Além do sine_data, um array chamado f_peaks[] declarado como variável global. Após cada execução da função FFT, este array é atualizado. Onde f_peaks[0] é a frequência mais dominante e os valores seguintes em ordem decrescente.

byte sine_data[91] = { 
  0, 4, 9, 13, 18, 22, 27, 31, 35, 40, 44, 49, 53, 57, 62, 66, 70, 75, 79, 83, 87, 
  91, 96, 100, 104, 108, 112, 116, 120, 124, 127, 131, 135, 139, 143, 146, 150, 
  153, 157, 160, 164, 167, 171, 174, 177, 180, 183, 186, 189, 192, 195, 198, 201, 
  204, 206, 209, 211, 214, 216, 219, 221, 223, 225, 227, 229, 231, 233, 235, 236, 
  238, 240, 241, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 253, 254, 
  254, 254, 255, 255, 255, 255 
}; 
float f_peaks[5]; // top 5 picos de frequência em ordem decrescente

Como armazenamos o valor do seno para 0 a 90 graus, qualquer valor de seno ou cosseno pode ser calculado. A função abaixo primeiro arredonda o número para zero casas decimais e retorna o valor dos dados armazenados. Este método precisa de apenas uma divisão de ponto flutuante. Isso pode ser reduzido ainda mais armazenando diretamente os valores do seno (não múltiplos de 255), mas isso consome muita memória no Arduino.

Usando o procedimento acima, reduz-se a precisão, mas melhora a velocidade. Para 64 pontos, dá vantagem de 8ms e para 128 pontos, vantagem de 20ms.

Passo 3: Explicação do Código: Função FFT

A FFT só pode ser realizada para tamanho de amostra 2, 4, 8, 16, 32, 64 e assim por diante. Se o valor não for 2^n, ele tomará o valor do lado inferior. Por exemplo, se escolhermos tamanho de amostra 70, ele considerará apenas as primeiras 64 amostras e omitirá o resto.

Sempre é recomendado ter tamanho de amostra 2^n, que pode ser:

2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048,...

Dois floats out_r e out_im consomem muita memória. No Arduino Nano, não funcionará para amostras maiores que 128 (e em alguns casos 128) devido à falta de memória disponível.

unsigned int data[13] = {1,2,4,8,16,32,64,128,256,512,1024,2048};
int a, c1, f, o, x;
a = N;
for(int i = 0; i < 12; i++) // calculando os níveis
{
  if(data[i] <= a) { o = i; }
}
int in_ps[data[o]] = {}; // input para sequenciamento
float out_r[data[o]] = {}; // parte real da transformada
float out_im[data[o]] = {}; // parte imaginária da transformada

O fluxo adicional é o seguinte:

1. O código gera uma ordem bit-reversed para o tamanho de amostra dado (detalhes sobre bit-reversing nas referências: passo 2)
2. Dados de entrada ordenados conforme a ordem gerada
3. FFT realizada
4. Amplitude do número complexo calculada
5. Picos detectados e ordenados em ordem decrescente
6. Resultados podem ser acessados em f_peaks[].

[Para acessar outros dados (além da frequência de pico), o código deve ser modificado para que variáveis locais possam ser copiadas para alguma variável global predefinida.]

Passo 4: Testando o Código

Uma onda triangular de amostra é dada como entrada. Para esta onda, a frequência de amostragem é 10 Hz e a frequência da própria onda é 1.25 Hz.

Como pode ser visto na saída bruta, o valor corresponde ao FFT calculado pelo Scilab. No entanto, esses valores não são exatamente iguais, pois usamos seno de baixa precisão, mas mais rápido.

No array de frequência de saída, as frequências são 1.25 e 3.75. Não é necessário obter o valor exato toda vez. Tipicamente, esses números são chamados de "frequency bins". Então, o valor de saída pode estar em qualquer lugar dentro dos bins especificados.

Velocidade:

Para Arduino Nano leva:

• 16 Pontos: 4ms
• 32 Pontos: 10ms
• 64 Pontos: 26ms
• 128 Pontos: 53ms

Passo 5: Conclusão

Este código FFT pode ser usado em aplicações em tempo real. Leva cerca de 30 ms para completar o cálculo. No entanto, sua resolução é limitada pelo número de amostras. O número de amostras é limitado pela memória do Arduino. Usando Arduino Mega ou outra placa de maior desempenho, a precisão pode ser melhorada.

Se tiver dúvidas, sugestões ou correções, sinta-se à vontade para comentar.

Código

EasyFFT (Arduino)

Este código realiza FFT e atualiza o array f_peaks com as 5 frequências mais dominantes.

/* 
// Exemplo de dados: 
int data[64] = {14, 30, 35, 34, 34, 40, 46, 45, 30, 4, -26, -48, -55, -49, -37, -28, -24, -22, -13, 6, 32, 55, 65, 57, 38, 17, 1, -6, -11, -19, -34, -51, -61, -56, -35, -7, 18, 32, 35, 34, 35, 41, 46, 43, 26, -2, -31, -50, -55, -47, -35, -27, -24, -21, -10, 11, 37, 58, 64, 55, 34, 13, -1, -7}; 
*/ 
//---------------------------------------------------------------------------// 
byte sine_data[91] = { 
  0, 4, 9, 13, 18, 22, 27, 31, 35, 40, 44, 49, 53, 57, 62, 66, 70, 75, 79, 83, 87, 
  91, 96, 100, 104, 108, 112, 116, 120, 124, 127, 131, 135, 139, 143, 146, 150, 
  153, 157, 160, 164, 167, 171, 174, 177, 180, 183, 186, 189, 192, 195, 198, 201, 
  204, 206, 209, 211, 214, 216, 219, 221, 223, 225, 227, 229, 231, 233, 235, 236, 
  238, 240, 241, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 253, 254, 
  254, 254, 255, 255, 255, 255 
}; // Cole isso no topo do programa [variável global]
float f_peaks[5]; // top 5 picos de frequência em ordem decrescente
//---------------------------------------------------------------------------//

void setup() {
  Serial.begin(250000);
}

void loop() {
  /* 
  // exemplo FFT
  FFT(data, 64, 100); 
  // para obter os cinco principais valores de frequência de X com 64 amostras a 100Hz de amostragem
  Serial.println(f_peaks[0]);
  Serial.println(f_peaks[1]);
  delay(99999);
  */
  /* 
  após executar FFT(), as frequências estão disponíveis em 
  f_peaks[0], f_peaks[1], f_peaks[2], f_peaks[3], f_peaks[4] 
  */
}

//----------------------------- Função FFT ----------------------------------------------//
float FFT(int in[], int N, float Frequency) {
  /* 
  Código para realizar FFT no Arduino, configuração: 
  cole sine_data[91] no topo do programa [variável global], 
  cole a função FFT no final do programa 
  Termos: 
  1. in[] : Array de dados, 
  2. N : Número de amostras (tamanho recomendado 2,4,8,16,32,64,128...) 
  3. Frequency: frequência de amostragem necessária como entrada (Hz) 
  Se o tamanho da amostra não for potência de 2, será cortado para o lado inferior do número. 
  Ex: para 150 amostras, o código considerará as primeiras 128 amostras, as restantes serão omitidas. 
  Para Arduino Nano, FFT de mais de 128 amostras não é possível devido a limitação de memória (64 recomendado) 
  Para maior número de amostras podem surgir problemas de memória. 
  Código por ABHILASH 
  Contato: abhilashpatel121@gmail.com 
  Documentação: https://www.instructables.com/member/abhilash_patel/instructables/ 
  2/3/2021: alterado tipo de dado de N de float para int para >=256 amostras 
  */
  unsigned int data[13] = {1,2,4,8,16,32,64,128,256,512,1024,2048};
  int a, c1, f, o, x;
  a = N;
  for(int i = 0; i < 12; i++) // calculando os níveis
  {
    if(data[i] <= a) { o = i; }
  }
  int in_ps[data[o]] = {}; // input para sequenciamento
  float out_r[data[o]] = {}; // parte real da transformada
  float out_im[data[o]] = {}; // parte imaginária da transformada
  x = 0;
  for(int b = 0; b < o; b++) // bit reversal
  {
    c1 = data[b];
    f = data[o] / (c1 + c1);
    for(int j = 0; j < c1; j++)
    {
      x = x + 1;
      in_ps[x] = in_ps[j] + f;
    }
  }
  for(int i = 0; i < data[o]; i++) // atualiza array de entrada conforme ordem bit reverse
  {
    if(in_ps[i] < a) { out_r[i] = in[in_ps[i]]; }
    if(in_ps[i] > a) { out_r[i] = in[in_ps[i] - a]; }
  }
  int i10, i11, n1;
  float e, c, s, tr, ti;
  for(int i = 0; i < o; i++) // fft
  {
    i10 = data[i]; // valores gerais de seno/cosseno
    i11 = data[o] / data[i+1]; // loop com seno/cosseno semelhantes
    e = 360 / data[i+1];
    e = 0 - e;
    n1 = 0;
    for(int j = 0; j < i10; j++)
    {
      c = cosine(e * j);
      s = sine(e * j);
      n1 = j;
      for(int k = 0; k < i11; k++)
      {
        tr = c * out_r[i10 + n1] - s * out_im[i10 + n1];
        ti = s * out_r[i10 + n1] + c * out_im[i10 + n1];
        out_r[n1 + i10] = out_r[n1] - tr;
        out_r[n1] = out_r[n1] + tr;
        out_im[n1 + i10] = out_im[n1] - ti;
        out_im[n1] = out_im[n1] + ti;
        n1 = n1 + i10 + i10;
      }
    }
  }
  /* 
  for(int i = 0; i < data[o]; i++) 
  { 
    Serial.print(out_r[i]); 
    Serial.print("\t"); 
    // descomente para imprimir saída bruta 
    Serial.print(out_im[i]); 
    Serial.println("i"); 
  } 
  */
  //---> a partir daqui out_r contém amplitude e out_im contém frequência (Hz)
  for(int i = 0; i < data[o-1]; i++) // obtendo amplitude do número complexo
  {
    out_r[i] = sqrt(out_r[i] * out_r[i] + out_im[i] * out_im[i]); // para aumentar velocidade, remova sqrt
    out_im[i] = i * Frequency / N;
    /* 
    Serial.print(out_im[i]); 
    Serial.print("Hz"); 
    Serial.print("\t"); 
    // descomente para imprimir bin de frequência 
    Serial.println(out_r[i]); 
    */
  }
  x = 0; // detecção de pico
  for(int i = 1; i < data[o-1] - 1; i++)
  {
    if(out_r[i] > out_r[i-1] && out_r[i] > out_r[i+1])
    {
      in_ps[x] = i; // array in_ps usado para armazenar número do pico
      x = x + 1;
    }
  }
  s = 0; c = 0;
  for(int i = 0; i < x; i++) // rearranja conforme magnitude
  {
    for(int j = c; j < x; j++)
    {
      if(out_r[in_ps[i]] < out_r[in_ps[j]])
      {
        s = in_ps[i];
        in_ps[i] = in_ps[j];
        in_ps[j] = s;
      }
    }
    c = c + 1;
  }
  for(int i = 0; i < 5; i++) // atualizando array f_peak (variável global) com ordem decrescente
  {
    f_peaks[i] = out_im[in_ps[i]];
  }
}

float sine(int i) {
  int j = i;
  float out;
  while(j < 0) { j = j + 360; }
  while(j > 360) { j = j - 360; }
  if(j > -1 && j < 91) { out = sine_data[j]; }
  else if(j > 90 && j < 181) { out = sine_data[180 - j]; }
  else if(j > 180 && j < 271) { out = -sine_data[j - 180]; }
  else if(j > 270 && j < 361) { out = -sine_data[360 - j]; }
  return (out / 255);
}

float cosine(int i) {
  int j = i;
  float out;
  while(j < 0) { j = j + 360; }
  while(j > 360) { j = j - 360; }
  if(j > -1 && j < 91) { out = sine_data[90 - j]; }
  else if(j > 90 && j < 181) { out = -sine_data[j - 90]; }
  else if(j > 180 && j < 271) { out = -sine_data[270 - j]; }
  else if(j > 270 && j < 361) { out = sine_data[j - 270]; }
  return (out / 255);
}
//------------------------------------------------------------------------------------//

Esquemáticos