22.10.2021

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


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

V j = ∑ i = 0 n − 1 α i j v i , j = 0 , 1 , … , n − 1 , {displaystyle V_{j}=sum _{i=0}^{n-1}alpha ^{ij}v_{i},quad j=0,;1,;ldots ,;n-1,}

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

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

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

v i = ( n ) − 1 ∑ j = 0 n − 1 α − i j V j , i = 0 , 1 , … , n − 1 , {displaystyle v_{i}=(n)^{-1}sum _{j=0}^{n-1}alpha ^{-ij}V_{j},quad i=0,;1,;ldots ,;n-1,}

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






Яндекс.Метрика