Discrete Fourier Transform

Definition

Definition

The Discrete Fourier Transform (DFT) algorithm is a fundamental method for analyzing the frequencies present in discrete signals. It transforms a sequence of complex numbers representing a signal from the time domain into a sequence of complex numbers representing the signal in the frequency domain

Explanation

Commence by taking a sequence of complex numbers that denote discrete data points within a time domain. Proceed by multiplying each data point by a complex sinusoid of differing frequencies. Aggregate the products obtained for each frequency, resulting in complex numbers that express the amplitudes and phases corresponding to those frequencies. This process iterates across all frequencies to encompass the entire spectrum of interest.

Guidance

• Get a list of numbers
• Loop Through Frequencies for each frequency from the start to the end
  • start with a total of zero for this frequency
  • Loop Through Data Points for each number in the list
    • Imagine a swinging arrow that goes around a circle. The arrow's speed depends on the frequency and its position depends on which number you're looking at
    • Multiply the number by where the arrow is pointing, and add it to the total for this frequency
• Return a list of all these totals, which shows how much of each frequency is in the original list of numbers

Tips

• utilize efficient algorithms like the Fast Fourier Transform (FFT) for practical implementations, as it significantly reduces computational complexity
• understand the properties of complex numbers and how they behave when multiplied and added
• choose appropriate data structures and algorithms for handling large datasets efficiently

Practice

Practice

DiscreteFourierTransform(input_sequence):
  N = length(input_sequence)
  output_sequence = array of length N

  for k from 0 to N-1:
    Y_k = 0
    for n from 0 to N-1:
      omega = e^(-2*pi*i*k*n/N)
      Y_k += input_sequence[n] * omega
    output_sequence[k] = Y_k

  return output_sequence

Solution

package main

import (
    "math"
)

type ComplexNumber struct {
    Real float64
    Imag float64
}

// Discrete Fourier Transform (DFT)

func DFT(input []float64) []ComplexNumber {
    N := len(input)
    output := make([]ComplexNumber, N)

    for k := 0; k < N; k++ {
        var sumReal, sumImag float64
        for n := 0; n < N; n++ {
            angle := -2 * math.Pi * float64(k) * float64(n) / float64(N)
            sumReal += input[n] * math.Cos(angle)
            sumImag += input[n] * math.Sin(angle)
        }
        output[k] = ComplexNumber{Real: sumReal, Imag: sumImag}
    }

    return output
}

// Inverse Discrete Fourier Transform (IDFT)
func IDFT(input []ComplexNumber) []float64 {
    N := len(input)
    output := make([]float64, N)

    for n := 0; n < N; n++ {
        var sumReal, sumImag float64
        for k := 0; k < N; k++ {
            angle := 2 * math.Pi * float64(k) * float64(n) / float64(N)
            sumReal += input[k].Real * math.Cos(angle) - input[k].Imag * math.Sin(angle)
            sumImag += input[k].Real * math.Sin(angle) + input[k].Imag * math.Cos(angle)
        }
        output[n] = sumReal / float64(N) // Scaling factor 1/N
    }

    return output
}

// Fast Fourier Transform (FFT)
func FFT(input []float64) []ComplexNumber {
    N := len(input)

    if N <= 1 {
        result := make([]ComplexNumber, N)
        for i := 0; i < N; i++ {
            result[i] = ComplexNumber{Real: input[i], Imag: 0}
        }
        return result
    }

    even := make([]float64, N/2)
    odd := make([]float64, N/2)

    for i := 0; i < N/2; i++ {
        even[i] = input[2*i]
        odd[i] = input[2*i+1]
    }

    evenTransformed := FFT(even)
    oddTransformed := FFT(odd)

    output := make([]ComplexNumber, N)

    for k := 0; k < N/2; k++ {
        angle := -2 * math.Pi * float64(k) / float64(N)
        expReal := math.Cos(angle)
        expImag := math.Sin(angle)

        termReal := expReal*oddTransformed[k].Real - expImag*oddTransformed[k].Imag
        termImag := expReal*oddTransformed[k].Imag + expImag*oddTransformed[k].Real

        output[k] = ComplexNumber{Real: evenTransformed[k].Real + termReal, Imag: evenTransformed[k].Imag + termImag}
        output[k+N/2] = ComplexNumber{Real: evenTransformed[k].Real - termReal, Imag: evenTransformed[k].Imag - termImag}
    }

    return output
}

import java.util.Arrays;

public class FourierTransform {

  // Discrete Fourier Transform (DFT)
  public static Complex[] DFT(double[] input) {
    int N = input.length;
    Complex[] output = new Complex[N];

    for (int k = 0; k < N; k++) {
      double sumReal = 0;
      double sumImag = 0;
      for (int n = 0; n < N; n++) {
        double angle = -2 * Math.PI * k * n / N;
        sumReal += input[n] * Math.cos(angle);
        sumImag += input[n] * Math.sin(angle);
      }
      output[k] = new Complex(sumReal, sumImag);
    }

    return output;
  }

  // Inverse Discrete Fourier Transform (IDFT)
  public static double[] IDFT(Complex[] input) {
    int N = input.length;
    double[] output = new double[N];

    for (int n = 0; n < N; n++) {
      double sumReal = 0;
      double sumImag = 0;
      for (int k = 0; k < N; k++) {
        double angle = 2 * Math.PI * k * n / N;
        sumReal += input[k].real * Math.cos(angle) - input[k].imag * Math.sin(angle);
        sumImag += input[k].real * Math.sin(angle) + input[k].imag * Math.cos(angle);
      }
      output[n] = sumReal / N; // Scaling factor 1/N
    }

    return output;
  }

  // Fast Fourier Transform (FFT)
  public static Complex[] FFT(double[] input) {
    int N = input.length;

    if (N == 1) {
      return new Complex[]{new Complex(input[0], 0)};
    }

    double[] even = new double[N / 2];
    double[] odd = new double[N / 2];

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

    Complex[] evenTransformed = FFT(even);
    Complex[] oddTransformed = FFT(odd);

    Complex[] output = new Complex[N];

    for (int k = 0; k < N / 2; k++) {
      double angle = -2 * Math.PI * k / N;
      Complex exp = new Complex(Math.cos(angle), Math.sin(angle));

      Complex term = oddTransformed[k].multiply(exp);

      output[k] = evenTransformed[k].add(term);
      output[k + N / 2] = evenTransformed[k].subtract(term);
    }

    return output;
  }

  public static class Complex {

    double real;
    double imag;

    public Complex(double real, double imag) {
      this.real = real;
      this.imag = imag;
    }

    public Complex add(Complex other) {
      return new Complex(this.real + other.real, this.imag + other.imag);
    }

    public Complex subtract(Complex other) {
      return new Complex(this.real - other.real, this.imag - other.imag);
    }

    public Complex multiply(Complex other) {
      return new Complex(this.real * other.real - this.imag * other.imag,
          this.real * other.imag + this.imag * other.real);
    }
  }
}

// Discrete Fourier Transform (DFT)
function DFT(input) {
  const N = input.length;
  const output = new Array(N);
  const theta = (-2 * Math.PI) / N;

  for (let k = 0; k < N; k++) {
    let sumReal = 0;
    let sumImag = 0;
    for (let n = 0; n < N; n++) {
      const angle = theta * k * n;
      sumReal += input[n] * Math.cos(angle);
      sumImag += input[n] * Math.sin(angle);
    }
    output[k] = { real: sumReal, imag: sumImag };
  }
  return output;
}

// Inverse Discrete Fourier Transform (IDFT)
function IDFT(input) {
  const N = input.length;
  const output = new Array(N);
  const theta = (2 * Math.PI) / N;

  for (let n = 0; n < N; n++) {
    let sumReal = 0;
    let sumImag = 0;
    for (let k = 0; k < N; k++) {
      const angle = theta * k * n;
      sumReal +=
        input[k].real * Math.cos(angle) - input[k].imag * Math.sin(angle);
      sumImag +=
        input[k].real * Math.sin(angle) + input[k].imag * Math.cos(angle);
    }
    output[n] = sumReal / N; // Scaling factor 1/N
  }
  return output;
}

// Fast Fourier Transform (FFT)
function FFT(input) {
  const N = input.length;

  if (N <= 1) {
    return input;
  }

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

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

  const evenTransformed = FFT(even);
  const oddTransformed = FFT(odd);

  const output = new Array(N);

  for (let k = 0; k < N / 2; k++) {
    const angle = (-2 * Math.PI * k) / N;
    const exp = {
      real: Math.cos(angle),
      imag: Math.sin(angle),
    };

    const term = {
      real:
        exp.real * oddTransformed[k].real - exp.imag * oddTransformed[k].imag,
      imag:
        exp.real * oddTransformed[k].imag + exp.imag * oddTransformed[k].real,
    };

    output[k] = {
      real: evenTransformed[k].real + term.real,
      imag: evenTransformed[k].imag + term.imag,
    };

    output[k + N / 2] = {
      real: evenTransformed[k].real - term.real,
      imag: evenTransformed[k].imag - term.imag,
    };
  }

  return output;
}

import kotlin.math.*

data class Complex(val real: Double, val imag: Double) {
    operator fun plus(other: Complex) = Complex(real + other.real, imag + other.imag)
    operator fun minus(other: Complex) = Complex(real - other.real, imag - other.imag)
    operator fun times(other: Complex) = Complex(
            real * other.real - imag * other.imag,
            real * other.imag + imag * other.real
    )
}

// Discrete Fourier Transform (DFT)
fun dft(input: DoubleArray): Array<Complex> {
    val N = input.size
    val output = Array(N) { Complex(0.0, 0.0) }

    for (k in 0 until N) {
        var sumReal = 0.0
        var sumImag = 0.0
        for (n in 0 until N) {
            val angle = -2 * PI * k * n / N
            sumReal += input[n] * cos(angle)
            sumImag += input[n] * sin(angle)
        }
        output[k] = Complex(sumReal, sumImag)
    }

    return output
}

// Inverse Discrete Fourier Transform (IDFT)
fun idft(input: Array<Complex>): DoubleArray {
    val N = input.size
    val output = DoubleArray(N)

    for (n in 0 until N) {
        var sumReal = 0.0
        var sumImag = 0.0
        for (k in 0 until N) {
            val angle = 2 * PI * k * n / N
            sumReal += input[k].real * cos(angle) - input[k].imag * sin(angle)
            sumImag += input[k].real * sin(angle) + input[k].imag * cos(angle)
        }
        output[n] = sumReal / N // Scaling factor 1/N
    }

    return output
}

// Fast Fourier Transform (FFT)
fun fft(input: DoubleArray): Array<Complex> {
    val N = input.size

    if (N == 1) {
        return arrayOf(Complex(input[0], 0.0))
    }

    val even = DoubleArray(N / 2)
    val odd = DoubleArray(N / 2)

    for (i in 0 until N / 2) {
        even[i] = input[2 * i]
        odd[i] = input[2 * i + 1]
    }

    val evenTransformed = fft(even)
    val oddTransformed = fft(odd)

    val output = Array(N) { Complex(0.0, 0.0) }

    for (k in 0 until N / 2) {
        val angle = -2 * PI * k / N
        val exp = Complex(cos(angle), sin(angle))
        val term = oddTransformed[k] * exp

        output[k] = evenTransformed[k] + term
        output[k + N / 2] = evenTransformed[k] - term
    }

    return output
}

import math

class ComplexNumber:
    def __init__(self, real, imag):
        self.real = real
        self.imag = imag

    def add(self, other):
        return ComplexNumber(self.real + other.real, self.imag + other.imag)

    def subtract(self, other):
        return ComplexNumber(self.real - other.real, self.imag - other.imag)

    def multiply(self, other):
        return ComplexNumber(
            self.real * other.real - self.imag * other.imag,
            self.real * other.imag + self.imag * other.real
        )

# Discrete Fourier Transform (DFT)
def DFT(input_signal):
    N = len(input_signal)
    output = [ComplexNumber(0, 0)] * N

    for k in range(N):
        for n in range(N):
            angle = -2 * math.pi * k * n / N
            output[k] = output[k].add(ComplexNumber(input_signal[n] * math.cos(angle),
                                                    input_signal[n] * math.sin(angle)))

    return output

# Inverse Discrete Fourier Transform (IDFT)
def IDFT(input_spectrum):
    N = len(input_spectrum)
    output = [0] * N

    for n in range(N):
        for k in range(N):
            angle = 2 * math.pi * k * n / N
            output[n] += input_spectrum[k].real * math.cos(angle) - input_spectrum[k].imag * math.sin(angle)

    return [value / N for value in output]

# Fast Fourier Transform (FFT)
def FFT(input_signal):
    N = len(input_signal)

    if N <= 1:
        return input_signal

    even = FFT(input_signal[::2])
    odd = FFT(input_signal[1::2])

    factor = [math.exp(-2j * math.pi * k / N) for k in range(N//2)]

    return [even[k] + factor[k] * odd[k] for k in range(N//2)] + \
           [even[k] - factor[k] * odd[k] for k in range(N//2)]

use std::f64::consts::PI;

#[derive(Debug, Clone, Copy)]
struct Complex {
    real: f64,
    imag: f64,
}

impl Complex {
    fn new(real: f64, imag: f64) -> Complex {
        Complex { real, imag }
    }

    fn add(self, other: Complex) -> Complex {
        Complex::new(self.real + other.real, self.imag + other.imag)
    }

    fn subtract(self, other: Complex) -> Complex {
        Complex::new(self.real - other.real, self.imag - other.imag)
    }

    fn multiply(self, other: Complex) -> Complex {
        Complex::new(
            self.real * other.real - self.imag * other.imag,
            self.real * other.imag + self.imag * other.real,
        )
    }
}

// Discrete Fourier Transform (DFT)
fn dft(input_signal: &[f64]) -> Vec<Complex> {
    let n = input_signal.len();
    let mut output = vec![Complex::new(0.0, 0.0); n];

    for k in 0..n {
        for n in 0..n {
            let angle = -2.0 * PI * (k as f64) * (n as f64) / (n as f64);
            output[k] = output[k].add(Complex::new(input_signal[n] * angle.cos(), input_signal[n] * angle.sin()));
        }
    }

    output
}

// Inverse Discrete Fourier Transform (IDFT)
fn idft(input_spectrum: &[Complex]) -> Vec<f64> {
    let n = input_spectrum.len();
    let mut output = vec![0.0; n];

    for n in 0..n {
        for k in 0..n {
            let angle = 2.0 * PI * (k as f64) * (n as f64) / (n as f64);
            output[n] += input_spectrum[k].real * angle.cos() - input_spectrum[k].imag * angle.sin();
        }
    }

    output.iter().map(|&x| x / (n as f64)).collect()
}

// Fast Fourier Transform (FFT)
fn fft(input_signal: &[f64]) -> Vec<Complex> {
    let n = input_signal.len();

    if n <= 1 {
        return input_signal.iter().map(|&x| Complex::new(x, 0.0)).collect();
    }

    let even: Vec<f64> = input_signal.iter().enumerate().filter(|(i, _)| i % 2 == 0).map(|(_, &x)| x).collect();
    let odd: Vec<f64> = input_signal.iter().enumerate().filter(|(i, _)| i % 2 != 0).map(|(_, &x)| x).collect();

    let even_transformed = fft(&even);
    let odd_transformed = fft(&odd);

    let factor: Vec<Complex> = (0..n / 2).map(|k| {
        let angle = -2.0 * PI * (k as f64) / (n as f64);
        Complex::new(angle.cos(), angle.sin())
    }).collect();

    let mut output = vec![Complex::new(0.0, 0.0); n];

    for k in 0..n / 2 {
        let term = odd_transformed[k].multiply(factor[k]);
        output[k] = even_transformed[k].add(term);
        output[k + n / 2] = even_transformed[k].subtract(term);
    }

    output
}

class ComplexNumber {
  constructor(
    public real: number,
    public imag: number,
  ) {}

  add(other: ComplexNumber): ComplexNumber {
    return new ComplexNumber(this.real + other.real, this.imag + other.imag);
  }

  subtract(other: ComplexNumber): ComplexNumber {
    return new ComplexNumber(this.real - other.real, this.imag - other.imag);
  }

  multiply(other: ComplexNumber): ComplexNumber {
    return new ComplexNumber(
      this.real * other.real - this.imag * other.imag,
      this.real * other.imag + this.imag * other.real,
    );
  }
}

// Discrete Fourier Transform (DFT)
function DFT(input: number[]): ComplexNumber[] {
  const N = input.length;
  const output: ComplexNumber[] = [];

  for (let k = 0; k < N; k++) {
    let sumReal = 0;
    let sumImag = 0;
    for (let n = 0; n < N; n++) {
      const angle = (-2 * Math.PI * k * n) / N;
      sumReal += input[n] * Math.cos(angle);
      sumImag += input[n] * Math.sin(angle);
    }
    output.push(new ComplexNumber(sumReal, sumImag));
  }

  return output;
}

// Inverse Discrete Fourier Transform (IDFT)
function IDFT(input: ComplexNumber[]): number[] {
  const N = input.length;
  const output: number[] = [];

  for (let n = 0; n < N; n++) {
    let sumReal = 0;
    let sumImag = 0;
    for (let k = 0; k < N; k++) {
      const angle = (2 * Math.PI * k * n) / N;
      sumReal +=
        input[k].real * Math.cos(angle) - input[k].imag * Math.sin(angle);
      sumImag +=
        input[k].real * Math.sin(angle) + input[k].imag * Math.cos(angle);
    }
    output.push(sumReal / N);
  }

  return output;
}

// Fast Fourier Transform (FFT)
function FFT(input: number[]): ComplexNumber[] {
  const N = input.length;

  if (N <= 1) {
    return input.map((val) => new ComplexNumber(val, 0));
  }

  const even: number[] = [];
  const odd: number[] = [];
  for (let i = 0; i < N / 2; i++) {
    even.push(input[2 * i]);
    odd.push(input[2 * i + 1]);
  }

  const evenTransformed = FFT(even);
  const oddTransformed = FFT(odd);

  const output: ComplexNumber[] = [];
  for (let k = 0; k < N / 2; k++) {
    const angle = (-2 * Math.PI * k) / N;
    const exp = new ComplexNumber(Math.cos(angle), Math.sin(angle));

    const term = oddTransformed[k].multiply(exp);

    output.push(evenTransformed[k].add(term));
    output.push(evenTransformed[k].subtract(term));
  }

  return output;
}