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

Дискретное преобразование Фурье над конечным полем — это один из видов дискретного преобразования Фурье для вектора $\vec v =(v_0,\;v_1,\;\ldots,\;v_{n-1}),\;v_i\in GF(q)$ над конечным полем $GF(q)$, определяемое как вектор $\vec 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,$

где $\alpha$ — элемент порядка $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$.

См. также

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