Konvoluce: co dělá každá lineární soustava
Pošli do soustavy jediný impuls a zaznamenej, co vyleze. Ten záznam se jmenuje impulsní odezva a — pokud je soustava lineární a časově neproměnná — popisuje ji úplně. Nic dalšího o ní není potřeba vědět.
Důvod je jednoduchý: každý signál je posloupnost impulsů různé velikosti. Soustava na každý odpoví svou odezvou, a protože je lineární, odpovědi se sečtou. Tomu sčítání se říká konvoluce.
- x[n] a h[n]
Vlevo vstup, vpravo to, co soustava udělá s jediným impulsem. Ta druhá věc soustavu úplně popisuje — nic víc o ní není potřeba vědět.
- h[k] → h[n − k]
Impulsní odezva se zrcadlově otočí a přiloží k signálu v místě n. To otočení není libovůle — plyne z toho, že dřívější vstup ovlivňuje pozdější výstup, ne naopak.
- y[n] = Σₖ x[k]·h[n−k]
Součin překryvu, sečtený. Jedno číslo výstupu. Pak se posune o krok a celé se to opakuje — to je konvoluce, a je to všechno, co lineární soustava dělá.
- N · M operací
Pro každý výstupní vzorek se projde celá odezva. Milion vzorků a filtr o tisíci koeficientech dá miliardu operací.
- x ∗ h ⟷ X · H
Konvoluce v čase je obyčejné násobení ve frekvenci. Takže: transformuj, vynásob po koších, transformuj zpět. Z N·M se stane N·log N — a to je důvod, proč se FFT používá i tam, kde nikoho spektrum nezajímá.
Proč se odezva otáčí. To zrcadlové otočení překvapí každého. Plyne z toho, že vstup před chvílí ovlivňuje výstup teď — takže když se dívám na výstup v čase n, nejstarší vstup je nejdál a prošel největší částí odezvy. Kontrola, která to potvrdí: konvoluce s posunutým Diracovým impulsem signál jen posune a nic jiného neudělá. Testy to ověřují na 1e-15.
Konvoluční věta
Přímý výpočet stojí N·M operací. Pro milion vzorků a filtr o tisíci koeficientech to je miliarda. Jenže:
Konvoluce v čase odpovídá obyčejnému násobení po koších ve frekvenci. Takže: transformuj oba signály, vynásob je, transformuj zpět. N·M se změní na N·log N.
To je druhý a možná důležitější důvod, proč FFT existuje: používá se i tam, kde o spektrum vůbec nejde. Filtrování dlouhého záznamu, násobení velkých čísel, korelace — všude se to jde přes frekvenci jen kvůli rychlosti.
Past, která vyrobí věrohodně vypadající nesmysl. Transformace předpokládá periodické opakování, takže násobení spekter dá cyklickou konvoluci: co přeteče na konci, obtočí se na začátek. Výsledek vypadá skoro správně a má pokažené konce. Řešení je doplnit oba signály nulami alespoň na délku N + M − 1 — solver v téhle labce to dělá a testy porovnávají obě cesty na 20 náhodných dvojicích (shoda 2,2·10⁻¹⁵).
A ještě jedna kontrola, která chytá překlepy v indexech. Konvoluce M a N vzorků má vždycky přesně M + N − 1 vzorků. Kdo dostane N, uřízl si doběh; kdo dostane M + N, má chybu o jedna. Ani jedno se samo neohlásí, takže to hlídá test.