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

Обобщение преобразования Фурье на любое кольцо

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

Определение

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

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

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

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

${\displaystyle \alpha ^{k}\neq 1}$для ${\displaystyle 1\leq k<n}$

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

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

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

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

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

Обратный

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

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

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

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

${\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}}$ ${\displaystyle \sum _{k=0}^{n-1}\alpha ^{(j'-j)k}=0}$ ${\displaystyle j'\neq j}$ ${\displaystyle k=j'-j}$ ${\displaystyle \sum _{k=0}^{n-1}\alpha ^{(j'-j)k}=n}$ ${\displaystyle j'=j}$

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

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

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

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

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

${\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 -кортеж с формальным многочленом ${\displaystyle (v_{0},\ldots ,v_{n-1})}$

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

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

${\displaystyle f_{k}=v_{0}+v_{1}\alpha ^{k}+v_{2}\alpha ^{2k}+\cdots +v_{n-1}\alpha ^{(n-1)k}.\,}$

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

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

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

С

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Унитарность

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

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

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

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

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

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

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

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

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

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

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

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

${\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 ), используют составной модуль. ${\displaystyle \mathbb {Z} /m}$

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

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

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

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

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

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

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

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

• Дискретное преобразование Фурье (комплексное)
• Преобразование Фурье на конечных группах
• сумма Гаусса
• Свертка
• Спектральный анализ методом наименьших квадратов
• Алгоритм умножения

Ссылки

1. Мартин Фюрер, «Быстрое целочисленное умножение», Труды 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