Anzahl Multiplikationen DFT, FFT

[burga (Gast)]

Bei einer Blocklänge von N=1024 hätte ich bei einer DFT N^2 
Multiplikationen. Was wenn ich aber ein Bild der Größe 1024x1024 habe 
sind es 2*(N^2)?

[Egon D. (Gast)]

burga schrieb:

> Bei einer Blocklänge von N=1024 hätte ich bei
> einer DFT N^2 Multiplikationen.

Ja.


> Was wenn ich aber ein Bild der Größe 1024x1024 habe
> sind es 2*(N^2)?

Nee: 2*1024*(N^2) = 2*(N^3)


Jede Zeile mit 1024 Pixeln kostet N^2 Operationen, das
Bild hat 1024 Zeilen, und die ganze Aktion muss nochmal
in Spaltenrichtung wiederholt werden.

[Kalle (Gast)]

Egon D. schrieb:
> 2*1024*(N^2) = 2*(N^3)

Interessant

[leo (Gast)]

Kalle schrieb:
> Egon D. schrieb:
>> 2*1024*(N^2) = 2*(N^3)
>
> Interessant

Yepp. Stimmt wohl ∀ N ∈ 1024

leo

[Egon D. (Gast)]

leo schrieb:

> Kalle schrieb:
>> Egon D. schrieb:
>>> 2*1024*(N^2) = 2*(N^3)
>>
>> Interessant
>
> Yepp. Stimmt wohl ∀ N ∈ 1024

... was auf unbegreifliche und mystische Weise mit der
Angabe "Blocklänge N=1024" zusammenzuhängen scheint.

Wunder über Wunder...

[burga (Gast)]

Für N habe ich die 1024 vorgesehen, also 2*(1024^2)?

[burga (Gast)]

Was stimmt den nun, sind es 1024*(1024^2) Multiplikationen?

[Mager (Gast)]

burga schrieb:

> Was stimmt den nun, sind es 1024*(1024^2) Multiplikationen?

Zu faul um zu suchen? Beschäftige dich gefälligst mit der Materie.