Trasformata di Fourier discreta (DFT)[modifica]
Definizione di DFT[modifica]
Data una sequenza
costituita da un numero
finito di campioni, la sua trasformata di Fourier discreta (DFT)
, all'interno del suo periodo
, è definita:

e può essere interpretata come la discretizzazione in frequenza della DTFT
, di cui vengono prese
frequenze
equispaziate:

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)[modifica]
L'antitrasformata della DFT, all'interno del suo periodo
, è definita:

Estensioni periodiche[modifica]
La DFT e la IDFT[1] sono periodiche di periodo
:

Si definiscono le estensioni periodiche
e
, rispettivamente di
e
:

Tecnica di aggiunta degli zeri[modifica]
È possibile teoricamente ricavare per interpolazione la DTFT partendo dagli
campioni della DFT:

In pratica la DTFT viene approssimata a una DFT definita su un nuovo periodo
, applicata a una sequenza
che non è altro che la sequenza di partenza
a cui sono stati accodati
campioni nulli:

Aggiungere degli zeri in fondo alla sequenza
permette di aumentare artificialmente il periodo della sua DFT senza alterare la DTFT a cui si cerca di approssimare:

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

Considerando solamente l'intervallo
si ottiene come DFT
una funzione
campionata a una frequenza molto bassa:

|
|
|
Basta però aggiungere degli zeri a destra della porta per migliorare la risoluzione della DTFT:
|
|
|
|
|
|
|
Aliasing nel tempo[modifica]
Partendo dalla sequenza
di durata non finita:

la sua DTFT campionata nel primo periodo
:

non coincide esattamente con la DFT calcolata sulla sequenza troncata:

perché vi è un effetto di aliasing nel tempo dovuto al fatto che la sequenza
di partenza non ha durata finita.
Al crescere dell'ampiezza del periodo
, la DFT della sequenza troncata tende sempre di più alla DTFT campionata nel primo periodo.
Proprietà della DFT[modifica]
Le proprietà della DFT sono analoghe a quelle della DTFT, ma ci vogliono alcuni accorgimenti:
- la DFT
è periodica di periodo
→ le operazioni sulla DFT
devono condurre a una sequenza periodica di periodo
;
- la IDFT
è periodica di periodo
→ le operazioni sulla IDFT
devono condurre a una sequenza periodica di periodo
.
Operatore di modulo[modifica]
L'operatore di modulo restituisce sempre un numero compreso in
:

Se
è un numero negativo, si somma
a
tante volte fino a ottenere un numero compreso in
:

Operatore di ritardo circolare[modifica]
L'operatore di ritardo circolare restituisce una sequenza ritardata che è ancora compresa in
:

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
;
- si applica il ritardo di
campioni a
:
;
- la sequenza ritardata
è pari alla sequenza periodicizzata
troncata nel primo periodo
(
).
Convoluzione circolare[modifica]
La convoluzione circolare tra due sequenze
e
è definita:

dove
è la più grande tra le durate delle singole sequenze.
- Proprietà commutativa

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




Convoluzione circolare[modifica]

- Accorgimenti
- la convoluzione circolare di due sequenze di durata
campioni ha una uguale durata di
campioni (a differenza della convoluzione lineare della DTFT, la cui sequenza risultante ha durata
campioni);
- la convoluzione circolare
di due IDFT
e
, entrambe di periodo
, è periodica di periodo
:

Proprietà di simmetria[modifica]
Se la sequenza
è reale:
- se
è una sequenza pari:
;
- se
è una sequenza dispari:
;
- per la DFT vale la simmetria hermitiana intorno a 0:

- per la DFT vale la simmetria hermitiana intorno a
;
- il campione in
della DFT è sempre reale:

Trasformata di Fourier veloce (FFT)[modifica]
La DFT ha complessità quadratica (
).
La FFT è un algoritmo di complessità linearitmica (
) che implementa la DFT e la IDFT in maniera più efficiente.
La DFT può essere rappresentata in termini di matrici:

dove:

Algoritmo della decimazione nel tempo[modifica]
L'algoritmo della decimazione nel tempo è un algoritmo di tipo "divide et impera" che riduce la complessità dell'algoritmo di DFT.
- Ipotesi
è una potenza di 2
La sequenza si suddivide in due sottosequenze costituite da metà campioni:
- la sottosequenza
è formata dai campioni pari:

- la sottosequenza
è formata dai campioni dispari:

Ogni DFT
, elemento del vettore
, si ottiene dalla somma delle DFT delle singole sottosequenze
e
:

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

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

All'ultimo passo (
), quando si arriva a dover valutare le DFT su 1 punto, la complessità totale è linearitmica:

Riduzione di complessità[modifica]
La complessità può essere ulteriormente ridotta sfruttando le proprietà di simmetria della matrice
.
- Esempio con
campioni
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/09250b6a3f4292ec3397a79a42ef842feed4d73d)
Dimostrazione

![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/59875fdd24aa453405f5f7c00004a70e6d510ec1)
Schema circuitale a farfalla
Tutte le considerazioni sulla DFT valgono anche per la IDFT: basta applicare l'algoritmo sul complesso coniugato della DFT e poi dividere per
:
![{\displaystyle 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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0079b2700473f7957ebb6996d140180d7b99f43a)
- ↑ Si noti che la sequenza di partenza
non era periodica, ma aveva durata finita.