Дискретное преобразование Фурье по кольцу

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

Определение

Пусть $R$ — любое кольцо , пусть $n\geq 1$ быть целым числом, и пусть $\alpha \in R$ быть главным корнем n-й степени из единицы, определяемым следующим образом: ^{[ 1 ]}

{\begin{aligned}&\alpha ^{n}=1\\&\sum _{j=0}^{n-1}\alpha ^{jk}=0{\text{ for }}1\leq k<n\end{aligned}}

( 1 )

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

f_{k}=\sum _{j=0}^{n-1}v_{j}\alpha ^{jk}.

( 2 )

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

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

\alpha ^{k}\neq 1

для

1\leq k<n

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

Брать $\beta =\alpha ^{k}$ с $1\leq k<n$ . С $\alpha ^{n}=1$ , $\beta ^{n}=(\alpha ^{n})^{k}=1$ , давая:

\beta ^{n}-1=(\beta -1)\left(\sum _{j=0}^{n-1}\beta ^{j}\right)=0

где сумма соответствует ( 1 ). С $\alpha$ есть первоначальный корень единства, $\beta -1\neq 0$ . Поскольку $R$ является областью целостности, сумма должна быть равна нулю. ∎

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

Обратный

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

v_{j}={\frac {1}{n}}\sum _{k=0}^{n-1}f_{k}\alpha ^{-jk}.

( 3 )

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

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

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

{\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}}

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

Формулировка матрицы

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

{\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}}.

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

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

{\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},\ldots ,v_{n-1})$ с формальным полиномом

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}\alpha ^{k}+v_{2}\alpha ^{2k}+\cdots +v_{n-1}\alpha ^{(n-1)k}.\,

Это означает, что $f_{k}$ это просто значение многочлена $p_{v}(x)$ для $x=\alpha ^{k}$ , то есть,

f_{k}=p_{v}(\alpha ^{k}).\,

( 4 )

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

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

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}+\cdots +f_{n-1}x^{n-1},

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

v_{j}={\frac {1}{n}}p_{f}(\alpha ^{-j}).

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

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

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

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

\alpha =e^{\frac {-2\pi i}{n}},

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

f_{k}=\sum _{j=0}^{n-1}v_{j}e^{{\frac {-2\pi i}{n}}jk}.

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

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

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

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

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

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

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

Как и выше, мы можем расширить базовое поле до $\mathrm {GF} (q)$ для того, чтобы найти примитивный корень, т.е. поле разложения для $x^{n}-1$ . Сейчас $x^{n}-1=\prod _{k}(x-\alpha ^{k})$ , поэтому элемент $\sum _{j=0}^{n-1}v_{j}x^{j}\in F[x]/(x^{n}-1)$ карты в $\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$ .

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

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

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

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

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

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

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

Унитарность

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

$(AA^{*})_{ik}=\sum _{j=0}^{n-1}\alpha ^{j(i+qk)}=n\delta _{i,-qk}$

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

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

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

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

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

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

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

например для $p=5$ , $\alpha =2$

{\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$

{\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}}

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

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

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

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

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

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

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

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

См. также

Ссылки

^ Jump up to: ^а ^б ^с Мартин Фюрер, « Быстрое умножение целых чисел », Труды STOC 2007, стр. 57–66. Раздел 2: Дискретное преобразование Фурье.
^ Р. Лидл и Г. Пильц. Прикладная абстрактная алгебра, 2-е издание. Уайли, 1999, стр. 217–219.
^ https://github.com/jacksonwalters/dft-finite-groups
^ Агарвал, Р.; Буррус, К. (апрель 1974 г.). «Быстрая свертка с использованием преобразований числа Ферма с применением цифровой фильтрации» . Транзакции IEEE по акустике, речи и обработке сигналов . 22 (2): 87–97. дои : 10.1109/ТАССП.1974.1162555 . ISSN 0096-3518 .
^ Рейдер, CM (декабрь 1972 г.). «Дискретные свертки посредством преобразований Мерсенна» . Транзакции IEEE на компьютерах . С-21 (12): 1269–1273. дои : 10.1109/TC.1972.223497 . ISSN 0018-9340 . S2CID 1939809 .
^ Крэндалл, Ричард; Феджин, Барри (1994), «Дискретные взвешенные преобразования и арифметика больших целых чисел» (PDF) , Mathematics of Computation , 62 (205): 305–324, doi : 10.2307/2153411 , JSTOR 2153411
^ Яо Ван и Сюэлун Чжу, «Быстрый алгоритм преобразования Фурье по конечным полям и его реализация СБИС», Журнал IEEE по выбранным областям в коммуникациях 6 (3) 572–577, 1988

Внешние ссылки

http://www.apfloat.org/ntt.html

[furer-1] Jump up to: ^а ^б ^с Мартин Фюрер, « Быстрое умножение целых чисел », Труды STOC 2007, стр. 57–66. Раздел 2: Дискретное преобразование Фурье.

[2] Р. Лидл и Г. Пильц. Прикладная абстрактная алгебра, 2-е издание. Уайли, 1999, стр. 217–219.

[3] ttps://github.com/jacksonwalters/dft-finite-groups

[4] Агарвал, Р.; Буррус, К. (апрель 1974 г.). «Быстрая свертка с использованием преобразований числа Ферма с применением цифровой фильтрации» . Транзакции IEEE по акустике, речи и обработке сигналов . 22 (2): 87–97. дои : 10.1109/ТАССП.1974.1162555 . ISSN 0096-3518 .

[5] Рейдер, CM (декабрь 1972 г.). «Дискретные свертки посредством преобразований Мерсенна» . Транзакции IEEE на компьютерах . С-21 (12): 1269–1273. дои : 10.1109/TC.1972.223497 . ISSN 0018-9340 . S2CID 1939809 .

[6] Крэндалл, Ричард; Феджин, Барри (1994), «Дискретные взвешенные преобразования и арифметика больших целых чисел» (PDF) , Mathematics of Computation , 62 (205): 305–324, doi : 10.2307/2153411 , JSTOR 2153411

[7] Яо Ван и Сюэлун Чжу, «Быстрый алгоритм преобразования Фурье по конечным полям и его реализация СБИС», Журнал IEEE по выбранным областям в коммуникациях 6 (3) 572–577, 1988

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]