Tumpang tindih-Tambah versus Tumpang-Simpan

24

Perbedaan apa atau kriteria lain yang dapat digunakan untuk membantu memutuskan antara menggunakan overlap-add dan overlap-save untuk penyaringan? Baik overlap-add dan overlap-save dijelaskan sebagai algoritma untuk melakukan konvolusi data stream yang cepat berbasis FFT dengan kernel filter FIR. Apa perbedaan latensi, efisiensi komputasi, atau caching lokalitas (dll.), Jika ada? Atau apakah mereka sama?

hotpaw2
sumber

Jawaban:

27

Pada dasarnya, OS sedikit lebih efisien karena tidak memerlukan penambahan transien yang tumpang tindih. Namun, Anda mungkin ingin menggunakan OA jika Anda perlu menggunakan kembali FFT dengan zero-padding daripada sampel berulang.

Berikut ini ikhtisar singkat dari artikel yang saya tulis beberapa waktu lalu

Konvolusi cepat mengacu pada penggunaan konvolusi sirkuler blok untuk mencapai konvolusi linier. Konvolusi cepat dapat diselesaikan dengan metode OA atau OS. OS juga dikenal sebagai "tumpang tindih memo". Dalam penyaringan OA, setiap blok data sinyal hanya berisi sampel sebanyak yang memungkinkan konvolusi melingkar setara dengan konvolusi linier. Blok data sinyal adalah nol-empuk sebelum FFT untuk mencegah respons impuls filter dari "membungkus" akhir urutan. Pemfilteran OA menambahkan transien input-on dari satu blok dengan transien input-off dari blok sebelumnya. Dalam penyaringan OS, ditunjukkan pada Gambar 1, tidak ada zero-padding yang dilakukan pada data input, sehingga konvolusi melingkar tidak setara dengan konvolusi linier. Bagian yang "membungkus" tidak berguna dan dibuang. Untuk mengimbangi ini, bagian terakhir dari blok input sebelumnya digunakan sebagai awal dari blok selanjutnya. OS tidak memerlukan penambahan transien, membuatnya lebih cepat dari OA.

Mark Borgerding
sumber
Artikel bagus! =)
Phonon
Mungkin ada beberapa optimasi dalam cara DFT atas bagian nol-empuk buffer OA dihitung, yang memberikan keunggulan pada metode OA. Ini tergantung pada prosesor dan paket FFT Anda. Anda juga dapat menulis algoritma FFT Anda sendiri secara khusus untuk OA yang memperhitungkan zero-pad.
orodbhen
@ orodbhen, apakah Anda tahu ada paket FFT seperti itu?
Mark Borgerding
@ MarkBorgerding Di OpenCV Anda dapat menentukan jumlah baris nol, tapi itu khusus untuk 2D. Sejauh apa optimasi implisit hadir dalam paket FFT itu atau lainnya, saya tidak tahu. Saya bisa memikirkan banyak kasus di mana FFT khusus untuk mengeksploitasi sparseness akan sangat membantu, tetapi saya sendiri belum menyusuri jalan itu. Belum.
orodbhen
1
Untung Anda mengutip karena tautannya rusak :(
Mehrdad