Trasformata di Fourier discreta (TFD)

La serie di Fourier (Serie di Fourier - analisi e sintesiUn segnale periodico di periodo $T$ si scrive come somma di esponenziali in relazione armonica, $x(t)=\sum_ka_ke^{jk\omega_0t}$ con $\omega_0=2\pi/T$, e i coefficienti si ottengono per proiezione, $a_k=\frac1T\int_Tx(t)e^{-jk\omega_0t}dt$. L'ortogonalità degli esponenziali dà la formula; la convergenza è in media quadratica (Riesz-Fischer), con il fenomeno di Gibbs nei salti.Serie di Fourier - analisi e sintesi →) scrive un segnale continuo periodico come somma di infinite armoniche. Per un segnale discreto periodico la situazione è più semplice: ci sono solo $N$ armoniche distinte e la serie diventa una somma finita. È la TFD (trasformata di Fourier discreta, in inglese DFT). In pratica si calcola con l'algoritmo FFT (vedi FFT e zero-padding - TF, TFtd e asse delle pulsazioniLa FFT dei campioni di un segnale a durata finita, moltiplicata per il passo $T_c$, approssima la trasformata di Fourier: $X(\omega_k)\approx T_c,\mathtt{fft}(x,M)[k]$ con $\omega_k=\frac{2\pi k}{MT_c}$ (e fattore di fase $e^{-j\omega t_0}$ se l'asse parte da $t_0$). Lo zero-padding ($M>N$) infittisce i punti della stessa TFtd senza aggiungere informazione; la risoluzione dipende dalla durata osservata. Per un segnale reale $|X|$ è simmetrico: il picco in $k$ ha un gemello in $M-k$.FFT e zero-padding - TF, TFtd e asse delle pulsazioni →).

Armoniche a tempo discreto

Sia $x(n)$ periodico di periodo $N$ (intero). Gli esponenziali con lo stesso periodo sono $$e^{j\frac{2\pi}Nkn},\qquad k\in\mathbb Z.$$ Ma nel discreto $e^{j(\omega+2\pi)n}=e^{j\omega n}$ (Segnali periodici, sinusoidi ed esponenziali immaginari puriUn segnale continuo è periodico di periodo T se x(t+T)=x(t); $e^{j2\pi f_0t}$ ha periodo minimo $1/|f_0|$ e una somma di periodici è periodica solo se il rapporto dei periodi è razionale. A tempo discreto $e^{j2\pi\nu n}$ è periodico solo se $\nu$ è razionale, e le pulsazioni che differiscono di $2\pi$ sono lo stesso segnale: ogni sinusoide si riporta alla forma canonica con $\omega\in[0,\pi]$.Segnali periodici, sinusoidi ed esponenziali immaginari puri →): l'armonica $k+N$ coincide con la $k$, perché $e^{j\frac{2\pi}N(k+N)n}=e^{j\frac{2\pi}Nkn}\,e^{j2\pi n}=e^{j\frac{2\pi}Nkn}$. Quindi le armoniche distinte sono solo $N$: $k=0,1,\dots,N-1$ (o equivalentemente $-\frac N2\le k<\frac N2$).

L'ortogonalità vale ancora, con somme al posto di integrali: per $k,m\in\{0,\ldots,N-1\}$ $$\frac1N\sum_{n=0}^{N-1}e^{j\frac{2\pi}N(k-m)n}=\begin{cases}1&k=m\\0&k\neq m\end{cases}$$ (per $k\ne m$ è una somma geometrica di ragione $e^{j2\pi(k-m)/N}\ne1$ e vale $\frac{1-e^{j2\pi(k-m)}}{1-e^{j2\pi(k-m)/N}}=0$).

Definizione

$$\boxed{X(k)=\frac1N\sum_{n=0}^{N-1}x(n)\,e^{-j\frac{2\pi}Nkn}\ \ (\text{analisi}),\qquad x(n)=\sum_{k=0}^{N-1}X(k)\,e^{j\frac{2\pi}Nkn}\ \ (\text{sintesi}).}$$

$X(k)$ è periodico in $k$ di periodo $N$, come $x(n)$ in $n$. Il significato è quello della serie di Fourier: $X(0)=\frac1N\sum x(n)$ è il valor medio; $X(k)$ misura la componente alla pulsazione $\frac{2\pi k}N$ (cioè $k$ cicli ogni $N$ campioni).

Attenzione alle convenzioni. In queste note il fattore $\frac1N$ sta nell'analisi (come nei coefficienti della serie). Le librerie di calcolo (numpy.fft.fft, fft di Matlab) non lo includono: fft(x) restituisce $N\cdot X(k)$. Altri testi mettono $\frac1N$ nella sintesi o $\frac1{\sqrt N}$ in entrambe. Prima di usare una formula si controlla sempre la convenzione.

Versione matriciale

Si raccolgono i campioni in un vettore $\mathbf x=[x(0),\dots,x(N-1)]^T\in\mathbb C^N$ e i coefficienti in $\mathbf X$. La sintesi è un prodotto matrice-vettore $$\mathbf x=F\,\mathbf X,\qquad F_{nk}=e^{j\frac{2\pi}Nnk}.$$ Le colonne di $F$ sono le $N$ armoniche, ortogonali tra loro e di norma $\sqrt N$: $F^HF=N\,I$ (dove $F^H$ è la trasposta coniugata). Quindi $F^{-1}=\frac1NF^H$ e l'analisi è $$\mathbf X=\frac1NF^H\mathbf x.$$ C'è un isomorfismo tra i segnali periodici di periodo $N$ e lo spazio euclideo $\mathbb C^N$: la TFD è un cambio di base (dalla base canonica a quella delle armoniche). Per $N=4$ la matrice è $$F=\begin{pmatrix}1&1&1&1\\1&j&-1&-j\\1&-1&1&-1\\1&-j&-1&j\end{pmatrix}$$ (le potenze di $j=e^{j\pi/2}$).

Esempi

1. Calcolo diretto, $N=4$. $x=(1,2,3,4)$. $$X(0)=\tfrac14(1+2+3+4)=\tfrac{10}4=2{,}5;\qquad X(1)=\tfrac14\left(1+2e^{-j\pi/2}+3e^{-j\pi}+4e^{-j3\pi/2}\right)=\tfrac14(1-2j-3+4j)=\tfrac{-2+2j}{4}=-0{,}5+0{,}5j;$$ $$X(2)=\tfrac14(1-2+3-4)=-0{,}5;\qquad X(3)=\tfrac14\left(1+2j-3-4j\right)=-0{,}5-0{,}5j.$$ Si nota $X(3)=X^*(1)$ (segnale reale: $X(N-k)=X^*(k)$). Controllo con Parseval: $\frac1N\sum|x|^2=\frac{1+4+9+16}4=7{,}5$ e $\sum|X|^2=6{,}25+0{,}5+0{,}25+0{,}5=7{,}5$ ✓.

2. Impulso e costante. $x(n)=\delta(n)$ (un impulso per periodo): $X(k)=\frac1N$ per ogni $k$ (tutte le armoniche uguali: il pettine). $x(n)=1$: $X(0)=1$, tutti gli altri $0$.

3. Sinusoidi. $x(n)=\cos\left(\frac{2\pi}Nmn\right)=\frac12e^{j\frac{2\pi}Nmn}+\frac12e^{-j\frac{2\pi}Nmn}$: $X(m)=X(-m)=X(N-m)=\frac12$. Per $N=8$, $x(n)=\cos\left(\frac{2\pi n}{8}\right)+\frac12\sin\left(\frac{2\pi3n}8\right)$: la parte coseno dà $X(1)=X(7)=\frac12$; $\frac12\sin(\cdot)=\frac1{4j}\left(e^{j\frac{2\pi}83n}-e^{-j\frac{2\pi}83n}\right)$ dà $X(3)=\frac{1}{4j}=-\frac j4$ e $X(-3)=X(5)=+\frac j4$. Tutti gli altri nulli (verificato con la FFT).

Proprietà

Valgono tutte con gli indici intesi modulo $N$:

Il ritardo $x(n-n_0)$ è un ritardo ciclico: gli ultimi campioni rientrano in testa (il segnale è periodico). Simmetria hermitiana: per un segnale reale, $X(N-k)=X^*(k)$: lo spettro in modulo è simmetrico rispetto a $k=\frac N2$, e basta guardarne la prima metà.

Convoluzione circolare

Per due segnali periodici di periodo $N$ la convoluzione ordinaria diverge (Calcolo della convoluzione e sue proprietàIl supporto della convoluzione è la somma dei supporti, $\operatorname{rect}*\operatorname{rect}=\Lambda$, e due esponenziali causali danno $(e^{-bt}-e^{-at})/(a-b)$. Si calcola con il metodo grafico a casi (ribaltare, traslare, individuare gli intervalli di sovrapposizione). Proprietà: lineare, commutativa, associativa, $\delta$ è l'elemento neutro, la traslazione si somma, l'area è il prodotto delle aree.Calcolo della convoluzione e sue proprietà →). Si definisce la convoluzione circolare $$(x\circledast y)(n)=\sum_{m=0}^{N-1}x(m)\,y\big((n-m)\bmod N\big).$$ È periodica di periodo $N$, commutativa e associativa, e l'elemento neutro è il pettine $\operatorname{comb}_N$ (cioè $\delta(n)$ nel periodo). Nel dominio della TFD diventa un prodotto: i coefficienti di $x\circledast y$ sono $N\,X(k)Y(k)$ (con la convenzione dei coefficienti con $\frac1N$).

Esempio. $N=4$, $x=(1,2,3,4)$ e $y=(1,0,0,1)$, cioè $y(n)=\delta(n)+\delta(n-3)$. La convoluzione con $\delta(n-3)$ è un ritardo ciclico di 3 campioni: $$z(n)=x(n)+x\big((n-3)\bmod4\big)\ \Rightarrow\ z=(1+2,\ 2+3,\ 3+4,\ 4+1)=(3,5,7,5).$$ (Ad esempio $z(0)=x(0)+x(1)$, perché $(0-3)\bmod4=1$.) Lo stesso risultato si ottiene antitrasformando il prodotto delle trasformate.

Convoluzione lineare tramite TFD. Siano $a$ e $b$ sequenze finite di $L_a$ e $L_b$ campioni. La loro convoluzione ordinaria ha $L_a+L_b-1$ campioni. Se si completano con zeri a una lunghezza $M\ge L_a+L_b-1$ e si fa la convoluzione circolare di periodo $M$, i campioni "che ritornano" cadono su zeri e non si sovrappongono: il risultato coincide con la convoluzione lineare. Esempio: $a=(1,2,1)$, $b=(1,-1,2)$, $M=8$: antitrasformando il prodotto delle FFT si trova $(1,1,1,3,2,0,0,0)$, cioè la convoluzione $(1,1,1,3,2)$ calcolata in Sistemi LTI, risposta impulsiva e convoluzioneUn sistema lineare tempo-invariante (LTI) è completamente descritto dalla sua risposta impulsiva $h=\Sigma[\delta]$: l'uscita è la convoluzione $y=x*h$, cioè $y(t)=\int x(u)h(t-u)du$ (somma $\sum_k x(k)h(n-k)$ nel discreto). Il teorema discende da linearità e tempo-invarianza applicate alla scomposizione del segnale in impulsi.Sistemi LTI, risposta impulsiva e convoluzione →. È il modo in cui le librerie calcolano velocemente le convoluzioni lunghe.

Costo di calcolo e FFT

Calcolare direttamente $N$ coefficienti da $N$ campioni richiede $N^2$ moltiplicazioni (è il prodotto con la matrice $F$). L'algoritmo FFT (Fast Fourier Transform) sfrutta la struttura di $F$ e richiede circa $N\log_2N$ operazioni: per $N=2^{20}$ (un milione di campioni) si passa da $10^{12}$ a $2\cdot10^7$ operazioni. La FFT è più veloce quando $N$ è una potenza di 2.

Relazione con la serie e con la TFtd

• Se $x(n)=\tilde x(nT_c)$ sono i campioni di un segnale continuo periodico, i coefficienti $X(k)$ della TFD sono la ripetizione periodica (somma di repliche) dei coefficienti $a_k$ della serie: $X(k)=\sum_ma_{k+mN}$ (aliasing in frequenza: le armoniche oltre $\frac N2$ si sovrappongono a quelle basse).
• Se $x$ è una sequenza finita di $N$ campioni e se ne considera la ripetizione periodica, la TFD è il campionamento della sua trasformata di Fourier a tempo discreto: $X(k)=\frac1N\hat X\left(\frac{2\pi k}N\right)$. Aggiungendo zeri ($M>N$) si campiona più fitto la stessa $\hat X(\omega)$ (Trasformata di Fourier a tempo discreto (TFtd)La TFtd di una sequenza è $X(\omega)=\sum_nx(n)e^{-j\omega n}$, funzione continua e periodica di periodo $2\pi$; si inverte con $x(n)=\frac1{2\pi}\int_{-\pi}^{\pi}X(\omega)e^{j\omega n}d\omega$. Ha le stesse proprietà della TF continua (la convoluzione diventa prodotto, $n,x(n)\leftrightarrow jX'$). È la risposta in frequenza dei sistemi discreti; con la TFD e lo zero-padding se ne ottengono campioni arbitrariamente fitti.Trasformata di Fourier a tempo discreto (TFtd) →).

Errori comuni

• Confondere la convenzione con il fattore $\frac1N$ ($\mathtt{fft}$ restituisce $N X$).
• Usare il ritardo ordinario al posto del ritardo ciclico.
• Dimenticare che gli indici $k$ sono modulo $N$ (la componente "$-1$" è la $N-1$).
• Aspettarsi che la convoluzione circolare coincida con la lineare senza zero-padding a lunghezza $\ge L_a+L_b-1$.