📐 Modül 4 · Matematik Cephanesi · Bölüm 4.5 · 11 dk okuma

Fourier Dönüşümü

Her sinyali sinüs toplamı olarak yaz — sinyalden hesaba bir köprü.

Önkoşul

4.1 — Vektör, Matris, MVM

Bu bölümde öğreneceklerin

Bir sinyalin frekans bileşenlerine ayrıştırılması fikrini açıkla
Sürekli ve ayrık (DFT) Fourier dönüşümünü yaz
FFT'nin O(N log N) karmaşıklığını ve neden bu kadar önemli olduğunu söyle
Konvolüsyon teoremini (zaman çarpımı = frekans MVM'si) hatırla
SIDRA crossbar'ında konvolüsyonu doğrudan yaparak FFT'yi neden atladığını göster

Açılış: Müzikteki Notalar = Sinyalin Sırrı

Bir piyanoda Do, Mi, Sol tuşlarına aynı anda bas — bir akor duyarsın. Akor karmaşık bir dalga, ama beynin onu üç ayrı notaya ayırır. Bu, kulağının yaptığı doğal Fourier dönüşümü.

Joseph Fourier 1822’de gösterdi: her periyodik sinyal sinüs ve kosinüslerin toplamı olarak yazılabilir. Bu, modern sinyal işlemenin (radyo, ses, görüntü, MRI, JPEG, MP3, WiFi, 5G — hepsi!) temelidir.

AI için Fourier neden önemli?

Konvolüsyon teoremi: zaman alanında konvolüsyon = frekans alanında çarpım. CNN’in temeli.
FFT (Fast Fourier Transform): $O(N \log N)$ algoritma, $N^2$ ‘i $N \log N$ ‘e indirir. Modern bilgisayarın temel taşlarından biri.
Spectral methods: sinyalleri frekans uzayında işleme genelde daha verimli (filtreleme, sıkıştırma, denoising).

SIDRA için ilginç soru: crossbar Fourier yapabilir mi? Cevap: evet, DFT bir MVM’dir (matris × vektör). Ama daha ilginç: SIDRA konvolüsyonu doğrudan crossbar’da yapabilir → FFT’ye ihtiyacı yok.

Bu bölüm Fourier’i sezgiden hesaba kurar, FFT’nin sırrını söyler, ve SIDRA’nın neden Fourier’i “atladığını” gösterir.

Sezgi: Sinyal = Frekans Toplamı

Bir kare dalga görsel olarak basit, ama frekans bileşenleri sonsuz çoktur:

\text{kare}(t) = \frac{4}{\pi}\left(\sin t + \frac{\sin 3t}{3} + \frac{\sin 5t}{5} + \frac{\sin 7t}{7} + \ldots\right)

Sadece tek harmonikler, azalan genlikle. Yeterli sayı eklersen kare dalga ortaya çıkar (Gibbs olayı küçük dalgalanma bırakır ama yaklaşım iyi).

Genel ilke: Her “iyi davranışlı” sinyal sinüslerin toplamıdır. Ayrıştırma = Fourier dönüşümü.

Bir sinyalin “spektrumu”:

Sinyal	Spektrum
Tek frekans sinüs	Tek pik (o frekansta)
Kare dalga	Tek harmonikler 1f, 3f, 5f, …
Patlama (impuls)	Düz spektrum (her frekansta eşit)
Beyaz gürültü	Düz spektrum (rastgele)
Beethoven 5. senfoni	Karmaşık piklerin koleksiyonu

Pratik kullanım:

Filtreleme: Sinyalden istenmeyen frekansları kaldır (bas/treble, gürültü temizleme).
Sıkıştırma: JPEG/MP3 az önemli frekansları atar (sıkıştırma).
Fonksiyon analizi: Hangi frekanslar dominant? FFT göster.
Konvolüsyon: filtreleme bir konvolüsyon, frekans alanında çarpıma dönüşür → hızlı.

Formalizm: Sürekli ve Ayrık Fourier

L1 · Başlangıç

Sürekli Fourier dönüşümü:

Sürekli sinyal $x(t)$ için:

X(f) = \int_{-\infty}^{\infty} x(t) e^{-2\pi i f t} \, dt

Ters dönüşüm:

x(t) = \int_{-\infty}^{\infty} X(f) e^{2\pi i f t} \, df

$X(f)$ kompleks sayı: genlik = nasıl güçlü, faz = ne zaman.

Ayrık Fourier (DFT):

Diziler için ( $N$ örnek):

X_k = \sum_{n=0}^{N-1} x_n e^{-2\pi i k n / N}, \quad k = 0, 1, \ldots, N-1

Bu bir MVM’dir — matris elemanları $W_{kn} = e^{-2\pi i kn/N}$ . Karmaşıklık: $O(N^2)$ .

FFT (Fast Fourier Transform):

Cooley-Tukey 1965 algoritması: çift/tek ayrımı + özyinelemeli. Karmaşıklık $O(N \log N)$ .

$N$	DFT	FFT
256	65,536	2,048
1024	1M	10,240
1M	10¹²	20M

FFT olmasa modern dijital sinyal işleme imkânsız. Modern hesaplamanın belki en önemli algoritması.

L2 · Tam

Konvolüsyon teoremi:

İki sinyal $x(t)$ ve $h(t)$ . Konvolüsyon:

(x * h)(t) = \int x(\tau) h(t - \tau) \, d\tau

Fourier dönüşümü:

\mathcal{F}\{x * h\} = X(f) \cdot H(f)

Zaman alanında konvolüsyon = frekans alanında çarpım. Bu çok güçlü:

Konvolüsyon karmaşıklığı (zaman): $O(N^2)$ .
Frekansa geç + çarp + geri (FFT): $O(N \log N)$ .

Pratik etki: uzun konvolüsyonlar (radar, ses, görüntü işleme) FFT ile hızlandırılır.

CNN bağlantısı:

CNN’in konvolüsyon katmanı = sınırlı bir $h$ (filtre, 3×3, 5×5) ile konvolüsyon. Küçük filtre → doğrudan konvolüsyon hızlı; FFT’ye gerek yok genelde.

Ama büyük filtrelerle (örn. küresel attention) FFT çekirdeği kullanılabilir.

SIDRA’da konvolüsyon:

SIDRA crossbar konvolüsyonu doğrudan yapabilir. Sliding window MVM:

Filter ağırlıkları crossbar’a programlanır.
Her pozisyon için pencere giriş, MVM yapılır → çıkış pikseli.
N×N filtre, M×M görüntü → M² × N² MVM.

Crossbar ~10 ns/MVM → tam görüntü konvolüsyonu mikrosaniye sırası.

FFT’ye gerek var mı? SIDRA için genelde hayır — küçük filtreler doğrudan, büyük filtreler için FFT yine MVM olduğu için crossbar’a uyum.

L3 · Derin

FFT crossbar üzerinde:

DFT $W_{kn} = e^{-2\pi i kn/N}$ matrisi sabit. Crossbar’da programlanabilir → DFT bir MVM olur.

Ama: kompleks sayılar. Memristör reel iletkenlik. Çözüm: 2× boyut → reel ve sanal kısımları ayrı sakla. $N \times N$ DFT matrisi → $2N \times 2N$ reel crossbar.

256-DFT: 256×256 → 512×512 reel = 4 SIDRA crossbar. Mümkün, ama FFT $O(N \log N)$ avantajı kaybolur (crossbar zaten paralel, $O(1)$ ).

Pratik karar: SIDRA’da hesaplama-yoğun konvolüsyonu doğrudan crossbar’da yap; FFT’ye gerek yok. FFT, dijital CPU/DSP’de yapılması daha mantıklı (özelleşmiş donanım var).

Diğer Fourier benzeri dönüşümler:

DCT (Discrete Cosine Transform): JPEG’in temeli, sıkıştırma.
Hadamard dönüşümü: ±1 elemanları → çarpma yok, sadece ±. Hızlı yaklaşıklama.
Wavelet: zaman + frekans birlikte. Dalgacık tabanlı sıkıştırma (JPEG-2000).

Hepsi MVM tabanlıdır → SIDRA’da yapılabilir, ama özelleşmiş dijital donanım genelde daha verimli.

Spectral methods AI’da:

Son yıllarda spectral neural networks populer:

Fourier Neural Operators (Li et al. 2020): kısmi diferensiyel denklem çözücüler.
Spectral attention (Lee-Thorp et al. 2022): FFT ile attention’ı hızlandır.
Wavelet transformer (Wang et al. 2024): hibrit zaman-frekans.

Bu tür modeller SIDRA için ilgi çekici — kısmen hibrit (CMOS FFT + crossbar MVM) Y10 hedefinde.

Deney: Bir Sinyalin DFT'sini Elle Hesapla

4-örnek dizi: $\mathbf{x} = (1, 0, -1, 0)$ .

DFT:

$X_k = \sum_{n=0}^{3} x_n e^{-2\pi i k n / 4} = \sum_{n=0}^{3} x_n e^{-i\pi k n / 2}$

$X_0 = 1 + 0 - 1 + 0 = 0$ $X_1 = 1 + 0 \cdot e^{-i\pi/2} - 1 \cdot e^{-i\pi} + 0 = 1 - (-1) = 2$ $X_2 = 1 + 0 - 1 \cdot e^{-i 2\pi} + 0 = 1 - 1 = 0$ $X_3 = 1 + 0 - 1 \cdot e^{-i 3\pi} + 0 = 1 - (-1) = 2$

$\mathbf{X} = (0, 2, 0, 2)$

Yorumla: Sinyal $\cos(\pi n / 2)$ benzer (sadece $k=1$ ve $k=3$ pikleri var). Beklendiği gibi: dizi gerçekten $\cos$ dalgasıdır (1, 0, -1, 0).

SIDRA crossbar’da:

DFT matrisi $W$ :

W = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i \end{bmatrix}

Reel ve sanal ayır:

W_R = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 0 & -1 & 0 \\ 1 & -1 & 1 & -1 \\ 1 & 0 & -1 & 0 \end{bmatrix}, \quad W_I = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & -1 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & -1 \end{bmatrix}

İki ayrı crossbar (4×4 her biri) ile DFT yapılır. Sonuç: reel + i × sanal kısım.

Ama dijital FFT: 4-DFT için $4 \log 4 = 8$ kompleks çarpma, mikrosaniyenin altında. SIDRA bu kadar küçük DFT için gereksiz. Fakat 1024-DFT için (sinyal işlemede sık), crossbar dahil seçenek.

Kısa Sınav

1/6Fourier dönüşümünün temel iddiası nedir?

Laboratuvar Görevi

SIDRA crossbar’ında 256-girişli sinyal için konvolüsyon vs FFT karşılaştırması.

Veri:

Sinyal: $x \in \mathbb{R}^{256}$ (örn. ses örneği).
Filtre: $h \in \mathbb{R}^{32}$ (örn. low-pass).
Konvolüsyon $y = x * h$ : $|y| = 256 + 32 - 1 = 287$ .

Hesap karmaşıklığı:

(a) Doğrudan konvolüsyon FLOP sayısı? (b) FFT-tabanlı: FFT( $x$ , 512) + FFT( $h$ , 512, zero-pad) + elementwise çarpım + inverse FFT(512). FLOP sayısı? (c) SIDRA crossbar üzerinde doğrudan konvolüsyon: kaç MVM, kaç ns? (d) SIDRA crossbar üzerinde FFT-tabanlı: 512-DFT crossbar boyutu, MVM sayısı, süre? (e) Hangi seçenek SIDRA’da daha uygun?

Çözümler

(a) Doğrudan: 287 çıkış × 32 çarpma + ~31 toplama = 287 × 63 ≈ 18K FLOP.

(b) FFT 512 = 512 × log 512 = 512 × 9 ≈ 4600 FLOP/dönüşüm. 3 dönüşüm (x, h forward + inverse) + 512 elementwise çarpım = ~14,800 FLOP. Doğrudan’dan az ama log avantajı küçük (filtre küçük).

(c) Doğrudan SIDRA: 32-girişli filtre. Crossbar 256×256’da 32 satır kullan → 287 sliding window. Her bir 10 ns. Toplam: ~2900 ns ≈ 3 µs.

(d) FFT SIDRA: 512×512 DFT matrisi → 4 crossbar (256×256 her biri). Reel+sanal ayrım → 8 crossbar. 3 FFT × 4 MVM = 12 MVM × 10 ns = 120 ns. Plus elementwise: 5 ns. Total: ~125 ns. Çok daha hızlı.

(e) Büyük sinyallerde FFT SIDRA için iyi — özellikle çoklu paralel sinyaller. Küçük sinyallerde doğrudan konvolüsyon yeterli. Hibrit yaklaşım: sinyal boyutuna göre seç. Compiler kararı (Modül 6.7).

Özet Kart

Fourier: her sinyal sinüs toplamı.
DFT: ayrık dönüşüm, $X_k = \sum x_n e^{-2\pi ikn/N}$ . Karmaşıklık $O(N^2)$ .
FFT: Cooley-Tukey 1965, $O(N \log N)$ . Modern hesaplamanın temel taşlarından.
Konvolüsyon teoremi: $\mathcal{F}\{x*h\} = X \cdot H$ . CNN’in matematiksel temeli.
SIDRA bağlantısı: DFT bir MVM → crossbar yapabilir, ama doğrudan konvolüsyon çoğu zaman daha verimli.
Hibrit: büyük sinyallerde FFT crossbar; küçükte doğrudan.

Vizyon: Spektral AI ve SIDRA'nın Yeri

Bugün AI’nın çoğu zaman alanında çalışır (Transformer’lar dahil). Spektral AI yeni bir akım:

Y1 (bugün): Konvolüsyon SIDRA’da doğrudan; spektral analiz CMOS FFT’de.
Y3 (2027): Spectral attention prototipi (Lee-Thorp tarzı). Dil modeli inference 2-3× hız.
Y10 (2029): Hibrit zaman-frekans işleme. Görüntü ve ses modelleri.
Y100 (2031+): Fourier Neural Operator donanımı. Hava, akışkan dinamiği, PDE-tabanlı bilim AI’ı.
Y1000 (uzun vade): Quantum FFT (Shor algoritmasının temeli) ile hibrit. Klasik + kuantum spektral AI.

Türkiye için anlam: Spektral AI yeni — büyük rakipler henüz domine etmedi. SIDRA + spektral işleme = TÜBİTAK BİLGEM gibi araştırma kurumlarıyla işbirliği fırsatı.

Beklenmedik gelecek: Doğrudan-fiziksel-Fourier çipi. Optik dalga kılavuzları sinyali ışık olarak frekans bileşenlerine doğal ayırır (prizma!). SIDRA Y100 fotonik versiyonunda Fourier “ücretsiz” olabilir.

Daha İleri

Bir sonraki bölüm: 4.6 — Nicemleme ve Kuantizasyon Hatası
Önceki: 4.4 — Olasılık ve Gürültü
Klasik referans: Oppenheim & Schafer, Discrete-Time Signal Processing.
Fourier matematiği: Bracewell, The Fourier Transform and Its Applications.
FFT keşfi: Cooley & Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comput. 1965.
Fourier Neural Operators: Li et al., Fourier Neural Operator for Parametric Partial Differential Equations, ICLR 2021.
FNet (Spectral attention): Lee-Thorp et al., FNet: Mixing Tokens with Fourier Transforms, NAACL 2022.

Önkoşul

Bu bölümde öğreneceklerin

🪝 Açılış: Müzikteki Notalar = Sinyalin Sırrı

🧭 Sezgi: Sinyal = Frekans Toplamı

📐 Formalizm: Sürekli ve Ayrık Fourier

🧪 Deney: Bir Sinyalin DFT'sini Elle Hesapla

📝 Kısa Sınav

🛠️ Laboratuvar Görevi

🗂️ Özet Kart

🔮 Vizyon: Spektral AI ve SIDRA'nın Yeri

📚 Daha İleri