Введение
Дискретное преобразование Фурье для простых размеров
Алгоритм Радера (1968), названный в честь Чарльза М. Радера из Лаборатории Линкольна Массачусетского технологического института, является быстрым алгоритмом преобразования Фурье (FFT), который вычисляет дискретное преобразование Фурье (DFT) простых размеров, переформулируя DFT как циклическую свертку (другой алгоритм для FFT простых размеров, алгоритм Блюстейна, также работает, переписывая DFT как свертку). Поскольку алгоритм Радера зависит только от периодичности ядра DFT, он непосредственно применим к любому другому преобразованию (простого порядка) с аналогичным свойством, такому как преобразование теории чисел или дискретное преобразование Хартли. Алгоритм может быть модифицирован для получения двукратной экономии для DFT реальных данных, используя слегка измененную переиндексацию/перестановку для получения двух циклических сверток реальных данных; альтернативная адаптация для DFT реальных данных использует дискретное преобразование Хартли. Винноград расширил алгоритм Радера, включив в него размеры DFT, являющиеся степенями простых чисел, и сегодня алгоритм Радера иногда описывается как частный случай алгоритма FFT Виннограда, также называемого алгоритмом мультипликативного преобразования Фурье (Tolimieri et al., 1997), который применим к еще большему классу размеров. Однако для составных размеров, таких как степени простых чисел, алгоритм Cooley–Tukey FFT намного проще и практичнее в реализации, поэтому алгоритм Радера обычно используется только для больших простых базовых случаев рекурсивного разложения DFT Cooley–Tukey). Этот генератор – это целое число g, такое, что для любого ненулевого индекса n существует уникальное (образующее биекцию из q в ненулевые n). Аналогично, для любого ненулевого индекса k существует уникальное , где отрицательный показатель обозначает мультипликативную обратную величину . Это означает, что мы можем переписать DFT, используя эти новые индексы p и q следующим образом:
Rader's algorithm (1968), named for Charles M. Rader of MIT Lincoln Laboratory, is a fast Fourier transform (FFT) algorithm that computes the discrete Fourier transform (DFT) of prime sizes by re expressing the DFT as a cyclic convolution (the other algorithm for FFTs of prime sizes, Bluestein's algorithm, also works by rewriting the DFT as a convolution). Since Rader's algorithm only depends upon the periodicity of the DFT kernel, it is directly applicable to any other transform (of prime order) with a similar property, such as a number theoretic transform or the discrete Hartley transform. The algorithm can be modified to gain a factor of two savings for the case of DFTs of real data, using a slightly modified re indexing/permutation to obtain two half size cyclic convolutions of real data; an alternative adaptation for DFTs of real data uses the discrete Hartley transform. Winograd extended Rader's algorithm to include prime power DFT sizes , and today Rader's algorithm is sometimes described as a special case of Winograd's FFT algorithm, also called the multiplicative Fourier transform algorithm (Tolimieri et al., 1997), which applies to an even larger class of sizes. However, for composite sizes such as prime powers, the Cooley–Tukey FFT algorithm is much simpler and more practical to implement, so Rader's algorithm is typically only used for large prime base cases of Cooley–Tukey's recursive decomposition of the DFT.). This generator is an integer g such that for any non zero index n and for a unique (forming a bijection from q to non zero n). Similarly, for any non zero index k and for a unique , where the negative exponent denotes the multiplicative inverse of That means that we can rewrite the DFT using these new indices p and q as:
(Помните, что xn и Xk неявно периодичны по N, а также что (тождество Эйлера). Таким образом, все индексы и показатели берутся по модулю N, как того требует групповая арифметика.) Итоговая сумма, приведенная выше, является точной циклической сверткой двух последовательностей aq и bq (длины N–1, поскольку ) и определяется следующим образом:
Оценка свёртывания
Поскольку N–1 является составным числом, эту свертку можно выполнить непосредственно с помощью теоремы о свертке и более традиционных алгоритмов FFT. Однако это может быть неэффективно, если N–1 само по себе имеет большие простые множители, что требует рекурсивного использования алгоритма Радера. Вместо этого можно вычислить циклическую свертку длины (N–1) точно, дополнив ее нулями до длины не менее 2(N–1)–1, например, до степени двойки, которую затем можно вычислить за время O(N log N) без рекурсивного применения алгоритма Радера. Следовательно, этот алгоритм требует O(N) сложений плюс O(N log N) времени для выполнения свертки. На практике O(N) сложений часто можно выполнить, включив их в свертку: если свертка выполняется парой FFT, то сумма xn задается выходным значением DC (0-м) FFT от aq плюс x0, и x0 можно добавить ко всем выходным значениям, добавив его к DC-компоненте свертки перед обратным FFT. Тем не менее, этот алгоритм требует по своей сути больше операций, чем FFT для близлежащих составных размеров, и обычно занимает в 3–10 раз больше времени на практике. Если алгоритм Радера выполняется с использованием FFT размера N–1 для вычисления свертки, а не с дополнением нулями, как упоминалось выше, эффективность сильно зависит от N и количества рекурсивных применений алгоритма Радера. Наихудший случай наступит, если N–1 будет равно 2N2, где N2 является простым числом, при этом N2–1 = 2N3, где N3 является простым числом, и так далее. В таких случаях, если предположить, что цепочка простых чисел простирается до некоторого ограниченного значения, рекурсивное применение алгоритма Радера фактически потребует времени O(N2). Такие Nj называются простыми числами Софи Жермен, а такая последовательность из них называется цепью Каннингема первого рода. Однако длины цепей Каннингема растут медленнее, чем log2(N), поэтому алгоритм Радера, применяемый таким образом, вероятно, не имеет сложности O(N2), хотя в худших случаях он может быть хуже, чем O(N log N). К счастью, гарантированная сложность O(N log N) может быть достигнута путем дополнения нулями.