Esercizio - Esercitazione sulla DFT

Testo (esercitazione di maggio, parte "Exercises on the DFT", corso Multimedia Signal Processing, UniPD). Cinque esercizi sulla DFT a $N$ punti, $X[k]=\sum_{n=0}^{N-1}x[n]e^{-j2\pi kn/N}$, e un sesto di riconoscimento di segnali e DFT da figure.

1. $x=\{1,1,0,0\}$ con $X[k]=\{2,\ \sqrt2e^{-j\pi/4},\ 0,\ \sqrt2e^{j\pi/4}\}$; $y=\{1,1,0,0,0,0,0,0\}$ ottenuto con zero-padding. Calcolare $Y[k]$ ($8$ valori) e verificare $Y[k]=Y^*[8-k]$; confrontare le DTFT di $x$ e $y$; calcolare la DTFT di $y$ in $\hat\omega=2\pi k/8$ e confrontare con $Y[k]$; verificare $Y[0]=X[0]$, $Y[2]=X[1]$, $Y[4]=X[2]$, $Y[6]=X[3]$.
2. $x[n]=6\cos(14\pi n/20)+4\cos(6\pi n/20-0.5\pi)$ (periodica): scriverla come somma di quattro esponenziali complessi e trovare la DFT a $20$ punti di $x[0..19]$.
3. $x=\{a,b,0,0,0,0\}$ ($a,b\ne0$) con DFT a $6$ punti $X[k]$ e $y=\{a,b,0,0,0,0,0,0\}$ con DFT a $8$ punti $Y[k]$: confrontare $X[0]$ e $Y[0]$; trovare $K$ tale che $Y[K]=X[3]$; generalizzare a una sequenza $v$ di $N$ punti ottenuta con $N-6$ zeri e spiegare perché $N$ deve essere pari.
4. $x=\{c,0,0,0,0,0,0,0,0,d\}$ ($c,d$ reali non nulli), DFT a $10$ punti $X[k]$: (a) $y[n]$ con DFT $Y[k]=X^*[k]$; (b) $Q[k]$ per $q=\{0,0,0,0,d,c,0,0,0,0\}$ in funzione di $X[k]$; (c) $r[n]$ con DFT $R[k]=\lvert X[k]\rvert^2$.
5. (a) Il segnale a $30$ punti con $X(k)=1$ per $k=4$, $0$ altrimenti. (b) La DFT di $x(n)=\cos(2\pi Pn/N)$, con $P$ intero tra $0$ e $N$.
6. Associare ciascuno di otto segnali discreti alla sua DFT (figura).

Teoria usata: Trasformata di Fourier discreta (DFT) e convoluzione circolareLa DFT di N campioni x[0..N-1] è X[k] = sum x[n] e^{-j2pi kn/N}, k = 0..N-1 (IDFT: x[n] = (1/N) sum X[k] e^{j2pi kn/N}); vede il segnale come periodico di periodo N e dà N campioni equispaziati della DTFT, cioè X(z) valutata sulle radici N-esime dell'unità. Se x ha durata M <= N non c'è aliasing temporale e lo zero-padding (N > M) infittisce solo i campioni della stessa DTFT. Proprietà: traslazione circolare, simmetria coniugata X[k] = X*[N-k], prodotto = convoluzione circolare. La convoluzione circolare coincide con la lineare solo se N >= Dx + M - 1; altrimenti la coda si ripiega sull'inizio. La FFT calcola la DFT con (N/2) log2 N moltiplicazioni invece di N^2.Trasformata di Fourier discreta (DFT) e convoluzione circolare →, Trasformata di Fourier a tempo discretoLa trasformata di Fourier di un segnale discreto è $S(f)=\sum_nT,s(nT),e^{-i2\pi fnT}$: una funzione continua e periodica in $f$ di periodo $F_p=1/T$. L'antitrasformata è l'integrale su un periodo, $s(nT)=\int_0^{F_p}S(f)e^{i2\pi fnT}df$. Le regole sono quelle del caso continuo (traslazione, convoluzione $\leftrightarrow$ prodotto, Parseval $\sum T|s|^2=\int_0^{F_p}|S|^2$), con incremento e somma corrente al posto di derivata e integrale. Per segnali reali $S(f)=S^*(-f)$, quindi basta $[0,F_p/2]$. Esempi: $\delta\to1$, $1\to\delta_{F_p}$, rect $\to$ sinc periodico, $a^n\mathbf 1_0\to\frac T{1-ae^{-i2\pi fT}}$.Trasformata di Fourier a tempo discreto →, Analisi spettrale con la DFT - finestre e leakageAnalizzare lo spettro di un segnale con la DFT vuol dire osservarne solo L campioni (finestra rettangolare) e campionare in frequenza la DTFT. Una sinusoide non dà una riga ma il nucleo di Dirichlet della finestra centrato in w0: lobo principale largo 4pi/L e lobi laterali (il primo a -13.3 dB). Due toni più vicini della mezza larghezza del lobo non si separano (risoluzione, che dipende solo da L), e i lobi laterali di un tono mascherano i toni deboli (leakage). La DFT campiona la DTFT a 2pi k/N: l'ampiezza è corretta solo se il tono cade su un bin (periodi interi nella finestra), altrimenti si perde fino a 3.9 dB; lo zero-padding infittisce i campioni ma non migliora la risoluzione. Le finestre rastremate (Hann, Hamming, Blackman) abbassano i lobi laterali (-31, -42, -58 dB) a prezzo di un lobo principale più largo.Analisi spettrale con la DFT - finestre e leakage →, Numeri complessi, formula di Eulero ed esponenziali complessiUn numero complesso si scrive in forma cartesiana a+jb o polare |x|e^{jφ}; il prodotto moltiplica i moduli e somma le fasi. La formula di Eulero e^{jα}=cos α + j sin α lega esponenziali e sinusoidi e permette di trattare tutti i segnali del corso come somme di esponenziali complessi e^{(σ+jω)t}.Numeri complessi, formula di Eulero ed esponenziali complessi →.

Esercizio 1

(a) $x$ ha due campioni non nulli, quindi per $y$ (con $N=8$): $$Y[k]=1\cdot e^{-j0}+1\cdot e^{-j2\pi k/8}=1+e^{-j\pi k/4},\qquad k=0,\dots,7.$$ Calcolando:

Verifica della simmetria coniugata: $Y[1]=Y^*[7]$, $Y[2]=Y^*[6]$, $Y[3]=Y^*[5]$, e $Y[0]$, $Y[4]$ reali ✓, perché $x$ è reale. Per esempio $Y[3]=1+e^{-j3\pi/4}=1-\frac{\sqrt2}2-j\frac{\sqrt2}2$ e $Y[5]=1+e^{-j5\pi/4}=1-\frac{\sqrt2}2+j\frac{\sqrt2}2$.

(b) $x$ e $y$ hanno lo stesso supporto non nullo $\{0,1\}$, quindi la stessa DTFT $X(e^{j\hat\omega})=Y(e^{j\hat\omega})=1+e^{-j\hat\omega}$: lo zero-padding non cambia la trasformata, che non dipende da $N$.

(c) In $\hat\omega=2\pi k/8$ la DTFT vale $1+e^{-j2\pi k/8}=Y[k]$: la DFT è il campionamento della DTFT (Trasformata di Fourier discreta (DFT) e convoluzione circolareLa DFT di N campioni x[0..N-1] è X[k] = sum x[n] e^{-j2pi kn/N}, k = 0..N-1 (IDFT: x[n] = (1/N) sum X[k] e^{j2pi kn/N}); vede il segnale come periodico di periodo N e dà N campioni equispaziati della DTFT, cioè X(z) valutata sulle radici N-esime dell'unità. Se x ha durata M <= N non c'è aliasing temporale e lo zero-padding (N > M) infittisce solo i campioni della stessa DTFT. Proprietà: traslazione circolare, simmetria coniugata X[k] = X*[N-k], prodotto = convoluzione circolare. La convoluzione circolare coincide con la lineare solo se N >= Dx + M - 1; altrimenti la coda si ripiega sull'inizio. La FFT calcola la DFT con (N/2) log2 N moltiplicazioni invece di N^2.Trasformata di Fourier discreta (DFT) e convoluzione circolare →).

(d) I valori pari: $Y[0]=2=X[0]$, $Y[2]=1-j=\sqrt2e^{-j\pi/4}=X[1]$, $Y[4]=0=X[2]$, $Y[6]=1+j=\sqrt2e^{j\pi/4}=X[3]$ ✓. Lo zero-padding raddoppia il numero di campioni: quelli di indice pari coincidono con la DFT a $4$ punti, quelli dispari sono nuovi (interpolazione in frequenza). Tutti i valori sono stati verificati con Python (np.fft.fft a $4$ e $8$ punti).

Esercizio 2

Quattro esponenziali. Con $\cos\theta=\frac12(e^{j\theta}+e^{-j\theta})$ e $\frac{14\pi}{20}=2\pi\frac{7}{20}$, $\frac{6\pi}{20}=2\pi\frac3{20}$: $$x[n]=3e^{j2\pi\frac7{20}n}+3e^{-j2\pi\frac7{20}n}+2e^{j(2\pi\frac3{20}n-0.5\pi)}+2e^{-j(2\pi\frac3{20}n-0.5\pi)}.$$

DFT a $20$ punti. Un esponenziale $Ae^{j\varphi}e^{j2\pi k_0n/N}$ ha DFT $NAe^{j\varphi}$ in $k=k_0$ (e $0$ altrove). Con $N=20$ e $e^{-j2\pi\frac7{20}n}=e^{j2\pi\frac{13}{20}n}$ (indice $13=20-7$):

• $k=7$: $20\cdot3=60$;
• $k=13$: $20\cdot3=60$;
• $k=3$: $20\cdot2e^{-j\pi/2}=40e^{-j\pi/2}=-40j$;
• $k=17$ ($=20-3$): $20\cdot2e^{+j\pi/2}=40j$;
• tutti gli altri $X[k]=0$.

Verificato con np.fft.fft (uniche componenti non nulle $X[3]=-40j$, $X[7]=60$, $X[13]=60$, $X[17]=40j$). La fase $-0.5\pi$ del secondo coseno compare nella fase di $X[3]$ e con segno opposto in $X[17]$ (simmetria coniugata).

Esercizio 3

(a) $X[k]=a+be^{-j2\pi k/6}$ e $Y[k]=a+be^{-j2\pi k/8}$. In $k=0$: $X[0]=a+b=Y[0]$ ✓ (la somma dei campioni non dipende da $N$).

(b) $X[3]=a+be^{-j\pi}=a-b$. Cerchiamo $K$ con $Y[K]=a+be^{-j2\pi K/8}=a-b$: serve $e^{-j2\pi K/8}=-1$, cioè $K=4$ ($e^{-j\pi}=-1$). Quindi $Y[4]=X[3]=a-b$: l'indice a metà periodo, $N/2$ in entrambi i casi ($3=6/2$, $4=8/2$), è la frequenza $\hat\omega=\pi$.

(c) Per un segnale $v$ a $N$ punti: $V[k]=a+be^{-j2\pi k/N}$. Si vuole $V[k]=a-b$, cioè $e^{-j2\pi k/N}=-1$, quindi $2\pi k/N=\pi$ e $k=N/2$. Poiché $k$ deve essere intero, $N$ deve essere pari: per $N$ dispari la frequenza $\hat\omega=\pi$ non coincide con nessun bin $2\pi k/N$ ($N/2$ non è intero).

Esercizio 4

(a) Per un segnale reale, $X^*[k]=X[N-k]$ è la DFT del segnale riflesso $y[n]=x[(N-n)_N]$ (coniugare in un dominio = riflettere e coniugare nell'altro; qui $x$ è reale). Con $N=10$: $y[0]=x[0]=c$, $y[1]=x[9]=d$, $y[2]=x[8]=0,\dots$: $$y=\{c,\ d,\ 0,0,0,0,0,0,0,0\}.$$

(b) $q$ è $x$ traslato circolarmente di $5$: $q[5]=x[0]=c$, $q[4]=x[-1]=x[9]=d$. Per la proprietà di traslazione: $Q[k]=e^{-j2\pi\cdot5k/10}X[k]=e^{-j\pi k}X[k]=(-1)^kX[k]$ (verificato numericamente: il rapporto $Q/X$ vale $+1,-1,+1,\dots$).

(c) $R[k]=\lvert X[k]\rvert^2=X[k]X^*[k]=X[k]Y[k]$, con $Y=X^*$ del punto (a): il prodotto corrisponde alla convoluzione circolare $r[n]=\sum_my[m]x[(n-m)_{10}]$. Entrambi hanno due elementi non nulli: $r[0]=y[0]x[0]+y[1]x[(0-1)_{10}]=c^2+d\cdot x[9]=c^2+d^2$; $r[1]=y[0]x[1]+y[1]x[0]=0+dc=cd$; $r[9]=y[0]x[9]+y[1]x[8]=cd$; tutti gli altri sono nulli ($r[2],\dots,r[8]=0$): $$r=\{c^2+d^2,\ cd,\ 0,0,0,0,0,0,0,\ cd\}.$$ È l'autocorrelazione circolare di $x$: simmetrica attorno a $0$, con $r[0]=\sum x^2$ ($\sum x^2=c^2+d^2$, ✓ Parseval). Con $c=2$, $d=5$: $r=\{29,10,0,\dots,0,10\}$ (verificato con ifft(abs(fft(x))**2)).

Esercizio 5

(a) $x[n]=\frac1N\sum_kX[k]e^{j2\pi kn/N}$ con solo $X[4]=1$ e $N=30$: $$x[n]=\frac1{30}e^{j2\pi\cdot4n/30}=\frac1{30}e^{j\frac{4\pi}{15}n},\qquad0\le n<30.$$

(b) Con $\cos\frac{2\pi Pn}N=\frac12e^{j2\pi Pn/N}+\frac12e^{-j2\pi Pn/N}$ e $e^{-j2\pi Pn/N}=e^{j2\pi(N-P)n/N}$: ogni esponenziale ha DFT $N$ nel proprio indice, quindi $$X[k]=\frac N2\,\delta[k-P]+\frac N2\,\delta[k-(N-P)],\qquad k=0,\dots,N-1\ (\text{indici modulo }N).$$ Casi particolari (la soluzione del corso tratta solo $P=0$): se $P=0$, $x[n]=1$ e $X[0]=N$ (le due righe coincidono: $N/2+N/2$); anche se $P=N/2$ ($N$ pari) le due righe coincidono e $X[N/2]=N$, con $x[n]=(-1)^n$. Esempio con $N=12$: $P=3$ dà $X[3]=X[9]=6$, $P=6$ dà $X[6]=12$ (verificato con Python).

Esercizio 6 (riconoscere segnali e DFT)

L'esercizio usa figure non riprodotte qui; i criteri della soluzione del corso sono:

• impulso $\delta[n]$: DFT piatta ($X[k]=1$ per ogni $k$);
• costante: un solo bin non nullo in $k=0$ ($X[k]=N\delta[k]$);
• coseno con periodi interi nella finestra: due righe (a $k_0$ e $N-k_0$); frequenza più alta = righe più lontane da $k=0$;
• coseno con periodi non interi (leakage): energia sparsa nei bin vicini invece di due righe;
• impulso rettangolare ($1$ per $0\le n<M$): DFT a forma di sinc, con lobi laterali che decrescono dal bin $0$;
• coseno per finestra rettangolare: due lobi larghi (sinc) centrati sulle frequenze del coseno, perché moltiplicare nel tempo equivale a convolvere in frequenza (Analisi spettrale con la DFT - finestre e leakageAnalizzare lo spettro di un segnale con la DFT vuol dire osservarne solo L campioni (finestra rettangolare) e campionare in frequenza la DTFT. Una sinusoide non dà una riga ma il nucleo di Dirichlet della finestra centrato in w0: lobo principale largo 4pi/L e lobi laterali (il primo a -13.3 dB). Due toni più vicini della mezza larghezza del lobo non si separano (risoluzione, che dipende solo da L), e i lobi laterali di un tono mascherano i toni deboli (leakage). La DFT campiona la DTFT a 2pi k/N: l'ampiezza è corretta solo se il tono cade su un bin (periodi interi nella finestra), altrimenti si perde fino a 3.9 dB; lo zero-padding infittisce i campioni ma non migliora la risoluzione. Le finestre rastremate (Hann, Hamming, Blackman) abbassano i lobi laterali (-31, -42, -58 dB) a prezzo di un lobo principale più largo.Analisi spettrale con la DFT - finestre e leakage →).