de ce vrem DFT folosi pentru a calcula convoluţia liniară?

[neoflash]

Am citit textul din cartea pe care, dacă ne-pad serie suficient de lung, putem folosi pentru a calcula DFT strânge liniară între cele două serii. Întrebarea mea este ceea ce este motivaţia de a face asta? O altă întrebare este că dacă se va padding să suporte denaturarea este discret Fourier serie de domeniu, chiar dacă nu în domeniul de timp? mulţumesc.

 

[zorro]

Bună neoflash, efectuarea de convoluţie utilizând FFT (aşa-numita convoluţie rapid) este mai rapid decât convoluţie directă. Dacă aveţi două sequencies de lungime N, complexitatea de convoluţie directă este de ordinul N ^ 2. Cu convoluţiei rapid, trebuie să efectuaţi două FFT (de directă şi inversă), care au complexitatea ordinea de N * log2 (N), plus multiplicarea spectre, cu complexitatea N. În total, există doar aproximativ N +2 * N * log2 operaţiunilor în loc de aproximativ N ^ 2. Ceea ce se calculează în acest mod este de convoluţie circulară. Zero padding este necesară pentru că se potriveşte de convoluţie secvenţă obişnuită. Salutari Z

 

[jessi]

[Quote = Zorro] Buna neoflash, efectuarea de convoluţie utilizând FFT (aşa-numita convoluţie rapid) este mai rapid decât convoluţie directă. Dacă aveţi două sequencies de lungime N, complexitatea de convoluţie directă este de ordinul N ^ 2. Cu convoluţiei rapid, trebuie să efectuaţi două FFT (de directă şi inversă), care au complexitatea ordinea de N * log2 (N), plus multiplicarea spectre, cu complexitatea N. În total, există doar aproximativ N +2 * N * log2 operaţiunilor în loc de aproximativ N ^ 2. Ceea ce se calculează în acest mod este de convoluţie circulară. Zero padding este necesară pentru că se potriveşte de convoluţie secvenţă obişnuită. În ceea ce priveşte Z [/quote] buna explicatie. Noi trebuie să subliniem din nou faptul că înţelept-produsul a două DFT se referă la convoluţie circulară a celor două domenii de timp corespunzătoare secvenţe. Zero-oadding este astfel necesară.