JavaScript를 사용하여 FFT를 구현하는 방법

신호 처리 분야에서 FFT(고속 푸리에 변환)는 시간 영역 신호를 주파수 영역 신호로 변환하는 데 널리 사용되는 알고리즘입니다. FFT의 효율성과 정확성으로 인해 오디오, 비디오, 음성, 이미지 및 전기와 같은 분야에서 널리 사용됩니다. 이식성이 뛰어나고 유연한 스크립팅 언어인 JavaScript는 웹 개발에 널리 사용되므로 JavaScript 버전의 FFT를 구현하는 것이 매우 필요합니다.

이 글에서는 JavaScript를 사용하여 FFT를 구현하는 방법을 소개합니다.

알고리즘 소개

FFT 알고리즘은 이산 시간 영역 신호를 이산 주파수 영역 신호로 변환할 수 있는 고속 푸리에 변환 알고리즘을 기반으로 합니다. 컴퓨터 분야에는 이산 푸리에 변환(DFT)과 고속 푸리에 변환(FFT)의 두 가지 유형의 FFT 알고리즘이 있습니다. 이산 푸리에 변환은 FFT의 기초입니다.

이산 푸리에 변환의 공식은 다음과 같습니다.

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

그 중 $x_n$은 시간 영역 신호 $x$에서 $n$번째 샘플링 지점의 값을 나타내고, $X_k$는 주파수 영역에서 $k$번째 주파수 성분의 값을 나타냅니다. $X$ 신호를 보내세요. 계산 복잡도는 $O(N^2)$이고 시간 복잡도도 높습니다.

고속 푸리에 변환은 분할 정복 전략을 기반으로 한 알고리즘으로, 이산 푸리에 변환의 계산 복잡성을 $O(Nlog N)$로 최적화하여 계산 속도를 크게 향상시킬 수 있습니다.

FFT 구현을 위한 JavaScript

다음으로 JavaScript를 사용하여 FFT 알고리즘을 구현하는 방법을 소개하겠습니다.

먼저 FFT 알고리즘의 입력과 출력을 명확히 해야 합니다. FFT 알고리즘의 입력은 시간 영역 신호 세트이고 출력은 주파수 영역 신호의 구성 요소입니다. JavaScript에서는 배열을 사용하여 개별 시간 영역 신호 세트를 나타낼 수 있습니다. 여기서 각 요소의 값은 해당 순간의 신호 샘플링 값을 나타냅니다.

FFT 알고리즘을 구현할 때 다음 단계가 필요합니다.

1. 입력 신호를 계산하여 시간 영역 샘플링 포인트를 얻습니다.
2. Bit-Reversal 알고리즘에 따라 획득한 샘플링 포인트를 재배열하여 계산 시 캐시 누락을 줄이고 계산 효율성을 높입니다.
3. FFT 알고리즘의 재귀 계산을 사용합니다. 재귀 프로세스는 신호를 분할하고 정복합니다. 각 재귀 레벨에서 신호는 짝수점과 홀수점의 두 하위 집합으로 나누어지고, 두 하위 집합은 재귀적으로 계산된 후 결합됩니다.
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 알고리즘을 구현하고 사용함으로써 신호 처리를 더욱 편리하게 만들고 웹 개발 및 기타 분야의 작업에 도움을 줄 수 있습니다.

위 내용은 JavaScript를 사용하여 FFT를 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!