Fourier Transform

Giriş
Açıklaması şöyle.

the Fourier transform takes a real or complex signal as an input, and produces a complex signal as an output,

Fourier Transform Neden Var

Bir çok sinyal periyodik değil. Şeklen şöyle

Açıklaması şöyle. Yani bir sinyali sinüs sinyallerin toplamı haline getiriyor.

... that any function, whether continuous or discontinuous, can be expanded into a series of sines (to be completely accurate, into a series of complex exponentials, but don't worry about this for now). What this means is that each of these sines can be combined linearly (fancy word to say "summed") to add up to the original signal.

In that sense you could say that aperiodic signals, such as the noise you took as an example, "have many different wavelengths". In fact, they are composed of an infinite sum of sinusoidal (hence periodic) waveforms, each with a different wavelength, amplitude, and phase.

- period / frequency / wavelength: how long it takes for that sine to complete a cycle (in seconds) / how many cycles that sine goes through in a second (in Hz) / the distance traveled by that sine in one cycle (in meters).
- amplitude: the amount of that sine in the original signal.
- phase: the offset of that sine relative to a sine with same frequency and 0 phase.

So, how do you get the wavelength, amplitude and phase for each of these components? Here comes the Fourier Transform.

Fourier Transform Çeşitleri

Temelde iki çeşit Fourier Transform var

1. Continuous Fourier Transform
Açıklaması şöyle.

There's little in the ways of actual need for this in digital electronics – digital signals are sampled, so you'd use the DFT.

Bu neden kullanılmıyor. Açıklaması şöyle. Yani sonsuz sinyaller içindir. Dijital sinyaller ise sonsuz değildir. Mutlaka örnekleme yapılır.

The answer is the same to the question: "Why do we need computers to process data when we have paper and pencil?"

DTFT as well as the continuous-time Fourier Transform is a theoretical tool for infinitely long hypothetical signals.

the DFT is to observe the spectrum of actual data that is finite in size.

2. Discrete Fourier Transform (DFT)

Açıklaması şöyle

- The Fourier transform is a framework to analyze these types of aperiodic signals. Using clever mathematics, you can transform a time-domain signal (including, but not limited to, noise) into the frequency-domain, which allows you to compute the characteristics (wavelength, amplitude and phase) for each sine wave that compose this signal.

- The DFT (Discrete Fourier Transform) is used when dealing with discrete signals, and is usually implemented using the FFT (Fast Fourier Transform) algorithm. Depending on your software/language (Matlab? Python? R? C?) there are libraries you can use to easily compute that.

Açıklaması şöyle.

Usually, that's implemented as an FFT, Fast Fourier Transform. That's one of the most important algorithmic discoveries of the 20th century, ...

Açıklaması şöyle.

There are 4 versions of Fourier transforms that are all close cousins.

It's all due to the basic property that "sampling in one domain corresponds to periodicity in the other domain". If a time signal is periodic, the frequency domain signal is discrete. If a frequency domain signal is periodic, the time domain signal is discrete.

Tablo şöyle.

> `Time                       Frequency               Transform 
Continuos & aperidoc          Continuos & aperidoc    Fourier Transform
Discrete  & aperidoc          Continuos &  peridoc    Discrete Time Fourier Transform
Continuos &  peridoc          Discrete  & aperidoc    Fourier Series
Discrete  &  peridoc          Discrete  &  peridoc    Discrete Fourier Transform

2.1 Fast Fourier Transform - Yani Discrete Fourier Transform Gerçekleştirimi

Açıklaması şöyle. Aslında Discrete Fourier Transform'un daha hızlı çalışan bir alt kümesi.

First, the fast Fourier transform is just an algorithm that realizes the discrete Fourier transform quickly; so it's a perfect subset of the DFT.

FFT zaman ekseninde verilen sinyali , frekans ekseninde gösterecek şekilde bileşenlere ayırır. FFT ile yapılan bir varsayım sinyalin tek seferlik değil, periyodik olmasıdır.

FFT 2^n örnek alırsa geriye 2^(n-1) tane gerçek veya sanal sayı (imaginary number) döndürür.
How to get Frequency from FFT result sorusundan da anlaşıldığı gibi 44,100 Hz ile yapılan 1024 örnekleme de FFT sonucunda çıkan değerlerin sadece 511 tanesi kullanılabiliyor.

FFT yaparken örneklemeye window'da denilir. Sinyal üzerindeki pencereyi kaydırırken, pencerelerin bir miktar çakışmasına dikkat edilir.

Örnek

Şöyle yaparız

/*
  Fast Fourier transform
  T is the precision level: float, double, long double.
  Overwrites the input.
  Only works for input sizes that are a power of 2.
*/
template<typename T>
    requires std::is_floating_point<T>
void FFT(std::vector<std::complex<T>>& input)
{
    if (input.size() == 0) {
        throw std::invalid_argument("input is empty");
    }
    if (input.size() & (input.size() - 1)) {
        throw std::invalid_argument("input length is not a power of two");
    }

    auto const table = internal::rootsOfUnity<T>(input.size());
    internal::FFT(input, table, input.size());
}

Kullanmak için şöyle yaparız.

// Test program
#include <iostream>

int main()
{
  static constexpr size_t n = 1048576;
  std::vector<std::complex<double>> input;
  for (std::size_t i = 0;  i < n;  ++i) {
    input.emplace_back(i);
  }

  // Overwrite input with its Fourier transform
  FFT<double>(input);

  // use the result, to avoid optimising out
  std::cout << input[0] << '\n';
}

internal namespace içindeki metodlar şöyledir.

#include <complex>
#include <vector>

namespace internal
{
  /*
    Creating the table of all N'th roots of unity.
    We use notation ω_i = e^(-2πi/n).
  */
  template<typename U>
  constexpr auto rootsOfUnity(std::size_t n)
  {
    constexpr auto pi = std::acos(U{-1.0});
    std::vector<std::complex<U>> table;
    table.reserve(n);

    for (std::size_t i = 0;  i < n;  ++i) {
      table.emplace_back(std::cos(-2.0 * pi * i / n), std::sin(-2.0 * pi * i / n));
    }

      return table;
  }

  template<typename V>        // V is vector of complex
  void FFT(V& input, const V& table, std::size_t total_size)
  {
    if (input.size() <= 1) {
      // The Fourier transform on one element does not do
      // anything, so nothing needed here.
      return;
    }

    const auto n2 = input.size() / 2;

    // Split up the input in even and odd components
    V evenComponents;  evenComponents.reserve(n2);
    V oddComponents;   oddComponents.reserve(n2);

    for (std::size_t i = 0;  i < input.size();  ) {
      evenComponents.push_back(input[i++]);
      oddComponents.push_back(input[i++]);
    }

    // Transform the even and odd input
    FFT(evenComponents, table, total_size);
    FFT(oddComponents, table, total_size);

    // Use the algorithm from Danielson and Lanczos
    for (std::size_t i = 0;  i < n2;  ++i) {
      // ω_n^i = (ω_N^(N/n))^i = ω_N^(Nk/n)
      auto const plusMinus = table[total_size / n2 * i] * oddComponents[i];
      input[i] = evenComponents[i] + plusMinus;
      input[i + n2] = evenComponents[i] - plusMinus;
    }
  }
}