Алгоритм Raders FFT - Raders FFT algorithm

Алгоритм Рейдера (1968),^[1] назван в честь Чарльза М. Рейдера Лаборатория Линкольна Массачусетского технологического института, это быстрое преобразование Фурье (БПФ) алгоритм, который вычисляет дискретное преобразование Фурье (DFT) из основной размеров, переформулируя ДПФ как циклический свертка (другой алгоритм для БПФ простых размеров, Алгоритм Блюстейна, также работает, переписывая ДПФ как свертку).

Поскольку алгоритм Рейдера зависит только от периодичности ядра ДПФ, он напрямую применим к любому другому преобразованию (простого порядка) с аналогичным свойством, например теоретико-числовое преобразование или дискретное преобразование Хартли.

Алгоритм можно модифицировать, чтобы получить двукратную экономию для случая ДПФ реальных данных, используя слегка измененную повторную индексацию / перестановку для получения двух циклических сверток половинного размера реальных данных;^[2] альтернативная адаптация для ДПФ реальных данных использует дискретное преобразование Хартли.^[3]

Виноград расширил алгоритм Рейдера, включив в него размеры ДПФ с простой степенью ${\displaystyle p^{m}}$,^[4][5] и сегодня алгоритм Рейдера иногда описывают как частный случай Алгоритм Винограда БПФ, также называемый алгоритм мультипликативного преобразования Фурье (Tolimieri et al., 1997),^[6] что относится к еще большему классу размеров. Однако для составной такие размеры, как простые степени, Алгоритм Кули – Тьюки БПФ намного проще и практичнее в реализации, поэтому алгоритм Рейдера обычно используется только для большого числа базовые случаи Кули-Тьюки рекурсивный разложение ДПФ.^[3]

Алгоритм

Визуальное представление Матрица ДПФ в алгоритме БПФ Рейдера массив, состоящий из цветных часов, представляет матрицу ДПФ размером 11. Путем перестановки строк и столбцов с использованием последовательности, сгенерированной примитивным корнем из 11 (который равен 2), за исключением 1-й строки и столбца, исходная матрица ДПФ становится а циркулянтная матрица. Умножение циркулянтной матрицы на последовательность данных эквивалентно циклическая свертка. Это соотношение является примером того, что мультипликативная группа циклично: ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }\cong C_{p-1}}$.

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1.}$

Если N - простое число, то множество ненулевых индексов п = 1,...,N–1 образует группа при умножении по модулю N. Одно из последствий теория чисел таких групп состоит в том, что существует генератор группы (иногда называемой первобытный корень, который можно быстро найти с помощью исчерпывающего поиска или чуть более эффективных алгоритмов^[7]), целое число грамм такой, что п = грамм^q (мод N) для любого ненулевого индекса п и для уникального q в 0, ...,N–2 (образуя биекция из q ненулевой п). по аналогии k = грамм^–п (мод N) для любого ненулевого индекса k и для уникального п в 0, ...,N–2, где отрицательный показатель означает мультипликативный обратный из грамм^п по модулю N. Это означает, что мы можем переписать ДПФ, используя эти новые индексы п и q в качестве:

${\displaystyle X_{0}=\sum _{n=0}^{N-1}x_{n},}$

${\displaystyle X_{g^{-p}}=x_{0}+\sum _{q=0}^{N-2}x_{g^{q}}e^{-{\frac {2\pi i}{N}}g^{-(p-q)}}\qquad p=0,\dots ,N-2.}$

(Напомним, что Икс_п и Икс_k неявно периодичны по N, а также что е^2πi= 1. Таким образом, все индексы и показатели берутся по модулю N в соответствии с требованиями групповой арифметики.)

Заключительное суммирование, приведенное выше, представляет собой в точности циклическую свертку двух последовательностей а_q и б_q длины N–1 (q = 0,...,N–2) определяется:

${\displaystyle a_{q}=x_{g^{q}}}$

${\displaystyle b_{q}=e^{-{\frac {2\pi i}{N}}g^{-q}}.}$

Оценка свертки

С N–1 является составным, эту свертку можно выполнить напрямую через теорема свертки и более традиционные алгоритмы БПФ. Однако это может быть неэффективным, если N–1 сам по себе имеет большие простые множители, что требует рекурсивного использования алгоритма Рейдера. Вместо этого можно вычислить длину - (N–1) циклическая свертка точно путем дополнения ее нулями до длины не менее 2 (N–1) –1, скажем сила двух, который затем может быть вычислен за O (N бревно N) время без рекурсивного применения алгоритма Рейдера.

Следовательно, этот алгоритм требует O (N) сложения плюс O (N бревно N) время для свертки. На практике O (N) сложения часто могут выполняться путем поглощения добавлений в свертку: если свертка выполняется парой БПФ, то сумма Икс_п задается выходом DC (0-й) БПФ а_q плюс Икс₀, и Икс₀ может быть добавлен ко всем выходам, добавив его к члену постоянного тока свертки перед обратным БПФ. Тем не менее, этот алгоритм требует больше операций, чем БПФ близких составных размеров, и на практике обычно занимает в 3–10 раз больше времени.

Если алгоритм Райдера выполняется с использованием БПФ размера N–1 для вычисления свертки, а не путем заполнения нулями, как упоминалось выше, эффективность сильно зависит от N и сколько раз алгоритм Рейдера должен применяться рекурсивно. Худший случай был бы, если бы N–1 были 2N₂ куда N₂ простое, с N₂–1 = 2N₃ куда N₃ простое и так далее. В таких случаях, если предположить, что цепочка простых чисел расширяется до некоторого ограниченного значения, рекурсивное применение алгоритма Рейдера фактически потребует O (N²) время. Такой N_j называются Софи Жермен простые числа, и такая их последовательность называется Сеть Каннингем первого вида. Однако длина цепей Каннингема растет медленнее, чем длина логарифмических цепей.₂(N), поэтому алгоритм Рейдера, примененный таким образом, вероятно, не О (N²), хотя, возможно, хуже, чем O (N бревно N) для худших случаев. К счастью, гарантия O (N бревно N) сложности можно достичь нулевым заполнением.

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

1. К. М. Рейдер, «Дискретное преобразование Фурье, когда количество выборок данных является простым», Proc. IEEE 56, 1107–1108 (1968).
2. С. Чу и К. Буррус, "Простой фактор FTT [sic] алгоритм с использованием распределенной арифметики, " Транзакции IEEE по акустике, речи и обработке сигналов 30 (2), 217–227 (1982).
3. Маттео Фриго и Стивен Дж. Джонсон, "Дизайн и реализация FFTW3," Труды IEEE 93 (2), 216–231 (2005).
4. С. Виноград, "О вычислении дискретного преобразования Фурье", Proc. Национальная академия наук США, 73(4), 1005–1006 (1976).
5. С. Виноград, "О вычислении дискретного преобразования Фурье", Математика вычислений, 32(141), 175–199 (1978).
6. Р. Толимьери, М. Ан и К. Лу, Алгоритмы дискретного преобразования Фурье и свертки, Springer-Verlag, 2-е изд., 1997.
7. Дональд Э. Кнут, Искусство программирования, т. 2: получисловые алгоритмы, 3-е издание, раздел 4.5.4, с. 391 (Аддисон – Уэсли, 1998).