Overlap-Add kontra Overlap-Save

24

Jakie różnice lub inne kryteria mogą pomóc w podjęciu decyzji między użyciem nakładania-dodawania i nakładania-zapisywania do filtrowania? Zarówno nakładanie-dodawanie, jak i zapisywanie-nakładanie są opisane jako algorytmy do szybkiego konwertowania strumieni danych za pomocą FFT za pomocą jąder filtrów FIR. Jakie są opóźnienia, efektywność obliczeniowa lub różnice w lokalizacji buforowania (itp.), Jeśli występują? A może są takie same?

hotpaw2
źródło

Odpowiedzi:

27

Zasadniczo OS jest nieco bardziej wydajny, ponieważ nie wymaga dodania nakładających się stanów nieustalonych. Możesz jednak użyć OA, jeśli chcesz ponownie użyć FFT z wypełnieniem zerowym zamiast powtarzanych próbek.

Oto krótki przegląd artykułu, który napisałem jakiś czas temu

Szybki splot odnosi się do blokowego zastosowania splotu kołowego do osiągnięcia splotu liniowego. Szybki splot można osiągnąć metodami OA lub OS. System operacyjny jest również znany jako „overlap-scrap”. W filtrowaniu OA każdy blok danych sygnałowych zawiera tylko tyle próbek, ile pozwala na to, aby splot kołowy był równoważny splotowi liniowemu. Blok danych sygnałowych jest wypełniany zerami przed FFT, aby zapobiec odpowiedzi „impulsu filtra” na „zawijanie” końca sekwencji. Filtrowanie OA dodaje transjent wejściowy z jednego bloku z transjentem wejściowym z poprzedniego bloku. W filtrowaniu systemu operacyjnego, pokazanym na rycinie 1, wypełnianie zerami nie jest przeprowadzane na danych wejściowych, dlatego splot kołowy nie jest równoważny splotowi liniowemu. Części, które „zawijają się” są bezużyteczne i odrzucane. Aby to zrekompensować, ostatnia część poprzedniego bloku wejściowego jest używana jako początek następnego bloku. System operacyjny nie wymaga dodawania stanów nieustalonych, dzięki czemu działa szybciej niż OA.

Mark Borgerding
źródło
Świetny artykuł! =)
Phonon
Mogą istnieć pewne optymalizacje w sposobie obliczania DFT nad wypełnioną zerą częścią bufora OA, które dają przewagę metodzie OA. Zależy to od twojego procesora i pakietu FFT. Można również napisać własny algorytm FFT specjalnie dla OA, który uwzględnia zerowanie.
orodbhen 10.10.16
@orodbhen, czy znasz taki pakiet FFT?
Mark Borgerding,
@MarkBorgerding W OpenCV możesz określić liczbę zerowych wierszy, ale jest to specyficzne dla 2D. Jeśli chodzi o domniemane optymalizacje obecne w tym lub innych pakietach FFT, nie wiem. Mogę wymyślić wiele przypadków, w których niestandardowy FFT do wykorzystania rzadkości byłby pomocny, ale sam nie poszedłem tą drogą. Jeszcze nie.
orodbhen
1
Dobrze, że zacytowałeś, ponieważ link jest zepsuty :(
Mehrdad