Metoda překrytí – uložení - Overlap–save method
v zpracování signálu, Překrytí - uložení je tradiční název pro efektivní způsob hodnocení diskrétní konvoluce mezi velmi dlouhým signálem a a konečná impulzní odezva (FIR) filtr :

(Rovnice 1)
kde h[m] = 0 pro m mimo region [1, M].
Koncept spočívá ve výpočtu krátkých segmentů y[n] libovolné délky La zřetězit segmenty dohromady. Zvažte segment, který začíná na n = kL + M, pro jakékoli celé číslo ka definovat:
Pak pro kL + M ≤ n ≤ kL + L + M - 1 a ekvivalentně M ≤ n − kL ≤ L + M − 1, můžeme psát:
Se střídánímj ≜ n-kL, úkol je omezen na výpočetní techniku yk(j), pro M ≤ j ≤ L + M − 1. Tyto kroky jsou znázorněny v prvních 3 stopách na obrázku 1, kromě toho, že požadovaná část výstupu (třetí stopa) odpovídá 1 ≤ j ≤ L.[B]
Pokud se pravidelně prodlužujeme Xk[n] s tečkou N ≥ L + M - 1, podle:
závity a jsou v regionu ekvivalentní M ≤ n ≤ L + M - 1. Proto stačí vypočítat N-směřovat kruhová (nebo cyklická) konvoluce z s v regionu [1,N]. Podoblast [M, L + M - 1] je připojen k výstupnímu proudu a ostatní hodnoty jsou zlikvidován. Výhodou je, že kruhovou konvoluci lze vypočítat efektivněji než lineární konvoluci, podle věta o kruhové konvoluci:
(Rovnice 2)
kde:
- DFTN a IDFTN 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á mocnina ze 2 a transformace jsou implementovány pomocí FFT algoritmus, pro efektivitu.
- Účinky úvodní a zadní hrany kruhové konvoluce se překrývají a přidávají,[C] a následně zlikvidován.[D]
Pseudo kód
(Algoritmus pro ukládání překrytí pro lineární konvoluci)h = FIR_impulse_responseM = překrytí délky (h) = M - 1N = 8 × překrytí (pro lepší výběr viz následující část)step_size = N - overlapH = DFT (h, N) position = 0zatímco pozice + N ≤ délka (x) yt = IDFT (DFT (x (pozice + (1: N))) × H) y (pozice + (1: step_size)) = yt (M: N) (zahoďte hodnoty M − 1 y) position = position + step_sizekonec
Úvahy o účinnosti

Když jsou DFT a IDFT implementovány algoritmem FFT, výše uvedený pseudokód vyžaduje asi N (log2(N) + 1) komplexní multiplikace pro FFT, produkt polí a IFFT.[E] Každá iterace vytváří N-M + 1 výstupní vzorky, takže počet komplexních násobení na výstupní vzorek je asi:
(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 Vzorky. Celkový počet komplexních multiplikací by byl:
Srovnatelně je počet složitých násobení požadovaných algoritmem pseudokódu:
Proto náklady metody překrytí – uložení je téměř stejné zatímco cena jedné velké kruhové konvoluce je téměř .
Překrytí – zahození
Překrytí – zahození[1] a Překrytí - šrot[2] jsou méně často používané štítky pro stejnou metodu popsanou zde. Tyto štítky jsou však ve skutečnosti lepší (než překrytí - uložit) odlišit od překrytí - přidat, protože oba metody „uložit“, ale pouze jedna se zahodí. „Uložit“ pouze odkazuje na skutečnost, že M - 1 vstupní (nebo výstupní) vzorek ze segmentu k jsou potřebné ke zpracování segmentu k + 1.
Rozšíření překrytí - uložení
Algoritmus překrytí a uložení lze rozšířit o další běžné operace systému:[F][3]
- další kanály IFFT lze zpracovat levněji než první opětovným použitím dopředného FFT
- vzorkovací frekvence lze změnit pomocí různě velkých dopředných a inverzních FFT
- frekvenční překlad (míchání) lze dosáhnout přeuspořádáním frekvenčních košů
Viz také
Poznámky
- ^ Rabiner a zlato, Obr. 2.35, čtvrtá stopa.
- ^ Posun nežádoucích okrajových efektů na poslední výstupy M-1 je potenciální výhoda za běhu, protože IDFT lze vypočítat v vyrovnávací paměti, místo aby byly počítány a kopírovány. Potom mohou být hranové efekty přepsány dalším IDFT. Následující poznámka pod čarou vysvětluje, jak se posun provádí, a to časovým posunem impulzní odezvy.
- ^ Nesmí být zaměňována s Metoda překrytí a přidání, který zachovává samostatné efekty náběžné a koncové hrany.
- ^ Okrajové efekty lze přesouvat z přední do zadní části výstupu IDFT s což znamená, že vyrovnávací paměť délky N je kruhově posunutý (otočeno) vzorky M-1. Prvek h (M) je tedy na n = 1. Prvek h (M-1) je na n = N. h (M-2) je na n = N-l. Atd.
- ^ Cooley – Tukey FFT algoritmus pro N = 2k potřeby (N / 2) log2(N) - viz FFT - definice a rychlost
- ^ Carlin a kol. 1999, str. 31, sl. 20.
Reference
- ^ Harris, F.J. (1987). D.F. Elliot (ed.). Příručka pro zpracování digitálního signálu. San Diego: Academic Press. 633–699. ISBN 0122370759.
- ^ Frerking, Marvin (1994). Digitální zpracování signálu v komunikačních systémech. New York: Van Nostrand Reinhold. ISBN 0442016166.
- ^ Borgerding, Mark (2006). „Proměna překrytí - uložení do vícepásmové směšovací banky s převzorkováním (PDF). IEEE Signal Processing Magazine (Březen 2006): 158–161.
- 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–67. ISBN 0-13-914101-4.
- US patent 6898235, Carlin, Joe; Terry Collins a Peter Hays a kol., „Širokopásmové komunikační zachycení a zařízení k určování směru pomocí hyperkanalizace“, publikováno 10. 12. 1999, vydáno 24. května 2005, url2 =https://worldwide.espacenet.com/patent/search/family/034590049/publication/US6898235B1?q=pn%3DUS6898235