Perché viene utilizzata la convoluzione circolare in DSP? Perché non convoluzione lineare?
Su Novembre 29, 2020 da admin-
Perché utilizziamo la convoluzione circolare in DSP?
-
Qual è il motivo principale e solido per il suo utilizzo nellelaborazione digitale?
-
Perché il concetto di circolare la convoluzione viene più spesso della convoluzione lineare?
Commenti
- noterai che tutte le tue risposte includono una menzione della trasformata discreta di Fourier che è implementata in modo più efficiente con la FFT. la DFT estende intrinsecamente periodicamente le sequenze di lunghezza finita passate ad essa (che è circolare). la convoluzione circolare è raramente l obiettivo . solitamente convoluzione lineare è lobiettivo. ma quando si moltiplica la DFT ‘ s $ X [k] $ e $ H [k] $ insieme, ciò corrisponde alla convoluzione circolare delle due sequenze periodicamente estese, $ x [n] $ e $ h [n] $ passate ai DFT. il problema è quindi in qualche modo trasformarlo in una convoluzione lineare.
Risposta
Dato un sistema LTI a tempo discreto con risposta allimpulso $ h [n] $ , si può calcolare la sua risposta a qualsiasi input $ x [n] $ da un convoluzione sum: $$ y [n] = x [n] \ star h [n] = \ sum_ {k = – \ infty} ^ {\ infty} {h [k] x [nk]} \ tag {1} $$
Senza ulteriori informazioni, la definizione di cui sopra è per la convoluzione lineare (convoluzione aperiodica) tra $ h [n] $ e $ x [n] $ , che sono sequenze aperiodiche a tempo discreto di lunghezza possibilmente infinita, se non diversamente specificato. Questo è diverso da una convoluzione circolare che si trova tra due sequenze periodiche di periodo $ N $ e calcolato su un singolo periodo.
Puoi calcolare lineare convoluzione nel dominio del tempo secondo lEq.1, o nel dominio della frequenza utilizzando la seguente proprietà DTFT (trasformata di Fourier a tempo discreto): $$ y [n] = x [n] \ star h [n] \ implica Y (e ^ {j \ omega}) = X (e ^ {j \ omega}) H (e ^ {j \ omega}) \ tag {2} $$
DTFT è naturalmente correlato alla convoluzione lineare, poiché si occupa di sequenze aperiodiche teoricamente esistenti che possono estendersi da $ – \ infty $ a $ \ infty $ riflesso nei suoi limiti della somma di definizione: $$ X (e ^ {j \ omega}) = \ sum_ {n = – \ infty} ^ {\ infty} x [n] e ^ {- j \ omega n} \ tag {3} $$
Quando vuoi fare un calcolo a mano, utilizzando espressioni simboliche per segnali, come $ x [n] = a ^ nu [n] $ e $ h [n] = b ^ nu [n] $ , puoi calcolare i risultati nei domini del tempo o della frequenza come descritto sopra.
Inoltre, quando si desidera calcolare lo stesso risultato utilizzando un computer, è possibile utilizzare lapproccio nel dominio del tempo basato su una ricorsione LCCDE (per sistemi IIR) o una somma di convoluzione finita diretta (per sistemi FIR), MA lapproccio nel dominio della frequenza non funzionerà con DTFT; poiché è principalmente uno strumento utilizzato per sviluppare la matematica dei segnali & teoria dei sistemi e non è adatto per computer digitali implementazioni, poiché la sua variabile $ \ omega $ è un vero continuo numero.
Ciò che viene utilizzato è invece la DFT (trasformata di Fourier discreta) definita come $$ X [k] = X (e ^ {j \ omega}) | _ {\ omega = \ frac {2 \ pi k} {N}} \ tag {4} $$
dove $ k = 0,1, …, N-1 $ e $ N $ è la lunghezza del DFT, che” viene quindi chiamato come N punti DFT del segnale $ x [n] $ .
LEq.4 implica che la sequenza DFT $ X [k] $ sia ottenuta come campioni uniformi del DTFT $ X (e ^ {j \ omega}) $ , che è una funzione periodica, quindi DFT $ X [k] $ è anche periodico ma consideriamo solo il suo primo periodo da $ k = 0 $ a $ N-1 $ .
Poiché le sequenze DFT sono intrinsecamente periodiche, anche le loro convoluzioni saranno periodiche (circolari).Pertanto, mentre una convoluzione lineare tra segnali aperiodici $ x [n] $ e $ y [n] $ è implicito nellespressione I-DTFT $$ y [n] = \ mathcal {I-DTFT} \ {X (e ^ {j \ omega}) H (e ^ {j \ omega}) \} $$ invece un la convoluzione circolare tra due sequenze periodiche è implicita nellespressione I-DFT $$ \ tilde {y} [n] = \ mathcal { I-DFT} \ {X [k] H [k] \} $$
Quindi, dato che vogliamo calcolare una convoluzione lineare tra due sequenze aperiodiche $ x [n] $ e $ h [n] $ di lunghezze $ L_x $ e $ L_h $ rispettivamente, utilizzando il dominio della frequenza dai loro $ N $ punti DFT, $ X [k] $ e $ H [k] $ , dobbiamo effettivamente calcolare una convoluzione circolare tra le estensioni periodiche dei segnali $ \ tilde {x} [n] $ e $ \ tilde {h} [n] $ di periodi $ N $ .
La chiave sta nello scegliere una lunghezza appropriata $ N $ delle DFT, che deve essere abbastanza lunga da evitare qualsiasi dominio del tempo aliasing della sequenza $ \ tilde {y} [n] $ , restituita dal calcolo IDFT: $$ \ tilde {y} [n] = \ sum_ {r = – \ infty} ^ {\ infty} y [n-rN] \ tag {5 } $$
dove $ y [n] $ è il risultato della convoluzione lineare che sarebbe restituita dallinverso teorico DTFT e $ \ tilde {y} [n] $ è il risultato periodico della convoluzione periodica (circolare) implicita dalla DFT inversa.
Tieni presente che se uno qualsiasi dei segnali ha una lunghezza infinita, “s NON possibile per calcolare la loro convoluzione lineare utilizzando lapproccio DFT, poiché $ N $ andrebbe allinfinito, praticamente impossibile. Limplementazione di una convoluzione lineare tramite DFT ha quindi i seguenti passaggi:
-
Scegli N in base ai seguenti criteri: $$ N \ geq L_x + L_h -1 $$ che garantisce una ricostruzione priva di alias del segnale inverso $ y [n] $ dalla sua DFT $ Y [k] $ della convoluzione circolare calcolata tramite $ X [k] H [k] $ .
-
Calcola DFT a N punti $ X [k] $ e $ H [k] $ di $ x [n] $ e $ h [n] $ .
-
Calcola $ Y [k] = X [k ] H [k] $
-
Calcola DFT inverso N punti di $ Y [k] $ per produrre loutput $ y [n] $
Risposta
Rispondendo alle tue domande:
- Perché utilizziamo la convoluzione circolare in DSP?
In DSP normalmente ci occupiamo di sequenze discrete di lunghezza finita (anche se il segnale in esame è infinito possiamo analizzarne solo una parte finita alla volta ). Quando si tratta di elaborare un segnale, il modo di elaborarlo deve essere implementabile in un dispositivo logico discreto (vale a dire un dispositivo che non può memorizzare valori continui perché questi valori sono infiniti e ha una quantità finita di memoria, archiviazione, ecc.). Questo spiega perché la Trasformata di Fourier a tempo discreto (DTFT) che trasforma una sequenza temporale discreta in una sequenza di frequenza continua non può essere implementata nellhardware. La convoluzione lineare nel tempo è equivalente alla moltiplicazione di 2 sequenze DTFT, ma poiché DTFT non può essere implementata nellhardware, questo non è il modo per ottenere la convoluzione lineare. Trasformata di Fourier discreta (DFT), daltra parte, trasforma una sequenza temporale discreta in una sequenza di frequenza discreta e questo consente di implementarla in Tuttavia, moltiplicare 2 sequenze DFT è equivalente in linea di principio alla convoluzione circolare (la convoluzione lineare può anche essere ottenuta se le sequenze temporali sono state precedentemente riempite con zeri sufficienti, vedere la spiegazione sotto).Il motivo per cui moltiplicare 2 sequenze DFT è equivalente alla convoluzione circolare e non lineare deriva dal fatto che DFT per una sequenza di lunghezza temporale finita è equivalente alla serie di Fourier discreta (DFS) della stessa sequenza di lunghezza temporale finita periodicamente estesa (concatenando il sequenza di lunghezza temporale finita infinitamente nellasse temporale) presa su un periodo. DFS è anche periodico nel dominio della frequenza, quindi la convoluzione lineare non si applica lì (vedere 8.2.5 e 8.6.5 di Oppenheim “s Discrete Time Signal Processing 3a edizione)
- Qual è il motivo principale e solido per il suo utilizzo nellelaborazione digitale?
Si ottiene per moltiplicazione DFT e DFT è facilmente implementabile nellhardware. Inoltre esistono algoritmi molto efficienti come FFT per calcolare la DFT
- Perché il concetto di convoluzione circolare viene più spesso di convoluzione lineare?
Dipende dallapplicazione. La convoluzione circolare può anche produrre la convoluzione lineare. Ad esempio, diciamo stiamo lavorando con il segnale A di lunghezza N e il segnale B anche di lunghezza N (può essere fatto anche per lunghezze diverse). La convoluzione circolare sarà di lunghezza N. Per ottenere la convoluzione lineare sia A che B devono essere riempiti di zeri fino a raggiungere una lunghezza di almeno 2 * N – 1. Quindi applicare il DFT su entrambi, moltiplicandoli e applicando inverso DFT ti darà la convoluzione lineare
Risposta
Ecco “un po di intuizione:
Quando tu trattare i segnali digitalmente, hai sempre a che fare con un segnale finito. Questo perché puoi elaborare solo su una quantità finita di punti dati.
Il problema tuttavia è che quando esegui trasformazioni nel dominio della frequenza usando il DFT, per definizione, un segnale non può essere finito. Pertanto, quando si esegue unoperazione DFT, cè unalterazione implicita del segnale da finito a periodico, anche se il segnale non è periodico.
Questo periodicità del segnale porta alla necessità di utilizzare la convoluzione in modo circolare.
Risposta
La DFT / FFT è un utile “martello” computazionale, ma tutti i suoi vettori base di trasformazione sono circolari (interi periodici) in apertura e possono essere estesi allinfinito come funzioni periodiche, che alcuni utenti confondono con la natura dei loro dati di input.
Se si azzera una quantità sufficiente, la convoluzione circolare produce lo stesso risultato della convoluzione lineare, ma a un costo di calcolo leggermente maggiore rispetto a quella circolare.
Lascia un commento