Дискретное преобразование Фурье (общее)

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

Определение [ править ]

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

${\ displaystyle {\ begin {align} & \ alpha ^ {n} = 1 \\ & \ sum _ {j = 0} ^ {n-1} \ alpha ^ {jk} = 0 {\ text {for}} 1 \ leq k <n \ qquad (1) \ end {выровнено}}}$

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

${\displaystyle f_{k}=\sum _{j=0}^{n-1}v_{j}\alpha ^{jk}.\qquad (2)}$

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

Если это область целостности (которая включает поля ), достаточно выбрать в качестве примитива корень n- й степени из единицы , который заменяет условие (1) на: ^[1]${\displaystyle R}$${\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). Так как примитивный корень из единицы, . Поскольку это область целостности, сумма должна быть равна нулю. ∎${\displaystyle \alpha }$${\displaystyle \beta -1\neq 0}$${\displaystyle R}$

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

Обратный [ править ]

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

${\displaystyle v_{j}={\frac {1}{n}}\sum _{k=0}^{n-1}f_{k}\alpha ^{-jk}.\qquad (3)}$

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

Доказательство: Подставляя (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 &&\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 &&\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}}.}$

Полиномиальная формулировка ^[2] [ править ]

Иногда удобно отождествить -набор с формальным многочленом ${\displaystyle 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}}$

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

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

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

${\displaystyle v_{j}={\frac {1}{n}}(f_{0}+f_{1}\alpha ^{-j}+f_{2}\alpha ^{-2j}+\cdots +f_{n-1}\alpha ^{-(n-1)j}).\qquad (5)}$

С участием

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

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

Особые случаи [ править ]

Комплексные числа [ править ]

Если это поле комплексных чисел, то й корни из единицы можно представить в виде точек на единичной окружности на комплексной плоскости . В этом случае обычно принимают ${\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}}}$

Конечные поля [ править ]

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

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

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

Номер теоретико-преобразование (NTT) ^[3] получается путем специализации дискретного преобразования Фурье , то целые числа по модулю простого р . Это конечное поле , и примитивные корни 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 ), используемое алгоритмом Шёнхаге – Штрассена , или преобразование числа Мерсенна ^[4] ( m = 2 ^k  - 1 ), используют составной модуль.${\displaystyle \mathbb {Z} /m}$

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

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

Свойства [ править ]

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

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

Быстрые алгоритмы [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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