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

v zpracování signálu, metoda překrytí – přidání je efektivní způsob hodnocení diskrétních konvoluce velmi dlouhého signálu ${displaystyle x [n]}$ s konečná impulzní odezva (FIR) filtr ${displaystyle h [n]}$ :

Obr. 1: Sekvence 5 grafů zobrazuje jeden cyklus algoritmu konvoluce Overlap-add. 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 pádu 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ů.

{displaystyle y [n] = x [n] * h [n] riangleq součet _ {m = -infty} ^ {infty} h [m] cdot x [nm] = součet _ {m = 1} ^ {M} h [m] cdot x [nm],}

(Rovnice 1)

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

Koncept spočívá v rozdělení problému do několika závinů h[n] s krátkými segmenty ${displaystyle x [n]}$ :

{displaystyle x_ {k} [n] riangleq {egin {cases} x [n + kL], & n = 1,2, ldots, L 0, & {ext {jinak}}, konec {případů}}}

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

{displaystyle x [n] = součet _ {k} x_ {k} [n-kL] ,,}

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

{displaystyle {egin {aligned} y [n] = left (sum _ {k} x_ {k} [n-kL] ight) * h [n] & = sum _ {k} left (x_ {k} [n -kL] * h [n] ight) & = součet _ {k} y_ {k} [n-kL], konec {zarovnáno}}}

kde lineární konvoluce ${displaystyle y_ {k} [n] riangleq x_ {k} [n] * h [n],}$ je mimo region nula [1, L + M − 1]. A pro jakýkoli parametr ${displaystyle Ngeq L + M-1 ,,}$ ^[A] je ekvivalentní s N-směřovat kruhová konvoluce z ${displaystyle x_ {k} [n],}$ s ${displaystyle h [n],}$ v region [1, N]. Výhodou je, že kruhovou konvoluci lze vypočítat efektivněji než lineární konvoluci, podle věta o kruhové konvoluci:

{displaystyle y_ {k} [n] = scriptstyle {ext {IDFT}} _ {N} displaystyle (scriptstyle {ext {DFT}} _ {N} displaystyle (x_ {k} [n]) cdot scriptstyle {ext {DFT }} _ {N} displaystyle (h [n])),}

(Rovnice 2)

kde:

DFT_N a IDFT_N odkazovat na Diskrétní Fourierova transformace a jeho inverzní, vyhodnoceno N diskrétní body a
$L$ se obvykle volí tak, že $N = L + M-1$ je celočíselná síla 2 a transformace jsou implementovány pomocí FFT algoritmus, pro efektivitu.

Pseudo kód

Toto je a pseudo kód algoritmu:

(Algoritmus přidání překrytí pro lineární konvoluci)h = FIR_impulse_responseM = délka (h) Nx = délka (x) N = 8 × M (pro lepší výběr viz následující část)step_size = N - (M-1) H = DFT (h, N) poloha = 0y (1: Nx + M-1) = 0zatímco pozice + velikost_kroku ≤ Nx dělat    y (pozice + (1: N)) = y (pozice + (1: N)) + IDFT (DFT (x (pozice + (1: step_size)), N) × H) pozice = pozice + step_sizekonec

Úvahy o účinnosti

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

{displaystyle {frac {Nleft (log _ {2} N + 1ight)} {N-M + 1}}}

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

{displaystyle {frac {N (log _ {2} (N) +1)} {N-M + 1}}.,}

(Rovnice 3)

Například když M= 201 a N=1024, Rovnice 3 se rovná 13,67, zatímco přímé hodnocení Rovnice 1 by vyžadovalo až 201 komplexních multiplikací na výstupní vzorek, nejhorší by bylo, kdyby oba X a h mají komplexní hodnotu. Všimněte si také, že pro všechny dané M, Rovnice 3 má minimum s ohledem na N. Obrázek 2 je graf hodnot N, které se minimalizují Rovnice 3 pro rozsah délek filtrů (M).

Namísto Rovnice 1, můžeme také zvážit podání žádosti Rovnice 2 do dlouhé sekvence délky ${displaystyle N_ {x}}$ Vzorky. Celkový počet komplexních multiplikací by byl:

{displaystyle N_ {x} cdot (log _ {2} (N_ {x}) + 1).}

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

{displaystyle N_ {x} cdot (log _ {2} (N) +1) cdot {frac {N} {N-M + 1}}.}

Proto náklady měřítka metody překrytí – přidání je téměř stejné ${displaystyle Oleft (N_ {x} přihlásit _ {2} noc)}$ zatímco cena jedné velké kruhové konvoluce je téměř ${displaystyle Oleft (N_ {x} log _ {2} N_ {x} ight)}$ . 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élka filtru N_h.

Viz také

Metoda překrytí – uložení

Poznámky

^ Tato podmínka znamená, že: ${displaystyle x_ {k}}$ segment má alespoň M-1 připojené nuly, které zabraňují kruhovému překrývání přechodových přechodů výstupu a pádu.
^ Cooley – Tukey FFT algoritmus pro N = 2^k potřeby (N / 2) log₂(N) - viz FFT - definice a rychlost

Reference

^ Rabiner, Lawrence R .; Gold, Bernard (1975). „2,25“. Teorie a aplikace číslicového zpracování signálu. Englewood Cliffs, N.J .: Prentice-Hall. str.63–65. ISBN 0-13-914101-4.

Další čtení

Oppenheim, Alan V .; Schafer, Ronald W. (1975). Zpracování digitálních signálů. Englewood Cliffs, N.J .: Prentice-Hall. ISBN 0-13-214635-5.
Hayes, M. Horace (1999). Zpracování digitálních signálů. Schaumova obrysová řada. New York: McGraw Hill. ISBN 0-07-027389-8.

externí odkazy

[2] Tato podmínka znamená, že: ${displaystyle x_ {k}}$ segment má alespoň M-1 připojené nuly, které zabraňují kruhovému překrývání přechodových přechodů výstupu a pádu.

[3] Cooley – Tukey FFT algoritmus pro N = 2^k potřeby (N / 2) log₂(N) - viz FFT - definice a rychlost

[Rabiner-1] Rabiner, Lawrence R .; Gold, Bernard (1975). „2,25“. Teorie a aplikace číslicového zpracování signálu. Englewood Cliffs, N.J .: Prentice-Hall. str.63–65. ISBN 0-13-914101-4.

[1]

[A]

[B]