Циклотомное быстрое преобразование Фурье

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

Фон

Дискретное преобразование Фурье по конечным полям находит широкое применение при декодировании кодов с исправлением ошибок, таких как коды БЧХ и коды Рида – Соломона . Обобщенное из комплексного поля , дискретное преобразование Фурье последовательности $\{f_{i}\}_{0}^{N-1}$ над конечным полем GF( p ^м ) определяется как

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

где $\alpha$ является N -м примитивным корнем из 1 в GF( p ^м ). Если мы определим полиномиальное представление $\{f_{i}\}_{0}^{N-1}$ как

$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},$

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

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

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

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

Алгоритм

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

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

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

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

$\{0\},$

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

$\ldots ,$

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

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

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

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

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

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

$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)$

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

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

$\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 ^м ), матрица $\mathbf {A}$ это просто двоичная матрица. При вычислении матрично-векторного произведения используется только сложение $\mathrm {A}$ и $\mathrm {L\Pi f}$. Показано, что мультипликативная сложность кругового алгоритма определяется выражением $O(n(\log _{2}n)^{\log _{2}{\frac {3}{2}}})$, а аддитивная сложность определяется выражением $O(n^{2}/(\log _{2}n)^{\log _{2}{\frac {8}{3}}})$.