Mengapa saya harus memberi sinyal nol sebelum mengambil transformasi Fourier?


77

Dalam jawaban untuk pertanyaan sebelumnya , dinyatakan bahwa seseorang harus melakukannya

zero-pad sinyal input (tambahkan nol sampai akhir sehingga setidaknya setengah dari gelombang "kosong")

Apa alasannya?


Itu tergantung pada apa yang Anda lakukan. Ini bisa menjadi komentar atas jawaban saya. Saya menambahkan beberapa penjelasan.
endolith

@endolith: Awalnya saya berpikir untuk meletakkannya sebagai komentar, tapi saya pikir pertanyaannya mungkin menarik, dan akan sangat disayangkan jika jawaban yang baik untuk itu terkubur dalam komentar di suatu tempat. Jika Anda tidak setuju, saya akan menghapus pertanyaan ini.
Jonas

9
Ya itu pertanyaan yang sangat umum. Anda dapat nol pad untuk membuat sesuatu kekuatan-2, Anda dapat nol pad untuk membuat transformasi melingkar berperilaku seperti transformasi non-melingkar, Anda dapat melakukannya untuk menguji ulang sinyal, untuk mengubah resolusi frekuensi, dll.
endolith

Jawaban:


82

Zero padding memungkinkan seseorang untuk menggunakan FFT yang lebih panjang, yang akan menghasilkan vektor hasil FFT yang lebih lama.

Hasil FFT yang lebih panjang memiliki lebih banyak nampan frekuensi yang berjarak frekuensinya lebih dekat. Tetapi mereka pada dasarnya akan memberikan hasil yang sama dengan interpolasi Sinc berkualitas tinggi dari FFT non-nol-empuk yang lebih pendek dari data asli.

Ini mungkin menghasilkan spektrum tampak lebih halus ketika diplot tanpa interpolasi lebih lanjut.

Meskipun interpolasi ini tidak akan membantu penyelesaian atau resolusi dan / atau antara frekuensi yang berdekatan atau berdekatan, mungkin akan memudahkan untuk secara visual menyelesaikan puncak dari frekuensi tunggal yang terisolasi yang tidak memiliki sinyal atau suara berdekatan yang signifikan dalam spektrum. . Secara statistik, kepadatan yang lebih tinggi dari nampan hasil FFT mungkin akan membuatnya lebih mungkin bahwa nampan magnitudo puncak lebih dekat dengan frekuensi sinusoid frekuensi input terisolasi terisolasi, dan tanpa interpolasi lebih lanjut (parabola, et.al.).

Tetapi, pada dasarnya, zero padding sebelum DFT / FFT adalah metode yang efisien secara komputasi untuk menginterpolasi sejumlah besar poin.

Zero-padding untuk lintas-korelasi, auto-korelasi, atau penyaringan konvolusi digunakan untuk tidak mencampur hasil konvolusi (karena konvolusi melingkar). Hasil lengkap konvolusi linier lebih panjang daripada salah satu dari dua vektor input. Jika Anda tidak menyediakan tempat untuk mengakhiri hasil konvolusi yang lebih lama ini, konvolusi cepat FFT hanya akan mencampurnya dengan dan meningkatkan hasil yang Anda inginkan. Zero-padding menyediakan banyak angka untuk mencampur hasil yang lebih lama. Dan jauh lebih mudah untuk mencampur sesuatu yang hanya dicampur / dijumlahkan dengan vektor nol.


12
Paragraf terakhir adalah jawaban kunci untuk pertanyaan awal, meskipun saya pikir itu bisa dinyatakan lebih jelas. Zero-padding dalam konteks korelasi atau konvolusi dapat dilakukan untuk memastikan bahwa penerapan proses dalam domain frekuensi menghasilkan linier, bukan konvolusi / korelasi sirkular . Namun, melakukannya bukan keharusan jika Anda bersedia melakukan beberapa pekerjaan pembukuan di samping, seperti pada algoritma tumpang-tindih dan tumpang tindih-tambahkan.
Jason R

4
@Jason R: Sebenarnya, keduanya berbelit-belit. FFT normal (non-pangkas) melakukan semua perkalian dan menambahkan untuk membungkus bagian dari hasil. Hanya saja dalam kasing yang cukup nol, semua yang dikalikan dan ditambah bernilai nol, jadi tidak ada yang peduli tentang apa pun yang dihitung dan dililitkan di lingkaran.
hotpaw2

9
Memang; perkalian DFT dari dua sinyal selalu menerapkan konvolusi melingkar. Saya seharusnya mengatakannya secara berbeda: Anda memasukkan nol di akhir satu sinyal untuk memastikan bahwa hasil yang diperoleh dengan melingkar secara melingkar adalah sama dengan apa yang Anda dapatkan jika Anda membelitnya secara linear (dengan asumsi bahwa konvolusi linear adalah yang Anda inginkan, yaitu biasanya demikian).
Jason R

27

Ada beberapa hal yang perlu dipertimbangkan sebelum Anda memutuskan untuk nol pad sinyal domain waktu Anda. Anda mungkin tidak perlu nol pad sinyal sama sekali!

1) Perpanjang data domain waktu (bukan nol padding) untuk mendapatkan resolusi yang lebih baik di domain frekuensi.

2) Tingkatkan jumlah poin FFT di luar panjang sinyal domain-waktu Anda (zero padding) jika Anda ingin melihat definisi yang lebih baik dari tempat sampah FFT, meskipun itu tidak membelikan Anda resolusi yang lebih benar. Anda juga dapat melakukan pad untuk mendapatkan 2 poin FFT poin.

3) Saat mengutak-atik titik FFT (di titik sebelumnya), pastikan titik frekuensi Anda berakhir di tempat yang Anda inginkan. Spasi poin adalah , di mana adalah frekuensi sampling dan adalah jumlah poin FFT.fs/NfsN

Ada beberapa angka bagus yang menggambarkan poin-poin ini di http://www.bitweenie.com/listings/fft-zero-padding/

Satu hal lagi yang disebutkan: Jika Anda nol pad sinyal dalam domain waktu dan Anda ingin menggunakan fungsi windowing, pastikan Anda jendela sinyal sebelum nol pad. Jika Anda menerapkan fungsi jendela setelah nol padding, Anda tidak akan mencapai apa yang seharusnya dicapai oleh jendela. Lebih khusus lagi, Anda masih akan memiliki transisi yang tajam dari sinyal ke nol alih-alih transisi yang mulus ke nol.


8

Secara umum zero-padding sebelum DFT setara dengan interpolasi, atau pengambilan sampel yang lebih sering, dalam domain yang diubah.

Berikut ini visualisasi cepat tentang cara kerja yang sebaliknya. Jika Anda mengambil sampel sinyal tanpa batas waktu dengan kecepatan lebih tinggi, Anda mendapatkan spektrum yang lebih 'terjepit', yaitu spektrum dengan lebih banyak nol di kedua ujungnya. Dengan kata lain, Anda dapat memperoleh lebih banyak sampel dalam waktu hanya dengan frekuensi zero-padding setelah DFT, dan kemudian IDFT menghasilkan hasil zero-padded.

Efek yang sama berlaku terbalik ketika zero-padding terjadi pada waktunya. Ini semua karena rekonstruksi sinyal yang sempurna dimungkinkan selama sinyal dibatasi dan sampel setidaknya pada tingkat Nyquist.

Istilah 'resolusi' tergantung pada bagaimana Anda mendefinisikannya. Bagi saya, ini berarti seberapa baik dua titik pengamatan yang berdekatan dalam waktu atau frekuensi dapat dibedakan (secara statistik). Dalam hal ini resolusi sebenarnya tergantung pada ukuran DFT karena kebocoran spektral. Artinya, lebih kecil ukuran jendela, lebih buram atau dioleskan sinyal yang ditransformasikan, dan sebaliknya. Ini berbeda dari seberapa sering Anda sampel, atau apa yang saya sebut 'definisi'. Misalnya, Anda dapat memiliki sampel yang sangat buram sampel pada tingkat tinggi (definisi tinggi), namun Anda masih tidak dapat memperoleh informasi lebih banyak daripada pengambilan sampel dengan kecepatan lebih rendah. Jadi secara ringkas, zero-padding tidak meningkatkan resolusi sama sekali karena Anda tidak mendapatkan informasi lebih banyak dari sebelumnya.


6

Jika seseorang memiliki minat pada spektrum fungsi windowing yang digunakan untuk mengisolasi sampel time-domain, maka zero-padding AKAN meningkatkan resolusi frekuensi dari fungsi windowing.

Jika sinyal waktu adalah , di mana adalah fungsi windowing, maka keseluruhan spektrumnya adalah , di mana mengisyaratkan konvolusi. x(t)w(t)w(t)X(f)?W(f)?

Jika fungsi windowing Anda adalah persegi panjang sederhana (ekstraksi dari beberapa set nilai dari . Kemudian adalah fungsi sinkronisasi. Jadi, misalnya, jika Nfft sama dengan lebar persegi panjang Anda, dan Anda memiliki sinusoid tepat di salah satu frekuensi nampan, maka sampel fungsi sinkronisasi yang akan muncul berpusat pada nampan itu jatuh tepat di persimpangan nol di luar puncak, dan Anda tidak melihat bentuk sinkronisasi di spektrum sama sekali. Jika Anda sekarang nol pad data Anda masuk ke FFTx(t)X(f), Anda akan melihat beberapa sampel di tempat selain puncak dan nol penyeberangan, mengungkapkan bentuk fungsi sinkronisasi dalam spektrum yang dihasilkan. Jadi apa gunanya zero-padding? Hal ini tentu berguna untuk mengungkap sifat transformasi diskrit dari sinyal berjendela, yang merupakan kasus biasa. Dalam arti praktis, ini bisa berguna dalam kasus apa pun di mana Anda tertarik pada bentuk spektral dari amplop terisolasi yang mengendarai gelombang pembawa.


4

Mungkin ada alasan berbeda untuk ini tergantung pada proses yang dilakukan sebelum dan sesudah transformasi Fourier. Alasan paling umum adalah untuk mencapai resolusi frekuensi yang lebih besar dalam setiap transformasi yang dihasilkan. Artinya, semakin besar jumlah sampel yang digunakan dalam transformasi Anda, semakin sempit binwidth dalam spektrum daya yang dihasilkan. Ingat: binwidth = sample_frequency / transform_size (sering disebut ukuran jendela). Anda dapat membayangkan dari ini, bahwa ketika Anda meningkatkan ukuran transformasi Anda, binwidth berkurang (= resolusi frekuensi lebih baik). Zero padding adalah cara meningkatkan ukuran transformasi tanpa memasukkan informasi baru ke sinyal.

Jadi mengapa tidak mengambil transformasi yang lebih besar tanpa bantalan nol? Bukankah itu akan mencapai efek yang sama? Pertanyaan bagus. Dalam banyak kasus, Anda mungkin ingin menganalisis aliran data domain waktu, yang untuknya Anda mungkin menggunakan transformasi Fourier (stft) singkat. Ini melibatkan pengambilan transformasi setiap sampel N sesuai dengan resolusi waktu yang Anda butuhkan untuk mengkarakterisasi perubahan dalam spektrum frekuensi. Di sinilah letak masalahnya. Jendela terlalu besar dan Anda akan kehilangan resolusi waktu, jendela terlalu kecil dan Anda akan kehilangan resolusi frekuensi. Solusinya kemudian adalah mengambil jendela domain waktu kecil memberikan Anda resolusi waktu yang baik dan kemudian nol pad mereka untuk memberikan resolusi frekuensi yang baik. Semoga ini bermanfaat buat kamu

Pembaruan
Saya tidak menjelaskan ini dengan baik. Saya seharusnya mengklarifikasi lebih baik. Mengacu pada transformasi berjendela, memang Anda tidak mendapatkan resolusi frekuensi yang lebih besar 'aktual' tetapi untuk tujuan visualisasi (membaca spektrum daya dengan mata) itu dapat memberikan hasil yang lebih jelas. Dengan menggunakan laju pengambilan sampel kritis, setiap lobus sisi menempati satu nampan, yang tergantung pada teknik grafik bisa menyesatkan. Zero padding menyediakan spektrum frekuensi interpolasi yang mungkin lebih terbuka. Selain itu, jika Anda menggunakan metode pengambilan puncak sederhana untuk estimasi frekuensi, efek interpolasi spektral dari zero padding akan memberi Anda sampel spektral lebih dekat ke puncak sebenarnya dari lobus utama. Tautan ini menyediakan beberapa diagram yang bermanfaat: http://www.dsprelated.com/dspbooks/sasp/Practical_Zero_Padding.html


9
Jawaban ini tidak benar. Zero-padding tidak meningkatkan resolusi frekuensi sama sekali; itu hanya menginterpolasi antara output dari transformasi yang lebih kecil. Anda dapat menganggap zero-padding sebagai menambahkan lebih banyak tempat sampah frekuensi yang memiliki bandwidth yang sama seperti yang mereka lakukan dengan transformasi yang lebih kecil; oleh karena itu, dari perspektif bank filter, passbands mereka tumpang tindih.
Jason R

1
Jika ini membantu memahami: Anda juga dapat melakukan yang sebaliknya: ambil FFT dari sebuah sinyal, kemudian nolkan pad hasilnya, dan balikkan FFT. Ini akan memiliki efek interpolasi sinyal asli. Tapi tentu saja sinyalnya masih sama, dengan bandwidth Nyquist yang sama. Interpolasi tidak akan memberi Anda informasi frekuensi yang lebih tinggi daripada yang semula ada.
endolith

1
@Jason R - Anda benar, jawaban saya menyesatkan, saya telah mencoba mengklarifikasi di atas pada posting asli. Saya seharusnya tidak menyatakan bahwa zero padding meningkatkan resolusi frekuensi.
Dan Barry

2

Saya tidak melihat ini disebutkan dalam tanggapan yang baik sebelumnya sehingga saya akan menambahkan alasan penting tambahan berikut untuk zero padding:

Algoritma Radix-2 lebih efisien sehingga nol padding ke kekuatan berikutnya 2 (atau kekuatan 4 dalam beberapa kasus untuk radix-4), atau lebih signifikan menghindari faktor prima besar dapat meningkatkan kinerja waktu nyata. Juga ketika menggunakan FFT untuk analisis, zero padding sering dilakukan untuk menghitung sampel DTFT, seperti menentukan respons frekuensi FIR: bandingkan fft ([1 1 1 1]) dengan fft ([1 1 1 1], 512) yang identik dengan freqz ([1 1 1 1]).

Dengan menggunakan situs kami, Anda mengakui telah membaca dan memahami Kebijakan Cookie dan Kebijakan Privasi kami.
Licensed under cc by-sa 3.0 with attribution required.
Judi bola