WikiSort.ru - Не сортированное

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 21 февраля 2017 года.

Дискретное преобразование Фурье над конечным полем — это один из видов дискретного преобразования Фурье для вектора ${\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}$ — нейтральный элемент поля по умножению.

См. также

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