Алгоритм БПФ с простым коэффициентом

Алгоритм простого фактора (PFA) , также называемый алгоритмом Гуда – Томаса (1958/1963), представляет собой алгоритм быстрого преобразования Фурье (БПФ), который повторно выражает дискретное преобразование Фурье (ДПФ) размера N = N ₁ N ₂ как двумерное ДПФ N ₁ × N ₂ , но только для случая, когда N ₁ и N ₂ взаимно простые . Эти меньшие преобразования размера N ₁ и N ₂ затем могут быть оценены путем рекурсивного применения PFA или с использованием какого-либо другого алгоритма БПФ.

PFA не следует путать со смешанным обобщением популярного алгоритма Кули-Тьюки , который также подразделяет ДПФ размера N = N ₁ N ₂ на меньшие преобразования размера N ₁ и N ₂ . Последний алгоритм может использовать любые коэффициенты (не обязательно относительно простые), но у него есть тот недостаток, что он также требует дополнительных умножений на корни из единицы, называемых коэффициентами поворота , в дополнение к меньшим преобразованиям. С другой стороны, PFA имеет недостатки: он работает только для относительно простых множителей (например, он бесполезен для размеров степени двойки ) и требует более сложной переиндексации данных на основе аддитивных групп изоморфизмов . Однако обратите внимание, что PFA можно комбинировать со смешанным основанием Кули – Тьюки, при этом первый разлагает N на относительно простые компоненты, а второй обрабатывает повторяющиеся факторы.

PFA также тесно связан с вложенным алгоритмом Винограда БПФ , где последний выполняет разложенное преобразование N ₁ на N ₂ с помощью более сложных методов двумерной свертки. Поэтому некоторые старые статьи также называют алгоритм Винограда PFA FFT.

(Хотя PFA отличается от алгоритма Кули-Тьюки, работа Гуда над PFA 1958 года была названа Кули и Тьюки источником вдохновения в их статье 1965 года, и первоначально возникла некоторая путаница относительно того, различны ли эти два алгоритма. Фактически , это была единственная предшествующая работа по БПФ, на которую они цитировали, поскольку тогда они не знали о более ранних исследованиях Гаусса и других.)

Алгоритм

Позволять $a(x)$ полином и $\omega _{n}$ директор ​ $n$корень единства . Мы определяем ДПФ $a(x)$ как $n$-кортеж $({\hat {a}}_{j})=(a(\omega _{n}^{j}))$.Другими словами, $${\hat {a}}_{j}=\sum _{i=0}^{n-1}a_{i}\omega _{n}^{ij}\quad {\text{ for all }}j=0,1,\dots ,n-1.$$Для простоты обозначим преобразование как ${\text{DFT}}_{\omega _{n}}$.

PFA опирается на взаимно простую факторизацию ${\textstyle n=\prod _{d=0}^{D-1}n_{d}}$ и поворачивается ${\text{DFT}}_{\omega _{n}}$ в ${\textstyle \bigotimes _{d}{\text{DFT}}_{\omega _{n_{d}}}}$ для некоторых вариантов $\omega _{n_{d}}$где ${\textstyle \bigotimes }$ – тензорное произведение .

Сопоставление на основе ЭЛТ

Для взаимно простой факторизации ${\textstyle n=\prod _{d=0}^{D-1}n_{d}}$, у нас есть китайская остаточная карта $m\mapsto (m{\bmod {n}}_{d})$ от $\mathbb {Z} _{n}$ к ${\textstyle \prod _{d=0}^{D-1}\mathbb {Z} _{n_{d}}}$ с ${\textstyle (m_{d})\mapsto \sum _{d=0}^{D-1}e_{d}m_{d}}$ как обратное, где $e_{d}$'s - центральные ортогональные идемпотентные элементы с ${\textstyle \sum _{d=0}^{D-1}e_{d}=1{\pmod {n}}}$.Выбор $\omega _{n_{d}}=\omega _{n}^{e_{d}}$ (поэтому, ${\textstyle \prod _{d=0}^{D-1}\omega _{n_{d}}=\omega _{n}^{\sum _{d=0}^{D-1}e_{d}}=\omega _{n}}$), мы перепишем ${\text{DFT}}_{\omega _{n}}$ следующее: $${\hat {a}}_{j}=\sum _{i=0}^{n-1}a_{i}\omega _{n}^{ij}=\sum _{i=0}^{n-1}a_{i}\left(\prod _{d=0}^{D-1}\omega _{n_{d}}\right)^{ij}=\sum _{i=0}^{n-1}a_{i}\prod _{d=0}^{D-1}\omega _{n_{d}}^{(i{\bmod {n}}_{d})(j{\bmod {n}}_{d})}=\sum _{i_{0}=0}^{n_{0}-1}\cdots \sum _{i_{D-1}=0}^{n_{D-1}-1}a_{\sum _{d=0}^{D-1}e_{d}i_{d}}\prod _{d=0}^{D-1}\omega _{n_{d}}^{i_{d}(j{\bmod {n}}_{d})}.$$Наконец, определите $a_{i_{0},\dots ,i_{D-1}}=a_{\sum _{d=0}^{D-1}i_{d}e_{d}}$ и ${\hat {a}}_{j_{0},\dots ,j_{D-1}}={\hat {a}}_{\sum _{d=0}^{D-1}j_{d}e_{d}}$, у нас есть $${\hat {a}}_{j_{0},\dots ,j_{D-1}}=\sum _{i_{0}=0}^{n_{0}-1}\cdots \sum _{i_{D-1}=0}^{n_{D-1}-1}a_{i_{0},\dots ,i_{D-1}}\prod _{d=0}^{D-1}\omega _{n_{d}}^{i_{d}j_{d}}.$$Следовательно, мы имеем многомерное ДПФ, $\otimes _{d=0}^{D-1}{\text{DFT}}_{\omega _{n_{d}}}$.

Как алгебраические изоморфизмы

PFA можно сформулировать на высоком уровне в терминах алгебраических изоморфизмов .Напомним сначала, что для коммутативного кольца $R$ и групповой изоморфизм из $G$ к ${\textstyle \prod _{d}G_{d}}$,мы имеем следующий изоморфизм алгебры $$R[G]\cong \bigotimes _{d}R[G_{d}]$$ где $\bigotimes$ относится к тензорному произведению алгебр .

Чтобы увидеть, как работает PFA, мы выбираем $G=(\mathbb {Z} _{n},+,0)$ и $G_{d}=(\mathbb {Z} _{n_{d}},+,0)$ быть аддитивными группами .Мы также выявляем $R[G]$ как ${\textstyle {\frac {R[x]}{\langle x^{n}-1\rangle }}}$ и $R[G_{d}]$ как ${\textstyle {\frac {R[x_{d}]}{\langle x_{d}^{n_{d}}-1\rangle }}}$.Выбор $\eta =a\mapsto (a{\bmod {n}}_{d})$ как групповой изоморфизм ${\textstyle G\cong \prod _{d}G_{d}}$, мы имеем изоморфизм алгебр ${\textstyle \eta ^{*}:R[G]\cong \bigotimes _{d}R[G_{d}]}$или, альтернативно, $$\eta ^{*}:{\frac {R[x]}{\langle x^{n}-1\rangle }}\cong \bigotimes _{d}{\frac {R[x_{d}]}{\langle x_{d}^{n_{d}}-1\rangle }}.$$Теперь заметьте, что ${\text{DFT}}_{\omega _{n}}$ на самом деле является изоморфизмом алгебры из ${\textstyle {\frac {R[x]}{\langle x^{n}-1\rangle }}}$ к ${\textstyle \prod _{i}{\frac {R[x]}{\langle x-\omega _{n}^{i}\rangle }}}$ и каждый ${\text{DFT}}_{\omega _{n_{d}}}$ является изоморфизмом алгебры из ${\textstyle {\frac {R[x]}{\langle {x_{d}}^{n_{d}}-1\rangle }}}$ к ${\textstyle \prod _{i_{d}}{\frac {R[x_{d}]}{\langle x_{d}-\omega _{n_{d}}^{i_{d}}\rangle }}}$,у нас есть изоморфизм алгебры $\eta '$ от ${\textstyle \bigotimes _{d}\prod _{i_{d}}{\frac {R[x_{d}]}{\langle x_{d}-\omega _{n_{d}}^{i_{d}}\rangle }}}$ к ${\textstyle \prod _{i}{\frac {R[x]}{\langle x-\omega _{n}^{i}\rangle }}}$.PFA говорит нам, что ${\textstyle {\text{DFT}}_{\omega _{n}}=\eta '\circ \bigotimes _{d}{\text{DFT}}_{\omega _{n_{d}}}\circ \eta ^{*}}$ где $\eta ^{*}$ и $\eta '$ переиндексируются без фактической арифметики в $R$.

Подсчет количества многомерных преобразований

Обратите внимание, что условие преобразования ${\text{DFT}}_{\omega _{n}}$ в ${\textstyle \eta '\circ \bigotimes _{d}{\text{DFT}}_{\omega _{n_{d}}}\circ \eta ^{*}}$ опирается на аддитивный групповой изоморфизм $\eta$ от $(\mathbb {Z} _{n},+,0)$ к ${\textstyle \prod _{d}(\mathbb {Z} _{n_{d}},+,0)}$.Любой аддитивный групповой изоморфизм будет работать.Подсчитать количество способов преобразования ${\text{DFT}}_{\omega _{n}}$ в ${\textstyle \eta '\circ \bigotimes _{d}{\text{DFT}}_{\omega _{n_{d}}}\circ \eta ^{*}}$,нам нужно только посчитать количество аддитивных изоморфизмов групп из $(\mathbb {Z} _{n},+,0)$ к ${\textstyle \prod _{d}(\mathbb {Z} _{n_{d}},+,0)}$или, альтернативно, количество автоморфизмов аддитивной группы на $(\mathbb {Z} _{n},+,0)$.С $(\mathbb {Z} _{n},+,0)$ цикличен , любой автоморфизм можно записать как $1\mapsto g$ где $g$ является генератором ​ $(\mathbb {Z} _{n},+,0)$.По определению $(\mathbb {Z} _{n},+,0)$, $g$'s в точности те, которые взаимно просты с $n$.Поэтому существуют именно $\varphi (n)$ много таких карт, где $\varphi$ — это функция Эйлера .Самый маленький пример $n=6$ где $\varphi (n)=2$, демонстрируя две карты в литературе: «ЭЛТ-картирование» и «Руританское отображение».

См. также

• Алгоритм Блюстейна БПФ
• Алгоритм БПФ Рейдера

Ссылки

• Хорошо, Эй Джей (1958). «Алгоритм взаимодействия и практический анализ Фурье». Журнал Королевского статистического общества, серия B. 20 (2): 361–372. JSTOR   2983896 . Приложение, там же. 22 (2), 373-375 (1960) JSTOR   2984108 .
• Томас, Л.Х. (1963). «Использование компьютера для решения задач по физике». Применение цифровых компьютеров . Бостон: Джинн.
• Дюамель, П.; Веттерли, М. (1990). «Быстрые преобразования Фурье: обзор учебного пособия и современное состояние» . Обработка сигналов . 19 (4): 259–299. дои : 10.1016/0165-1684(90)90158-У .
• Чан, Южная Каролина; Хо, КЛ (1991). «Об индексировании алгоритма быстрого преобразования Фурье с простым коэффициентом». Транзакции IEEE в схемах и системах . 38 (8): 951–953. дои : 10.1109/31.85638 .
• Хорошо, Эй Джей (1971). «Взаимосвязь между двумя быстрыми преобразованиями Фурье». Транзакции IEEE на компьютерах . 100 (3): 310–317. дои : 10.1109/TC.1971.223236 . S2CID   585818 .