Преобразование Фурье над конечным полем

Дискретное преобразование Фурье над конечным полем — это один из видов дискретного преобразования Фурье для вектора $\bar{v}=(v_0,\;v_1,\;\ldots,\;v_{n-1}),\;v_i\in GF(q)$ над конечным полем GF(q), определяемое как вектор $\bar{V}=(V_1,\;V_2,\;\ldots,\;V_{n-1}),\;V_j\in GF(q^m)$, где n делит q^m − 1 при некотором целом положительном m, с компонентами, вычисляемыми как

$V_j=\sum_{i=0}^{n-1}\alpha^{ij}v_i,\quad j=0,\;1,\;\ldots,\;n-1,$

где α — элемент порядка n в поле GF(q^m) (то есть такой, что $\alpha^n=1,\;\alpha^k\neq 1,\;k<n$).

Индекс i можно назвать временем, а $\bar{v}$ — временной функцией или сигналом. Аналогично индекс j — частотой, а $\bar{V}$ — частотной функцией или спектром.

Обратное преобразование в данном случае определяется таким образом

$v_i=(n)^{-1}\sum_{j=0}^{n-1}\alpha^{-ij}V_j,\quad i=0,\;1,\;\ldots,\;n-1,$

где n интерпретируется как элемент (число) по модулю характеристики p поля GF(q), то есть $(n)=n\,\bmod\,p$.

См. также

• Конечное поле
• Многочлен над конечным полем
• Дискретное преобразование Фурье
• Быстрое преобразование Фурье
• Дискретное комплексное преобразование
• Оконное преобразование Фурье