FFT aslında seni Gösteriyor

Soru

Bir piyanoda bir chord oynayın - diyelim, C ve E birlikte. Kulakınız bir ses duyar. Ancak bu ses iki frekans süperi ortaya çıkıyor: 261.6 Hz ve 329.6 Hz. Cochlea fiziksel olarak onları ayırır - farklı saç hücreleri farklı frekanslarda rezonansa girer, beyninize farklı sinyalleri gönderir.

Hızlı Fourier aynı şeyi yapar, ancak saç hücreleri yerine sayılarla. Bir sinyal verin (zaman üzerindeki amplif örneklerin bir dizi) ve bir frekans ve güçlü yönleri döndürür. Cevap: ** Hangi frekanslar mevcut ve her biri ne kadar?**

Aslında neler oluyor

Zaman içinde bir sinyal örneği bir sayı listesidir: her örnek noktada amplitüd. 44,100 Hz'deki 1 saniyelik kayıt 44,100 sayıdır. Bu rakamlar, time domain'deki sinyali tarif eder - zamanın işlevi olarak amplitüd.

FFT bunu fret domain'e dönüştürür - frekansın işlevi olarak basitleşir. Aynı bilgi, farklı temsil. Kartesian ve kutup koordinatları arasındaki geçiş gibi: Hiçbir şey yaratılmaz veya yok edilmez, sadece yeniden ifade edilir.

Matematiksel temel: Her periyodik sinyal farklı frekanslarda sine ve kosine dalgaların toplamı olarak yazılabilir. Bu Fourier'in teoremi (1807). FFT bu miktarın katlarını hesaplar - her frekansın ne kadarı sinyaldedir.

Neden "Fast"

Fourier dönüşümü hesaplamanın naif yolu gerektirir N örnekleri için N2 işlemleri. 1024 örnek için, bu yaklaşık 1 milyon operasyon. Cooley-Tukey algoritması (1965) bunu N·log2 (N) - aynı giriş için yaklaşık 10.000 operasyona azaltır. 100x hız. Bir milyon örnek için, hız 50.000x.

Oyun: N-point iki N/2 nokta dönüştürmelerini bölün, recursally. Bu, N'nin 2'nin gücü olmasını gerektirir (veya sıfırlarla pediniz). Her biri problemi yarı yarıya ayırdı. "butterfly" operasyonu yarıları birleştirir:

X[k]     = Even[k] + W · Odd[k]
X[k+N/2] = Even[k] - W · Odd[k]

W karmaşık bir üstel nerededir ( karmaşık uçakta bir rotasyon). Aynı iki sub-results size iki çıkış noktası verir. Bu yüzden algoritma "fast" - her hesaplamayı iki kez tekrarlıyor.

PinePaper'in uygulamaları Cooley-Tukey radix-2 DIT (zamanda yetersizlik). 40 JavaScript hattı. Bunu bir kütüphane ithal etmek yerine çiziyoruz çünkü öğrencilerin kaynağı okuyabilmesini ve her çizgiyi anlamasını istedik.

Bu Barlar ne anlama geliyor

Bir spektrum analizörü gördüğünüzde - her bar bir frekans bini temsil eder. Yükseklik, mevcut sinyaldeki bu frekansın büyüklüğüdür.

• ** Saf bir sine dalgası** frekansında yüksek bir bar üretiyor ve başka bir şey değil.
• **Bir kare dalgası ** temel ve her tuhaf harmonik (3rd, 5th, 7th...), 1/n olarak azaldı. Bu yüzden meydan dalgaları "buzzy" seslenir - saf sinlerin yapmadığı yüksek frekanslı enerji içerir.
• **Beyaz gürültü ** her yerde kabaca eşit yükseklik çubukları üretir. Her frekans eşit olasılık ile mevcuttur.
• **Bir insan sesi ** temel oluşturur (görünüyorsun) artı formantlar - ünlüleri ayırt eden ses yolunuzun biçiminden yankılanır.

Pencere: Edges Matter

Bir yakalama var. FFT, sinyalin sonsuza dek tekrarladığını varsayıyor. Ama örneğimiz sonludur - başlar ve durur. Eğer sinyal her iki uç noktada sıfır olacaksa, abruptoff yapay yüksek frekanslı içerik yaratır. Bu, spectral sızıntı olarak adlandırılır.

Düzeltme: Bir **window işlevi tarafından sinyali çoğaltın - bu musluklar kenarlarda sıfıra sorunsuzca. Ortak pencereler:

• Hann (cosine zil): iyi genel amaç, bazı frekans çözünürlüğünü kaybeder
• Hamming: Hann'a benzer ama kenarlarda sıfıra ulaşmıyor, biraz daha iyi yanlobe baskı bastırma
• ** Blackman**: Darer main lobe, daha iyi yanlobe baskı, daha fazla frekans çözünürlüğü kaybeder

Seçim her zaman frekans çözümü arasında bir ticarettir (nasıl tam olarak bir frekans tespit edebilirsiniz) ve leakage sızıntı (nasıl çok fazla enerji komşu binlere karşı kanamalar). Mükemmel bir pencere yoktur. Bu, belirsizlik prensibinin bir sonucudur - hem zaman hem de frekansın aynı anda kesin bilgisine sahip olamazsınız.

FFT Lives Nerede

FFT sonuçları ile sürekli etkileşime giriyorsunuz:

• MP3 ve AAC sıkıştırması: Sesi frekans domainine dönüştürmek, işitme eşinin altındaki discard frekansları, hangi kalıntıları sıkıştırın. Dönüşüm, kayıp ses sıkıştırmasının tüm temelidir.
• JPEG sıkıştırma: 2D sürüm (DCT) frekans domain 8×8 piksel bloklarını frekans alanına dönüştürür, yüksek frekanslı bileşenleri ölçer. Bu yüzden JPEG eserleri blok olarak görünür.
• WiFi ve 5G: OFDM encoding birçok frekans alt-karrier arasında verileri bölmektedir. FFT, zaman alan iletimi ve frekans-bölge veri sembolleri arasında dönüştürür.
• MRI görüntüleme: bir MR tarayıcıdan gelen ham sinyal frekans alanındadır. Ters FFT uzaysal imajı yeniden yapılandırır. Literally: Hiç görmediğiniz her MR Fourier dönüşümüdir.
• Shazam: Spektrogramları hesaplar (geçmiş pencereler üzerinde FFT), topları toplar, bir veritabanına karşı desenleri maçları. FFT her şarkıyı tanımanın ilk adımıdır.

60 yaşındaki bir algoritma, cebinizde, günde milyarlarca kez çalışır.

Deneyin

Open PinePaper, Spectrum Analyzer jeneratörünü seçin. Bir meydan dalga. Barlara bak - 1/n olarak düşen garip harmonikleri göreceksiniz. Bir testereye geçiş - şimdi tüm harmonikler mevcut, 1/n olarak düşüyor. Gürültüye geçiş - düz spektrum, her frekans eşit derecede muhtemeldir.

Pencere işlevini değiştirin. Hann spektrumu daha geniş zirvelerin pahasına nasıl yumuşatdığını izleyin. Blackman'a geçiş - dar zirveler ama daha düşük yanlobes.

FFT hakkında okumazsınız. Sinyalleri ölçüyorsunuz ve dönüştürmenin ne açığa çıktığını gözlemleyin. Bu, bilmek ve anlayış arasındaki fark.

Referanslar

• Brigham, E.O. (1988). * Hızlı Fourier ve Uygulamaları*. Prentice Hall.
• Cooley, J.W. & Tukey, J.W. (1965). Kompleks Fourier Serisinin Makine Hesaplaması için Algoritma. * Computation *, 19(90), 297-301.
• Fourier, J. (1822). Théorie analytique de la chaleur. Paris: Firmain Didot.
• Harris, F.J. (1994). Windows kullanımında, Discrete Fourier dönüşümü ile Harmonic Analysis için. * IEEE *, 66(1), 51-83.
• Oppenheim, A.V. & Schafer, R.W. (2009). Discrete-Time Signal Processing (3rd ed.). Prentice Hall.
• Shannon, C.E. (1949). Gürültünün Prestijinde İletişim. * IRE*, 37(1), 10-21.
• Smith, S.W. (1997). * Bilim Adamı ve Mühendisin Dijital İşaret İşleme Kılavuzu*. California Technical Publishing.
• Wang, A., et al. (2003). Industrial-Strength Audio Search Algorithm. * ISMIR 2003'ten alıntılar*. (Shazam'ın ses parmak izi algoritması.)
• Wallace, G.K. (1994). JPEG hala Resim Promosyon Standardı. * ACM *, 34 (4), 30-44.

---

*PinePaper'in FFT, Hann, Hamming ve Blackman pencereleme ile Cooley-Tukey radix-2 uygulamasıdır, artı düşük ve yüksek frekanslı filtreler. pinepaper.studio/editor