Teoria ed elaborazione dei segnali/DFT e FFT

Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è B4. DFT e FFT.

B3. Trasformata di Fourier a tempo discreto	Teoria ed elaborazione dei segnali (Elaborazione numerica dei segnali)	B5. Analisi in frequenza di segnali a tempo continuo campionati

Trasformata di Fourier discreta (DFT)

Definizione di DFT

4 Data una sequenza <math>x \left( n \right)</math> costituita da un numero <math>N</math> finito di campioni, la sua trasformata di Fourier discreta (DFT) <math>X \left( k \right)</math>, all'interno del suo periodo <math>N</math>, è definita:

<math>X \left( k \right) = \sum_{n = 0}^{N- 1} x \left( n \right) e^{-j2 \pi n \frac{k}{N}} , \quad k = 0,1,2, \ldots , N-1</math>

9 e può essere interpretata come la discretizzazione in frequenza della DTFT <math>X \left( e^{j2 \pi f} \right)</math>, di cui vengono prese <math>N</math> frequenze <math>f_k</math> equispaziate:

<math>f_k = {k \over N} , \quad k = 0, 1, 2, \ldots , N - 1</math>

3-7 Dal punto di vista algoritmico, la DFT è di complessità inferiore rispetto alla DTFT, e inoltre è definita in modo discreto → è rappresentabile su un calcolatore.

Inversione della DFT (IDFT)

5 L'antitrasformata della DFT, all'interno del suo periodo <math>N</math>, è definita:

<math>x \left( n \right) = \frac{1}{N} \sum_{k = 0}^{N - 1} X \left( k \right) e^{j2 \pi n \frac{k}{N}} , \quad n = 0,1,2, \ldots, N - 1</math>

Estensioni periodiche

5-8 La DFT e la IDFT sono periodiche di periodo <math>N</math>:

<math>\begin{cases} X \left( k \right) = X \left( k + N \right) \quad k = 0 , \ldots, N-1 \\

x \left( n \right) = x \left( n + N \right) \quad n = 0 , \ldots , N-1 \end{cases}</math>

Si definiscono le estensioni periodiche <math>\overline{X} \left( k \right)</math> e <math>\overline{x} \left( n \right)</math>, rispettivamente di <math>X \left( k \right)</math> e <math>x \left( n \right)</math>:

<math>\begin{cases} \overline{X} \left( k \right) = \sum_{n = 0}^{N - 1} x \left( n \right) e^{-j2 \pi n \frac{k}{N}} \quad \forall k \\

\overline{x} \left( n \right) = \frac{1}{N} \sum_{k = 0}^{N-1} X \left( k \right) e^{j2 \pi n \frac{k}{N}} \quad \forall n \end{cases}</math>

Tecnica di aggiunta degli zeri

11 È possibile teoricamente ricavare per interpolazione la DTFT partendo dagli <math>N</math> campioni della DFT:

<math>X \left( e^{j 2 \pi f} \right) = \frac{1}{N} \sum_{k = 0 }^{N-1} X \left( k \right) \frac{\sin{\left( \pi N f - k \pi \right)}}{\sin{\left( \pi f - \pi \frac{k}{N} \right)}} e^{-j \pi \left( N - 1 \right) \left( f - \frac{k}{N} \right)}</math>

10 Dimostrazione

\right) e^{-j2 \pi fn} = \frac{1}{N} \sum_{k = 0}^{N -1} X \left( k \right) \left( \sum_{n = 0}^{N - 1} e^{-j2 \pi f n} e^{j2 \pi n \frac{k}{N}} \right)</math>

<math>\sum_{n = 0}^{N - 1} e^{-j2 \pi f n} e^{j2 \pi n \frac{k}{N}} = \sum_{n = 0}^{N-1} e^{-j2 \pi n \left( f - \frac{k}{N} \right)} = \frac{1 - e^{-j2 \pi N \left( f - \frac{k}{N} \right)}}{1 - e^{-j2 \pi \left( f - \frac{k}{N} \right)}} = \frac{e^{-j \pi N \left( f - \frac{k}{N} \right)} \left( e^{j \pi N \left( f - \frac{k}{N} \right) } - e^{-j \pi N \left( f - \frac{k}{N} \right)} \right)}{e^{-j \pi \left( f - \frac{k}{N} \right)} \left( e^{j \pi \left( f - \frac{k}{N} \right) } - e^{-j \pi \left( f - \frac{k}{N} \right)} \right)} = e^{-j \pi \left( N - 1 \right) \left( f - \frac{k}{N} \right)} \frac{\sin{\left( \pi N f - k \pi \right)}}{\sin{\left( \pi f - \pi \frac{k}{N} \right)}}</math>

}}

12-13 In pratica la DTFT viene approssimata a una DFT definita su un nuovo periodo <math>N_1 \gg N</math>, applicata a una sequenza <math>x_z \left( n \right)</math> che non è altro che la sequenza di partenza <math>x \left( n \right)</math> a cui sono stati accodati <math>N_1 - N</math> campioni nulli:

<math>x_z \left( n \right) = \begin{cases} x \left( n \right) & n = 0 , \ldots , N - 1 \\

0 & n = N , \ldots , N_1 - 1 \end{cases}</math>

Aggiungere degli zeri in fondo alla sequenza <math>x \left( n \right)</math> permette di aumentare artificialmente il periodo della sua DFT senza alterare la DTFT a cui si cerca di approssimare:

<math>X \left( e^{j2 \pi f_k} \right) = \sum_{n = 0}^{N-1} x \left( n \right) e^{-j2 \pi f_k n} = \sum_{n = 0}^{N_1 - 1} x_z \left( n \right) e^{-j 2 \pi \frac{k}{N_1} n} \quad k = 0, \ldots, N_1 - 1</math>

e siccome il numero di campioni presi dalla DTFT è maggiore, la risoluzione della DTFT risulta molto più alta.

Esempio - Sequenza porta

<math>x \left( n \right) = \begin{cases} 1 & 0 \leq n \leq N - 1 \\

0 & n \geq N \end{cases}</math>

14 Considerando solamente l'intervallo <math>\left[ 0 , N - 1 \right]</math> si ottiene come DFT <math>\left| X \left( k \right) \right|</math> una funzione <math>\mathrm{sinc}</math> campionata a una frequenza molto bassa:

<math>X \left( k \right) = \sum_{n = 0}^{N-1} x \left( n \right) e^{-j2 \pi n \frac{k}{N}} = \sum_{n = 0}^{N-1} e^{-j2 \pi n \frac{k}{N}} = \frac{1 - e^{-j2 \pi k}}{1- e^{-j2 \pi \frac{k}{N}}} = \begin{cases} 0 & k \neq 0 \\

N & k = 0 \end{cases}</math>

<math>N_1 = N</math>

16 Basta però aggiungere degli zeri a destra della porta per migliorare la risoluzione della DTFT:

<math>N_1 = 2 N</math>

---

<math>N_1 = 4 N</math>

---

19 <math>N_1 = 100 N</math>

Aliasing nel tempo

22 Partendo dalla sequenza <math>x \left( n \right)</math> di durata non finita:

<math>x \left( n \right) = a^n u \left( n \right) \quad 0 < a < 1</math>

23 la sua DTFT campionata nel primo periodo <math>N</math>:

<math>X \left( k \right) = X \left( e^{j2 \pi \frac{k}{N}} \right) = \frac{1}{1 - a^{-j2 \pi \frac{k}{N}}} \quad k = 0, \ldots, N - 1</math>

non coincide esattamente con la DFT calcolata sulla sequenza troncata:

<math>X_N \left( k \right) = \frac{1 - a^N}{1 - a^{-j 2 \pi \frac{k}{N}}} \quad k = 0 , \ldots, N - 1</math>

24 perché vi è un effetto di aliasing nel tempo dovuto al fatto che la sequenza <math>x \left( n \right)</math> di partenza non ha durata finita.

25 Al crescere dell'ampiezza del periodo <math>N</math>, la DFT della sequenza troncata tende sempre di più alla DTFT campionata nel primo periodo.

Proprietà della DFT

Accorgimenti

30 Le proprietà della DFT sono analoghe a quelle della DTFT, ma ci vogliono alcuni accorgimenti:

• la DFT <math>X \left( k \right)</math> è periodica di periodo <math>N</math> → le operazioni sulla DFT <math>X \left( k \right)</math> devono condurre a una sequenza periodica di periodo <math>N</math>;
• la IDFT <math>x \left( n \right)</math> è periodica di periodo <math>N</math> → le operazioni sulla IDFT <math>x \left( n \right)</math> devono condurre a una sequenza periodica di periodo <math>N</math>.

Operatore di modulo

32 L'operatore di modulo restituisce sempre un numero compreso in <math>\left[ 0 , N - 1 \right]</math>:

<math>{\left| k \right|}_N = k \text{ mod } N</math>

Se <math>k</math> è un numero negativo, si somma <math>N</math> a <math>k</math> tante volte fino a ottenere un numero compreso in <math>\left[ 0 , N - 1 \right]</math>:

<math>{\left| - 13 \right|}_{16} = 3</math>

Operatore di ritardo circolare

L'operatore di ritardo circolare restituisce una sequenza ritardata che è ancora compresa in <math>\left[ 0 , N - 1 \right]</math>:

<math>x \left( {\left| n - N_0 \right|}_k \right)</math>

in quanto i campioni che vanno al di là del primo periodo ricompaiono all'inizio del primo periodo stesso.

Modo operativo

• si genera la sequenza periodicizzata <math>\overline{x} \left( n \right)</math>;
• si applica il ritardo di <math>N_0</math> campioni a <math>\overline{x} \left( n \right)</math>: <math>\overline{x} \left( n - N_0 \right)</math>;
• la sequenza ritardata <math>x \left( n - N_0 \right)</math> è pari alla sequenza periodicizzata <math>\overline{x} \left( n - N_0 \right)</math> troncata nel primo periodo <math>N</math> (<math>n \in \left[ 0 , N - 1 \right]</math>).

Convoluzione circolare

34 La convoluzione circolare tra due sequenze <math>x \left( n \right)</math> e <math>y \left( n \right)</math> è definita:

<math>x \left( n \right) \otimes y \left( n \right) = \sum_{k = 0}^{N-1} x \left( k \right) y \left( {\left| n - k \right|}_N \right)</math>

dove <math>N</math> è la più grande tra le durate delle singole sequenze.

Proprietà commutativa

<math>x \left( n \right) \otimes y \left( n \right) = y \left( n \right) \otimes x \left( n \right)</math>

39 La convoluzione circolare si può rappresentare con un prodotto matrice per vettore. Ad esempio, se la durata <math>N</math> è pari a 4:

<math>x \left( n \right) \otimes y \left( n \right) = \begin{bmatrix} y \left( 0 \right) & y \left( 3 \right) & y \left( 2 \right) & y \left( 1 \right) \\

y \left( 1 \right) & y \left( 0 \right) & y \left( 3 \right) & y \left( 2 \right) \\ y \left( 2 \right) & y \left( 1 \right) & y \left( 0 \right) & y \left( 3 \right) \\ y \left( 3 \right) & y \left( 2 \right) & y \left( 1 \right) & y \left( 0 \right) \end{bmatrix} \begin{bmatrix} x \left( 0 \right) \\ x \left( 1 \right) \\ x \left( 2 \right) \\ x \left( 3 \right) \end{bmatrix}</math>

Linearità

<math>z \left( n \right ) = a_1 x \left( n \right) + a_2 y \left( n \right) \Rightarrow Z \left( k \right) = a_1 X \left( k \right) + a_2 Y \left( k \right)</math>

Ritardo

<math>z \left( n \right) = x \left( {\left| n - N_0 \right|}_N \right) \Rightarrow Z \left( k \right) = X \left( k \right) e^{-j2 \pi \frac{k}{N} N_0}</math>

Modulazione

<math>z \left( n \right) = e^{j2 \pi \frac{k_0}{N} n} x \left( n \right) \Rightarrow Z \left( k \right) = X \left( {\left| k - k_0 \right|}_N \right)</math>

Convoluzione circolare

33 <math>z \left ( n \right) = x \left( n \right) \otimes y \left( n \right) \Rightarrow Z \left( k \right) = X \left( k \right) \cdot Y \left( k \right)</math>

Accorgimenti

• la convoluzione circolare di due sequenze di durata <math>N</math> campioni ha una uguale durata di <math>N</math> campioni (a differenza della convoluzione lineare della DTFT, la cui sequenza risultante ha durata <math>2 N - 1</math> campioni);
• la convoluzione circolare <math>\overline{z} \left( k \right)</math> di due IDFT <math>\overline{x} \left( k \right)</math> e <math>\overline{y} \left( k \right)</math>, entrambe di periodo <math>N</math>, è periodica di periodo <math>N</math>:

  <math>\overline{z} \left( n + N \right) = \sum_{k = 0}^{N-1} \overline{x} \left( k \right) \overline{y} \left( n + N - k \right) = \sum_{k = 0}^{N-1} \overline{x} \left( k \right) \overline{y} \left( n - k \right) = \overline{z} \left( n \right)</math>

Proprietà di simmetria

41 Se la sequenza <math>x \left( n \right)</math> è reale:

• <math>X \left( k \right) = X_R \left( k \right) + j X_I \left( k \right)</math>
  • se <math>x \left( n \right)</math> è una sequenza pari: <math>X_I \left( k \right) = 0</math>;
  • se <math>x \left( n \right)</math> è una sequenza dispari: <math>X_R \left( k \right) = 0</math>;
• per la DFT vale la simmetria hermitiana intorno a 0:

  <math>X \left( k \right) = X^* \left( {\left| - k \right|}_N \right)</math>

• 42 per la DFT vale la simmetria hermitiana intorno a <math>\tfrac{N}{2}</math>;
• il campione in <math>k = 0</math> della DFT è sempre reale:

  <math>X^* \left( 0 \right) = X \left( 0 \right) = \sum_{n = 0}^{N-1} x \left( n \right)</math>

Trasformata di Fourier veloce (FFT)

7-46 La DFT ha complessità quadratica (<math>N^2</math>).

47 La FFT è un algoritmo di complessità linearitmica (<math>N \log{N}</math>) che implementa la DFT e la IDFT in maniera più efficiente.

DFT

50 La DFT può essere rappresentata in termini di matrici:

<math>\mathbf{X} = \mathbf{H x} ; \; \begin{bmatrix} X \left( 0 \right) \\ X \left( 1 \right) \\ X \left( 2 \right) \\ \vdots \\ X \left( N - 1 \right) \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & H_N^1 & H_N^2 & \cdots & H_N^{N-1} \\ 1 & H_N^2 & H_N^4 & \cdots & H_N^{2 \left( N-1 \right)} \\

\vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & H_N^{N-1} & H_N^{2 \left( N - 1 \right)} & \cdots & H_N^{\left( N - 1 \right) \left( N - 1 \right)} \end{bmatrix} \cdot \begin{bmatrix} x \left( 0 \right) \\ x \left( 1 \right) \\ x \left( 2 \right) \\ \vdots \\ x \left( N - 1 \right) \end{bmatrix}</math> dove:

<math>H_N = e^{-j 2 \pi \frac{1}{N}} \Rightarrow H_N^{nk} = e^{-j2 \pi n \frac{k}{N}}</math>

Algoritmo della decimazione nel tempo

52 L'algoritmo della decimazione nel tempo è un algoritmo di tipo "divide et impera" che riduce la complessità dell'algoritmo di DFT.

Ipotesi

<math>N</math> è una potenza di 2

Divide

La sequenza si suddivide in due sottosequenze costituite da metà campioni:

• la sottosequenza <math>x_0 \left( n \right)</math> è formata dai campioni pari:

  <math>x_0 \left( n \right) = x \left( 2 n \right) \quad n = 0 , \ldots , \frac{N}{2} - 1</math>

• la sottosequenza <math>x_1 \left( n \right)</math> è formata dai campioni dispari:

  <math>x_1 \left( n \right) = x \left( 2 n + 1 \right) \quad n = 0 , \ldots , \frac{N}{2} - 1</math>

Ricombinazione

53 Ogni DFT <math>X \left( k \right)</math>, elemento del vettore <math>\mathbf{x}</math>, si ottiene dalla somma delle DFT delle singole sottosequenze <math>x_0 \left( n \right)</math> e <math>x_1 \left( n \right)</math>:

<math>X \left( k \right) = X_0 \left( {\left| k \right|}_{\frac{N}{2}} \right) + H_N^k X_1 \left( {\left| k \right|}_{\frac{N}{2}} \right) = \sum_{n = 0}^{\frac{N}{2} - 1} x_0 \left( n \right) H_{\frac{N}{2}}^{nk} + H_N^k \sum_{n = 0}^{\frac{N}{2} - 1} x_1 \left( n \right) H_{\frac{N}{2}}^{nk}</math>

Dimostrazione

</math>:

<math>= \sum_{n = 0}^{\frac{N}{2} - 1} x_0 \left( n \right) H_{\frac{N}{2}}^{nk} + H_N^k \sum_{n = 0}^{\frac{N}{2} - 1} x_1 \left( n \right) H_{\frac{N}{2}}^{ n k }</math>

}}

Complessità

55 Il numero totale di operazioni (somme e prodotti) complesse è pari a:

<math>N + {N^2 \over 2} < N^2</math>

57 Si può quindi riapplicare ripetutamente il procedimento "divide et impera" sulle sottosequenze. Al passo <math>k</math>-esimo si ha una complessità pari a:

<math>k \cdot N + 2^k {\left( \frac{N}{2^k} \right)}^2 \quad k = 1 , \ldots , \log_2 N</math>

All'ultimo passo (<math>k = \log_2 N</math>), quando si arriva a dover valutare le DFT su 1 punto, la complessità totale è linearitmica:

<math>\log_2 N \cdot N + N \approx \log_2 N \cdot N</math>

Riduzione di complessità

58 La complessità può essere ulteriormente ridotta sfruttando le proprietà di simmetria della matrice <math>\mathbf{H}</math>.

59-60 Esempio con <math>N=4</math> campioni

<math>\begin{cases} X \left( 0 \right) = x \left( 0 \right) + x \left( 2 \right) + x \left( 1 \right) + x \left( 3 \right) \\ X \left( 1 \right) = x \left( 0 \right) + H_2 x \left( 2 \right) + H_4 \left[ x \left( 1 \right) + H_2 x \left( 3 \right) \right] \\ X \left( 2 \right) = x \left( 0 \right) + x \left( 2 \right) + H_4^2 \left[ x \left( 1 \right) + x \left( 3 \right) \right] \\ X \left( 3 \right) = x \left( 0 \right) + H_2 x \left( 2 \right) + H_4^3 \left[ x \left( 1 \right) + H_2 x \left( 3 \right) \right] \end{cases}</math>

Dimostrazione

k \right

\right) + H_N^k X_1 \left( {\left| k \right|}_{\frac{N}{2}} \right) = X_0 \left( {\left| k \right|}_2 \right) + H_4^k X_1 \left( {\left| k \right|}_2 \right) \quad k = 0, \ldots , 3</math>

<math>\begin{cases} X_0 \left( k \right) = x \left( 0 \right) + x \left( 2 \right) H_2^k \\ X_1 \left( k \right) = x \left( 1 \right) + x \left( 3 \right) H_2^k \end{cases} \Rightarrow \begin{cases} X_0 \left( 0 \right) = x \left( 0 \right) + x \left( 2 \right) \\ X_0 \left( 1 \right) = x \left( 0 \right) + x \left( 2 \right) H_2 \\ X_1 \left( 0 \right) = x \left( 1 \right) + x \left( 3 \right) \\ X_1 \left( 1 \right) = x \left( 1 \right) + x \left( 3 \right) H_2 \end{cases} \Rightarrow \begin{cases} X \left( 0 \right) = X_0 \left( 0 \right) + X_1 \left( 0 \right) = x \left( 0 \right) + x \left( 2 \right) + x \left( 1 \right) + x \left( 3 \right) \\ X \left( 1 \right) = X_0 \left( 1 \right) + H_4 X_1 \left( 1 \right) = x \left( 0 \right) + H_2 x \left( 2 \right) + H_4 \left[ x \left( 1 \right) + H_2 x \left( 3 \right) \right] \\ X \left( 2 \right) = X_0 \left( 0 \right) + H_4^2 X_1 \left( 0 \right) = x \left( 0 \right) + x \left( 2 \right) + H_4^2 \left[ x \left( 1 \right) + x \left( 3 \right) \right] \\ X \left( 3 \right) = X_0 \left( 1 \right) + H_4^3 X_1 \left( 1 \right) = x \left( 0 \right) + H_2 x \left( 2 \right) + H_4^3 \left[ x \left( 1 \right) + H_2 x \left( 3 \right) \right] \end{cases}</math>

}}

61 Schema circuitale a farfalla

IDFT

49 Tutte le considerazioni sulla DFT valgono anche per la IDFT: basta applicare l'algoritmo sul complesso coniugato della DFT e poi dividere per <math>N</math>:

<math>x \left( n \right) = \frac{1}{N} \sum_{k = 0}^{N - 1} X \left( k \right) e^{j2 \pi n \frac{k}{N}} = \frac{1}{N} {\left[ \sum_{k=0}^{N-1} X^* \left( k \right) e^{-j2 \pi n \frac{k}{N}} \right]}^* \Rightarrow x \left( n \right) = \text{IDFT} \left[ X \left( k \right) \right] = \frac{1}{N} \text{DFT} \left[ X^* \left( k \right) \right] , \quad n = 0,1,2, \ldots, N - 1</math>

Note

Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è B4. DFT e FFT.

B3. Trasformata di Fourier a tempo discreto	Teoria ed elaborazione dei segnali (Elaborazione numerica dei segnali)	B5. Analisi in frequenza di segnali a tempo continuo campionati