Convoluția FFT folosește principiul conform căruia multiplicarea în domeniul frecvență corespunde convoluției în domeniul timp. Semnalul de intrare este transformat în domeniul frecvență utilizând DFT, înmulțit cu răspunsul în frecvență al filtrului, și apoi transformat înapoi în domeniul timp folosind Inverse DFT. Această tehnică de bază a fost cunoscută din zilele lui Fourier; cu toate acestea, nimeni nu s-a sinchisit cu adevărat. Acest lucru se datorează faptului că timpul necesar pentru a calcula DFT a fost mai mare decât timpul pentru a calcula direct convoluția. Aceasta s-a schimbat în 1965 odată cu dezvoltarea Transformatei Fourier Rapide (FFT). Prin utilizarea algoritmului FFT pentru a calcula DFT, convoluția prin intermediul domeniului frecvență poate fi mai rapidă decât convoluția directă a semnalelor în domeniul timp. Rezultatul final este același; Numai numărul de calcule a fost modificat printr-un algoritm mai eficient. Din acest motiv, convoluția FFT este numită și convoluție de mare viteză.

Convoluția FFT folosește metoda de suprapunere-adăugare prezentată în figura 18-1; numai modul în care segmentele de intrare sunt convertite în segmente de ieșire este modificat. Figura 18-2 prezintă un exemplu de modul în care un segment de intrare este transformat într-un segment de ieșire prin convoluție FFT. Pentru a începe, răspunsul în frecvență al filtrului este găsit prin aplicarea DFT kernelului de filtru, utilizând FFT. De exemplu, (a) arată un exemplu de kernel filtru, un filtru de band-pass windowed-sinc. FFT convertește acest lucru în părțile reală și imaginară ale răspunsului în frecvență, prezentate în (b) și (c). Aceste semnale din domeniu frecvență pot să nu pară ca un filtru band-passdeoarece ele sunt în formă dreptunghiulară. Amintiți-vă, forma polare este de obicei cea mai bună pentru oameni pentru a înțelege domeniul frecvență, în timp ce forma dreptunghiulară este în mod normal cea mai bună pentru calcule matematice. Aceste părți reală și imaginară sunt stocate în calculator pentru a fi utilizate atunci când se calculează fiecare segment.

Figura (d) arată segmentul de intrare de procesat. FFT este folosită pentru a-și găsi spectrul de frecvență, arătat în (e) și (f). Spectrul de frecvență al segmentului de ieșire, (h) & (i) este apoi găsit prin înmulțirea răspunsului în frecvență al filtrului, (b) și (c), prin spectrul segmentului de intrare, (e) și (f). Deoarece aceste spectre constau din părți reale și imaginare, ele se înmulțesc în conformitate cu Ec. 9-1 din Capitolul 9. FFT inversă este apoi utilizată pentru a găsi segmentul de ieșire, (g), din spectrul său de frecvență, (h) și (i). Este important să recunoaștem că acest segment de ieșire este exact același cu cel obținut prin convoluția directă a segmentului de intrare, (d) și a kernelului de filtru, (a).

FFT-urile trebuie să fie suficient de lungi încât convoluția circulară să nu aibă loc (descrisă și în Capitolul 9). Aceasta înseamnă că FFT ar trebui să aibă aceeași lungime ca segmentul de ieșire, (g). De exemplu, în exemplul din figura 18-2, kernelul filtrului conține 129 de puncte și fiecare segment conține 128 de puncte, ceea ce face ca segmentul de ieșire să fie lung de 256 de puncte. Aceasta necesită utilizarea FFT de 256 puncte. Aceasta înseamnă că nucleul de filtru, (a), trebuie umplut cu 127 de zerouri pentru a-l aduce la o lungime totală de 256 de puncte. De asemenea, fiecare dintre segmentele de intrare, (d) trebuie să fie umplut cu 128 de zerouri. Un alt exemplu, imaginați-vă că trebuie să faceți con-voluția unui semnal foarte lung cu un kernel filtru având 600 de eșantioane. O alternativă ar fi utilizarea de segmente de 425 puncte și FFT de 1024 puncte. Altă alternativă ar fi utilizarea de segmente de 1449 puncte și FFT de 2048 puncte.

Tabelul 18-1 prezintă un exemplu de program pentru efectuarea convoluției FFT. Acest program filtrează un semnal de 10 milioane de puncte prin convoluția acestuia cu un kernel filtru de 400 de puncte. Aceasta se face prin ruperea semnalului de intrare în 16000 de segmente, fiecare segment având 625 de puncte. Atunci când fiecare dintre aceste segmente este în convoluție cu kernelul de filtru, se produce un segment de ieșire de 625 + 400 - 1 = 1024 puncte. Astfel, sunt utilizate FFT de 1024 puncte. După definirea și inițializarea tuturor rețelelor (liniile 130-230), primul pas este de a calcula și de a stoca răspunsul în frecvență al filtrului (liniile 250-310). Linia 260 apelează o subrutină mitică care încarcă kernelul filtru în XX[0] până la XX[399] și stabilește XX[400] până la XX[1023] la o valoare zero. Subrutina din linia 270 este FFT, transformând cele 1024 de eșantioane păstrate în XX[ ] în cele 513 eșantioane păstrate în REX[ ] și IMX[ ], părțile reală și imaginară ale răspunsului în frecvență. Aceste valori sunt transferate în matricele REFR[ ] și IMFR[ ] (pentru: REAL și IMaginary Frequency Response), care vor fi utilizate mai târziu în program.

Figura 18-2 Convoluția FFT

Nucleul filtrului (a) și segmentul de semnal (d) sunt convertite în spectrele lor respective (b) & (c) și (e) & (f), via FFT. Aceste spectre sunt multiplicate, conducând la spectrul segmentului de ieșire (h) & (i). FFT inversă găsește apoi segmentul de ieșire (g).

Buclele FOR-NEXT între liniile 340 și 580 controlează modul în care sunt procesate 16000 de segmente. În linia 360, o subrutină încarcă următorul segment de procesat în XX[0] până la XX[624] și stabilește XX[625] până la XX[1023] la o valoare zero. În linia 370, subrutina FFT este utilizată pentru a găsi spectrul de frecvență al acestui segment, partea reală fiind plasată în cele 513 de puncte din REX[ ], iar partea imaginară fiind plasată în cele 513 de puncte din IMX[ ]. Linile 390-430 arată multiplicarea spectrului de frecvență al segmentului, ținut în REX[ ] și IMX[ ], prin răspunsul în frecvență al filtrului, ținut în REFR[ ] și IMFR[ ]. Rezultatul multiplicării este stocat în REX[ ] & IMX[ ], suprascriind datele anterior acolo. Deoarece acesta este acum spectrul de frecvență al segmentului de ieșire, IFFT poate fi folosit pentru a găsi segmentul de ieșire. Aceasta se face prin subrutina mitică IFFT din linia 450, care transformă cele 513 puncte ținute în REX[ ] & IMX[ ] în cele 1024 puncte ținute în XX[ ], segmentul de ieșire.

Linile 470-550 se ocupă de suprapunerea segmentelor. Fiecare segment de ieșire este împărțit în două secțiuni. Primele 625 de puncte (0 până la 624) trebuie combinate cu suprapunerea din segmentul de ieșire anterior și apoi scrise la semnalul de ieșire. Ultimele 399 de puncte (625 până la 1023) trebuie salvate astfel încât să se poată suprapune cu următorul segment de ieșire.

Pentru a înțelege acest lucru, priviți înapoi la Fig. 18-1. Eșantioanele 100 la 199 din (g) trebuie combinate cu suprapunerea din segmentul de ieșire anterior (f) și apoi pot fi mutate la semnalul de ieșire (i). În comparație, eșantioanele 200 la 299 din (g) trebuie salvate astfel încât să poată fi combinate cu următorul segment de ieșire, (h).

Acum, reveniți la program. Array-ul OLAP[ ] este utilizat pentru a reține cele 399 de eșantioane care se suprapun de la un segment la altul. În liniile 470 până la 490, cele 399 de valori din acest array (din segmentul de ieșire anterior) sunt adăugate la segmentul de ieșire la care se lucrează în prezent, ținut în XX[ ]. Subrutina mitică din linia 550 transmite apoi cele 625 de eșantioane în XX[0] până la XX[624] în fișierul care deține semnalul de ieșire. Cele 399 de eșantioane ale segmentului curent de ieșire care trebuie să fie păstrate la următorul segment de ieșire sunt apoi stocate în OLAP[ ] în liniile 510-530.

După ce au fost procesate toate segmentele de la 0 la 15999, array-ul OLAP[ ] va conține cele 399 de eșantioane din segmentul 15999 care ar trebui să suprapună segmentul 16000. Deoarece segmentul 16000 nu există (sau poate fi văzut ca conținând tot zerouri), 399 de eșantioane sunt înscrise pe semnalul de ieșire pe linia 600. Aceasta face lungimea punctelor din semnalul de ieșire. Aceasta corespunde lungimii semnalului de intrare plus lungimea kernelului filtru, minus 1.

Secțiunea următoare: Îmbunătățiri de viteză