Versionen fra 11. mar. 2013, 14:51 redigér Addbot (diskussion \| bidrag) Botter 151.154 edits m Bot: Migrerer 25 interwikilinks, som nu leveres af Wikidata på d:q623950 ← Gå til forrige forskel		Versionen fra 18. sep. 2014, 16:48 redigér fjern redigering Wolf~dawiki (diskussion \| bidrag) 111 edits m Indledende kommentar om, at der er tale om en radix 2 FFT, tilføjet. Radix 4 FFT nævnt (bygger på undertegnedes ekspertviden i feltet). Tag: Visuel redigering Gå til næste forskel →
Linje 12: == Algoritme == De hyppigst anvendte algoritmer bygger på et "del og hersk"-princip. I den såkaldte radix 2-FFT opdeles [[Vektor (matematik)\|Serien]] ~~opdeles~~ i to mindre serier, som derefter hver især opdeles igen ved [[Rekursiv\|rekursion]], indtil man når frem til så små serier, at de nemt kan transformeres. Metoden beskrives her ved pseudo-kode. Serien udtrykkes ved en vektor af [[Komplekse tal\|komplekse værdier]]: Linje 193: == Alternative metoder == Den her viste ~~metode~~radix 2 FFT er den mest udbredte algoritme i [[DSP]]-kode. Den bygger på, at længden af serien reduceres ved at dele den lige over i to halvdele. Heraf kommer kravet om, at ''n'' skal være en potens af 2. Deles serien op i fire dele, kaldes algoritmen for en radix 4 FFT, og på en processor med mange dataregistre kan den være markant hurtigere end radix 2 FFT-algoritmen. Der er senere udviklet metoder, hvor man udnytter primfaktoropløsning af ''n''. Når ''m'' indgår som [[Faktor (matematik)\|primfaktor]] i ''n'', så kan serien opdeles i ''m'' mindre serier, som hver har længden ''n / m''. Disse kan så igen opdeles, indtil længden af serierne selv bliver et [[primtal]].

Fast Fourier Transform: Forskelle mellem versioner