Matematik & Sinyal İşleme

Zor

Sedgewick

Discrete Fourier Transform (DFT) hesaplamasını Cooley-Tukey Radix-2 yöntemi ile O(n^2) süresinden O(n log n) süresine indiren temel algoritmadır.

Hızlı Fourier Dönüşümü (Fast Fourier Transform) Algoritması

Hızlı Fourier Dönüşümü (Fast Fourier Transform) Açıklaması

Hızlı Fourier Dönüşümü (FFT), bir zaman serisini veya sinyali frekans bileşenlerine ayıran Discrete Fourier Transform (DFT) işlemini son derece hızlı bir şekilde gerçekleştiren algoritmalar ailesidir.

DFT hesaplamasının kaba kuvvet yaklaşımı her girdi çifti için çarpım yaptığından $O(n^2)$ karmaşıklığa sahiptir. Cooley-Tukey algoritması, girdi boyutunu tek ve çift indeksli olmak üzere ikiye bölüp (divide-and-conquer), karmaşık birim kökleri (twiddle factors) ile birleştirerek bu süreyi $O(n log n)$ seviyesine indirir.

FFT, dijital sinyal işleme (DSP), ses/görüntü sıkıştırma (JPEG, MP3), hızlı büyük tamsayı/polinom çarpımı ve kuantum bilişimde (QFT) kritik bir öneme sahiptir.

Kaynak Notları

Cooley-Tukey algoritması, girdi dizisi uzunluğunun 2'nin bir kuvveti ($2^k$) olmasını gerektirir.
Ters FFT (IFFT) algoritması, birim köklerin işaretleri değiştirilerek ve sonuç dizisi n'e bölünerek aynı mantıkla çalıştırılır.

Çalışma Prensibi

Eğer girdi dizisinin boyutu n = 1 ise, diziyi olduğu gibi döndür (kök durum).
Girdi dizisini çift indeksli (even) ve tek indeksli (odd) olarak ikiye böl.
Çift indeksli elemanlar için FFT'yi özyinelemeli olarak çağır (Y_even).
Tek indeksli elemanlar için FFT'yi özyinelemeli olarak çağır (Y_odd).
k = 0'dan n/2 - 1'e kadar döngü kur:
Karmaşık birim kökünü hesapla: W = e^(-2 * pi * i * k / n) = cos(-2*pi*k/n) + i*sin(-2*pi*k/n).
Kombinasyon adımı (Butterfly):
Output[k] = Y_even[k] + W * Y_odd[k]
Output[k + n/2] = Y_even[k] - W * Y_odd[k]
Hesaplanan Output dizisini döndür.

Kod Örnekleri

Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.

Hızlı Fourier Dönüşümü (Fast Fourier Transform) Algoritması - TypeScript

1interface Complex {
2  re: number;
3  im: number;
4}
5
6function add(a: Complex, b: Complex): Complex {
7  return { re: a.re + b.re, im: a.im + b.im };
8}
9
10function sub(a: Complex, b: Complex): Complex {
11  return { re: a.re - b.re, im: a.im - b.im };
12}
13
14function mul(a: Complex, b: Complex): Complex {
15  return {
16    re: a.re * b.re - a.im * b.im,
17    im: a.re * b.im + a.im * b.re
18  };
19}
20
21export function cooleyTukeyFFT(a: Complex[]): Complex[] {
22  const n = a.length;
23  if (n <= 1) return a;
24  
25  const even: Complex[] = [];
26  const odd: Complex[] = [];
27  for (let i = 0; i < n; i++) {
28    if (i % 2 === 0) even.push(a[i]);
29    else odd.push(a[i]);
30  }
31  
32  const yEven = cooleyTukeyFFT(even);
33  const yOdd = cooleyTukeyFFT(odd);
34  
35  const y = new Array(n);
36  for (let k = 0; k < n / 2; k++) {
37    const angle = (-2 * Math.PI * k) / n;
38    const w: Complex = { re: Math.cos(angle), im: Math.sin(angle) };
39    const t = mul(w, yOdd[k]);
40    
41    y[k] = add(yEven[k], t);
42    y[k + n / 2] = sub(yEven[k], t);
43  }
44  
45  return y;
46}

Kendi Verilerinizle Test Edin

Gerçek sayı dizilerini girerek Cooley-Tukey kelebek (butterfly) adımlarını ve frekans spektrum genliklerini hesaplayın.

Hızlı Fourier Dönüşümü Simülatörü

Gerçek sayı dizilerini girerek Cooley-Tukey kelebek (butterfly) adımlarını ve frekans spektrum genliklerini hesaplayın.

Girdi

Sonuç

Henüz çalıştırılmadı

Algoritma Analizi

Zaman ve Alan Karmaşıklığı

Zaman Karmaşıklığı

En İyi Durum: O(n log n) - Her zaman aynı sayıda bölünme adımı gerçekleşir

Ortalama Durum: O(n log n)

En Kötü Durum: O(n log n)

Alan Karmaşıklığı

O(n) - Özyinelemeli dizileri ve sonuçları saklamak için - Bu algoritmanın karmaşıklığı belirtilmemiş.

Kelebek (Butterfly) İşlem Analizi

Her aşamada dizinin boyutu yarıya iner ve $\log_2 n$ adet seviyede toplam $n \log_2 n$ adet kelebek toplama/çıkarma işlemi gerçekleştirilir.
FFT algoritmasının donanımsal paralel implementasyonları, systolic yapılar veya paralel kelebek devreleri sayesinde $O(\log n)$ süresine kadar inebilir.
Büyük polinom çarpımlarında, polinom katsayıları FFT ile nokta gösterimine dönüştürülüp $O(n)$ zamanda çarpılır ve ters FFT ile tekrar katsayılarına dönüştürülerek toplamda $O(n \log n)$ çarpım süresi elde edilir.

Avantajlar ve Dezavantajlar

Avantajlar

DFT kaba kuvvet çarpımına ($O(n^2)$) kıyasla devasa veri kümelerinde binlerce kat performans artışı sağlar.
Yapısı son derece simetrik ve paralel programlamaya (GPU/FPGA) uygundur.
Gelişmiş sinyal filtreleme süreçlerinde eşsiz bir matematiksel verimlilik sunar.

Dezavantajlar

Dizi boyutunun 2'nin tam kuvveti olmaması durumunda padding (sıfır ekleme) yapılması gerekir veya karmaşık Radix-3/5 varyantları uygulanmalıdır.
Aşırı küçük dizilerde özyineleme maliyeti nedeniyle kaba kuvvet yaklaşımından daha yavaş olabilir.
Kayan noktalı (floating point) karmaşık sayı çarpımları nedeniyle yuvarlama hataları oluşabilir.

İlgili Algoritmalar

Hızlı Fourier Dönüşümü (Fast Fourier Transform) Algoritması ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar:

Ters FFT (IFFT)

Frekans spektrum verilerini tekrar zaman serisine dönüştüren algoritma.

Karatsuba Çarpımı

Polinomları katsayı bazında bölen bir diğer divide-and-conquer çarpım yöntemi.

Yükleniyor // RUNTIME_INITIALIZINGAlgoritma ve bileşen ağacı hazırlanıyor...

Hızlı Fourier Dönüşümü (Fast Fourier Transform) Algoritması

Hızlı Fourier Dönüşümü (Fast Fourier Transform) Açıklaması

FFT, dijital sinyal işleme (DSP), ses/görüntü sıkıştırma (JPEG, MP3), hızlı büyük tamsayı/polinom çarpımı ve kuantum bilişimde (QFT) kritik bir öneme sahiptir.

Kaynak Notları

Cooley-Tukey algoritması, girdi dizisi uzunluğunun 2'nin bir kuvveti ($2^k$) olmasını gerektirir.
Ters FFT (IFFT) algoritması, birim köklerin işaretleri değiştirilerek ve sonuç dizisi n'e bölünerek aynı mantıkla çalıştırılır.

Çalışma Prensibi

Eğer girdi dizisinin boyutu n = 1 ise, diziyi olduğu gibi döndür (kök durum).
Girdi dizisini çift indeksli (even) ve tek indeksli (odd) olarak ikiye böl.
Çift indeksli elemanlar için FFT'yi özyinelemeli olarak çağır (Y_even).
Tek indeksli elemanlar için FFT'yi özyinelemeli olarak çağır (Y_odd).
k = 0'dan n/2 - 1'e kadar döngü kur:
Karmaşık birim kökünü hesapla: W = e^(-2 * pi * i * k / n) = cos(-2*pi*k/n) + i*sin(-2*pi*k/n).
Kombinasyon adımı (Butterfly):
Output[k] = Y_even[k] + W * Y_odd[k]
Output[k + n/2] = Y_even[k] - W * Y_odd[k]
Hesaplanan Output dizisini döndür.

Kod Örnekleri

Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.

Hızlı Fourier Dönüşümü (Fast Fourier Transform) Algoritması - TypeScript

1interface Complex {
2  re: number;
3  im: number;
4}
5
6function add(a: Complex, b: Complex): Complex {
7  return { re: a.re + b.re, im: a.im + b.im };
8}
9
10function sub(a: Complex, b: Complex): Complex {
11  return { re: a.re - b.re, im: a.im - b.im };
12}
13
14function mul(a: Complex, b: Complex): Complex {
15  return {
16    re: a.re * b.re - a.im * b.im,
17    im: a.re * b.im + a.im * b.re
18  };
19}
20
21export function cooleyTukeyFFT(a: Complex[]): Complex[] {
22  const n = a.length;
23  if (n <= 1) return a;
24  
25  const even: Complex[] = [];
26  const odd: Complex[] = [];
27  for (let i = 0; i < n; i++) {
28    if (i % 2 === 0) even.push(a[i]);
29    else odd.push(a[i]);
30  }
31  
32  const yEven = cooleyTukeyFFT(even);
33  const yOdd = cooleyTukeyFFT(odd);
34  
35  const y = new Array(n);
36  for (let k = 0; k < n / 2; k++) {
37    const angle = (-2 * Math.PI * k) / n;
38    const w: Complex = { re: Math.cos(angle), im: Math.sin(angle) };
39    const t = mul(w, yOdd[k]);
40    
41    y[k] = add(yEven[k], t);
42    y[k + n / 2] = sub(yEven[k], t);
43  }
44  
45  return y;
46}

Kendi Verilerinizle Test Edin

Gerçek sayı dizilerini girerek Cooley-Tukey kelebek (butterfly) adımlarını ve frekans spektrum genliklerini hesaplayın.

Hızlı Fourier Dönüşümü Simülatörü

Gerçek sayı dizilerini girerek Cooley-Tukey kelebek (butterfly) adımlarını ve frekans spektrum genliklerini hesaplayın.

Girdi

Sonuç

Henüz çalıştırılmadı

Algoritma Analizi

Zaman ve Alan Karmaşıklığı

Zaman Karmaşıklığı

En İyi Durum: O(n log n) - Her zaman aynı sayıda bölünme adımı gerçekleşir

Ortalama Durum: O(n log n)

En Kötü Durum: O(n log n)

Alan Karmaşıklığı

O(n) - Özyinelemeli dizileri ve sonuçları saklamak için - Bu algoritmanın karmaşıklığı belirtilmemiş.

Kelebek (Butterfly) İşlem Analizi

Her aşamada dizinin boyutu yarıya iner ve $\log_2 n$ adet seviyede toplam $n \log_2 n$ adet kelebek toplama/çıkarma işlemi gerçekleştirilir.
FFT algoritmasının donanımsal paralel implementasyonları, systolic yapılar veya paralel kelebek devreleri sayesinde $O(\log n)$ süresine kadar inebilir.
Büyük polinom çarpımlarında, polinom katsayıları FFT ile nokta gösterimine dönüştürülüp $O(n)$ zamanda çarpılır ve ters FFT ile tekrar katsayılarına dönüştürülerek toplamda $O(n \log n)$ çarpım süresi elde edilir.

Avantajlar ve Dezavantajlar

Avantajlar

DFT kaba kuvvet çarpımına ($O(n^2)$) kıyasla devasa veri kümelerinde binlerce kat performans artışı sağlar.
Yapısı son derece simetrik ve paralel programlamaya (GPU/FPGA) uygundur.
Gelişmiş sinyal filtreleme süreçlerinde eşsiz bir matematiksel verimlilik sunar.

Dezavantajlar

Dizi boyutunun 2'nin tam kuvveti olmaması durumunda padding (sıfır ekleme) yapılması gerekir veya karmaşık Radix-3/5 varyantları uygulanmalıdır.
Aşırı küçük dizilerde özyineleme maliyeti nedeniyle kaba kuvvet yaklaşımından daha yavaş olabilir.
Kayan noktalı (floating point) karmaşık sayı çarpımları nedeniyle yuvarlama hataları oluşabilir.

İlgili Algoritmalar

Hızlı Fourier Dönüşümü (Fast Fourier Transform) Algoritması ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar:

Ters FFT (IFFT)

Frekans spektrum verilerini tekrar zaman serisine dönüştüren algoritma.

Karatsuba Çarpımı

Polinomları katsayı bazında bölen bir diğer divide-and-conquer çarpım yöntemi.