Proč se v DSP používá kruhová konvoluce? Proč ne lineární konvoluce?
On 29 listopadu, 2020 by admin-
Proč používáme v DSP kruhovou konvoluci?
-
Jaký je hlavní pádný důvod pro jeho použití v digitálním zpracování?
-
Proč koncept kruhového konvoluce přichází častěji než lineární konvoluce?
Komentáře
- všimnete si, že všechny vaše odpovědi obsahují zmínku diskrétní Fourierovy transformace, která je nejúčinněji implementována pomocí FFT. DFT neodmyslitelně periodicky rozšiřuje sekvence konečné délky, které jsou jí předávány (což je kruhové). kruhová konvoluce je zřídka cílem . obvykle lineární konvoluce je cíl. ale když vynásobíme DFT ‚ s $ X [k] $ a $ H [k] $ společně, odpovídá to kruhové konvoluci ze dvou periodicky prodloužených sekvencí byly $ x [n] $ a $ h [n] $ předány DFT. problémem je pak nějak to v lineární konvoluci.
Odpověď
Vzhledem k diskrétnímu časovému systému LTI s impulzní odezvou $ h [n] $ , lze vypočítat jeho odpověď na jakýkoli vstup $ x [n] $ pomocí convolution sum: $$ y [n] = x [n] \ star h [n] = \ sum_ {k = – \ infty} ^ {\ infty} {h [k] x [nk]} \ tag {1} $$
Bez dalšího je výše uvedená definice pro lineární konvoluce (aperiodická konvoluce) mezi $ h [n] $ a $ x [n] $ , což jsou neperiodické diskrétní sekvence s možná nekonečnou délkou, pokud není uvedeno jinak. To se liší od kruhové konvoluce , která je mezi dvěma periodickými sekvencemi období $ N $ a počítáno za jediné období.
Můžete vypočítat lineární konvoluce v časové doméně podle rovnice 1 nebo ve frekvenční doméně pomocí následující vlastnosti DTFT (diskrétní Fourierova transformace): $$ y [n] = x [n] \ star h [n] \ implikuje Y (e ^ {j \ omega}) = X (e ^ {j \ omega}) H (e ^ {j \ omega}) \ tag {2} $$
DTFT přirozeně souvisí s lineární konvolucí, protože se zabývá teoreticky existujícími neperiodickými sekvencemi, které mohou sahat od $ – \ infty $ do $ \ infty $ odrážející se v mezích určujícího součtu: $$ X (e ^ {j \ omega}) = \ sum_ {n = – \ infty} ^ {\ infty} x [n] e ^ {- j \ omega n} \ tag {3} $$
Když chcete provést výpočet ručně pomocí symbolických výrazů pro signály, jako je $ x [n] = a ^ nu [n] $ a $ h [n] = b ^ nu [n] $ , můžete vypočítat výsledky v časové nebo frekvenční doméně, jak je uvedeno výše.
Také když chcete vypočítat stejný výsledek pomocí počítače, můžete použít přístup v časové doméně založený na rekurzi LCCDE (pro systémy IIR) nebo přímém konečném konvolučním součtu (pro systémy FIR), ALE přístup ve frekvenční doméně nebude pracovat s DTFT; protože se jedná hlavně o nástroj používaný k vývoji matematiky teorie systémů & a není vhodný pro digitální počítač implementace, protože její proměnná $ \ omega $ je skutečný nepřetržitý number.
Místo toho se používá DFT (diskrétní Fourierova transformace) definovaná jako $$ X [k] = X (e ^ {j \ omega}) | _ {\ omega = \ frac {2 \ pi k} {N}} \ tag {4} $$
kde $ k = 0,1, …, N-1 $ a $ N $ je délka DFT, která se poté nazývá jako N-point DFT signálu $ x [n] $ .
Rovnice 4 znamená, že sekvence DFT $ X [k] $ se získá jako jednotné vzorky DTFT $ X (e ^ {j \ omega}) $ , což je periodická funkce, proto DFT $ X [k] $ je také periodické, ale uvažujeme pouze jeho první období od $ k = 0 $ do $ N-1 $ .
Vzhledem k tomu, že sekvence DFT jsou ze své podstaty periodické, pak jejich konvoluce budou také periodické (kruhové).Zatímco lineární konvoluce mezi neperiodickými signály $ x [n] $ a $ y [n] $ je implikováno výrazem I-DTFT $$ y [n] = \ mathcal {I-DTFT} \ {X (e ^ {j \ omega}) H (e ^ {j \ omega}) \} $$ místo toho kruhová konvoluce mezi dvěma periodickými sekvencemi je implikována výrazem I-DFT $$ \ tilde {y} [n] = \ mathcal { I-DFT} \ {X [k] H [k] \} $$
Takže vzhledem k tomu, že chceme vypočítat lineární konvoluci mezi dvěma neperiodickými sekvencemi $ x [n] $ a $ h [n] $ délek $ L_x $ respektive $ L_h $ , využívající frekvenční doménu svými $ N $ bodovými DFT, $ X [k] $ a $ H [k] $ , ve skutečnosti musíme vypočítat kruhovou konvoluci mezi periodickými rozšířeními signálů $ \ tilde {x} [n] $ a $ \ tilde {h} [n] $ období $ N $ .
Klíčem je výběr správné délky $ N $ DFT, která musí být dostatečně dlouhá, aby se zabránilo jakékoli časové doméně aliasing sekvence $ \ tilde {y} [n] $ , vráceno výpočtem IDFT: $$ \ tilde {y} [n] = \ sum_ {r = – \ infty} ^ {\ infty} y [n-rN] \ tag {5 } $$
kde $ y [n] $ je výsledkem lineární konvoluce, která by byla vrácena teoretickou inverzí DTFT a $ \ tilde {y} [n] $ je periodický výsledek periodické (kruhové) konvoluce implikované inverzní DFT.
Upozorňujeme, že pokud má některý ze signálů nekonečnou délku, pak to
NENÍ možné vypočítat jejich lineární konvoluci pomocí přístupu DFT, protože $ N $ by šlo do nekonečna, prakticky nemožné. Implementace lineární konvoluce pomocí DFT má potom následující kroky:
-
Vyberte N podle následujících kritérií: $$ N \ geq L_x + L_h -1 $$ , který zaručuje aliasovou rekonstrukci inverzního signálu $ y [n] $ z jeho DFT $ Y [k] $ vypočítané kruhové konvoluce pomocí $ X [k] H [k] $ .
-
Vypočítat DFT N-bodu $ X [k] $ a $ H [k] $ z $ x [n] $ a $ h [n] $ .
-
Vypočítat $ Y [k] = X [k ] H [k] $
-
Vypočítat inverzní D-bod NFT $ Y [k] $ produkovat výstup $ y [n] $
odpověď
Odpovědi na vaše otázky:
- Proč používáme v DSP kruhovou konvoluci?
V DSP se běžně zabýváme diskrétními sekvencemi konečné délky (i když je studovaný signál nekonečný, můžeme analyzovat pouze jeho konečnou část najednou ). Pokud jde o zpracování signálu, musí být způsob jeho zpracování implementovatelný v diskrétním logickém zařízení (konkrétně zařízení, které nemůže ukládat spojité hodnoty, protože tyto hodnoty jsou nekonečné a má omezené množství paměti, úložiště atd.). To vysvětluje, proč nelze v hardwaru implementovat diskrétní časově Fourierovu transformaci (DTFT), která transformuje diskrétní časovou sekvenci na spojitou frekvenční sekvenci. Lineární konvoluce v čase je ekvivalentní násobení dvou sekvencí DTFT, ale protože DTFT nelze implementovat v hardwaru, není to způsob, jak získat lineární konvoluci. Diskrétní Fourierova transformace (DFT) na druhé straně transformuje diskrétní časovou sekvenci na diskrétní frekvenční sekvenci a toto umožňuje její implementaci v hardware. Přesto vynásobení dvou sekvencí DFT je v zásadě ekvivalentní kruhové konvoluci (lineární konvoluce může být také získána, pokud jsou časové sekvence předem vyplněny dostatečnými nulami, viz vysvětlení níže).Důvod, proč násobení dvou sekvencí DFT je ekvivalentní kruhové a ne lineární konvoluci, pochází ze skutečnosti, že DFT pro sekvenci konečné časové délky je ekvivalentní diskrétní Fourierově řadě (DFS) téže stejné sekvence konečné konečné délky periodicky prodloužené (zřetězení posloupnost konečné časové délky nekonečně v časové ose) převzatá za jedno období. DFS je také periodický ve frekvenční oblasti, takže lineární konvoluce zde neplatí (viz 8.2.5 a 8.6.5 Oppenheimova diskrétního zpracování časového signálu, 3. vydání)
- Jaký je hlavní pádný důvod pro jeho použití v digitálním zpracování?
Získává se multiplikací DFT a DFT se snadno implementuje do hardwaru. Navíc existují velmi účinné algoritmy, jako je FFT, pro výpočet DFT
- Proč koncept kruhové konvoluce přichází častěji než lineární konvoluce?
To záleží na aplikaci. Kruhová konvoluce může také vést k lineární konvoluci. Řekněme například pracujeme se signálem A délky N a signálem B také délky N (lze to udělat i pro různé délky). Kruhová konvoluce bude mít délku N. Aby bylo možné získat lineární konvoluci, musí být obě A a B vyloženy nulami, dokud nedosáhnou délky alespoň 2 * N – 1. Poté aplikujte DFT na oba, vynásobte je a aplikujte inverzní DFT vám dá lineární konvoluci
Odpověď
Tady je trochu intuice:
Když zabývat se signály digitálně, vždy jednáte s konečným signálem. Je to proto, že můžete zpracovávat pouze na konečné množství datových bodů.
Problém však je, že když provádíte transformace do frekvenční domény pomocí DFT, podle definice nemůže být signál konečný. Proto při provádění operace DFT existuje implicitní změna vašeho signálu od toho, aby byl konečný, aby byl periodický, i když váš signál není periodický.
Toto periodicita signálu vede k potřebě kruhového použití konvoluce.
Odpověď
DFT / FFT je užitečné výpočetní „kladivo“, ale všechny jeho transformační základní vektory jsou kruhové (celé číslo periodické) v cloně a lze je nekonečně rozšiřovat jako periodické funkce, které si někteří uživatelé pletou s povahou jejich vstupních dat.
Pokud vynulujete pad na dostatečné množství, kruhová konvoluce vytvoří stejný výsledek jako lineární konvoluce, ale za mírně vyšší výpočetní cenu než kruhová.
Napsat komentář