Quão importante é usar a potência 2 ao usar a FFT?

8

Aqui está o problema. Eu tenho uma matriz de dados 2D, a primeira coluna representa os dados de tempo e a segunda coluna representa os dados de resposta senoidal, com base nos dados de tempo. Aplico fft e obtenho minha frequência (com a qual comecei) em um compartimento específico, conforme esperado, e encontro a amplitude e o ângulo de fase desse compartimento. Agora, o problema é que tenho a mesma configuração, mas com mais pontos de dados, aplico o fft novamente e o número do compartimento muda (o que é normal e é onde eu espero que seja), a amplitude é a mesma, mas o ângulo da fase é diferente) primeiro isso é normal? segundo, que abordagem devo adotar? Obrigado

PS: nenhuma das configurações (mencionadas acima) fornece dados com comprimento de potência de 2, digamos que o primeiro fornece 1620 pontos de dados e o segundo fornece 1745 pontos de dados; portanto, deve usar a próxima potência de 2 para ambos do começando?

lamia
fonte

Respostas:

5

Bibliotecas modernas de FFT, como a FFTW e a estrutura Accelerate da Apple, podem executar FFTs sem potência de 2 com muita eficiência, desde que todos os divisores principais do comprimento composto sejam bastante pequenos (2,3,5, etc.)

Um poder de 2 torna mais simples (cerca de 1 página do código-fonte) se você precisar codificar sua própria FFT por algum motivo, ou se estiver de outra forma restringido quanto ao tamanho máximo do programa (ou portas FPGA, etc.)

Para a medição de fase, pode ser mais fácil executar um deslocamento de ffts (pré-gire os dados por N / 2) para referenciar a fase FFT ao centro da janela de dados, onde a razão de uniformidade / ímpar e, portanto, a fase não muda ou alterne com o número do compartimento (para a fase que é a mesma no centro da janela de dados), mesmo para sinais não periódicos no comprimento da FFT, conforme você variar o comprimento.

hotpaw2
fonte
Oi hotpaw2, desculpe, esqueci de mencionar que estou usando o matlab FFT, isso faz alguma diferença? obrigado novamente.
lamia
O Matlab pode usar uma biblioteca moderna de FFT, como a FFTW, internamente. Verifique a documentação do matlab para sua versão.
hotpaw2
Além disso, @ hotpaw2, estou usando fftshift já ...
Lamia
Com fftshift, coloque o centro de janelas de dados onde deseja medir a fase. Ou calcule a fase do centro para trás no tempo usando uma boa estimativa de frequência.
hotpaw2
5

Não há nada inerentemente 'mágico' em executar uma potência de 2 DFT, além do fato de que executar uma potência de 2 DFT permite executar a DFT em vez de . Portanto, o poder de 2 DFT (o algoritmo que faz isso é conhecido como FFT) permite que você simplesmente acelere sua computação por um grande fator.O(Nlog(N))O(N2)

Eu aplico o fft novamente e o número do compartimento muda (o que é normal e é onde eu espero que seja), a amplitude é a mesma, mas o ângulo da fase é diferente) primeiro isso é normal?

Se você fizer uma DFT maior que o seu vetor de dados, estará essencialmente interpolando no domínio da frequência. Portanto, seu novo pico pode não ser o pico equivalente antigo que você detectou pela primeira vez antes de fazer uma DFT maior. E como não é o mesmo, você está essencialmente escolhendo uma base exponencial complexa diferente (seno mais cosseno) desta vez, o que significa que você provavelmente teria um valor de fase diferente, sim.

PS: nenhuma das configurações (mencionadas acima) fornece dados com comprimento de potência de 2, digamos que o primeiro fornece 1620 pontos de dados e o segundo fornece 1745 pontos de dados; portanto, deve usar a próxima potência de 2 para ambos do começando?

Sim, se você deseja obter uma potência de 2 FFT, basta escolher a próxima potência de 2 FFT de comprimento maior que o comprimento do registro de dados.

eu não necessariamente quero ou não quero tomar o poder de 2 FFT (desempenho no tempo não é problema meu), mais como, eu preciso?

Você nunca deve ter uma FFT de comprimento inferior ao tamanho do seu registro, a menos que queira descartar dados. A questão de "Qual é o tamanho da minha FFT", assumindo que o tamanho da FFT é maior que o tamanho do registro de dados, torna-se rapidamente dependente do aplicativo. Normalmente, você pode obter uma duração de FFT igual à duração do seu registro. No entanto, às vezes você deseja escolher um pico de uma FFT 'mais suave'. Nesse caso, você pode ter um comprimento maior de FFT (2 vezes mais, 3 vezes mais, 10 vezes mais etc.) e interpolaria seu pico no domínio da frequência. Não há número mágico, no entanto. Lembre-se de que a granularidade do seu resultado de FFT é sempre .fsN

Tarin Ziyaee
fonte
Obrigado user4619 pelas respostas, eu não necessariamente quero ou não quero tomar o poder de 2 FFT (desempenho no tempo não é problema meu), mais como, eu preciso?
lamia
Além disso, @ user4619, já que você mencionou que sim, o ângulo de fase pode mudar. Em quem devo confiar que está me dando a resposta correta? (eu não sei o ângulo de fase antes da mão ou a amplitude, eu só sei a freqüência antes da mão) ... obrigado
Lamia
@lamia Power-of-2 é apenas para problemas de velocidade. É isso. Não há nada de mágico nisso caso contrário. Sobre o ângulo de fase - lembre-se de que, embora o ângulo de fase mude, o mesmo ocorre com a frequência de pico. Se você executar uma FFT de 1000 pontos, você escolhe o compartimento de frequência 100 como o pico e encontra seu ângulo de fase. Está correto. Em seguida, você executa uma FFT de 343212 pontos e escolhe uma frequência 34321 como pico, e ela possui um ângulo de fase diferente. Isso ainda está correto. "Fase" é uma função da frequência. (Se você encontrou este sinta-se útil livre para upvote)
Tarin Ziyaee
@lamia Veja também minhas edições.
Tarin Ziyaee
Muito obrigado para as explicações que você forneceu :)
Lamia
3

Mostrando a resposta de @ user4619:

Usando IPython, que é semelhante ao Matlab

In[1]: fft(arange(2**22))
1 loops, best of 3: 354 ms per loop

In[2]: fft(arange(4*1000*90*12)) # close to 2**22
# equal to 2*2 * 2*5*2*5*2*5 * 3*3*2*5 * 2*2*3
1 loops, best of 3: 295 ms per loop

In[2]: fft(arange(2**22+1))
1 loops, best of 3: 14 s per loop

Se você estiver usando números realmente primos, é bastante importante (um fator de 50!). Se você estiver usando números com fatores baixos, não é importante. Mas fazê-lo apenas com números primos apenas o torna mais rápido - não muda a resposta.

Scott
fonte