Metoda překrytí – přidání - Overlap–add method

Při zpracování signálu je způsob přidávání překrývání je účinným způsobem, jak vyhodnotit diskrétní konvoluce velmi dlouhého signálu s konečnou impulzní odezvou (FIR) :

Obr. 1: Sekvence pěti grafů zobrazuje jeden cyklus konvolučního algoritmu překrytí a přidání. První graf je dlouhá sekvence dat, která mají být zpracována pomocí lowpass FIR filtru. Druhý graf je jeden segment dat, která se mají zpracovávat po částech. Třetí graf je filtrovaný segment, včetně přechodových přechodů vzestupu a poklesu filtru. 4. graf ukazuje, kam budou přidána nová data s výsledkem předchozích segmentů. Pátý graf je aktualizovaný výstupní proud. Filtr FIR je nízkoprůchodový vůz s M = 16 vzorků, délka segmentů je L = 100 vzorků a překrytí je 15 vzorků.

 

 

 

 

( Rov. 1 )

kde h [ m ] = 0 pro m mimo oblast [1, M ] .

Koncept spočívá v rozdělení problému na několik konvolucí h [ n ] s krátkými segmenty :

kde L je libovolná délka segmentu. Pak:

a y [ n ] lze zapsat jako součet krátkých závinů:

kde lineární konvoluce je mimo oblast [1, L + M - 1] nula . A pro každý parametr , je ekvivalentní k N -bodu kruhové konvoluce části se v oblasti [1, N ] . Výhodou je, že kruhovou konvoluci lze podle věty o kruhové konvoluci vypočítat efektivněji než lineární konvoluci :

 

 

 

 

( Rov. 2 )

kde :

  • DFT N a IDFT N odkazují na diskrétní Fourierovu transformaci a její inverzi, vyhodnocenou přes N diskrétních bodů a
  • L je obvykle vybráno tak, že N = L + M-1 je celočíselná síla 2 a transformace jsou kvůli účinnosti implementovány pomocí algoritmu FFT .

Pseudo kód

Následuje pseudokód algoritmu:

(Overlap-add algorithm for linear convolution)
h = FIR_impulse_response
M = length(h)
Nx = length(x)
N = 8 × 2^ceiling( log2(M) )     (8 times the smallest power of two bigger than filter length M.  See next section for a slightly better choice.)
step_size = N - (M-1)  (L in the text above)
H = DFT(h, N)
position = 0
y(1 : Nx + M-1) = 0

while position + step_size ≤ Nx do
    y(position+(1:N)) = y(position+(1:N)) + IDFT(DFT(x(position+(1:step_size)), N) × H)
    position = position + step_size
end

Úvahy o účinnosti

Obr. 2: Graf hodnot N (celočíselný výkon 2), které minimalizují nákladovou funkci

Když jsou DFT a IDFT implementovány algoritmem FFT, výše uvedený pseudokód vyžaduje přibližně N (log 2 (N) + 1) komplexní multiplikace pro FFT, produkt polí a IFFT. Každá iterace produkuje výstupní vzorky N-M + 1 , takže počet komplexních násobení na výstupní vzorek je asi :

 

 

 

 

( Rov. 3 )

Například když M = 201 a N = 1024, Eq.3 se rovná 13,67, zatímco přímé vyhodnocení Eq.1 by vyžadovalo až 201 komplexních multiplikací na výstupní vzorek, nejhorší případ je, když jsou x i h komplexně oceněny. Všimněte si také, že pro danou M , Eq.3 má minimální vzhledem k N . Obrázek 2 je graf hodnot N, které minimalizují rovnici 3 pro rozsah délek filtrů (M).

Místo Eq.1 můžeme také zvážit použití Eq.2 na dlouhou sekvenci vzorků délky . Celkový počet komplexních multiplikací by byl:

Srovnatelně je počet složitých násobení požadovaných algoritmem pseudokódu:

Proto je cena metody překrytí a přidání téměř stejná jako cena jedné velké kruhové konvoluce . Tyto dvě metody jsou také porovnány na obrázku 3 vytvořeném simulací Matlab. Obrysy jsou čáry konstantního poměru časů potřebných k provedení obou metod. Když je metoda přidání překrytí rychlejší, poměr překročí 1 a zobrazí se poměry až 3.

Obrázek 3: Zisk metody přidání překrytí ve srovnání s jedinou velkou kruhovou konvolucí. Osy ukazují hodnoty délky signálu N x a délky filtru N h .

Viz také

Poznámky

Reference

Další čtení

  • Oppenheim, Alan V .; Schafer, Ronald W. (1975). Digitální zpracování signálu . Englewood Cliffs, NJ: Prentice-Hall. ISBN   0-13-214635-5 .
  • Hayes, M. Horace (1999). Digitální zpracování signálu . Schaumova osnova. New York: McGraw Hill. ISBN   0-07-027389-8 .

externí odkazy