Pagina:Codifica numerica del segnale audio.djvu/391

E - Richiami su trasformate numeriche

373

$F(k)={\begin{cases}F_{1}(k)+W_{N}^{k}\ F_{2}(k)&0\leq k\leq {\frac {N}{2}}-1\\F_{1}\left(k-{\frac {N}{2}}\right)+W_{N}^{k}\ F_{2}\left(k-{\frac {N}{2}}\right)&{\frac {N}{2}}\leq k\leq N-1\end{cases}}$

(E.16)

Dato che $W_{N}^{k+N/2}=-W_{N}^{k}$, la (E.16) può essere riscritta come

$F(k)={\begin{cases}F_{1}(k)+W_{N}^{k}\ F_{2}(k)&0\leq k\leq {\frac {N}{2}}-1\\F_{1}\left(k-{\frac {N}{2}}\right)+W_{N}^{k-N/2}\ F_{2}\left(k-{\frac {N}{2}}\right)&{\frac {N}{2}}\leq k\leq N-1\end{cases}}$

(E.17)

In tal modo si vede, ad esempio, come la DFT di una serie di 8 campioni può essere ottenuta a partire dalle trasformate di due serie di quattro suoi elementi. Procedendo nella scomposizione di ciascuna sottoserie, si arriverà a poter applicare la (E. 12). Lo spettro completo del segnale sarà ottenibile ricombinando le trasformate tramite ripetute applicazioni della (E. 16).

Visto che la scomposizione del segnale in sottoserie si traduce nel riordinamento bit reversed dei campioni e che la valutazione della (E. 12) non richiede l’effettuazione di nessuna moltiplicazione, l’ordine di complessità N log₂N già ricordato deriva dall'applicazione della (E.16) a ciascuno dei log₂N livelli di scomposizione ottenuti per ognuno degli N campioni dello spettro.

Inoltre, ora si può comprendere che il riordinamento bit reversed ha il compito di riordinare la serie dei campioni in modo da rendere adiacenti i campioni ai quali applicare la (E. 12), che, in realtà, distano N/2 intervalli di campionamento; tali considerazioni valgono anche per le ulteriori sottosequenze in modo tale che la (E.16) possa essere applicata sequenzialmente, ottenendo in uscita la serie ordinata dei campioni dello spettro voluto (fig. E.5).

Come ultima considerazione si pone l’accento sul fatto che le (E.12) coincidono con le (E. 14) scritte per N=2; ciò vuol dire che, ai fini del calcolo, non si distingue tra calcolo delle trasformate ricombinazione delle sottoserie. Il programma di calcolo della FFT si ridurrà all’applicazione iterativa della (E.16) ai campioni opportunamente ordinati, con N crescente dal valore 2 ad N/2 secondo le potenze di 2.