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

редактировать

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

Содержание

1 Определение
2 Обратное
3 Формулировка матрицы
4 Полиномиальная формулировка
5 Особые случаи
- 5.1 Комплексные числа
- 5.2 Конечные поля
- 5.3 Теоретико-числовое преобразование
- 5.4 Дискретно-взвешенное преобразование
6 Свойства
7 Быстрые алгоритмы
8 См. Также
9 Ссылки
10 Внешние ссылки

Определение

Пусть $R {\ displaystyle R}$ $R$ будет любым кольцом, пусть $n ≥ 1 {\ displaystyle n \ geq 1}$ $n \ geq 1$ быть целым числом, и пусть $α ∈ R {\ displaystyle \ alpha \ in R}$ $\ альфа \ in R$ будет принципалом корень n-й степени из единицы, определяемый следующим образом:

α n = 1 ∑ j = 0 n - 1 α jk = 0 для 1 ≤ k < n ( 1) {\displaystyle {\begin{aligned}\alpha ^{n}=1\\\sum _{j=0}^{n-1}\alpha ^{jk}=0{\text{ for }}1\leq k

{\ displaystyle {\ begin {align} \ alpha ^ {n} = 1 \\ \ sum _ {j = 0} ^ {n-1} \ alpha ^ {jk} = 0 {\ text {for}} 1 \ leq k <n \ qquad (1) \ end {align}}}

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

fk = ∑ j = 0 n - 1 vj α jk. (2) {\ displaystyle f_ {k} = \ sum _ {j = 0} ^ {n-1} v_ {j} \ alpha ^ {jk}. \ Qquad (2)}

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

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

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

α К ≠ 1 {\ displaystyle \ alpha ^ {k} \ neq 1}

\ alpha ^ {{k}} \ neq 1

для

1 ≤ k < n {\displaystyle 1\leq k

1 \ leq k <n

Доказательство: возьмем $β = α k {\ displaystyle \ beta = \ alpha ^ {k}}$ $\ beta = \ alpha ^ {k}$ с $1 ≤ k < n {\displaystyle 1\leq k$ $1 \ leq k <n$ . Поскольку $α n = 1 {\ displaystyle \ alpha ^ {n} = 1}$ $\ alpha ^ {n} = 1$ , $β n = (α n) k = 1 {\ displaystyle \ beta ^ {n} = (\ alpha ^ {n}) ^ {k} = 1}$ $\ beta ^ {n} = (\ alpha ^ {n}) ^ {k} = 1$ , что дает:

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

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

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

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

Обратное

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

vj = 1 n ∑ k = 0 n - 1 fk α - jk. (3) {\ displaystyle v_ {j} = {\ frac {1} {n}} \ sum _ {k = 0} ^ {n-1} f_ {k} \ alpha ^ {- jk}. \ Qquad ( 3)}

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

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

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

1 n ∑ k = 0 n - 1 fk α - jk = 1 n ∑ k = 0 n - 1 ∑ j ′ = 0 n - 1 vj ′ α j ′ k α - jk = 1 n ∑ j ′ = 0 n - 1 vj ′ ∑ k = 0 n - 1 α (j ′ - j) k. {\ displaystyle {\ begin {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 {align}}}

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

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

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

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

[f 0 f 1 ⋮ fn - 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)] [v 0 v 1 ⋮ vn - 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 \ 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} f_ {0} \\ f_ {1} \\\ vdots \\ f _ {{n-1}} \ end {bmatrix}} = {\ begin {bma trix} 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}}.

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

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

[v 0 v 1 ⋮ vn - 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 ⋮ fn - 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 \ 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}}.}

{\ 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 \ альфа ^ {{- 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}}.

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

Иногда удобно идентифицировать $n { \ displaystyle n}$ $n$ -tuple $(v 0,…, vn - 1) {\ displaystyle (v_ {0}, \ ldots, v_ {n-1})}$ $(v_ {0}, \ ldots, v _ {{n-1}})$ с формальным многочленом

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

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

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

fk = v 0 + v 1 α k + v 2 α 2 k + ⋯ + vn - 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} = v_ {0} + v_ {1} \ alpha ^ {{k}} + v_ {2} \ alpha ^ {{2k}} + \ cdots + v _ {{n-1}} \ alpha ^ {{(n-1) k}}. \,

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

fk = pv ( α k). {\ displaystyle f_ {k} = p_ {v} (\ alpha ^ {k}). \,}

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

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

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

vj = 1 n (f 0 + f 1 α - j + f 2 α - 2 j + ⋯ + fn - 1 α - (n - 1) j). (5) {\ 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)}

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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 1 = 2 (mod 5) 2 2 = 4 (mod 5) 2 3 = 3 (мод. 5) 2 4 = 1 (мод. 5) {\ displaystyle {\ begin {align} 2 ^ {1} = 2 {\ pmod {5}} \\ 2 ^ {2} = 4 {\ pmod {5}} \\ 2 ^ {3} = 3 {\ pmod {5}} \\ 2 ^ {4} = 1 {\ pmod {5}} \ end {align}}}

{\ displaystyle {\ begin {align} 2 ^ {1} = 2 {\ pmod {5}} \\ 2 ^ {2} = 4 {\ pmod {5}} \\ 2 ^ {3} = 3 {\ pmod {5}} \\ 2 ^ {4} = 1 {\ pmod {5}} \ end {align}}}

когда $N = 4 {\ displaystyle N = 4}$ $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] [е (0) е (1) е (2) е (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}}}

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

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

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

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

Свойства

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

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

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

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

См. Также

Ссылки

^ Мартин Фюрер, «Более быстрое целочисленное умножение ", Труды STOC 2007, стр. 57–66. Раздел 2: Дискретное преобразование Фурье.
^Р. Lidl и G. Pilz. Прикладная абстрактная алгебра, 2-е издание. Wiley, 1999, стр. 217–219.
^Крэндалл, Ричард; Фэгин, Барри (1994), «Дискретные взвешенные преобразования и арифметика с большими целыми числами» (PDF), Математика вычислений, 62 (205): 305–324, doi : 10.2307 / 2153411
^Яо Ван и Сюэлун Чжу, «Быстрый алгоритм преобразования Фурье по конечным полям и его реализация на СБИС», IEEE Journal on Selected Areas in Communications 6 (3) 572–577, 1988

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

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