Дискретное преобразование Фурье

Дискре́тное преобразова́ние Фурье́, преобразование вектора из $n$ комплексных чисел $x=(x_0, x_1, x_2,\ldots, x_{n-1})$ в другой вектор $y=(y_0, y_1, y_2, \ldots, y_{n-1})$ комплексных чисел, определяемое формулой $(1),$ которая зависит от выбора параметра $w_n$ – первообразного корня из единицы степени $n$ в поле комплексных чисел $$\tag{1}\text{ДПФ}_{n,w_n}:y_i =\sum_{j=0}^{n-1}{w_n}^{ij} x_j, \quad i = 0, 1, \dots, n-1.$$Дискретное преобразование Фурье может рассматриваться как аппроксимация более сложных конструкций: интегрального преобразования и ряда Фурье.