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

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

$V_j=\underset{i=0}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{\mathrm{\alpha <!--\; \alpha \; -->}}^{ij}{v}_i,j=0,1,\dots <!--\; \dots \; -->,n-<!--\; -\; -->1,$$V_{j}=\sum _{{i=0}}^{{n-1}}\alpha ^{{ij}}v_{i},\quad j=0,\;1,\;\ldots ,\;n-1,$

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

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

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

$v_i=(n{)}^{-<!--\; -\; -->1}\underset{j=0}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{\mathrm{\alpha <!--\; \alpha \; -->}}^{-<!--\; -\; -->ij}{V}_j,i=0,1,\dots <!--\; \dots \; -->,n-<!--\; -\; -->1,$$v_{i}=(n)^{-1}\sum _{j=0}^{n-1}\alpha ^{-ij}V_{j},\quad i=0,\;1,\;\ldots ,\;n-1,$

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

См. такжеПравить

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