miksi haluamme käyttää DFT laskea lineaarisen kierre?

[neoflash]

Luin siitä oppikirja, että jos me PAD-sarjan tarpeeksi kauan, voimme käyttää DFT laskea lineaarisen convolve kahden sarjan.

Kysymykseni on, mikä on motivaatio tehdä sitä?

Toinen kysymys on se, että onko pehmuste on menossa aiheutuu vääristymiä on diskreetti Fourier-sarja verkkotunnuksen, mutta ei ajoissa alalla?

kiitos.

 

[zorro]

Hi neoflash,

suorittaa kierteen käyttäen FFT (ns. nopeasti konvoluutio) on nopeampi kuin suora kierre.
Jos sinulla on kaksi sequencies pituus N, monimutkaisuus suoraan konvoluutio on järjestyksessä N ^ 2.
Nopean kierteen, sinun täytyy tehdä kaksi FFT: n (suora ja käänteinen), jotka ovat monimutkaisia, jotta N * log2 (N), sekä spektrejä kertomalla, joiden monimutkaisuus N. Kaikkiaan on vain noin N 2 * N * log2 (N) toiminta sen sijaan noin N ^ 2.
Mikä lasketaan tällä tavalla on pyöreä kierre.Zero padding on tarpeen, että se vastaa tavallista järjestyksessä kierre.
Terveisin

Z

 

[Jessin]

Zorro kirjoitti:

Hi neoflash,suorittaa kierteen käyttäen FFT (ns. nopeasti konvoluutio) on nopeampi kuin suora kierre.

Jos sinulla on kaksi sequencies pituus N, monimutkaisuus suoraan konvoluutio on järjestyksessä N ^ 2.

Nopean kierteen, sinun täytyy tehdä kaksi FFT: n (suora ja käänteinen), jotka ovat monimutkaisia, jotta N * log2 (N), sekä spektrejä kertomalla, joiden monimutkaisuus N. Kaikkiaan on vain noin N 2 * N * log2 (N) toiminta sen sijaan noin N ^ 2.

Mikä lasketaan tällä tavalla on pyöreä kierre.
Zero padding on tarpeen, että se vastaa tavallista järjestyksessä kierre.

TerveisinZ