Metoda překrývání - uložení - Overlap–save method

Při zpracování signálu je překrytí – uložení tradiční název pro účinný způsob vyhodnocení diskrétní konvoluce mezi velmi dlouhým signálem a filtrem FIR ( konečná impulsní odezva ) : ${\ displaystyle x [n]}$ ${\ Displaystyle h [n]}$

Obr. 1: Sekvence čtyř grafů zobrazuje jeden cyklus algoritmu konvoluce překrývání - uložení. 1. graf je dlouhá sekvence dat, která mají být zpracována pomocí nízkoprůchodového FIR filtru. Druhý graf je jeden segment dat, která mají být zpracována po částech. Třetí graf je filtrovaný segment s použitelnou částí červeně. 4. graf ukazuje filtrovaný segment připojený k výstupnímu proudu. Filtr FIR je dolní propust v boxu s M = 16 vzorků, délka segmentů je L = 100 vzorků a překrytí je 15 vzorků.

{\ Displaystyle y [n] = x [n]*h [n] \ \ triangleq \ \ sum _ {m =-\ infty}^{\ infty} h [m] \ cdot x [nm] = \ sum _ {m = 1}^{M} h [m] \ cdot x [nm],}

( Rovnice 1 )

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

Cílem je vypočítat krátké segmenty y [ n ] libovolné délky L a spojit segmenty dohromady. Zvažte segment, který začíná n = kL + M , pro jakékoli celé číslo k , a definujte :

{\ Displaystyle x_ {k} [n] \ \ triangleq {\ begin {cases} x [n+kL], & 1 \ leq n \ leq L+M-1 \\ 0, & {\ textrm {else}}. \ end {cases}}}

{\ Displaystyle y_ {k} [n] \ \ triangleq \ x_ {k} [n]*h [n] = \ sum _ {m = 1}^{M} h [m] \ cdot x_ {k} [ nm].}

Potom pro kL + M ≤ n ≤ kL + L + M - 1 a ekvivalentně M ≤ n - kL ≤ L + M - 1 můžeme napsat :

{\ Displaystyle y [n] = \ sum _ {m = 1}^{M} h [m] \ cdot x_ {k} [n-kL-m] \ \ \ triangleq \ \ y_ {k} [n- kL].}

Substitucí $j ≜ n-kL$ je úkol redukován na výpočet $y k (j)$ , pro M ≤ $j$ ≤ L + M -1 . Tyto kroky jsou znázorněny na prvních 3 stopy obrázku 1, kromě toho, že požadovaná část výstup (třetí stopa) odpovídá 1 ≤ $j$ ≤ L .

Pokud periodicky prodlužujeme x _k [ n ] s periodou N ≥ L + M - 1, podle :

{\ Displaystyle x_ {k, N} [n] \ \ triangleq \ \ sum _ {\ ell =-\ infty}^{\ infty} x_ {k} [n- \ ell N],}

se závity a jsou ekvivalentní v regionu M ≤ n ≤ L + M - 1. Je proto postačující spočítat N -bodu kruhový (nebo cyklický) konvoluce ze se v oblasti [1, N ]. Subregion [ M , L + M - 1] je připojen k výstupnímu proudu a ostatní hodnoty jsou zahozeny . Výhodou je, že kruhovou konvoluci lze vypočítat efektivněji než lineární konvoluci, podle věty o kruhové konvoluci : ${\ Displaystyle (x_ {k, N})*h \,}$ ${\ displaystyle x_ {k}*h \,}$ ${\ displaystyle x_ {k} [n] \,}$ ${\ Displaystyle h [n] \,}$

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

( Rovnice 2 )

kde :

DFT _N a IDFT _N odkazují na diskrétní Fourierovu transformaci a její inverzní, vyhodnocené přes N diskrétních bodů, a
$L$ je obvykle zvoleno tak, že $N = L+M-1$ je celočíselná mocnina 2 a transformace jsou pro účinnost implementovány pomocí algoritmu FFT .
Přední a zadní okrajové efekty kruhové konvoluce se překrývají a přidávají a následně zahodí.

Pseudo kód

(Overlap-save algorithm for linear convolution)
h = FIR_impulse_response
M = length(h)
overlap = M − 1
N = 8 × overlap    (see next section for a better choice)
step_size = N − overlap
H = DFT(h, N)
position = 0

while position + N ≤ length(x)
    yt = IDFT(DFT(x(position+(1:N))) × H)
    y(position+(1:step_size)) = yt(M : N)    (discard M−1 y-values)
    position = position + step_size
end

Úvahy o účinnosti

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

{\ displaystyle {\ tfrac {N \ left (\ log _ {2} N+1 \ right)} {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, součin 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 přibližně :

{\ 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é vyhodnocení rovnice 1 by vyžadovalo až 201 komplexních násobení 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í Eq.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 násobení by byl: ${\ displaystyle N_ {x}}$

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

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

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

Proto je cena této metody překryv-Save váhy téměř přičemž náklady na jeden velký kruhový konvoluce je téměř . ${\ displaystyle O \ left (N_ {x} \ log _ {2} N \ right)}$ ${\ displaystyle O \ left (N_ {x} \ log _ {2} N_ {x} \ right)}$

Překrývat - zahodit

Overlap – discard a Overlap – scrap jsou méně běžně používané štítky pro stejnou metodu zde popsanou. Tyto štítky je však ve skutečnosti lépe (než překrytí – uložení ) odlišit od překrývání – přidání , protože obě metody „ukládají“, ale pouze jeden zahodí. „Uložit“ pouze odkazuje na skutečnost, že ke zpracování segmentu k + 1 jsou potřeba vstupní (nebo výstupní) vzorky M - 1 ze segmentu k .

Rozšíření překrývání - uložení

Algoritmus překrytí – uložení lze rozšířit o další běžné operace systému:

další kanály IFFT lze zpracovat levněji než první opětovným použitím dopředného FFT
vzorkovací frekvence lze měnit pomocí dopředných a obrácených FFT různých velikostí
frekvenčního překladu (míchání) lze dosáhnout přeskupením frekvenčních přihrádek

Viz také

Metoda překrytí – přidání

Poznámky

Reference

Rabiner, Lawrence R .; Zlato, Bernard (1975). „2,25“. Teorie a aplikace zpracování digitálního signálu . Englewood Cliffs, New Jersey: Prentice-Hall. s. 63–67 . ISBN 0-13-914101-4.
US patent 6898235 , Carlin, Joe; Collins, Terry & Hays, Peter a kol., „Zařízení pro širokopásmové zachycování a zjišťování směru pomocí hyperchannelizace“, publikováno 10. prosince 1999 , vydáno 2005-05-24 , url2 = https://worldwide.espacenet.com/patent /hledání/rodina/034590049/publikace/US6898235B1? q = pn%3DUS6898235

Externí odkazy

Dr. Deepa Kundur, Add Overlap and Overlap Save , University of Toronto

Languages

In other projects