Compreendendo a saída FFT

87

Preciso de ajuda para entender a saída do cálculo DFT / FFT.

Sou um engenheiro de software experiente e preciso interpretar algumas leituras do acelerômetro de smartphones, como encontrar as frequências principais. Infelizmente, dormi durante a maior parte das minhas aulas de EE na faculdade há quinze anos, mas tenho lido sobre DFT e FFT nos últimos dias (sem sucesso, aparentemente).

Por favor, nenhuma resposta de "vá fazer uma aula de EE". Na verdade, estou planejando fazer isso se meu empregador me pagar. :)

Então aqui está meu problema:

Capturei um sinal em 32 Hz. Aqui está uma amostra de 1 segundo de 32 pontos, que tracei no Excel.

insira a descrição da imagem aqui

Então, obtive algum código FFT escrito em Java da Columbia University (depois de seguir as sugestões em um post sobre " FFT confiável e rápida em Java ").

A saída deste programa é a seguinte. Acredito que ele esteja executando um FFT local, portanto, ele reutiliza o mesmo buffer para entrada e saída.

Before: 

Re: [0.887  1.645  2.005  1.069  1.069  0.69  1.046  1.847  0.808  0.617  0.792  1.384  1.782  0.925  0.751  0.858  0.915  1.006  0.985  0.97  1.075  1.183  1.408  1.575  1.556  1.282  1.06  1.061  1.283  1.701  1.101  0.702  ]

Im: [0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  ]

After: 

Re: [37.054  1.774  -1.075  1.451  -0.653  -0.253  -1.686  -3.602  0.226  0.374  -0.194  -0.312  -1.432  0.429  0.709  -0.085  0.0090  -0.085  0.709  0.429  -1.432  -0.312  -0.194  0.374  0.226  -3.602  -1.686  -0.253  -0.653  1.451  -1.075  1.774  ]

Im: [0.0  1.474  -0.238  -2.026  -0.22  -0.24  -5.009  -1.398  0.416  -1.251  -0.708  -0.713  0.851  1.882  0.379  0.021  0.0  -0.021  -0.379  -1.882  -0.851  0.713  0.708  1.251  -0.416  1.398  5.009  0.24  0.22  2.026  0.238  -1.474  ]

Portanto, neste ponto, não posso fazer cara ou coroa com a saída. Eu entendo os conceitos DFT, como a parte real sendo as amplitudes das ondas cossenos componentes e a parte imaginária sendo as amplitudes das ondas senoidais componentes. Também posso acompanhar este diagrama do grande livro " O Guia do Cientista e do Engenheiro para Processamento de Sinal Digital ": insira a descrição da imagem aqui

Então, minhas perguntas específicas são:

  1. A partir da saída do FFT, como encontro as "frequências mais ocorrentes"? Isso faz parte da minha análise dos dados do meu acelerômetro. Devo ler as matrizes reais (cosseno) ou imaginárias (seno)?

  2. Eu tenho uma entrada de 32 pontos no domínio do tempo. A saída do FFT não deveria ser uma matriz de 16 elementos para reais e uma matriz de 16 elementos para o imaginário? Por que o programa fornece saídas de array reais e imaginárias de tamanho 32?

  3. Em relação à pergunta anterior, como analiso os índices nas matrizes de saída? Dada minha entrada de 32 amostras amostradas em 32 Hz, meu entendimento é que uma saída de matriz de 16 elementos deve ter seu índice uniformemente espalhado até 1/2 da taxa de amostragem (de 32 Hz), então estou correto em entender que cada elemento da matriz representa (32 Hz * 1/2) / 16 = 1 Hz?

  4. Por que a saída FFT tem valores negativos? Achei que os valores representam as amplitudes de uma sinusóide. Por exemplo, a saída de Real [3] = -1,075 deve significar uma amplitude de -1,075 para uma onda cosseno de frequência 3. Está certo? Como pode uma amplitude ser negativa?

stackoverflowuser2010
fonte
O que você gostaria de calcular a partir das leituras do acelerômetro: velocidade, distância? O ruído das leituras do acelerômetro segue a distribuição gaussiana e não consigo ver como o ajuste de uma onda senoidal resolveria isso.
Ali
2
a tag java deve ser removida porque é mais genérica do que para um idioma específico
usuário3791372
Olhando para a fonte da Columbia University, não é nada eficiente. É uma implementação simples e não otimizada de Cooley-Tucky com tabelas de pesquisa de borboleta, e a reversão de bits é feita manualmente em vez de usar funções de biblioteca existentes
Mark Jeronimus
@MarkJeronimus: Você pode recomendar uma implementação FFT eficiente em Java? Se bem me lembro, o motivo pelo qual usei o código da Columbia University foi que a biblioteca FFTW era muito complexa para ser executada em um smartphone Android.
stackoverflowuser2010
Eu encontrei algumas implementações 'otimizadas' espalhadas, mas elas são basicamente um algoritmo por tamanho N, então se você precisa de uma gama de tamanhos, você precisa de todas essas rotinas. Na prática, usei principalmente Intel Integrated Performance Primitives (sim, de Java, por meio de JNA), mas isso não é gratuito. Em casa, uso basicamente o mesmo algoritmo que você vinculou, mas escrito do zero em 2005 usando um livro didático. É apenas FFT (Fast Fourier Transform), nada tão 'Fast' sobre isso para justificar o nome 'Fast FFT'.
Mark Jeronimus

Respostas:

85
  1. Você não deve procurar a parte real ou imaginativa de um número complexo (qual é o seu array real e imaginário). Em vez disso, você deseja procurar a magnitude da frequência que é definida como sqrt (real * real + imag * imag). Esse número sempre será positivo. Agora tudo o que você precisa pesquisar é o valor máximo (ignore a primeira entrada em sua matriz. Esse é o seu deslocamento DC e não contém informações dependentes de frequência).

  2. Você obtém 32 saídas reais e 32 imaginárias porque está usando um FFT complexo a complexo. Lembre-se de que você converteu suas 32 amostras em 64 valores (ou 32 valores complexos) estendendo-as com zero partes imaginárias. Isso resulta em uma saída FFT simétrica em que o resultado da frequência ocorre duas vezes. Quando estiver pronto para usar nas saídas 0 a N / 2, e uma vez espelhado nas saídas N / 2 a N. No seu caso, é mais fácil simplesmente ignorar as saídas N / 2 a N. Você não precisa delas, elas são apenas um artefato sobre como você calcula sua FFT.

  3. A frequência para a equação fft-bin é (bin_id * freq / 2) / (N / 2) onde freq é a sua frequência de amostra (também conhecida como 32 Hz e N é o tamanho do seu FFT). No seu caso, isso simplifica para 1 Hz por compartimento. Os bins N / 2 a N representam frequências negativas (conceito estranho, eu sei). Para o seu caso, eles não contêm nenhuma informação significativa porque são apenas um espelho das primeiras N / 2 frequências.

  4. Suas partes reais e imaginárias de cada caixa formam um número complexo. Tudo bem se as partes reais e imaginárias forem negativas, enquanto a magnitude da frequência em si for positiva (veja minha resposta à pergunta 1). Eu sugiro que você leia sobre números complexos. Explicar como eles funcionam (e por que são úteis) excede o que é possível explicar em uma única questão de overflow de pilha.

Nota: Você também pode querer ler o que é autocorrelação e como ela é usada para encontrar a frequência fundamental de um sinal. Tenho a sensação de que é isso que você realmente deseja.

Nils Pipenbrinck
fonte
1
Obrigado. Em relação a 1: eu vi esta página Matlab que mostra um espectro de frequência ( mathworks.com/help/techdoc/ref/fft.html ). Nessa página, há um gráfico com o título "Espectro de amplitude de um lado de y (t)". Isso está traçando a magnitude da frequência conforme você sugeriu, sqrt (real ^ 2 + img ^ 2)? Em relação a 3: ainda não obtive o resultado de 2 Hz por bin. No meu caso, N = 32 e freq = 32, certo? Portanto, há N / 2 = 32/2 = 16 bins, e a frequência mais alta (Nyquist) é freq / 2 = 32/2 = 16 Hz, resultando em 16 Hz por 16 bins, dando 1 Hz por bin?
stackoverflowuser2010
1
Sim, o gráfico mostra a magnitude do espectro - | Y (f) |. As barras de valor absoluto significam magnitude. Largura da bandeja = taxa de amostragem / tamanho FFT. Sua taxa de amostragem é 32 Hz, seu tamanho FFT é 32. Sim, você está certo sobre a largura do compartimento!
Matt Montag de
Corrigida a frequência bin.
André Chalella
1
Boa resposta, obrigado! Desculpe estar um pouco atrasado para a festa, mas talvez você possa me responder qual unidade é a magnitude da frequência (conforme mencionado por você no ponto 1), em geral? No meu caso, em um sinal de valores de um acelerômetro (é m / s ^ 2). Eu não consigo entender.
Markus Wüstenberg
Fascinante! Minhas barras de frequência de visualização de música estavam todas saindo espelhadas da esquerda para a direita; a resposta # 2 explica isso !! Louco!!
Ryan S
11

Você já tem algumas boas respostas, mas vou apenas acrescentar que você realmente precisa aplicar uma função de janela aos dados do domínio do tempo antes do FFT, caso contrário, você obterá artefatos desagradáveis ​​em seu espectro, devido ao vazamento espectral .

Paul R
fonte
Compreendo que já passou muito tempo desde esta resposta. No entanto, você seria capaz de elaborar sobre que tipo de artefatos você quer dizer?
MattHusz de
1
@MattHusz: o termo geral para a origem desses artefatos é “vazamento espectral” - adicionei um link para a resposta agora que explica isso. A melhor maneira que posso descrever o efeito, porém, é que seu espectro ficará “manchado” devido à janela retangular implícita.
Paul R
6

1) Procure os índices no array real com os valores mais altos, além do primeiro (que é o componente DC). Você provavelmente precisará de uma taxa de amostragem consideravelmente maior do que 32 Hz e de um tamanho de janela maior para obter resultados significativos.

2) A segunda metade de ambas as matrizes é o espelho da primeira metade. Por exemplo, observe que o último elemento da matriz real (1.774) é igual ao segundo elemento (1.774) e o último elemento da matriz imaginária (1.474) é o negativo do segundo elemento.

3) A frequência máxima que você pode obter a uma taxa de amostragem de 32 Hz é 16 Hz ( limite de Nyquist ), então cada etapa é de 2 Hz. Conforme observado anteriormente, lembre-se de que o primeiro elemento é 0 Hz (ou seja, o deslocamento CC).

4) Claro, uma amplitude negativa faz todo o sentido. Significa apenas que o sinal está "invertido" - um FFT padrão é baseado em um cosseno, que normalmente tem valor = 1 em t = 0, então um sinal que tinha valor = -1 no tempo = 0 teria uma amplitude negativa .

Crepúsculo-inativo-
fonte
Obrigado pela resposta. (1) Você quer dizer que posso ignorar a matriz imaginária (seno) e, em caso afirmativo, por quê? Certamente o componente senoidal deve ser importante? (2) Por que esse espelhamento ocorre? É apenas o resultado do algoritmo FFT? A maioria das pessoas ignora a metade espelhada? (3) Como você calculou os passos de 2 Hz? Eu entendo o limite de Nyquist de 16 Hz, então se houver 16 elementos de matriz (não espelhados), cada elemento deve ser 16 Hz / 16 = 1 Hz cada? (4) Para encontrar as frequências principais, devo apenas pegar o valor absoluto dos valores de amplitude nas matrizes de saída?
stackoverflowuser2010
Você não deve procurar no array real o valor mais alto e não pode ignorar o array seno / I. Em vez disso, você deseja a magnitude do vetor complexo composto. O espelhamento ocorre porque metade da entrada (a matriz I) é toda zeros, então o resultado tem metade dos graus de liberdade. Você pode ignorá-lo se seus dados forem estritamente reais.
hotpaw2
@duskwuff Muito obrigado: você respondeu a uma pergunta que eu ia postar, se eu não tivesse encontrado sua resposta: como interpretar a SEGUNDA parte do FFT. Quero modificar os dados e fazer o inverso e continuei obtendo apenas metade dos resultados, porque modifiquei os dados errados naquela parte. Obrigado novamente.
Martin
(3), o valor do passo = 2 Hz permanece implícito para mim até agora. Temos 16 bins, representados por array de comprimento = 16. Precisamos descrever todas as frequências de 0 Hz a 16 Hz. Presumo que cada caixa descreve uma parte desse intervalo, não é?
krafter
@krafter Acho que caiu pela metade porque você não pode deduzir uma frequência de um único valor (já que não há repetição).
JVE999
5

Observe que a "frequência de maior ocorrência" pode ser espalhada em vários compartimentos FFT, mesmo com uma função de janela. Portanto, você pode ter que usar uma janela mais longa, várias janelas ou interpolação para estimar melhor a frequência de quaisquer picos espectrais.

hotpaw2
fonte