11: Дискретні перетворення Фур'є

Дискретне перетворення Фур'є (DFT) - це дискретизована версія перетворення Фур'є, яка широко використовується в числовому моделюванні та аналізі. З огляду на набір$N$ чисел$\{f_0, f_1, \dots, f_{N-1}\}$, DFT виробляє інший набір$N$$N$ чисел$\{F_0, F_1, \dots, F_{N-1}\}$, визначених наступним чином:

$$\mathrm{DFT}\Big\{f_0, f_1, \dots, f_{N-1}\Big\} = \Big\{F_0, F_1, \dots, F_{N-1}\Big\} \qquad\mathrm{where}\quad F_n = \sum_{m=0}^{N-1} e^{-2\pi i \frac{mn}{N}}\, f_m.$$

Оберненим цим перетворенням є зворотне дискретне перетворення Фур'є (IDFT):

$$\mathrm{IDFT}\Big\{F_0, F_1, \dots, F_{N-1}\Big\} = \Big\{f_0, f_1, \dots, f_{N-1}\Big\} \qquad\mathrm{where}\quad f_m = \frac{1}{N} \sum_{n=0}^{N-1} e^{2\pi i \frac{mn}{N}}\, F_n.$$

Зворотний зв'язок між DFT та IDFT просто довести, використовуючи особистість

$$\sum_{m=0}^{N-1} e^{\pm 2\pi i \frac{m(n-n')}{N}} = N \delta_{nn'},$$

де$\delta_{nn'}$ позначає дельту Кронекера. Ця ідентичність походить від формули геометричних рядів.