Дискретное преобразование Фурье над кольцом
Обобщение преобразования Фурье на любое кольцо
Преобразования Фурье

В математике дискретное преобразование Фурье над кольцом обобщает дискретное преобразование Фурье (ДПФ) функции, значениями которой обычно являются комплексные числа , над произвольным кольцом .

Определение

Пусть R — любое кольцо , пусть — целое число, и пусть — главный корень степени n из единицы, определяемый как: [1] н ≥ 1 {\displaystyle n\geq 1} α ∈ Р {\displaystyle \альфа \в R}

α н = 1 ∑ дж = 0 н − 1 α дж к = 0  для  1 ≤ к < н {\displaystyle {\begin{align}&\alpha ^{n}=1\\&\sum _{j=0}^{n-1}\alpha ^{jk}=0{\text{ для }}1\leq k<n\end{align}}} ( 1 )

Дискретное преобразование Фурье отображает n -кортеж элементов R в другой n -кортеж элементов R согласно следующей формуле: ( в 0 , … , в н − 1 ) {\displaystyle (v_{0},\ldots,v_{n-1})} ( ф 0 , … , ф н − 1 ) {\displaystyle (f_{0},\ldots ,f_{n-1})}

ф к = ∑ дж = 0 н − 1 в дж α дж к . {\displaystyle f_{k}=\sum _{j=0}^{n-1}v_{j}\alpha ^{jk}.} ( 2 )

По соглашению, кортеж находится во временной области , а индекс j называется временем . Кортеж находится в частотной области , а индекс k называется частотой . Кортеж также называется спектром . Эта терминология происходит из приложений преобразований Фурье в обработке сигналов . ( в 0 , … , в н − 1 ) {\displaystyle (v_{0},\ldots,v_{n-1})} ( ф 0 , … , ф н − 1 ) {\displaystyle (f_{0},\ldots ,f_{n-1})} ( ф 0 , … , ф н − 1 ) {\displaystyle (f_{0},\ldots ,f_{n-1})} ( в 0 , … , в н − 1 ) {\displaystyle (v_{0},\ldots,v_{n-1})}

Если R — область целостности (включающая поля ), то достаточно выбрать в качестве примитивного корень n-й степени из единицы , что заменяет условие ( 1 ) на: [1] α {\displaystyle \альфа}

α к ≠ 1 {\displaystyle \альфа ^{k}\neq 1} для 1 ≤ к < н {\displaystyle 1\leq k<n}
Доказательство

Возьмите с . Так как , , давая: β = α к {\displaystyle \beta =\alpha ^{k}} 1 ≤ к < н {\displaystyle 1\leq k<n} α н = 1 {\displaystyle \альфа ^{n}=1} β н = ( α н ) к = 1 {\displaystyle \beta ^{n}=(\alpha ^{n})^{k}=1}

β н − 1 = ( β − 1 ) ( ∑ дж = 0 н − 1 β дж ) = 0 {\displaystyle \beta ^{n}-1=(\beta -1)\left(\sum _{j=0}^{n-1}\beta ^{j}\right)=0}

где сумма совпадает с ( 1 ). Так как — примитивный корень из единицы, . Так как R — область целостности, сумма должна быть равна нулю. ∎ α {\displaystyle \альфа} β − 1 ≠ 0 {\displaystyle \beta -1\neq 0}

Другое простое условие применяется в случае, когда n является степенью двойки: ( 1 ) можно заменить на . [1] α н / 2 = − 1 {\displaystyle \альфа ^{n/2}=-1}

Обратный

Обратное дискретное преобразование Фурье задается как:

в дж = 1 н ∑ к = 0 н − 1 ф к α − дж к . {\displaystyle v_{j}={\frac {1}{n}}\sum _{k=0}^{n-1}f_{k}\alpha ^{-jk}.} ( 3 )

где — мультипликативная обратная величина n в R (если эта обратная величина не существует, ДПФ не может быть инвертирована). 1 / н {\displaystyle 1/n}

Доказательство

Подставляя ( 2 ) в правую часть ( 3 ), получаем

1 н ∑ к = 0 н − 1 ф к α − дж к = 1 н ∑ к = 0 н − 1 ∑ дж ′ = 0 н − 1 в дж ′ α дж ′ к α − дж к = 1 н ∑ дж ′ = 0 н − 1 в дж ′ ∑ к = 0 н − 1 α ( дж ′ − дж ) к . {\displaystyle {\begin{aligned}&{\frac {1}{n}}\sum _{k=0}^{n-1}f_{k}\alpha ^{-jk}\\={} &{\frac {1}{n}}\sum _{k=0}^{n-1}\sum _{j'=0}^{n-1}v_{j'}\alpha ^{j 'k}\alpha ^{-jk}\\={}&{\frac {1}{n}}\sum _{j'=0}^{n-1}v_{j'}\sum _{ k=0}^{n-1}\alpha ^{(j'-j)k}.\end{aligned}}}

Это в точности равно , потому что когда (по ( 1 ) с ), и когда . ∎ в дж {\displaystyle v_{j}} ∑ к = 0 н − 1 α ( дж ′ − дж ) к = 0 {\displaystyle \sum _{k=0}^{n-1}\alpha ^{(j'-j)k}=0} дж ′ ≠ дж {\displaystyle j'\neq j} к = дж ′ − дж {\displaystyle k=j'-j} ∑ к = 0 н − 1 α ( дж ′ − дж ) к = н {\displaystyle \sum _{k=0}^{n-1}\alpha ^{(j'-j)k}=n} дж ′ = дж {\displaystyle j'=j}

Матричная формулировка

Поскольку дискретное преобразование Фурье является линейным оператором , его можно описать умножением матриц . В матричной записи дискретное преобразование Фурье выражается следующим образом:

[ ф 0 ф 1 ⋮ ф н − 1 ] = [ 1 1 1 ⋯ 1 1 α α 2 ⋯ α н − 1 1 α 2 α 4 ⋯ α 2 ( н − 1 ) ⋮ ⋮ ⋮ ⋱ ⋮ 1 α н − 1 α 2 ( н − 1 ) ⋯ α ( н − 1 ) ( н − 1 ) ] [ в 0 в 1 ⋮ в н − 1 ] . {\displaystyle {\begin{bmatrix}f_{0}\\f_{1}\\\vdots \\f_{n-1}\end{bmatrix}}={\begin{bmatrix}1&1&1&\cdots &1\\1&\alpha &\alpha ^{2}&\cdots &\alpha ^{n-1}\\1&\alpha ^{2}&\alpha ^{4}&\cdots &\alpha ^{2(n-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\alpha ^{n-1}&\alpha ^{2(n-1)}&\cdots &\alpha ^{(n-1)(n-1)}\\\end{bmatrix}}{\begin{bmatrix}v_{0}\\v_{1}\\\vdots \\v_{n-1}\end{bmatrix}}.}

Матрица для этого преобразования называется матрицей ДПФ .

Аналогично, матричная запись для обратного преобразования Фурье имеет вид

[ v 0 v 1 ⋮ v n − 1 ] = 1 n [ 1 1 1 ⋯ 1 1 α − 1 α − 2 ⋯ α − ( n − 1 ) 1 α − 2 α − 4 ⋯ α − 2 ( n − 1 ) ⋮ ⋮ ⋮ ⋱ ⋮ 1 α − ( n − 1 ) α − 2 ( n − 1 ) ⋯ α − ( n − 1 ) ( n − 1 ) ] [ f 0 f 1 ⋮ f n − 1 ] . {\displaystyle {\begin{bmatrix}v_{0}\\v_{1}\\\vdots \\v_{n-1}\end{bmatrix}}={\frac {1}{n}}{\begin{bmatrix}1&1&1&\cdots &1\\1&\alpha ^{-1}&\alpha ^{-2}&\cdots &\alpha ^{-(n-1)}\\1&\alpha ^{-2}&\alpha ^{-4}&\cdots &\alpha ^{-2(n-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\alpha ^{-(n-1)}&\alpha ^{-2(n-1)}&\cdots &\alpha ^{-(n-1)(n-1)}\end{bmatrix}}{\begin{bmatrix}f_{0}\\f_{1}\\\vdots \\f_{n-1}\end{bmatrix}}.}

Полиномиальная формулировка

Иногда удобно отождествлять n -кортеж с формальным многочленом ( v 0 , … , v n − 1 ) {\displaystyle (v_{0},\ldots ,v_{n-1})}

p v ( x ) = v 0 + v 1 x + v 2 x 2 + ⋯ + v n − 1 x n − 1 . {\displaystyle p_{v}(x)=v_{0}+v_{1}x+v_{2}x^{2}+\cdots +v_{n-1}x^{n-1}.\,}

Записывая суммирование в определении дискретного преобразования Фурье ( 2 ), получаем:

f k = v 0 + v 1 α k + v 2 α 2 k + ⋯ + v n − 1 α ( n − 1 ) k . {\displaystyle f_{k}=v_{0}+v_{1}\alpha ^{k}+v_{2}\alpha ^{2k}+\cdots +v_{n-1}\alpha ^{(n-1)k}.\,}

Это означает, что это просто значение полинома для , т.е. f k {\displaystyle f_{k}} p v ( x ) {\displaystyle p_{v}(x)} x = α k {\displaystyle x=\alpha ^{k}}

f k = p v ( α k ) . {\displaystyle f_{k}=p_{v}(\alpha ^{k}).\,} ( 4 )

Таким образом, можно считать, что преобразование Фурье связывает коэффициенты и значения полинома : коэффициенты находятся во временной области, а значения — в частотной области. Здесь, конечно, важно, чтобы полином оценивался в n -ных корнях из единицы, которые в точности являются степенями . α {\displaystyle \alpha }

Аналогично можно записать определение обратного преобразования Фурье ( 3 ):

v j = 1 n ( f 0 + f 1 α − j + f 2 α − 2 j + ⋯ + f n − 1 α − ( n − 1 ) j ) . {\displaystyle v_{j}={\frac {1}{n}}(f_{0}+f_{1}\alpha ^{-j}+f_{2}\alpha ^{-2j}+\cdots +f_{n-1}\alpha ^{-(n-1)j}).} ( 5 )

С

p f ( x ) = f 0 + f 1 x + f 2 x 2 + ⋯ + f n − 1 x n − 1 , {\displaystyle p_{f}(x)=f_{0}+f_{1}x+f_{2}x^{2}+\cdots +f_{n-1}x^{n-1},}

это означает, что

v j = 1 n p f ( α − j ) . {\displaystyle v_{j}={\frac {1}{n}}p_{f}(\alpha ^{-j}).}

Мы можем резюмировать это следующим образом: если значения являются коэффициентами , то значения являются коэффициентами , с точностью до скалярного множителя и переупорядочения. [ 2] p v ( x ) {\displaystyle p_{v}(x)} p f ( x ) {\displaystyle p_{f}(x)} p f ( x ) {\displaystyle p_{f}(x)} p v ( x ) {\displaystyle p_{v}(x)}

Особые случаи

Комплексные числа

Если - поле комплексных чисел, то корни th из единицы можно визуализировать как точки на единичной окружности комплексной плоскости . В этом случае обычно берут F = C {\displaystyle F={\mathbb {C} }} n {\displaystyle n}

α = e − 2 π i n , {\displaystyle \alpha =e^{\frac {-2\pi i}{n}},}

что дает обычную формулу для комплексного дискретного преобразования Фурье :

f k = ∑ j = 0 n − 1 v j e − 2 π i n j k . {\displaystyle f_{k}=\sum _{j=0}^{n-1}v_{j}e^{{\frac {-2\pi i}{n}}jk}.}

Над комплексными числами часто принято нормализовать формулы для ДПФ и обратного ДПФ, используя скалярный множитель в обеих формулах, а не в формуле для ДПФ и в формуле для обратного ДПФ. При такой нормализации матрица ДПФ становится унитарной. Обратите внимание, что это не имеет смысла в произвольном поле. 1 n {\displaystyle {\frac {1}{\sqrt {n}}}} 1 {\displaystyle 1} 1 n {\displaystyle {\frac {1}{n}}} n {\displaystyle {\sqrt {n}}}

Конечные поля

Если — конечное поле , где q — степень простого числа, то существование примитивного корня степени n автоматически подразумевает, что n делит , поскольку мультипликативный порядок каждого элемента должен делить размер мультипликативной группы F , которая равна . Это, в частности, гарантирует, что является обратимым, так что запись в ( 3 ) имеет смысл. F = G F ( q ) {\displaystyle F=\mathrm {GF} (q)} q − 1 {\displaystyle q-1} q − 1 {\displaystyle q-1} n = 1 + 1 + ⋯ + 1 ⏟ n   t i m e s {\displaystyle n=\underbrace {1+1+\cdots +1} _{n\ {\rm {times}}}} 1 n {\displaystyle {\frac {1}{n}}}

Применение дискретного преобразования Фурье над является сведение кодов Рида–Соломона к кодам БЧХ в теории кодирования . Такое преобразование может быть эффективно выполнено с помощью соответствующих быстрых алгоритмов, например, циклотомического быстрого преобразования Фурье . G F ( q ) {\displaystyle \mathrm {GF} (q)}

Полиномиальная формулировка без nйкорень

Предположим . Если , то может быть так, что . Это означает, что мы не можем найти корень единицы в . Мы можем рассматривать преобразование Фурье как изоморфизм для некоторых многочленов , в соответствии с теоремой Машке . Отображение задается китайской теоремой об остатках , а обратное задается применением тождества Безу для многочленов. [3] F = G F ( p ) {\displaystyle F=\mathrm {GF} (p)} p ∤ n {\displaystyle p\nmid n} n ∤ p − 1 {\displaystyle n\nmid p-1} n t h {\displaystyle n^{th}} F {\displaystyle F} F [ C n ] = F [ x ] / ( x n − 1 ) ≅ ⨁ i F [ x ] / ( P i ( x ) ) {\displaystyle \mathrm {F} [C_{n}]=\mathrm {F} [x]/(x^{n}-1)\cong \bigoplus _{i}\mathrm {F} [x]/(P_{i}(x))} P i ( x ) {\displaystyle P_{i}(x)}

x n − 1 = ∏ d | n Φ d ( x ) {\displaystyle x^{n}-1=\prod _{d|n}\Phi _{d}(x)} , произведение циклотомических многочленов. Факторизация эквивалентна факторизации простого идеала в . Мы получаем многочлены степени , где и — порядок . Φ d ( x ) {\displaystyle \Phi _{d}(x)} F [ x ] {\displaystyle F[x]} ( p ) {\displaystyle (p)} Z [ ζ ] = Z [ x ] / ( Φ d ( x ) ) {\displaystyle \mathrm {Z} [\zeta ]=\mathrm {Z} [x]/(\Phi _{d}(x))} g {\displaystyle g} P 1 … P g {\displaystyle P_{1}\ldots P_{g}} f {\displaystyle f} f g = φ ( d ) {\displaystyle fg=\varphi (d)} f {\displaystyle f} p  mod  d {\displaystyle p{\text{ mod }}d}

Как и выше, мы можем расширить базовое поле до , чтобы найти примитивный корень, т. е. поле расщепления для . Теперь , поэтому элемент отображается на для каждого . G F ( q ) {\displaystyle \mathrm {GF} (q)} x n − 1 {\displaystyle x^{n}-1} x n − 1 = ∏ k ( x − α k ) {\displaystyle x^{n}-1=\prod _{k}(x-\alpha ^{k})} ∑ j = 0 n − 1 v j x j ∈ F [ x ] / ( x n − 1 ) {\displaystyle \sum _{j=0}^{n-1}v_{j}x^{j}\in F[x]/(x^{n}-1)} ∑ j = 0 n − 1 v j x j mod ( x − α k ) ≡ ∑ j = 0 n − 1 v j ( α k ) j {\displaystyle \sum _{j=0}^{n-1}v_{j}x^{j}\mod (x-\alpha ^{k})\equiv \sum _{j=0}^{n-1}v_{j}(\alpha ^{k})^{j}} k {\displaystyle k}

Когда p делит n

Когда , мы все еще можем определить -линейный изоморфизм, как указано выше. Обратите внимание, что где и . Применяем указанную выше факторизацию к , и теперь получаем разложение . Возникающие модули теперь неразложимы, а не неприводимы. p | n {\displaystyle p|n} F p {\displaystyle F_{p}} ( x n − 1 ) = ( x m − 1 ) p s {\displaystyle (x^{n}-1)=(x^{m}-1)^{p^{s}}} n = m p s {\displaystyle n=mp^{s}} p ∤ m {\displaystyle p\nmid m} x m − 1 {\displaystyle x^{m}-1} F [ x ] / ( x n − 1 ) ≅ ⨁ i F [ x ] / ( P i ( x ) p s ) {\displaystyle F[x]/(x^{n}-1)\cong \bigoplus _{i}F[x]/(P_{i}(x)^{p^{s}})}

Порядок матрицы ДПФ

Предположим , что у нас есть корень из единицы . Пусть будет указанной выше матрицей ДПФ, матрицей Вандермонда с элементами для . Напомним, что поскольку если , то каждый элемент равен 1. Если , то у нас есть геометрическая прогрессия с знаменателем , поэтому мы получаем . Поскольку числитель равен нулю, но поэтому знаменатель ненулевой. p ∤ n {\displaystyle p\nmid n} n t h {\displaystyle n^{th}} α {\displaystyle \alpha } A {\displaystyle A} A i j = α i j {\displaystyle A_{ij}=\alpha ^{ij}} 0 ≤ i , j < n {\displaystyle 0\leq i,j<n} ∑ j = 0 n − 1 α ( k − l ) j = n δ k , l {\displaystyle \sum _{j=0}^{n-1}\alpha ^{(k-l)j}=n\delta _{k,l}} k = l {\displaystyle k=l} k ≠ l {\displaystyle k\neq l} α k − l {\displaystyle \alpha ^{k-l}} 1 − α n ( k − l ) 1 − α k − l {\displaystyle {\frac {1-\alpha ^{n(k-l)}}{1-\alpha ^{k-l}}}} α n = 1 {\displaystyle \alpha ^{n}=1} k − l ≠ 0 {\displaystyle k-l\neq 0}

Сначала вычисляем квадрат, . Вычисляя аналогично и упрощая дельты, получаем . Таким образом, и порядок равен . ( A 2 ) i k = ∑ j = 0 n − 1 α j ( i + k ) = n δ i , − k {\displaystyle (A^{2})_{ik}=\sum _{j=0}^{n-1}\alpha ^{j(i+k)}=n\delta _{i,-k}} A 4 = ( A 2 ) 2 {\displaystyle A^{4}=(A^{2})^{2}} ( A 4 ) i k = n 2 δ i , k {\displaystyle (A^{4})_{ik}=n^{2}\delta _{i,k}} A 4 = n 2 I n {\displaystyle A^{4}=n^{2}I_{n}} 4 ⋅ ord ( n 2 ) {\displaystyle 4\cdot {\text{ord}}(n^{2})}

Нормализация матрицы ДПФ

Чтобы выровняться с комплексным случаем и гарантировать, что матрица имеет порядок 4, мы можем нормализовать указанную выше матрицу DFT с помощью . Обратите внимание, что хотя может и не существовать в поле расщепления , мы можем сформировать квадратичное расширение , в котором квадратный корень существует. Затем мы можем установить , и . A {\displaystyle A} 1 n {\displaystyle {\frac {1}{\sqrt {n}}}} n {\displaystyle {\sqrt {n}}} F q {\displaystyle F_{q}} x n − 1 {\displaystyle x^{n}-1} F q 2 ≅ F q [ x ] / ( x 2 − n ) {\displaystyle F_{q^{2}}\cong F_{q}[x]/(x^{2}-n)} U = 1 n A {\displaystyle U={\frac {1}{\sqrt {n}}}A} U 4 = I n {\displaystyle U^{4}=I_{n}}

Унитарность

Предположим . Можно спросить, является ли матрица ДПФ унитарной над конечным полем . Если элементы матрицы находятся над , то необходимо обеспечить, чтобы она была полным квадратом или была расширена до , чтобы определить автоморфизм второго порядка . Рассмотрим приведенную выше матрицу ДПФ . Обратите внимание, что является симметричной. Сопрягая и транспонируя, получаем . p ∤ n {\displaystyle p\nmid n} F q {\displaystyle F_{q}} q {\displaystyle q} F q 2 {\displaystyle F_{q^{2}}} x ↦ x q {\displaystyle x\mapsto x^{q}} A i j = α i j {\displaystyle A_{ij}=\alpha ^{ij}} A {\displaystyle A} A i j ∗ = α q j i {\displaystyle A_{ij}^{*}=\alpha ^{qji}}

( A A ∗ ) i k = ∑ j = 0 n − 1 α j ( i + q k ) = n δ i , − q k {\displaystyle (AA^{*})_{ik}=\sum _{j=0}^{n-1}\alpha ^{j(i+qk)}=n\delta _{i,-qk}}

по аналогичному аргументу геометрической прогрессии, как и выше. Мы можем удалить , нормализуя так, чтобы и . Таким образом, является унитарным тогда и только тогда, когда . Напомним, что поскольку у нас есть корень из единицы, . Это означает, что . Обратите внимание, что если изначально не был полным квадратом, то и поэтому . n {\displaystyle n} U = 1 n A {\displaystyle U={\frac {1}{\sqrt {n}}}A} ( U U ∗ ) i k = δ i , − q k {\displaystyle (UU^{*})_{ik}=\delta _{i,-qk}} U {\displaystyle U} q ≡ − 1 ( mod n ) {\displaystyle q\equiv -1\,({\text{mod}}\,n)} n t h {\displaystyle n^{th}} n | q 2 − 1 {\displaystyle n|q^{2}-1} q 2 − 1 ≡ ( q + 1 ) ( q − 1 ) ≡ 0 ( mod n ) {\displaystyle q^{2}-1\equiv (q+1)(q-1)\equiv 0\,({\text{mod}}\,n)} q {\displaystyle q} n | q − 1 {\displaystyle n|q-1} q ≡ 1 ( mod n ) {\displaystyle q\equiv 1\,({\text{mod}}\,n)}

Например, когда нам нужно расширить до, чтобы получить корень пятой степени из единицы . p = 3 , n = 5 {\displaystyle p=3,n=5} q 2 = 3 4 {\displaystyle q^{2}=3^{4}} q = 9 ≡ − 1 ( mod 5 ) {\displaystyle q=9\equiv -1\,({\text{mod}}\,5)}

Например, когда мы расширяем до , чтобы получить корень восьмой степени из единицы. , то , и в этом случае и . является квадратным корнем из тождества, поэтому не является унитарным. p = 3 , n = 8 {\displaystyle p=3,n=8} F 3 2 {\displaystyle F_{3^{2}}} q 2 = 9 {\displaystyle q^{2}=9} q ≡ 3 ( mod 8 ) {\displaystyle q\equiv 3\,({\text{mod}}\,8)} q + 1 ≢ 0 {\displaystyle q+1\not \equiv 0} q − 1 ≢ 0 {\displaystyle q-1\not \equiv 0} U U ∗ {\displaystyle UU^{*}} U {\displaystyle U}

Собственные значения матрицы ДПФ

Когда , у нас есть корень из единицы в поле расщепления . Обратите внимание, что характеристический многочлен указанной выше матрицы ДПФ может не расщепляться по . Матрица ДПФ имеет порядок 4. Возможно, нам потребуется перейти к дальнейшему расширению , расширению расщепления характеристического многочлена матрицы ДПФ, которое по крайней мере содержит четвертые корни из единицы. Если является генератором мультипликативной группы , то собственные значения равны , в точной аналогии с комплексным случаем. Они встречаются с некоторой неотрицательной кратностью. p ∤ n {\displaystyle p\nmid n} n t h {\displaystyle n^{th}} α {\displaystyle \alpha } F q ≅ F p [ x ] / ( x n − 1 ) {\displaystyle F_{q}\cong F_{p}[x]/(x^{n}-1)} F q {\displaystyle F_{q}} F q ′ {\displaystyle F_{q'}} a {\displaystyle a} F q ′ {\displaystyle F_{q'}} { ± 1 , ± a ( q ′ − 1 ) / 4 } {\displaystyle \{\pm 1,\pm a^{(q'-1)/4}\}}

Теоретико-числовое преобразование

Теоретико -числовое преобразование (NTT) [4] получается путем специализации дискретного преобразования Фурье к , целым числам по модулю простого числа p . Это конечное поле , и примитивные корни степени n из единицы существуют всякий раз, когда n делит , поэтому для положительного целого числа ξ имеем . В частности, пусть будет примитивным корнем степени n из единицы, тогда корень степени n из единицы можно найти, положив . F = Z / p {\displaystyle F={\mathbb {Z} }/p} p − 1 {\displaystyle p-1} p = ξ n + 1 {\displaystyle p=\xi n+1} ω {\displaystyle \omega } ( p − 1 ) {\displaystyle (p-1)} α {\displaystyle \alpha } α = ω ξ {\displaystyle \alpha =\omega ^{\xi }}

например, для , p = 5 {\displaystyle p=5} α = 2 {\displaystyle \alpha =2}

2 1 = 2 ( mod 5 ) 2 2 = 4 ( mod 5 ) 2 3 = 3 ( mod 5 ) 2 4 = 1 ( mod 5 ) {\displaystyle {\begin{aligned}2^{1}&=2{\pmod {5}}\\2^{2}&=4{\pmod {5}}\\2^{3}&=3{\pmod {5}}\\2^{4}&=1{\pmod {5}}\end{aligned}}}

когда N = 4 {\displaystyle N=4}

[ F ( 0 ) F ( 1 ) F ( 2 ) F ( 3 ) ] = [ 1 1 1 1 1 2 4 3 1 4 1 4 1 3 4 2 ] [ f ( 0 ) f ( 1 ) f ( 2 ) f ( 3 ) ] {\displaystyle {\begin{bmatrix}F(0)\\F(1)\\F(2)\\F(3)\end{bmatrix}}={\begin{bmatrix}1&1&1&1\\1&2&4&3\\1&4&1&4\\1&3&4&2\end{bmatrix}}{\begin{bmatrix}f(0)\\f(1)\\f(2)\\f(3)\end{bmatrix}}}

Числовое теоретико-преобразование может иметь смысл в кольце , даже когда модуль m не является простым, при условии, что существует главный корень порядка n . Специальные случаи числового теоретико-преобразования, такие как числовое преобразование Ферма ( m = 2 k +1 ), используемое алгоритмом Шёнхаге–Штрассена , или числовое преобразование Мерсенна [5] ( m = 2 k  − 1 ), используют составной модуль. Z / m {\displaystyle \mathbb {Z} /m}

Дискретное взвешенное преобразование

Дискретное взвешенное преобразование (ДВП) представляет собой вариацию дискретного преобразования Фурье над произвольными кольцами, включающую взвешивание входных данных перед их преобразованием путем поэлементного умножения на весовой вектор, а затем взвешивания результата на другой вектор. [6] Дискретное взвешенное преобразование с иррациональной базой является частным случаем этого.

Характеристики

Большинство важных атрибутов комплексного DFT , включая обратное преобразование, теорему о свертке и большинство алгоритмов быстрого преобразования Фурье (FFT), зависят только от свойства, что ядро ​​преобразования является главным корнем единицы. Эти свойства также сохраняются, с идентичными доказательствами, над произвольными кольцами. В случае полей эта аналогия может быть формализована полем с одним элементом , рассматривая любое поле с примитивным корнем n- й степени из единицы как алгебру над полем расширения [ необходимо разъяснение ] F 1 n . {\displaystyle \mathbf {F} _{1^{n}}.}

В частности, применимость алгоритмов быстрого преобразования Фурье для вычисления NTT в сочетании с теоремой о свертке означает, что теоретико -числовое преобразование дает эффективный способ вычисления точных свёрток целочисленных последовательностей. Хотя комплексное DFT может выполнять ту же задачу, оно подвержено ошибкам округления в арифметике с плавающей точкой конечной точности ; NTT не имеет округления, поскольку имеет дело исключительно с целыми числами фиксированного размера, которые могут быть точно представлены. O ( n log ⁡ n ) {\displaystyle O(n\log n)}

Быстрые алгоритмы

Для реализации «быстрого» алгоритма (подобного тому, как БПФ вычисляет ДПФ ), часто желательно, чтобы длина преобразования также была в высокой степени составной, например, степенью двойки . Однако существуют специализированные алгоритмы быстрого преобразования Фурье для конечных полей, такие как алгоритм Вана и Чжу [7] , которые эффективны независимо от того, является ли длина преобразования множителем.

Смотрите также

Ссылки

  1. ^ abc Мартин Фюрер, «Быстрое целочисленное умножение», Труды STOC 2007, стр. 57–66. Раздел 2: Дискретное преобразование Фурье.
  2. ^ Р. Лидл и Г. Пильц. Прикладная абстрактная алгебра, 2-е издание. Wiley, 1999, стр. 217–219.
  3. ^ "Jacksonwalters/DFT-конечные-группы". GitHub .
  4. ^ Агарвал, Р.; Буррус, К. (апрель 1974 г.). «Быстрая свертка с использованием преобразований чисел Ферма с приложениями к цифровой фильтрации». Труды IEEE по акустике, речи и обработке сигналов . 22 (2): 87–97. doi :10.1109/TASSP.1974.1162555. ISSN  0096-3518.
  5. ^ Rader, CM (декабрь 1972 г.). «Дискретные свертки с помощью преобразований Мерсенна». IEEE Transactions on Computers . C-21 (12): 1269–1273. doi :10.1109/TC.1972.223497. ISSN  0018-9340. S2CID  1939809.
  6. ^ Крэндалл, Ричард; Фейгин, Барри (1994), «Дискретные взвешенные преобразования и арифметика больших целых чисел» (PDF) , Математика вычислений , 62 (205): 305–324, doi : 10.2307/2153411 , JSTOR  2153411
  7. ^ Яо Ван и Сюэлун Чжу, «Быстрый алгоритм преобразования Фурье над конечными полями и его реализация на СБИС», Журнал IEEE по избранным направлениям в коммуникациях 6(3)572–577, 1988
  • http://www.apfloat.org/ntt.html
Retrieved from "https://en.wikipedia.org/w/index.php?title=Discrete_Fourier_transform_over_a_ring&oldid=1243777349#Number-theoretic_transform"