FFT Code Break Down

Question

J'essaie de mettre en œuvre la FFT dans l'un de mes projets. Malheureusement, j'ai l'impression que chaque site que je visite explique les choses par-dessus ma tête. J'ai regardé de nombreux sites différents pour obtenir des éclaircissements, mais hélas, cela m'a jusqu'ici échappé. Chacun des sites que j'ai consultés jusqu'à présent a soit bien écrit le code sans aucun commentaire sur les variables ou d'autres explications, ou a expliqué des choses à un niveau tel que je ne peux pas le comprendre.

J'apprécierais que quelqu'un puisse décomposer chaque partie de ce code et le processus de la manière la plus descriptive possible. Tout d'abord, je sais que l'entrée à la FFT est [1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0]. Que représentent ces chiffres? Sont-ils en hertz ou en volts? Enfin, je sais que la sortie de la FFT est 4.000 2.613 0.000 1.082 0.000 1.082 0.000 2.613. Que représentent ces chiffres? Quelle est l'unité? Comment peuvent-ils être utilisés pour obtenir l'ampleur ou la fréquence de l'ensemble de données? Encore une fois, je suis à la recherche de toutes les étapes à expliquer, alors commenter le code FFT suivant serait également très utile. Je serais éternellement reconnaissant si vous pouvez expliquer cela assez bien qu'un enfant de 5 ans comprendrait. (Je ressens parfois cet âge en regardant les articles).

Merci pour toute l'aide à l'avance. Vous les gars ici m'a aidé à sortir d'une tonne.

CODE SOURCE: http://rosettacode.org/wiki/Fast_Fourier_transform#Python

CODE:

from cmath import exp, pi 

def fft(x): 
    # I understand that we are taking the length of the array sent 
    # into the function and assigning it to N. But I do not get why. 
    N = len(x) 
    # I get that we are returning itself if it is the only item. 
    # What does x represent at this point? 
    if N <= 1: return x 
    # We are creating an even variable and assigning it to the fft of 
    # the even terms of x. This is possibly because we can use this 
    # to take advantage of the symmetry? 
    even = fft(x[0::2]) 
    # We are now doing the same thing with the odd variable. It is 
    # going to be the fft of the odd terms of x. Why would we need 
    # both if we are using it to take advantage of the symmetry? 
    odd = fft(x[1::2]) 
    T= [exp(-2j*pi*k/N)*odd[k] for k in range(N//2)] 
    return [even[k] + T[k] for k in range(N//2)] + \ 
      [even[k] - T[k] for k in range(N//2)] 
# I understand that we are printing a join formatted as a float 
# I get that the float will have 3 numbers after the decimal place and 
# will take up a total of 5 spots 
# I also understand that the abs(f) is what is being formatted and 
# that the absolute value is getting rid of the imaginary portion 
# that is often seen returned by the FFT 
print(' '.join("%5.3f" % abs(f) 
      for f in fft([1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0]))) 

RETOURS:

4.000 2.613 0.000 1.082 0.000 1.082 0.000 2.613 

Answer 1

Une FFT est juste un moyen rapide de calculer une DFT (en utilisant un tour d'affacturage). Peut-être que vous apprendrez ce que fait un DFT en premier, car le trucage de FFT pourrait troubler la question de savoir ce que fait un DFT. Une DFT est juste une transformation de base (un type de matrice de multiplication). Les unités peuvent être complètement arbitraires (milliVolts, pouces, gallons, dollars, etc.) Et tout ensemble de résultats de fréquence dépend d'un taux d'échantillonnage des données d'entrée.