Comment implémenter FFT à l'aide de JavaScript

Dans le domaine du traitement du signal, la transformée de Fourier rapide (FFT) est un algorithme largement utilisé pour convertir des signaux dans le domaine temporel en signaux dans le domaine fréquentiel. L'efficacité et la précision de la FFT la rendent largement utilisée dans des domaines tels que l'audio, la vidéo, la parole, l'image et l'électricité. En tant que langage de script hautement portable et flexible, JavaScript est largement utilisé dans le développement Web. Il est donc indispensable d'implémenter la version JavaScript de FFT.

Cet article explique comment utiliser JavaScript pour implémenter FFT.

Introduction à l'algorithme

L'algorithme FFT est basé sur l'algorithme de transformation de Fourier rapide, qui peut convertir un signal discret dans le domaine temporel en un signal discret dans le domaine fréquentiel. Dans le domaine informatique, il existe deux types d'algorithmes FFT : la transformée de Fourier discrète (DFT) et la transformée de Fourier rapide (FFT). La transformée de Fourier discrète est la base de la FFT.

La formule de la transformée de Fourier discrète est :

$$X_k=sum_{n=0}^{N-1}x_ne^{-i2pi kn/N} , k=0,1,2,cdots,N-1$$

Où, $x_n$ représente la valeur du $n$ème point d'échantillonnage dans le signal du domaine temporel $x$, $X_k $ Représente la valeur de la $k$ème composante de fréquence dans le signal du domaine fréquentiel $X$. Sa complexité de calcul est de $O(N^2)$ et sa complexité temporelle est élevée.

La transformée de Fourier rapide est un algorithme basé sur la stratégie diviser pour régner, qui peut optimiser la complexité de calcul de la transformée de Fourier discrète à $O(Nlog N)$, améliorant considérablement la complexité de calcul . vitesse.

JavaScript pour implémenter FFT

Ensuite, nous présenterons comment utiliser JavaScript pour implémenter l'algorithme FFT.

Tout d'abord, nous devons clarifier l'entrée et la sortie de l'algorithme FFT. L'entrée de l'algorithme FFT est un ensemble de signaux dans le domaine temporel et la sortie est la composante du signal dans le domaine fréquentiel. En JavaScript, nous pouvons utiliser un tableau pour représenter un ensemble de signaux discrets dans le domaine temporel, où la valeur de chaque élément représente la valeur échantillonnée du signal à ce moment-là.

Lors de la mise en œuvre de l'algorithme FFT, nous avons besoin des étapes suivantes :

1. Calculez le signal d'entrée pour obtenir les points d'échantillonnage du domaine temporel.
2. Réorganisez les points d'échantillonnage obtenus selon l'algorithme Bit-Reversal pour réduire les échecs de cache dans les calculs et améliorer l'efficacité des calculs.
3. Utilisez le calcul récursif de l'algorithme FFT. Le processus récursif divise et conquiert le signal. Dans chaque niveau récursif, le signal est divisé en deux sous-ensembles de points pairs et de points impairs, puis les deux sous-ensembles sont calculés de manière récursive puis joints.
4. Calculez l'amplitude et la phase du signal dans le domaine fréquentiel. D'après la formule $|X_k|=sqrt{Re(X_k)^2+Im(X_k)^2}$ et $angle X_k=tan^{-1}left(frac{Im(X_k)}{Re(X_k )} à droite)$ pour calculer l'amplitude et la phase de la fréquence.

Ce qui suit est un exemple de code pour implémenter l'algorithme FFT en JavaScript :

function fft(signal) {
  const N = signal.length;
  const X = new Array(N);

  if (N === 1) {
    X[0] = signal[0];
    return X;
  }

  const even = new Array(N / 2);
  const odd = new Array(N / 2);

  for (let i = 0; i < N / 2; i++) {
    even[i] = signal[2 * i];
    odd[i] = signal[2 * i + 1];
  }

  const E = fft(even);
  const O = fft(odd);

  for (let i = 0; i < N / 2; i++) {
    const w = Math.exp((-2 * Math.PI * i) / N);
    const b = w * O[i];

    X[i] = E[i] + b;
    X[i + N / 2] = E[i] - b;
  }

  return X;
}

function amplitudeAndPhase(X) {
  const N = X.length;
  const amplitude = new Array(N);
  const phase = new Array(N);

  for (let i = 0; i < N; i++) {
    const Re = X[i].real;
    const Im = X[i].imaginary;

    amplitude[i] = Math.sqrt(Re * Re + Im * Im);
    phase[i] = Math.atan2(Im, Re);
  }

  return { amplitude, phase };
}

function bitReversal(signal) {
  const N = signal.length;
  const X = new Array(N);

  for (let i = 0; i < N; i++) {
    X[reverseBits(i, Math.log2(N))] = signal[i];
  }

  return X;
}

function reverseBits(num, bits) {
  let reversed = 0;

  for (let i = 0; i < bits; i++) {
    reversed = (reversed << 1) | (num & 1);
    num >>= 1;
  }

  return reversed;
}

Dans cet exemple de code, nous définissons plusieurs fonctions auxiliaires, notamment le calcul de l'amplitude et phase, algorithme d'inversion de bits, etc. La plus importante est la fonction fft, qui accepte un tableau comme signal d'entrée et calcule l'algorithme FFT par récursivité.

Conclusion

L'algorithme FFT est un algorithme de traitement du signal couramment utilisé et est largement utilisé dans les domaines de l'audio, de la vidéo, de la parole, de l'image et d'autres domaines. Cet article décrit comment implémenter l'algorithme FFT à l'aide de JavaScript. Dans une implémentation spécifique, nous devons adopter certaines méthodes d'optimisation, telles que l'algorithme Bit-Reversal et la méthode récursive. En implémentant et en utilisant l'algorithme FFT, nous pouvons rendre le traitement du signal plus pratique, facilitant ainsi le travail de développement Web et d'autres domaines.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!