Fourier-transzformáció

Legyen az $f \,$ függvény Lebesgue-integrálható az $I \,$ intervallumon. Ekkor $f \,$ Fourier-transzformáltja az

$\mathrm Ff= \int _I f(t)e^{-2 \pi ixt}dt \,$

függvény.

A Fourier-transzformáció kiterjeszthető a négyzetesen Lebesgue-integrálható függvények terére:

$\mathrm Ff= \lim _{n \rightarrow \infty}\int _I f_n(t)e^{-2 \pi ixt}dt \,$,

ahol az összes $f_n \,$ függvény integrálható. Ha az $I \,$ intervallum végtelen, akkor ez egy valódi kiterjesztés.

A Fourier-transzformáció disztribúciókra is definiálható.

Tulajdonságai

• A Fourier-transzformáció korlátos lineáris operátor.
• Unitér

Vezessük be a következő műveleteket:

$(\tau _hf)(x)=f(x+h) \,$ transzláció

$(\nu _hf)(x)=hf(x) \,$ moduláció

$(\delta _hf)(x)=f(hx) \,$ dilatáció

Ezek a műveletek a következő kapcsolatban vannak a Fourier-transzformációval:

$F\tau _hf(x)=\nu _hFf(x) \,$

$F\nu _hf(x)=\tau _{-h}Ff(x) \,$

$F\delta _hf(x)=\frac{1}{h}\delta_{\frac{1}{h}}Ff(x) \,$

Jelölje $* \,$ a konvolúciót. Ekkor

$F(f*g)=Ff \cdot Fg \,$

Legyen $Mf=2 \pi itf(t) \,$ és jelölje $f \,$ deriváltját $Df \,$. Ha $f \,$ és $Mf \,$ is integrálható, akkor $Ff \,$ mindenütt differenciálható, és

$DFf = -FMf \,$

$FDf = MFf \,$

A Fourier-transzformáció invertálható:

$\mathrm F^{-1}f= \int _I f(t)e^{2 \pi ixt}dt \,$

Fourier-sorok

A periodikus függvények Fourier-sorba fejthetők:

$f(t)= \sum _{k=-\infty}^{\infty} c_ke^{-2 \pi i\nu _0k}$

ahol $\nu _0 \,$ az alapfrekvencia, a periódus reciproka.

• A differenciálható függvények Fourier-sora pontonként konvergens, ami nem igaz minden integrálható függvényre (Kolmogorov konstrukciója).
• Sőt, van folytonos függvény, aminek Fourier-sora periódusonként egy pontban divergál (Reiman).
• A Dirichlet-Jordan konvergenciatétel szerint az $f(x) \,$ korlátos változású függvény Fourier-sora minden $x \,$ pontban $f(x) \,$-beli jobb és bal oldali határértékének számtani közepéhez tart.
• A négyzetesen integrálható függvények Fourier-sora normában konvergens. Ez Riesz-Fischer eredménye.

Példák

• Háromszögjel:

A háromszögjel különböző közelítései

A háromszögjel fázisszögtől függően szinuszos vagy koszinuszos kifejezésekkel közelíthető. A képletekben $h \,$ jelöli az amplitúdót:

$\begin{array}{rl} f(t) =& -\frac{8h}{\pi^2}\left[ {\cos{\omega t} + \frac{1}{3^2} \cos{3 \omega t} + \frac{1}{5^2} \cos{5 \omega t} + \cdots}\right] \\[.6em] =& -\frac{8h}{\pi^2} \sum_{k=1}^\infty \dfrac{ \cos ((2k-1) \omega t)}{(2k-1)^2} \end{array}$

$\begin{array}{rl} f(t) =& \frac{8h}{\pi^2}\left[ {\sin {\omega t} - \frac {1}{3^2}\sin{3 \omega t} + \frac {1}{5^2}\sin {5 \omega t} \mp \cdots}\right] \\[.6em] =& \frac {8h}{\pi^2} \sum_{k=1}^\infty (-1)^{k-1} \dfrac{ \sin((2k-1) \omega t)}{(2k-1)^2} \end{array}$

• Négyszögjel:

A négyszögjel különböző közelítései

Hasonlóan a négyszögjel:

$\begin{array}{rl} f(t) =& \frac{4h}{\pi}\left[ {\sin {\omega t} + \frac {1}{3}\sin{3 \omega t} + \frac {1}{5}\sin{5 \omega t} + \cdots}\right] \\[.6em] =& \frac{4h}{\pi} \sum_{k=1}^\infty \dfrac{ \sin\left( (2k-1)\omega t \right) }{2k-1} \end{array}$

$\begin{array}{rl} f(t) =& \frac{4h}{\pi}\left[ {\cos {\omega t} - \frac {1}{3}\cos{3 \omega t} + \frac {1}{5}\cos{5 \omega t} \mp \ldots}\right] \\[.6em] =& \frac{4h}{\pi} \sum_{k=1}^\infty (-1)^{k-1} \dfrac{\cos\left( (2k-1)\omega t \right)}{ 2k-1} \end{array}$

• Fűrészfogjel: (növekvő)

A fűrészfogjel különböző közelítései

Ugyanígy közelíthetők szinuszos kifejezésekkel a pontra szimmetrikus függvények. Itt a váltakozó előjelek fáziseltolódást eredményeznek:

$\begin{array}{rl} f(t) =&- \frac{2h}{\pi}\left[ {\sin {\omega t} - \frac {1}{2}\sin{2 \omega t} + \frac {1}{3}\sin {3 \omega t} \mp \cdots}\right] \\[.6em] =& - \frac {2h}{\pi}\sum_{k=1}^{\infty}(-1)^{k-1} \dfrac {\sin k \omega t}{k} \end{array}$

• Szinuszjel:

A szinuszjel különböző közelítései

$\begin{array}{rl} f(t) =& h\left| \sin {\omega t} \right|\\[.6em] =& \frac{4h}{\pi}\left[ \frac{1}{2} - \frac { \cos {2 \omega t}}{3}-\frac { \cos {4 \omega t}}{15}-\frac { \cos {6 \omega t}}{35}- \cdots\right] \\[.6em] =& \frac{2h}{\pi} - \frac{4h}{\pi} \sum_{k=1}^{\infin} \dfrac { \cos {2 k\omega t}}{(2k)^2-1} \end{array}$

Diszkrét Fourier-transzformáció

A Fourier-transzformációnak diszkrét változata is van:

$\mathrm Ff= \sum _{-\infty}^{\infty} f(n)e^{-2 \pi ixn}$

Sokszor ezt használják a gyakorlatban, mert csak véges sok mintavételezés lehetséges. A függvény értelmezési tartományáról felteszik, hogy diszkrét és véges. Nem tévesztendő össze a Fourier-sorral.

Gyors Fourier-transzformáció

A gyors Fourier-transzformáció (FFT = Fast Fourier Transform) a diszkrét Fourier-transzformált kiszámítására szolgál. Ehhez $N = 2 ^n \,$ egyenközű mintavétel szükséges, ahol $n \geq 6$. Műveletigénye $N \log N \,$. A mintavételezés frekvenciáját úgy kell választani, hogy legalább kétszer akkora legyen, mint a maximális feldolgozandó frekvencia, különben torz kép jön létre. Több perióduson át kell mintavételezni úgy, hogy a mintavételezés máshova essen az egyes periódusokban. Például, ha a jel frekvenciája 1 kHz, akkor jobb 2100 Hz-cel mintavételezni, mint 2000-rel, és még jobb mondjuk 4100 Hz-cel, vagy még ennél is nagyobb frekvenciával.

A sor:

$y(\omega)=\frac{T}{\sqrt {2\pi}}\sum _{n=-\infty}^{\infty}x_ne^{-i \omega t_n}$

ahol

$x_n=\frac{1}{\sqrt {2\pi}}\int _{-\pi F}^{\pi F}y_ne^{i \omega t_n}d \omega$

Algoritmus

A gyors Fourier-transzformáció egy rekurzív algoritmus, ami az Oszd meg és uralkodj! elvén működik.

Legelőször is idézzük fel, hogy a $2n \,$ pontú diszkrét Fourier-transzformáció a következőképpen definiálható:

$f_j = \sum_{k=0}^{2n-1} x_k \;e^{-\frac{2\pi i}{2n} jk } \qquad j = 0,\dots,2n-1.$

Legyenek a páros indexű együtthatók

$x'_0=x_0,\ x'_1=x_2, \ ..., \ x'_{n-1} = x_{2n-2} \,$

és ezek diszkrét Fourier-transzformálja

$f'_0,\ ... ,\ f'_{n-1} \,$;

hasonlóan, jelölje a páratlan indexű együtthatókat

$x''_0 = x_1,\ x''_1 = x_3,\ ...,\ x''_{n-1} = x_{2n-1} \,$

és legyen ezek diszkrét Fourier-transzformáltja

$f''_0,\ ...,\ f''_{n-1} \,$.

Ekkor:

$\begin{matrix} f_j & = & \sum_{k=0}^{n-1} x_{2k} e^{-\frac{2\pi i}{2n} j(2k)} + \sum_{k=0}^{n-1} x_{2k+1} e^{-\frac{2\pi i}{2n} j(2k+1)} \\ \\ & = & \sum_{k=0}^{n-1} x'_{k} e^{-\frac{2\pi i}{n} jk} + e^{-\frac{\pi i}{n}j} \sum_{k=0}^{n-1} x''_k e^{-\frac{2\pi i}{n} jk} \\ \\ & = & \left\{ \begin{matrix} f'_j + e^{-\frac{\pi i}{n}j} f''_j & \mbox{ha } j<n \\ \\ f'_{j-n} - e^{-\frac{\pi i}{n}(j-n)} f''_{j-n} & \mbox{ha } j \geq n \end{matrix} \right. \end{matrix}$

Pszeudokód

Az algoritmus pszeudokódja:

$\mathrm{function}\ \operatorname{fft}(n,\vec f):$

$\mathrm{if}\ (n = 1)$

$\mathrm{return}\ \vec f$

$\mathrm{else} \$

$\vec g = \operatorname{fft}\left(\tfrac{n}{2},( f_0, f_2, \ldots ,f_{n-2})\right)$

$\vec u = \operatorname{fft}\left(\tfrac{n}{2}, (f_1, f_3, \ldots ,f_{n-1})\right)$

$\mathrm{for} \ k = 0 \ \mathrm{to} \ \tfrac{n}{2}-1$

$\begin{align} c_k = g_k + u_k \cdot e^{-2 \pi i k/n} \\ c_{k+n/2} = g_k - u_k \cdot e^{-2 \pi i k/n} \end{align}$

$\mathrm{return}\ \vec c$

Alkalmazások

A Fourier-transzformációknak és a Fourier-soroknak számos alkalmazásuk van:

• a valószínűségszámítás, statisztika elméletében
• a jelfeldolgozásban
• a hang- és videotechnikában
• a rezgésanalízisben
• analóg áramkörök leírásában
• spektrométerekben
• differenciálegyenletek megoldásában

Források

• S. Bochner, K. Chandrasekharan: Fourier Transforms. Princeton Book Comp. Publ., 2001, ISBN 0-691-09578-7.
• O. Föllinger, M. Kluwe: Laplace-, Fourier- und z-Transformation. Hüthig, 2003, ISBN 3-7785-2911-0.
• B. Lenze: Einführung in die Fourier-Analysis. Logos Verlag, Berlin 2000, ISBN 3-931216-46-2.
• M. J. Lighthill: Introduction to Fourier Analysis and Generalised Functions. Cambridge University Press, Cambridge 2003, ISBN 0-521-09128-4.
• A. Papoulis: The Fourier Integral and Its Applications. McGraw-Hill, New York 1962, ISBN 0-07-048447-3.
• E. M. Stein, R. Shakarchi: Fourier Analysis: An Introduction. Princeton University Press, Princeton 2003, ISBN 0-691-11384-X.
• James W. Cooley, John W. Tukey: An algorithm for the machine calculation of complex Fourier series. In: Math. Comput. 19, 1965, S. 297–301.
• C. M. Rader: Discrete Fourier transforms when the number of data samples is prime. In: Proc. IEEE 56, 1107–1108 (1968).
• Leo I. Bluestein: A linear filtering approach to the computation of the discrete Fourier transform. In: Northeast Electronics Research and Engineering Meeting Record 10, 1968, S. 218-219.
• Georg Bruun: z-Transform DFT filters and FFTs. In: IEEE Trans. on Acoustics, Speech and Signal Processing (ASSP) 26, Nr. 1, 1978, S. 56-63.
• M. T. Heideman, D. H. Johnson, C. S. Burrus : Gauss and the History of the Fast Fourier Transform. In: Arch. Hist. Sc. 34, Nr. 3, 1985.
• Alan V. Oppenheim, Ronald W. Schafer: Zeitdiskrete Signalverarbeitung. 3. Auflage. R. Oldenbourg Verlag, München/Wien 1999, ISBN 3-486-24145-1.
• E. Oran Brigham: FFT. Schnelle Fourier-Transformation. R. Oldenbourg Verlag, München/Wien 1995, ISBN 3-486-23177-4.
• Fourier-transzformáció FFT programmal
• Stoyan-Takó a Fourier-transzformációról
• Periódusanalízis
• A Fourier-transzformáció, társai és alkalmazásaik
• Fourier-transzformációs optikai spektroszkópia
• Frekvenciatartomány, Fourier-transzformáció, Fourier-sor, DFT, DTFT
• A Fourier-transzformáció rövid elmélete és gyakorlati alkalmazása
• Fourier-sorok, Fourier-transzformáció, egységimpulzus