Циклотомическое быстрое преобразование Фурье - Cyclotomic fast Fourier transform

В циклотомическое быстрое преобразование Фурье это тип быстрое преобразование Фурье алгоритм закончился конечные поля.^[1] Этот алгоритм сначала разлагает ДПФ на несколько циклических сверток, а затем выводит результаты ДПФ из результатов циклической свертки. При применении к ДПФ более ${\displaystyle GF(2^{m})}$, этот алгоритм имеет очень низкую мультипликативную сложность. На практике, поскольку обычно существуют эффективные алгоритмы для циклических сверток определенной длины, этот алгоритм очень эффективен.^[2]

Фон

В дискретное преобразование Фурье над конечные поля находит широкое применение при декодировании коды с исправлением ошибок Такие как Коды BCH и Коды Рида – Соломона. Обобщено из сложное поле, дискретное преобразование Фурье последовательности ${\displaystyle \{f_{i}\}_{0}^{N-1}}$ над конечным полем GF (п^м) определяется как

${\displaystyle F_{j}=\sum _{i=0}^{N-1}f_{i}\alpha ^{ij},0\leq j\leq N-1,}$

куда ${\displaystyle \alpha }$ это N-го первобытный корень из 1 в ГФ (п^м). Если мы определим полиномиальное представление ${\displaystyle \{f_{i}\}_{0}^{N-1}}$ в качестве

${\displaystyle f(x)=f_{0}+f_{1}x+f_{2}x^{2}+\cdots +f_{N-1}x^{N-1}=\sum _{0}^{N-1}f_{i}x^{i},}$

легко увидеть, что ${\displaystyle F_{j}}$ просто ${\displaystyle f(\alpha ^{j})}$. То есть дискретное преобразование Фурье последовательности преобразует ее в задачу полиномиального вычисления.

Написано в матричном формате,

${\displaystyle \mathbf {F} =\left[{\begin{matrix}F_{0}\\F_{1}\\\vdots \\F_{N-1}\end{matrix}}\right]=\left[{\begin{matrix}\alpha ^{0}&\alpha ^{0}&\cdots &\alpha ^{0}\\\alpha ^{0}&\alpha ^{1}&\cdots &\alpha ^{N-1}\\\vdots &\vdots &\ddots &\vdots \\\alpha ^{0}&\alpha ^{N-1}&\cdots &\alpha ^{(N-1)(N-1)}\end{matrix}}\right]\left[{\begin{matrix}f_{0}\\f_{1}\\\vdots \\f_{N-1}\end{matrix}}\right]={\mathcal {F}}\mathbf {f} .}$

Прямая оценка ДПФ имеет ${\displaystyle O(N^{2})}$ сложность. Быстрые преобразования Фурье - это просто эффективные алгоритмы, оценивающие вышеуказанное произведение матрицы и вектора.

Алгоритм

Сначала определим линеаризованный полином над GF (p^м) в качестве

${\displaystyle L(x)=\sum _{i}l_{i}x^{p^{i}},l_{i}\in \mathrm {GF} (p^{m}).}$

${\displaystyle L(x)}$ называется линеаризованным, потому что ${\displaystyle L(x_{1}+x_{2})=L(x_{1})+L(x_{2})}$, что связано с тем, что для элементов ${\displaystyle x_{1},x_{2}\in \mathrm {GF} (p^{m}),}$${\displaystyle (x_{1}+x_{2})^{p}=x_{1}^{p}+x_{2}^{p}.}$

Заметь ${\displaystyle p}$ обратима по модулю ${\displaystyle N}$ потому что ${\displaystyle N}$ должен разделить заказ ${\displaystyle p^{m}-1}$ мультипликативной группы поля ${\displaystyle \mathrm {GF} (p^{m})}$. Итак, элементы ${\displaystyle \{0,1,2,\ldots ,N-1\}}$ можно разделить на ${\displaystyle l+1}$ циклотомические смежные классы по модулю ${\displaystyle N}$:

${\displaystyle \{0\},}$

${\displaystyle \{k_{1},pk_{1},p^{2}k_{1},\ldots ,p^{m_{1}-1}k_{1}\},}$

${\displaystyle \ldots ,}$

${\displaystyle \{k_{l},pk_{l},p^{2}k_{l},\ldots ,p^{m_{l}-1}k_{l}\},}$

куда ${\displaystyle k_{i}=p^{m_{i}}k_{i}{\pmod {N}}}$. Следовательно, входные данные преобразования Фурье можно переписать как

${\displaystyle f(x)=\sum _{i=0}^{l}L_{i}(x^{k_{i}}),\quad L_{i}(y)=\sum _{t=0}^{m_{i}-1}y^{p^{t}}f_{p^{t}k_{i}{\bmod {N}}}.}$

Таким образом, полиномиальное представление разлагается на сумму линейных многочленов, и, следовательно, ${\displaystyle F_{j}}$ дан кем-то

${\displaystyle F_{j}=f(\alpha ^{j})=\sum _{i=0}^{l}L_{i}(\alpha ^{jk_{i}})}$.

Расширение ${\displaystyle \alpha ^{jk_{i}}\in \mathrm {GF} (p^{m_{i}})}$ с надлежащей основой ${\displaystyle \{\beta _{i,0},\beta _{i,1},\ldots ,\beta _{i,m_{i}-1}\}}$, у нас есть ${\displaystyle \alpha ^{jk_{i}}=\sum _{s=0}^{m_{i}-1}a_{ijs}\beta _{i,s}}$ куда ${\displaystyle a_{ijs}\in \mathrm {GF} (p)}$, а по свойству линеаризованного многочлена ${\displaystyle L_{i}(x)}$, у нас есть

${\displaystyle F_{j}=\sum _{i=0}^{l}\sum _{s=0}^{m_{i}-1}a_{ijs}\left(\sum _{t=0}^{m_{i}-1}\beta _{i,s}^{p^{t}}f_{p^{t}k_{i}{\bmod {N}}}\right)}$

Это уравнение можно переписать в матричной форме как ${\displaystyle \mathbf {F} =\mathbf {AL\Pi f} }$, куда ${\displaystyle \mathbf {A} }$ является ${\displaystyle N\times N}$ матрица над GF (п), который содержит элементы ${\displaystyle a_{ijs}}$, ${\displaystyle \mathbf {L} }$ - блочно-диагональная матрица, а ${\displaystyle \mathbf {\Pi } }$ матрица перестановок, перегруппировывающая элементы в ${\displaystyle \mathbf {f} }$ по циклотомическому индексу смежности.

Обратите внимание, что если нормальная основа ${\displaystyle \{\gamma _{i}^{p^{0}},\gamma _{i}^{p^{1}},\cdots ,\gamma _{i}^{p^{m_{i}-1}}\}}$ используется для раскрытия элементов поля ${\displaystyle \mathrm {GF} (p^{m_{i}})}$, i-й блок ${\displaystyle \mathbf {L} }$ дан кем-то:

${\displaystyle \mathbf {L} _{i}={\begin{bmatrix}\gamma _{i}^{p^{0}}&\gamma _{i}^{p^{1}}&\cdots &\gamma _{i}^{p^{m_{i}-1}}\\\gamma _{i}^{p^{1}}&\gamma _{i}^{p^{2}}&\cdots &\gamma _{i}^{p^{0}}\\\vdots &\vdots &\ddots &\vdots \\\gamma _{i}^{p^{m_{i}-1}}&\gamma _{i}^{p^{0}}&\cdots &\gamma _{i}^{p^{m_{i}-2}}\\\end{bmatrix}}}$

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

Сложность

Применительно к характеристика -2 поля GF (2^м), матрица ${\displaystyle \mathbf {A} }$ это просто двоичная матрица. Только сложение используется при вычислении матрично-векторного произведения ${\displaystyle \mathrm {A} }$ и ${\displaystyle \mathrm {L\Pi f} }$. Было показано, что мультипликативная сложность циклотомического алгоритма определяется выражением ${\displaystyle O(n(\log _{2}n)^{\log _{2}{\frac {3}{2}}})}$, а аддитивная сложность определяется выражением ${\displaystyle O(n^{2}/(\log _{2}n)^{\log _{2}{\frac {8}{3}}})}$.^[2]

Рекомендации

1. С.В. Федоренко и П.В. Трифонов, Федоренко, С. В .; Трифонов, П.В. (2003). «О вычислении быстрого преобразования Фурье по конечным полям» (PDF). Материалы международного семинара по алгебраической и комбинаторной теории кодирования: 108–111.
2. У Сюэбинь; Ван, Инь; Ян, Чжиюань (2012). «Об алгоритмах и сложностях циклотомических быстрых преобразований Фурье над произвольными конечными полями». Транзакции IEEE при обработке сигналов. 60 (3): 1149–1158. Дои:10.1109 / чайная ложка.2011.2178844.