Convoluzione circolare e segnali multidimensionali

Teorema di convoluzione discreto

L’estensione del teorema di convoluzione al dominio discreto non è immediata. Dati un segnale discreto $𝑥\left[𝑛\right]$, $𝑛=0,\dots ,{𝑁}_{𝑥}-1$ e un filtro $ℎ\left[𝑛\right]$, $𝑛=0,\dots ,{𝑁}_{ℎ}-1$. La loro convoluzione sarà:

$$𝑦\left[𝑛\right]=𝑥\left[𝑛\right]\ast ℎ\left[𝑛\right]$$

Il teorema ci porterebbe a pensare che:

$$𝑌\left[𝑘\right]=𝑋\left[𝑘\right]𝐻\left[𝑘\right]\Rightarrow 𝑦\left[𝑛\right]\stackrel{\mathrm{ℱ︀}}{\leftrightarrow }𝑌\left[𝑘\right]$$

Tuttavia c’è un problema: se le 2 sequenze non hanno la stessa lunghezza, si può eseguire la convoluzione ma non il prodotto.

Una soluzione potrebbe essere quella di portare le 2 sequenze alla stessa lunghezza aggiungendo degli zeri a quella più corta. Però il risultato non è ancora corretto.

Convoluzione circolare

Problema: Eseguire il prodotto in frequenza equivale a convoluire la periodizzazione di $𝑥\left[𝑛\right]$ per $ℎ\left[𝑛\right]$ (diventano periodiche perché la DFT è appunto discretizzata).

Anche prendendo solo i primi $𝑁$ valori, otteniamo comunque un risultato diverso da quello atteso. Il risultato dell’anti-trasformata sarà quindi il risultato di questa operazione, detta convoluzione circolare.

$$𝑦\left[𝑛\right]=𝑥\left[𝑛\right]⊛ℎ\left[𝑛\right]=\sum _{𝑘=0}^{𝑁-1}𝑥\left[𝑘\right]ℎ\left[𝑛-𝑘\right]$$

Date 2 sequenze $𝑥\left[𝑛\right]$ e $ℎ\left[𝑛\right]$ di lunghezza ${𝑁}_{𝑥}$ e ${𝑁}_{ℎ}$, il prodotto delle trasformate è la trasformata della convoluzione circolare tra le 2 sequenze:

$$𝑥\left[𝑛\right]⊛ℎ\left[𝑛\right]\stackrel{\mathrm{ℱ︀}}{\leftrightarrow }𝑋\left[𝑘\right]𝐻\left[𝑘\right]$$

Caution

Questo risultato non ci fornisce la risposta del filtro.

Risposta in frequenza di sistemi discreti

Per far coincidere la convoluzione circolare bisogna evitare il sovrapporsi dei campioni lungo un periodo. Bisogna quindi aggiungere un ulteriore zero padding in entrambe le sequenze, in modo che i campioni delle sequenze originali siano separati da almeno ${𝑁}_{𝑥}+{𝑁}_{ℎ}-1$ (lunghezza della convoluzione lineare).

1. Generiamo 2 sequenze di lunghezza $𝑀\ge {𝑁}_{𝑥}+{𝑁}_{ℎ}-1$ aggiungendo gli zeri alla fine delle sequenze originali.
2. Applichiamo la DFT ad entrambe le sequenze, ottenendo le trasformate di lunghezza $𝑀$.
3. Moltiplichiamo le 2 sequenze.
4. Applichiamo la IDFT e selezioniamo i primi ${𝑁}_{𝑥}+{𝑁}_{ℎ}-1$ campioni.

FFT

Con la convoluzione è possibile calcolare l’uscita di un sistema LTI con minore complessità computazionale. Tuttavia, il calcolo della DFT con la definizione data ha complessità $𝑂\left({𝑁}^2\right)$.

Un algoritmo più veloce per calcolare la trasformata viene chiamato Fast Fourier Transform (FFT) e riduce la complessità a $𝑂\left(𝑁log\left(𝑁\right)\right)$.

Filtri numerici in frequenza

Dato che ora il filtro viene implementato in frequenza, è possibile definire filtri ideali con risposta impulsiva infinita (IIR) specificando direttamente la loro risposta in frequenza sui campioni della DFT, senza dover progettare un kernel a supporto finito come per i filtri FIR. La risposta impulsiva infinita, però, non può essere rappresentata esattamente in un blocco finito: la moltiplicazione in frequenza corrisponde comunque a una convoluzione circolare, quindi il risultato non coincide con la convoluzione lineare.

In pratica questi filtri hanno inoltre effetti indesiderati sul segnale, come la manifestazione di ripple e overshoot in prossimità delle discontinuità: un fronte netto richiede le armoniche ad alta frequenza, che il filtro taglia (fenomeno di Gibbs). Questo fenomeno viene chiamato ringing.

Segnali multi-dimensionali

In natura, molti segnali si muovono su domini spaziali o spazio-temporali. Ciò significa che il valore di un segnale dipende da più di una variabile.

Un segnale multi-dimensionale in $𝑁$ dimensioni sarà rappresentato da una funzione:

$$𝑥:{ℝ}^{𝑁}\to {ℝ}^{𝐾}$$

dove $𝐾$ rappresenta la dimensionalità dei valori assunti dal segnale.

Sistemi multi-dimensionali

Un sistema multi-dimensionale riceve in ingresso un segnale $𝑁$-dimensionale e restituisce un segnale $𝑀$-dimensionale.

D’ora in poi, per semplicità considereremo segnali e sistemi multi-dimensionali che danno un risultato scalare.

Sistemi LDI

Il concetto di sistema LDI è praticamente identico a quello di un sistema LTI, solo che si parla di dominio-invarianza anziché di tempo-invarianza.

Questo significa che il sistema si comporterà allo stesso modo in qualsiasi punto del dominio.

Risposta impulsiva di sistemi LDI

Dato un sistema multi-dimensionale LDI, la risposta sarà sempre data dalla convoluzione tra l’ingresso e la risposta impulsiva.

$$\begin{array}{cc}𝑦\left({𝑣}_1,\dots ,{𝑣}_{𝑁}\right)& =𝑥\left({𝑣}_1,\dots ,{𝑣}_{𝑁}\right)\ast ℎ\left({𝑣}_1,\dots ,{𝑣}_{𝑁}\right)\\ & ={\int }_{{𝜆}_1=-\infty }^{+\infty }\dots {\int }_{{𝜆}_{𝑁}=-\infty }^{+\infty }𝑥\left({𝜆}_1,\dots ,{𝜆}_{𝑁}\right)ℎ\left({𝑣}_1-{𝜆}_1,\dots ,{𝑣}_{𝑁}-{𝜆}_{𝑁}\right)d{𝜆}_{𝑁}\dots d{𝜆}_1\end{array}$$

Quindi il concetto rimane lo stesso: per ogni asse ribaltiamo la risposta impulsiva, facciamo scorrere il filtro su tutti i punti dello spazio e infine moltiplichiamo e integriamo su tutte le dimensioni.

Trasformata di Fourier multi-dimensionale

Dato un segnale $𝑥\left({𝑣}_1,\dots ,{𝑣}_{𝑁}\right)$, la sua FT sarà:

$$𝑋\left({𝑓}_1,\dots ,{𝑓}_{𝑁}\right)={\int }_{-\infty }^{+\infty }\dots {\int }_{-\infty }^{+\infty }𝑥\left({𝑣}_1,\dots ,{𝑣}_{𝑁}\right){𝑒}^{-𝑗2𝜋\left({𝑓}_1{𝑣}_1+\dots +{𝑓}_{𝑁}{𝑣}_{𝑁}\right)}d{𝑣}_1\dots d{𝑣}_{𝑁}$$

L’operazione equivale a trasformare il segnale sequenzialmente su ogni dimensione. Quindi si dimostra facilmente che essa mantiene ed estende tutte le proprietà già viste per la trasformata mono-dimensionale.

Per esempio, la trasformata di un segnale bidimensionale (come un’immagine) è uno spettro bidimensionale dove convenzionalmente la frequenza fondamentale è posta al centro (all’intersezione con gli assi).