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

Дискретное преобразование Фурье над конечным полем — это один из видов дискретного преобразования Фурье для вектора ${\displaystyle {\vec {v}}=(v_{0},\;v_{1},\;\ldots ,\;v_{n-1}),\;v_{i}\in GF(q^{m})}$ над конечным полем ${\displaystyle GF(q^{m})}$, определяемое как вектор ${\displaystyle {\vec {V}}=(V_{0},\;V_{1},\;V_{2},\;\ldots ,\;V_{n-1}),\;V_{j}\in GF(q^{m})}$, где ${\displaystyle n}$ делит ${\displaystyle q^{m}-1}$ при некотором целом положительном ${\displaystyle m}$, с компонентами, вычисляемыми как

${\displaystyle V_{j}=\sum _{i=0}^{n-1}\alpha ^{ij}v_{i},\quad j=0,\;1,\;\ldots ,\;n-1,}$

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

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

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

${\displaystyle v_{i}=(n)^{-1}\sum _{j=0}^{n-1}\alpha ^{-ij}V_{j},\quad i=0,\;1,\;\ldots ,\;n-1,}$

где ${\displaystyle (n)}$ интерпретируется как элемент поля ${\displaystyle GF(q^{m})}$, то есть ${\displaystyle (n)=n\cdot e}$, где ${\displaystyle e}$ — нейтральный элемент поля по умножению.