Să presupunem că disprețuiți convoluția. Ce vei face dacă ai un semnal de intrare și un răspuns la impuls și trebuie să găsești semnalul de ieșire rezultat? Figura 9-8 oferă un răspuns: transformați cele două semnale în domeniul frecvență, multiplicați-le și apoi transformați rezultatul înapoi în domeniul timp. Aceasta înlocuiește o convoluție cu două DFT, o multiplicare și o DFT inversă. Chiar dacă pașii intermediari sunt foarte diferiți, ieșirea este identică cu algoritmul standard de convoluție.

Oare cineva urăște convoluția suficient pentru a merge la această nevoie? Răspunsul este da. Convoluția este evitată din două motive. În primul rând, convoluția este dificil de rezolvat din punct de vedere matematic. De exemplu, să presupunem că vi se dă un răspuns la impuls al sistemului și semnalul său de ieșire. Cum calculați ce semnal de intrare este? Aceasta se numește deconvoluție și este practic imposibil de înțeles în domeniul timp. Totuși, deconvoluția poate fi efectuată în domeniul frecvență ca o divizare simplă, operația inversă a multiplicării. Domeniul frecvență devine atractiv ori de câte ori complexitatea transformatei Fourier este mai mică decât complexitatea convoluției. Aceasta nu este o chestiune de care vă place mai bine; este o problemă pe care o urăști mai puțin.

Al doilea motiv pentru evitarea convoluției este viteza de calcul. De exemplu, să presupunem că proiectați un filtru digital cu un kernel (răspuns la impuls) care conține 512 eșantioane. Folosind un calculator personal de 200 MHz cu numere în virgulă mobilă, fiecare eșantion din semnalul de ieșire necesită o calculare de aproximativ o milisecundă, folosind algoritmul de convoluție standard. Cu alte cuvinte, debitul sistemului este de numai aproximativ 1000 de eșantioane pe secundă. Acest lucru este de 40 de ori prea lent pentru audio de înaltă fidelitate și de 10.000 de ori prea lent pentru video de calitate la televizor!

Algoritmul de convoluție standard este lent din cauza numărului mare de multiplicări și adunări care trebuie calculate. Din păcate, pur și simplu aducerea problemei în domeniul frecvență prin DFT nu ajută deloc. La fel de multe calcule sunt necesare pentru a calcula DFT-uri, așa cum sunt necesare pentru a calcula direct convoluția. S-a realizat o descoperire în problemă pe la începutul anilor 1960, când a fost dezvoltată Transformata Fourier Rapidă (FFT). FFT este un algoritm inteligent pentru calculul rapid al DFT. Folosind FFT, convoluția prin înmulțire în domeniul frecvență poate fi de sute de ori mai rapidă decât convoluția convențională. Problemele care durează ore de calcul sunt reduse la doar câteva minute. Acesta este motivul pentru care oamenii sunt încântați de FFT și procesează semnale în domeniul frecvențelor. FFT va fi prezentată în capitolul 12 și metoda convoluției FFT în capitolul 18. Pentru moment, concentrați-vă asupra modului în care semnalele sunt în convoluție prin înmulțirea domeniului frecvență.

Figura 9-8 Convoluția în domeniul frecvență.

În domeniul timp, x[n] este în convoluție cu h[n] rezultând y[n], ca în fig. (a), (d) și (g). Aceeași procedură poate fi aplicată în domenul frecvență. DFT este utilizată pentru a găsi spectrul de frecvență al semnalului de intrare (b) și (c) și răspunsul în frecvență al sistemului (e) și (f). Multiplicând aceste două semnale din domeniul frecvență rezultă spectrul de frecvență al semnalului de ieșire (h) și (i). Apoi este utilizată DFT Inversă pentru a găsi semnalul de ieșire (g).

Pentru a începe, trebuie să definim cum să înmulțim un semnal din domeniu frecvență cu altul, adică ce înseamnă a scrie: X[f] × H[f] = Y[f]. În formă polară, magnitudinile sunt înmulțite: MagY[f] = Mag X[f] x Mag H[f] și fazele se adună: PhaseY[f] = Phase X[f] + Phase H[f]. Pentru a înțelege acest lucru, imaginați-vă o undă cosinus care intră într-un sistem cu o anumită amplitudine și fază. De asemenea, semnalul de ieșire este o undă cosinus cu o anumită amplitudine și fază. Forma polară a răspunsului în frecvență descrie în mod direct modul în care cele două amplitudini sunt legate și modul în care cele două faze sunt legate.

Atunci când multiplicarea domeniului frecvență este efectuată în formă rectangulară, există termeni încrucișați între părțile reală și imaginară. De exemplu, o undă sinus care intră în sistem poate produce atât unde cosinus, cât și unde sinus în ieșire. Pentru a multiplica semnalele din domeniu frecvență în notație dreptunghiulară:

Concentrați-vă pe înțelegerea multiplicării folosind notația polară și ideea undelor cosinus care trec prin sistem. Apoi, pur și simplu acceptați că aceste ecuații mai elaborate rezultă atunci când aceleași operații sunt executate în formă dreptunghiulară. De exemplu, să examinăm divizarea unui semnal din domeniu frecvență de către un altul. În forma polară, divizarea semnalelor din domeniu frecvență se realizează prin operațiile inverse utilizate pentru multiplicare. Pentru a calcula: H[f] = Y[f] / X[f], împărțiți magnitudinile și scădeți fazele, adică Mag H[f] = Mag Y[f] / Mag X[f], PhaseH[f] = PhaseY[f] - PhaseX[f]. În formă rectangulară aceasta devine:

Acum înapoi la convoluția domeniului frecvență. S-ar putea să fi observat că am înșelat puțin în figura 9-8. Amintiți-vă, convoluția unui semnal de N puncte cu un răspuns la impuls de M puncte are ca rezultat un semnal de ieșire de N+M-1 puncte. Ne-am înșelat făcând ultima parte a semnalului de intrare toate zerouri pentru a permite această expansiune să aibă loc. Mai specific, (a) conține 453 de eșantioane nonzero și (b) conține 60 de eșantioane nonzero. Aceasta înseamnă că convoluția celor două, prezentată în (c), se poate încadra confortabil în cele 512 de puncte furnizate.

Figura 9-9 Convoluția circulară.

Un semnal din 256 puncte (a) în convoluție cu un răspuns la impuls de 51 eșantioane (b) conduc la un semnal de 306 eșantioane (c). Dacă această convoluție este realizată în domeniul frecvență utilizând DFT-uri de 256 puncte, cele 306 de puncte din convoluția corectă nu pot încăpea în cele 256 eșantioane realizate. Cum se arată în (d), eșantioanele de la 256 la 305 din semnalul de ieșire sunt împinse în perioada următoare la dreapta, unde ele se adună la începutul semnalului perioadei următoare. Figura (e) este o singură perioadă a semnalului rezultat.

Acum, luați în considerare cazul mai general din fig. 9-9. Semnalul de intrare (a) are o lungime de 256 de puncte, în timp ce răspunsul la impuls, (b), conține 51 de puncte nonzero. Aceasta face convoluția celor două semnale lungă de 306 eșantioane, așa cum se arată în (c). Problema este că, dacă folosim multiplicarea în domeniul frecvență pentru a efectua convoluția, în semnalul de ieșire sunt permise numai 256 de eșantioane. Cu alte cuvinte, DFT de 256 de puncte sunt folosite pentru a muta (a) și (b) în domeniul frecvență. După multiplicare, pentru a găsi semnalul de ieșire, se utilizează o DFT inversă de 256 de puncte. Cum îngrămădiți 306 valori ale semnalului corect în 256 de puncte furnizate de algoritmul domeniului frecvență? Răspunsul este că nu puteți! Cele 256 de puncte ajung să fie o versiune distorsio-nată a semnalului corect. Acest proces este numit convoluție circulară. Este important pentru că doriți să o evitați.

Pentru a înțelege convoluția circulară, amintiți-vă că o DFT de N puncte vede domeniul timp ca fiind un semnal periodic infinit de lung, cu N eșantioane pe perioadă. Figura (d) prezintă trei perioade ale modului în care DFT vede semnalul de ieșire din acest exemplu. Deoarece N = 256, fiecare perioadă constă din 256 de puncte: 0-255, 256-511 și 512-767. Convoluția domeniului frecvență încearcă să plaseze semnalul de ieșire corect de 306 puncte, arătat în (c), în fiecare dintre aceste perioade de 256 de puncte. Rezultatul este că 49 de eșantioane sunt împinse în perioada vecinătății spre dreapta, unde se suprapun cu eșantioanele care sunt în mod legitim acolo. Aceste secțiuni suprapuse se adună, rezultând în fiecare dintre perioade apariția, arătată în (e), a convoluției circulare.

Odată ce natura convoluției circulare este înțeleasă, este destul de ușor de evitat. Pur și simplu introduceți fiecare dintre semnalele din convoluție cu suficiente zerouri pentru a permite spațiu semnalului de ieșire să manevreze cele

N+M-1 puncte în convoluție corectă. De exemplu, semnalele din (a) și (b) ar putea fi căptușite cu zerouri pentru a le face lungi de 512 de puncte, permițând utilizarea DFT de 512 puncte. După convoluția în domeniul frecvență, semnalul de ieșire ar consta din 306 de eșantioane nonzero plus 206 de eșantioane cu o valoare zero. Capitolul 18 explică în detaliu această procedură.

De ce se numește convoluție circulară? Uitați-vă înapoi la fig. 9-9d și examinați perioada centrală, eșantioanele 256-511. Deoarece toate perioadele sunt la fel, porțiunea semnalului care iese din această perioadă spre dreapta este la fel cu cea care intră în aceasta din stânga. Dacă luați în considerare doar o singură perioadă, cum ar fi în (e), se pare că partea dreaptă a semnalului este cumva conectată la partea stângă. Imaginați-vă un șarpe mușcând coada proprie; eșantionul 255 este situat lângă eșantionul 0, la fel cum eșantionul 100 este situat lângă eșantionul 101. Când o parte a semnalului iese în dreapta, ea reapare în mod magic în stânga. Cu alte cuvinte, domeniul timp de N puncte se comportă ca și cum ar fi circular.

În ultimul capitol am pus întrebarea: contează cu adevărat dacă domeniul timp al DFT este privit ca fiind de N puncte, mai degrabă decât un semnal periodic infinit de lung de perioadă N? Convoluția circulară este un exemplu unde contează. Dacă semnalul din domeniul timp este înțeles a fi periodic, distorsiunea întâlnită în convoluția circulară poate fi explicată pur și simplu ca semnal care se extinde de la o perioadă la alta. În comparație, se ajunge la o concluzie des-tul de bizară dacă se iau în considerare doar N puncte din domeniul timp. Asta este, convoluția domeniului frecvență acționează ca și cum domeniul timp este într-un fel înfășurat într-un inel circular cu eșantionul 0 fiind poziționat lângă eșantionul N-1.