Gyors Fourier-transzformáció

FFT technológia

Ez az útmutató tartalmazza a forráskódot az operációs szoftver számításához FFT, részletes magyarázatot arra, hogyan működik és elméleti alapon. Mindez megtalálható más oldalakon, de nehéz megtalálni, hogy készlet: a program és a magyarázatok és az elmélet, és az orosz.

Ha nincs ideje, vagy vágy, hogy foglalkozik az elmélet, akkor közvetlenül másolja a szöveget a program a C ++. Itt látható a header file és a forrás fft.h fft.cpp a gyors Fourier-transzformáció a beütések számát egyenlő a hatalom kettő. Szükség van ahhoz, hogy a funkció FFT. Itt látható a fejléc fájlt, és a forráskód minden (!) A minták száma. Ő egy kicsit lassabb, de a sebesség is ott van, kb Nlog2 N. hívása szükséges universal_fft funkciót.

meghatározzák

1. definíció

Mivel véges x0. x1. x2. XN-1 (általában komplex). A diszkrét Fourier-transzformáció (DFT), hogy keressen más szekvenciák X0. X1. X2. XN-1, amelynek elemeit a következő képlettel számoljuk:

2. meghatározás

Mivel véges X0. X1. X2. XN-1 (általában komplex). Az inverz diszkrét Fourier-transzformáció (DFT), hogy keressen más szekvenciák x0. x1. x2. XN-1, amelynek elemeit a következő képlettel számoljuk:

A fő jellemzője ezeknek transzformációk (ami lehet bizonyítani az érintett szakaszok a matematika), hogy egy sor fordulat (közvetlen konverzió) szekvencia, és ha majd alkalmazza az inverz transzformációt, megint kap az eredeti sorrendet.

meghatározása 3

forog az úgynevezett multiplikátor.

Tekintsük a tulajdonságok száma babrál tényezőket, amelyek szükségünk lesz a jövőben.

A felső ábrán fordult a szorzó nem indexet - mértékben. Ezért, ha ez egyenlő az egység, akkor ne írja:

Közvetlen Fourier-transzformáció lehet kifejezni fordult tényezők. Ennek eredményeként a (1) képlet a következő lesz:

Ezek a tényezők valóban indokolt a nevét. Döntetlen a komplex síkon, minden komplex szám, mint egy vektor származó eredetét. Mi képviseli a komplex szám exponenciális formában: újra j # 966;. ahol R - a modul, és a # 966; - érv. A modul hosszának felel meg a vektor, és az érvelés - a forgásszög:

Most némi fordult tényező. A egység egyenlő egység, és a fázis - 2π / N. Mint ismeretes, a szorzás a komplex számok képviselik exponenciális formában, ezek szorzatát modulok és érvek -ról. Majd szorozzuk az eredeti szám a perdület tényező nem változik a hossza a vektor, de megváltoztatják a szöget. Azaz, a vektor elforgatását akkora szögben, 2π / N (lásd. Az előző ábrán).

Ha most megnézi az általános képletű (3), világossá válik, geometriai jelentése a Fourier-transzformáció: az, hogy képviselje a N komplex számok, vektorok a beállított, az egyes összegeként vektorok a beállított forgatjuk többszörösei 2π / N.

Hírek Fórum
Knights-éter elmélet