discrete fourier transform in for loop in javascript

The Discrete Fourier Transform (DFT) is a common signal processing technique to transform a signal from time domain to frequency domain. In JavaScript, we can implement the DFT using a for loop as follows:

index.tsx
function dft(signal) {
  const N = signal.length;
  const re = [];
  const im = [];
  for (let k = 0; k < N; k++) {
    let sumRe = 0;
    let sumIm = 0;
    for (let n = 0; n < N; n++) {
      const theta = (2 * Math.PI * k * n) / N;
      sumRe += signal[n] * Math.cos(theta);
      sumIm -= signal[n] * Math.sin(theta);
    }
    re[k] = sumRe;
    im[k] = sumIm;
  }
  return [re, im];
}
392 chars
18 lines

This implementation takes an input signal and returns the corresponding Fourier coefficients as an array of real and imaginary parts. The input signal should be an array of N real or complex numbers.

This DFT implementation has a time complexity of O(N^2), which is not efficient for large values of N. However, it is a simple and intuitive implementation that demonstrates the basic concept of the DFT.

Note that there are more efficient algorithms for computing the DFT, such as the Fast Fourier Transform (FFT), which have a time complexity of O(N log N).

gistlibby LogSnag