JavaScriptを使用してFFTを実装する方法

信号処理の分野では、高速フーリエ変換 (FFT) は、時間領域信号を周波数領域信号に変換するために広く使用されているアルゴリズムです。 FFT は効率と正確さにより、オーディオ、ビデオ、音声、画像、電気などの分野で広く使用されています。 JavaScript は移植性が高く柔軟なスクリプト言語として Web 開発で広く使用されているため、JavaScript バージョンの FFT を実装することが非常に必要です。

この記事では、JavaScript を使用して FFT を実装する方法を紹介します。

アルゴリズムの概要

FFT アルゴリズムは高速フーリエ変換アルゴリズムに基づいており、離散時間領域信号を離散周波数領域信号に変換できます。コンピュータの分野におけるFFTアルゴリズムには離散フーリエ変換(DFT)と高速フーリエ変換(FFT)の2種類があり、離散フーリエ変換はFFTの基礎となります。

離散フーリエ変換の公式は次のとおりです:

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

このうち、$x_n$ は時間領域信号 $x$ の $n$ 番目のサンプリング点の値を表し、$X_k $ は周波数を表します。領域信号 $X$ 内の $k$ 番目の周波数成分の値です。その計算量は $O(N^2)$ で、時間計算量は高くなります。

高速フーリエ変換は分割統治戦略に基づくアルゴリズムで、離散フーリエ変換の計算量を $O(N\log N)$ に最適化し、計算量を大幅に改善します。 。 スピード。

JavaScript による FFT の実装

次に、JavaScript を使用して FFT アルゴリズムを実装する方法を紹介します。

まず、FFT アルゴリズムの入力と出力を明確にする必要があります。 FFT アルゴリズムの入力は時間領域信号のセットであり、出力は周波数領域の信号の成分です。 JavaScript では、配列を使用して一連の離散時間領域信号を表すことができます。各要素の値は、その時点での信号のサンプル値を表します。

FFT アルゴリズムを実装する場合は、次の手順が必要です。

1. 入力信号を計算して、時間領域のサンプリング ポイントを取得します。
2. 取得したサンプリング ポイントをビット反転アルゴリズムに従って再配置し、計算におけるキャッシュ ミスを減らし、計算効率を向上させます。
3. FFT アルゴリズムの再帰計算を使用します。再帰的なプロセスにより、信号が分割され、征服されます。各再帰レベルでは、信号が偶数点と奇数点の 2 つのサブセットに分割され、2 つのサブセットが再帰的に計算されて結合されます。
4. 周波数領域信号の振幅と位相を計算します。式 $|X_k|=\sqrt{Re(X_k)^2 Im(X_k)^2}$ と $\angle X_k=\tan^{-1}\left(\frac{Im(X_k)} によると{Re (X_k)}\right)$ は周波数振幅と位相を計算します。

次は、JavaScript で FFT アルゴリズムを実装するためのサンプル コードです:

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;
}

このサンプル コードでは、振幅と位相の計算、ビット反転などのいくつかの補助関数を定義します。アルゴリズムなど最も重要な関数は fft 関数です。この関数は配列を入力信号として受け取り、再帰を使用して FFT アルゴリズムを計算します。

結論

FFT アルゴリズムは、一般的に使用される信号処理アルゴリズムであり、オーディオ、ビデオ、音声、画像、その他の分野で広く使用されています。この記事では、JavaScript を使用して FFT アルゴリズムを実装する方法について説明します。具体的な実装では、ビット反転アルゴリズムや再帰的手法などの最適化手法を採用する必要があります。 FFT アルゴリズムを実装して使用することで、信号処理がより便利になり、Web 開発やその他の分野の作業に役立ちます。

以上がJavaScriptを使用してFFTを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。