Pagina:Codifica numerica del segnale audio.djvu/389

E - Richiami su trasformate numeriche

371

L’idea base di tutti gli algoritmi di FFT è quella di scomporre una sequenza di campioni da trasformare in serie più brevi, le cui DFT, ricombinate, forniscano la DFT del segnale originario. In una FFT con radice pari a due, le serie da trasformare vengono ripetutamente dimezzate fino ad ottenere serie di due soli elementi, dopo log₂N iterazioni. La DFT di una serie di due campioni risulta banalmente calcolabile, in quanto risulta essere dato da

${\begin{cases}F(0)=f(0)W_{2}^{0*0}+f(l)W_{2}^{1*0}=f(0)+f(l)\\F(1)=f(0)W_{2}^{0*1}+f(l)W_{2}^{1*1}=f(0)-f(l)\end{cases}}$

(E.12)

Si fa notare come per il calcolo di tale DFT non venga richiesto il calcolo di moltiplicazioni. Negli algoritmi di decimazione nel tempo la serie dei campioni è ripetutamente scomposta in due sottoserie, la prima delle quali contenente gli elementi di ordine pari della serie originaria, mentre la seconda quella di ordine dispari. L’ordinamento bit reserved deriva da tale progressiva scomposizione. È opportuno notare come le sottoserie generate possano essere viste come risultato di due campionamenti del segnale originario con una frequenza dimezzata ed istanti iniziali opportunamente sfasati. In tal modo la (E.11) può essere riscritta come

$F(k)=\sum _{n=0}^{N/2-1}f(2n)W_{N}^{2nk}+\sum _{n=0}^{N/2-1}f(2n+1)W_{N}^{(2n+1)k}$

$F(k)=\sum _{n=0}^{N/2-1}f_{1}(n)W_{N/2}^{nk}+W_{N}^{k}\sum _{n=0}^{N/2-1}f_{2}(n)W_{N}^{2nk}$

(E.13)

dove f₁ è la serie degli elementi pari, mentre f₂ è la serie degli elementi dispari. Il coefficiente W]^ tiene, appunto, conto dello sfasamento tra le due sottosequenze.

Dato che W_N²=W_N/2¹ (fig. E.4) la (E. 13) può essere scritta come

$F(k)=\sum _{n=0}^{N/2-1}f_{1}(n)W_{N/2}^{nk}+W_{N}^{k}\sum _{n=0}^{N/2-1}f_{2}(n)W_{N/2}^{nk}$

(E.14)