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

Дискретное преобразование Фурье над конечным полем — один из видов дискретного преобразования Фурье для вектора ${\vec {v}}=(v_{0},\;v_{1},\;\ldots ,\;v_{n-1}),\;v_{i}\in GF(q^{m})$ над конечным полем $GF(q^{m})$, определяемое как вектор ${\vec {V}}=(V_{0},\;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)$ интерпретируется как элемент поля $GF(q^{m})$, то есть $(n)=n\cdot e$, где $e$ — нейтральный элемент поля по умножению.

См. также

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