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

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

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

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

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

Алгоритм

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

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

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

Если N — простое число, то множество ненулевых индексов $n\in {}\{1,\dots ,N-1\}$ образует группу при умножении модулю N. по Одним из следствий теории чисел таких групп является то, что существует генератор группы (иногда называемый примитивным корнем ), который можно найти путем перебора или несколько более совершенных алгоритмов. ). Этот генератор представляет собой целое число g такое, что $n=g^{q}{\pmod {N}}$ для любого ненулевого индекса n и уникального $q\in {}\{0,\dots ,N-2\}$ (образуя биекцию от q до ненулевого n ). Сходным образом, $k=g^{-p}{\pmod {N}}$ для любого ненулевого индекса k и для уникального $p\in {}\{0,\dots ,N-2\}$, где отрицательный показатель степени обозначает мультипликативную обратную величину $g^{p}\mod N$. Это означает, что мы можем переписать ДПФ, используя эти новые индексы p и q, как:

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

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

(Напомним, что x _n и X _k неявно периодичны по N , а также что $e^{2\pi i}=1$ ( тождество Эйлера ). Таким образом, все индексы и показатели степени берутся по модулю N , как того требует групповая арифметика.)

Окончательное суммирование, приведенное выше, представляет собой в точности циклическую свертку двух последовательностей a _q и b _q (длины N –1, поскольку $q\in {}\{0,\dots ,N-2\}$) определяется:

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

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

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

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

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

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