Lezione (2025-11-27)

Teorema di convoluzione discreto

L’estensione del teorema di convoluzione al dominio discreto non è immediata. Dati un segnale discreto $x[n]$, $n = 1, \ldots, N_x$ e un filtro $h[n]$, $n = 1, \ldots, N_h$. La loro convoluzione sarà:

$$y[n] = x[n] * h[n]$$

Il teorema ci porterebbe a pensare che:

$$Y[k] = X[k]\ H[k] \implies y[n] \trFourierA Y[K]$$

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 $x[n]$ per $h[n]$ (diventano periodiche perchè la DFT è appunto discretizzata).

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

$$y[n] = x[n] \circledast h[n] = \sum_{k = 0}^{N - 1} x[k]\ h[n - k]$$

Date 2 sequenze $x[n]$ e $h[n]$ di lunghezza $N_x$ e $N_h$, il prodotto delle trasformate è la trasformata della convoluzione circolare tra le 2 sequenze:

$$x[n] \circledast h[n] \trFourierA X[k]\ H[k]$$

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 per almeno $N_x + N_h - 1$ (lunghezza della convoluzione lineare).

1. Generiamo 2 sequenze di lunghezza $M > N_x + N_h - 1$ aggiungendo gli zeri alla fine delle sequenze originali.
2. Applichiamo la DFT ad entrambe le sequenze, ottenendo le trasformate di lunghezza $M$.
3. Moltiplichiamo le 2 sequenze.
4. Applichiamo la IDFT e selezioniamo i primi $N_x + N_h - 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à $O(N^2)$.

Un algoritmo più veloce per calcolare la trasformata viene chiamato Fast Fourier Transform (FFT) e riduce la complessità a $O(N\ \fLog{N})$.

Filtri numerici in frequenza

Dato che ora il filtro viene implementato in frequenza, è possibile implementare filtri IIR (a risposta impulsiva infinita) che non hanno problemi legati alla lunghezza del kernel.

Tuttavia in pratica questi filtri hanno degli effetti indesiderati sul segnale, come la manifestazione di ripple e overshoot (le basse frequenze non sono più compensate dalle armoniche a frequenza maggiore). 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 $N$ dimensioni sarà rappresentato da una funzione:

$$x: \R^N \to \R^K$$

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

Sistemi multi-dimensionali

Un sistema multi-dimensionale riceve in ingresso un segnale $N$-dimensionale e restituisce un segnale $M$-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.

$$y(v_1, \ldots, v_N) = x(v_1, \ldots, v_N) * h(v_1, \ldots, v_N) = \int_{\lambda_1 = -\infty}^{+\infty} \dots \int_{\lambda_N = -\infty}^{+\infty} x(\lambda_1, \ldots, \lambda_N)\ h(v_1 - \lambda_1, \ldots, v_N - \lambda_N)\ \partial \lambda_N \dots \partial \lambda_1$$

Quindi il concetto rimane lo stesso: per ogni asse ribalto la risposta impulsiva e poi faccio scorrere il filtro su tutti i punti dello spazio, poi moltiplico e integro su tutte le dimensioni.

Trasformata di Fourier multi-dimensionale

Dato un segnale $x(v_1, \ldots, v_N)$, la sua FT sarà:

$$X(f_1, \ldots, f_N) = \int_{-\infty}^{+\infty} \dots \int_{-\infty}^{+\infty} x(v_1, \ldots, v_N)\ e^{- j 2 \pi (f_1\ v_1 + \dots + f_N\ v_N)}\ df_1 \dots df_N$$

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 sta al centro (all’intersezione con gli assi).