Дискре́тное преобразова́ние Фурье́ (ДПФ, классическое дискретное преобразование Фурье размера $n;$ англ. Discrete Fourier Transform – DFT), преобразование вектора из $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.$$В алгебре элемент $w$ некоторого поля характеристики $0$ называется первообразным корнем из $1,$ если $w^n = 1$ и $n$ степеней этого корня $w^0, w^1, w^2, w^3, \ldots, w^{n-1}$ попарно различны.

Как и в большинстве публикаций, в качестве параметра ДПФ размера $n$ в данной статье берётся первообразный корень $$w_n =e^{-2\pi i/n} = \cos(–2\pi /n) + i \sin(–2\pi /n).$$ДПФ может рассматриваться как аппроксимация более сложных конструкций: интегрального преобразования и ряда Фурье.

Число операций, выполняемых при «наивном» вычислении по определению

Считая $w_n$ заданным, числа ${w_n}^2, {w_n}^3,\ldots, {w_n}^{n-1}$ можно вычислить, выполнив $n-2$ умножения на $w_n.$ Поскольку ${w_n}^n = 1,$ каждый множитель ${w_n}^{ij}$ в $(1)$ равен ${w_n}^{ij\bmod n},$ т. е. равен одному из чисел ${w_n}^0, {w_n}^1, {w_n}^2, {w_n}^3, \ldots, {w_n}^{n-1},$ и каждое $y_i$ может быть вычислено по формуле $(1)$ путём выполнения $(n-1)$ умножений и $(n-1)$ сложений. В итоге вычисление $\text{ДПФ}_{n,w_n},$ исходя из определения, требует проведения $n-2 + n\cdot(2n-2)$ арифметических операций над комплексными числами (учитываются операции сложения, вычитания, умножения комплексных чисел и операция деления комплексного числа на вещественное число). Используя обозначение «О большое», можно сказать, что наивное вычисление ДПФ размера $n$ по определению требует проведения $O(n^2)$ арифметических операций. Наивный алгоритм вычисления ДПФ не оптимален. Существует целый класс алгоритмов, объединённых общим названием «быстрое преобразование Фурье», сокращённо БПФ (англ. Fast Fourier Transform – FFT), позволяющих вычислить ДПФ любого размера $n,$ выполнив $O(n\,\log_2n)$ арифметических операций над комплексными числами.

Явная формула преобразования, обратного ДПФ

Введём многочлен одной переменной степени $n-1$ $$X(t) = x_0 + x_1 t + x_2 t^2 + x_3 t^3 +\ldots+ x_{n-1} t^{n-1}$$и обозначим $w_n$ как $w.$ В таких обозначениях $\text{ДПФ}_{n,w_n}$ сопоставляет набору коэффициентов $(x_0, x_1, x_2, \ldots, x_{n-1})$ многочлена $X(t)$ набор значений $(y_0, y_1, y_2, \ldots, y_{n-1})$ этого многочлена в заданных точках $(1,w,w^2,w^3,\ldots,w^{n-1}).$ Обратное дискретное преобразование Фурье проводит интерполяцию – вычисляет по набору значений $(y_0, y_1, y_2, \ldots, y_{n-1})$ многочлена $X(t)$ в заданных точках $(1,w,w^2,w^3,\ldots,w^{n-1})$ коэффициенты многочлена $(x_0, x_1, x_2, \ldots, x_{n-1}).$

В матричной форме $(1)$ переписывается как $y^T = W_{n,w}\,x^T,$ где где верхний индекс $T$ означает транспонирование и $$\tag{2}W_{n,w}=\begin{Vmatrix} 1&1&1&1&\ldots&1\\ 1&w^1&w^2&w^3&\ldots&w^{n-1}\\ 1&w^2&w^4&w^6&\ldots&w^{2(n-1)}\\ &&&\ldots\\ 1&w^{n-1}&w^{2(n-1)}&w^{3(n-1)}&\ldots&w^{(n-1)(n-1)} \end{Vmatrix}.$$Матрица $(2)$ является частным случаем матрицы Вандермонда. Проверим, что обратной к матрице $W_{n,w}$ является матрица $1/n\cdot W_{n,\bar{w}},$ где $\bar w$ – комплексное число, сопряжённое к $w$ и равное $1/w.$ Для этого покажем, что $$\tag{3}W_{n,w}W_{n,\bar{w}}=NE,$$где $E$ – единичная матрица $n×n.$

Нумеруя строки и столбцы рассматриваемых матриц, начиная с нуля, выпишем элемент произведения матриц $W_{n,w}W_{n,\bar{w}},$ лежащий на пересечении $i$-й строки с $j$-м столбцом. Этот элемент равен сумме $n$ попарных произведений элементов $i$-й строки матрицы $W_{n,w},$ равных $$1, w^i, (w^i)^2,\ldots, (w^i)^{n-1},$$и элементов $j$-го столбца матрицы $W_{n,\bar{w}},$ равных $$1, w^{-j}, (w^{-j})^2,\ldots, (w^{-j})^{n-1}.$$Эта сумма является суммой геометрической прогрессии со знаменателем $w^{i-j}:$ $$\tag{4}S = 1 + w^{i-j} +(w^{i-j})^2 + \ldots +(w^{i-j})^{n-1}.$$Умножив $(4)$ почленно на $w^{i-j},$ получим$$\tag{5}w^{i-j}S  = w^{i-j} +(w^{i-j})^2 +\ldots +(w^{i-j})^{n-1} +(w^{i-j})^n,$$где последнее слагаемое, очевидно, равно $1.$ Сравнивая $(4)$ и $(5),$ видим, что правая часть $(5)$ получается из правой части $(4)$ перестановкой 1-го слагаемого в конец суммы и потому эти правые части равны. Значит, $S = w^{i-j} S$ , или $(1- w^{i-j})S = 0.$

В случае $i=j$ сумма $S$ превращается в сумму из $n$ единиц и равна $n.$ В случае же $i\ne j,$ имеем $w^i\ne w^j,$ т. к. $w$ – первообразный корень из $1,$ и поэтому число $w^{i-j}$ не равно $1.$ Поскольку в поле комплексных чисел, как и во всяком поле, нет делителей нуля, из равенства $(1- w^{i-j})S = 0$ вытекает $S=0.$

Таким образом, мы доказали, что каждый элемент главной диагонали матрицы $W_{n,w}W_{n,\bar{w}}$ равен $n,$ а остальные элементы этой матрицы равны $0,$ т. е. доказали $(3).$ Тем самым показано, что преобразование, обратное к дискретному преобразованию Фурье размера $n,$ может быть выполнено с помощью ДПФ размера $n$ и последующих $n$ делений комплексного числа на вещественное число $n.$ Значит, с использованием БПФ обратное ДПФ может быть выполнено столь же быстро, как и прямое ДПФ, а именно за $O(n\,\log_2n)$ арифметических операций. Этот факт лежит в основе алгоритмов т. н. быстрого умножения многочленов.

По определению, значение $n$-значного $d$-ичного числа есть не что иное, как значение в точке $d$ многочлена, коэффициентами которого являются цифры числа. Поэтому быстрое умножение многочленов над комплексными числами может быть положено в основу алгоритмов быстрого умножения многозначных чисел. С момента появления теории интегральных преобразований Фурье математики и физики знали, что свёртка функций может быть выполнена путём поточечного умножения их преобразований Фурье. Идея же применить этот факт к комбинаторной задаче умножения многозначных чисел появилась впервые в статье студента 4-го курса механико-математического факультета МГУ А. Тоома (Тоом. 1963). С тех пор эта идея используется во всех алгоритмах быстрого умножения многозначных чисел.

При использовании ДПФ и БПФ в задаче ускорения умножения многозначных чисел и задачах шифрования оказывается полезным перейти от комплексных чисел к конечным числовым системам, элементы которых могут быть представлены конечными двоичными кодами. В качестве таких числовых систем могут использоваться конечные поля при условии существования в них первообразного корня из $1$ степени $n.$ А поскольку подбор полей, в которых существует первообразный корень нужной степени $n,$ может оказаться затруднительным, вместо поля можно работать с кольцами вычетов по составному модулю и конечными ассоциативными коммутативными кольцами с единицей. При этом придётся использовать определение первообразного корня из $1$ степени $n,$ служащего параметром ДПФ (см. Факторкольцо).

Так возникает теория т. н. теоретико-числовых ДПФ и БПФ.

Наряду с обычным (одномерным) ДПФ может быть определено и многомерное дискретное преобразование Фурье.