Bagaimana untuk melaksanakan FFT menggunakan JavaScript

Dalam bidang pemprosesan isyarat, Fast Fourier Transform (FFT) ialah algoritma yang digunakan secara meluas untuk menukar isyarat domain masa kepada isyarat domain frekuensi. Kecekapan dan ketepatan FFT menjadikannya digunakan secara meluas dalam bidang seperti audio, video, pertuturan, imej dan elektrik. Sebagai bahasa skrip yang sangat mudah alih dan fleksibel, JavaScript digunakan secara meluas dalam pembangunan web, jadi sangat perlu untuk melaksanakan versi JavaScript FFT.

Artikel ini akan memperkenalkan cara menggunakan JavaScript untuk melaksanakan FFT.

Pengenalan Algoritma

Algoritma FFT adalah berdasarkan algoritma Fast Fourier Transform, yang boleh menukar isyarat domain masa diskret kepada isyarat domain frekuensi diskret. Dalam bidang komputer, terdapat dua jenis algoritma FFT: transformasi Fourier diskret (DFT) dan transformasi Fourier pantas (FFT) Transformasi Fourier diskret adalah asas FFT.

Formula penjelmaan Fourier diskret ialah:

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

di mana, $x_n$ mewakili nilai titik pensampelan $n$th dalam isyarat domain masa $x$, $X_k$ mewakili isyarat domain frekuensi $X Nilai komponen frekuensi $k$th dalam $. Kerumitan pengiraannya ialah $O(N^2)$ dan kerumitan masanya adalah tinggi.

Transformasi Fourier pantas ialah algoritma berdasarkan strategi bahagi-dan-takluk, yang boleh mengoptimumkan kerumitan pengiraan transformasi Fourier diskret kepada $O(Nlog N)$, meningkatkan kelajuan pengiraan dengan ketara.

JavaScript melaksanakan FFT

Seterusnya, kami akan memperkenalkan cara menggunakan JavaScript untuk melaksanakan algoritma FFT.

Pertama, kita perlu menjelaskan input dan output algoritma FFT. Input algoritma FFT ialah satu set isyarat domain masa, dan output ialah komponen isyarat dalam domain frekuensi. Dalam JavaScript, kita boleh menggunakan tatasusunan untuk mewakili satu set isyarat domain masa diskret, di mana nilai setiap elemen mewakili nilai sampel isyarat pada masa itu.

Apabila melaksanakan algoritma FFT, kita memerlukan langkah berikut:

1. Kira isyarat input untuk mendapatkan titik pensampelan domain masa.
2. Susun semula titik pensampelan yang diperoleh mengikut algoritma Pembalikan Bit untuk mengurangkan kesilapan cache dalam pengiraan dan meningkatkan kecekapan pengiraan.
3. Gunakan pengiraan rekursif algoritma FFT. Proses rekursif membahagi dan menakluk isyarat. Dalam setiap tahap rekursif, isyarat dibahagikan kepada dua subset titik genap dan titik ganjil, dan kemudian kedua subset dikira secara rekursif dan kemudian dicantumkan.
4. Kira amplitud dan fasa isyarat domain frekuensi. Mengikut formula $|X_k|=sqrt{Re(X_k)^2+Im(X_k)^2}$ dan $angle X_k=tan^{-1}left(frac{Im(X_k)}{Re(X_k )} kanan)$ untuk mengira amplitud frekuensi dan fasa.

Berikut ialah contoh kod untuk melaksanakan algoritma FFT dalam 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;
}

Dalam kod sampel ini, kami mentakrifkan beberapa fungsi tambahan, termasuk mengira amplitud dan fasa, Bit -Algoritma pembalikan, dsb. Yang paling penting ialah fungsi fft, yang menerima tatasusunan sebagai isyarat input dan mengira algoritma FFT menggunakan rekursi.

Kesimpulan

Algoritma FFT ialah algoritma pemprosesan isyarat yang biasa digunakan dan digunakan secara meluas dalam audio, video, pertuturan, imej dan medan lain. Artikel ini menerangkan cara melaksanakan algoritma FFT menggunakan JavaScript. Dalam pelaksanaan khusus, kita perlu menggunakan beberapa kaedah pengoptimuman, seperti algoritma Bit-Reversal dan kaedah rekursif. Dengan melaksanakan dan menggunakan algoritma FFT, kami boleh menjadikan pemprosesan isyarat lebih mudah dan membantu dengan kerja dalam pembangunan web dan bidang lain.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan FFT menggunakan JavaScript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!