Dlatego chcemy wykorzystać do obliczenia DFT splotu liniowego?

[neoflash]

Czytam tekst z książki, że jeśli pad serii wystarczająco długo, możemy użyć DFT do obliczenia liniowe convolve dwóch serii. Moje pytanie brzmi: jaka jest motywacja robi? Inną kwestią jest to, że czy dopełnienie będzie ponosił zniekształceń jest dyskretny domeny szereg Fouriera, choć nie w dziedzinie czasu? dzięki.

 

[zorro]

Hi neoflash, wykonywania splotu FFT (tzw. szybki splot) jest szybsza niż bezpośrednie splotu. Jeśli masz dwie sekwencje N długość, złożoność bezpośredni skręt jest rzędu n ^ 2. Dzięki szybkiej splot, musisz wykonać dwa FFT jest (bezpośrednie i odwrotne), które mają złożoność rzędu N * log2 (N) oraz mnożenie widm, złożoność N. W sumie tylko około N +2 * N * log2 (N) operacji zamiast około N ^ 2. Co jest obliczana w ten sposób jest okrągły splot. Zero dopełnienie jest konieczne, że pasuje zwykły splot sekwencji. Pozdrawiam Z

 

[jessi]

[Quote = zorro] Hi neoflash, wykonywania splotu FFT (tzw. szybki splot) jest szybsza niż bezpośrednie splotu. Jeśli masz dwie sekwencje N długość, złożoność bezpośredni skręt jest rzędu n ^ 2. Dzięki szybkiej splot, musisz wykonać dwa FFT jest (bezpośrednie i odwrotne), które mają złożoność rzędu N * log2 (N) oraz mnożenie widm, złożoność N. W sumie tylko około N +2 * N * log2 (N) operacji zamiast około N ^ 2. Co jest obliczana w ten sposób jest okrągły splot. Zero dopełnienie jest konieczne, że pasuje zwykły splot sekwencji. Pozdrawiam Z [/quote] Dobre wyjaśnienie. Należy jeszcze raz podkreślić, że mądrze produkt dwóch DFT dotyczy okrągły splot dwóch odpowiadających dziedzinie czasu sekwencji. Zero-oadding jest zatem wymagane.