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

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

Определение

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

${displaystyle {egin {выравнивается} & alpha ^ {n} = 1 & sum _ {j = 0} ^ {n-1} alpha ^ {jk} = 0 {ext {for}} 1leq k$

Дискретное преобразование Фурье отображает ппара ${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})}$. Эта терминология происходит от применения преобразований Фурье в обработка сигнала.

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

${displaystyle alpha ^ {k} экв 1}$ для ${displaystyle 1leq k$

Доказательство: возьми ${displaystyle eta = alpha ^ {k}}$ с участием ${displaystyle 1leq k$. поскольку ${displaystyle alpha ^ {n} = 1}$, ${displaystyle eta ^ {n} = (альфа ^ {n}) ^ {k} = 1}$, давая:

${displaystyle eta ^ {n} -1 = (eta -1) слева (сумма _ {j = 0} ^ {n-1} eta ^ {j} ight) = 0}$

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

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

Обратный

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

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

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

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

${displaystyle {egin {align} & {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 {выровнено}}}$

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

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

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

${displaystyle {egin {bmatrix} f_ {0} f_ {1} vdots f_ {n-1} end {bmatrix}} = {egin {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}} {egin {bmatrix} v_ {0} v_ {1} vdots v_ {n-1} end {bmatrix}}.}$

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

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

${displaystyle {egin {bmatrix} v_ {0} v_ {1} vdots v_ {n-1} end {bmatrix}} = {frac {1} {n}} {egin {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}} {egin {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}).,}$

Следовательно, преобразование Фурье связывает коэффициенты и ценности полинома: коэффициенты находятся во временной области, а значения - в частотной области. Здесь, конечно, важно, чтобы полином вычислялся на ${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} альфа ^ {- (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 {-2pi i} {n}},}$

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

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

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

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

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

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

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

В теоретико-числовое преобразование (NTT) получается специализацией дискретного преобразования Фурье на ${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 {egin {align} 2 ^ {1} & = 2 {pmod {5}} 2 ^ {2} & = 4 {pmod {5}} 2 ^ {3} & = 3 {pmod {5} } 2 ^ {4} & = 1 {pmod {5}} конец {выровнено}}}$

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

${displaystyle {egin {bmatrix} F (0) F (1) F (2) F (3) end {bmatrix}} = {egin {bmatrix} 1 & 1 & 1 & 1 1 & 2 & 4 & 3 1 & 4 & 1 & 4 1 & 3 & 4 & 2end {bmatrix}} {egin {bmatrix} f (0) f (1) f (2) f (3) end {bmatrix}}}$

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

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

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

Свойства

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

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

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

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

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

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

использованная литература

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

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