Algoritmi e strutture per il calcolo della DFT su blocchi di dati parzialmente sovrapposti

In questo lavoro viene affrontato il problema di calcolare la trasformata discreta di Fourier (DFT)su blocchi di dati parzialmente sovrapposti'. A questo scopo vengo- no presentati due algoritmi che utilizzano, per il calcolo della DFT su un nuovo blocco, alcuni risultati intermedi ottenuti durante il calcolo della DFT sul blocco precedente. Entrambi gli algoritmi hanno una complessita di calcolo dell'ordine di N logP, dove N e il numero di elementi di ogni blocco e P il numero di elementi diversi in due blocchi successivi. Per questi algoritmi vengono proposte delle strutture che calcolano la DFT con diverso grado di parallelismo e vengono confrontate le risorse richieste. Nella prima parte del lavoro viene generalizzata la trasformata discreta di Fourier,allo scopo di inquadrare in modo unitario gli algoritmi veloci per il calcolo ,di tale trasformata e le strutture che la realizzano. Queste ci permette di avere un preciso riferimento per la valutazione degli algoritmi e delle strutture presentati nelle parti successiva. Nella seconda parte viene introdotto il problema del calcolo della DFT su blocchi di dati parzialmente sovrapposti, e vengono date strutture che utilizzano gli algoritmi veloci gia noti. Nella terza parte viene presentato il primo algoritmo e le strutture relative. L'algoritmo si basa sul fatto che se due blocchi di dati differiscono per un elemento, allora i dati con indice pari del secondo blocco coincidono con i dati con indice dispari del primo blocco. Pertanto, applicando l'algoritmo di decimazione in tempo, la DFT parziale sui dati con indice pari non deve essere ricalcolata. Nella quarta parte viene presentato il secondo algoritmo e le strutture relative. L'algoritmo si basa sul fatto che i coefficienti di opportune trasformate parziali possono essere espressi come funzioni di se stessi e dei dati per cui due blocchi successivi differiscono. I due algoritmi e le strutture vengono confrontati nella quinta parte.