Алгоритм БПФ Кули – Тьюки

Алгоритм Кули-Тьюки , названный в честь Дж. Кули и Джона Тьюки , является наиболее распространенным алгоритмом быстрого преобразования Фурье (БПФ). Он повторно выражает дискретное преобразование Фурье (ДПФ) произвольного составного размера . $N=N_{1}N_{2}$ в терминах N ₁ меньших ДПФ размером N ₂ рекурсивно , чтобы сократить время вычислений до O( N log N ) для очень сложных N ( гладких чисел ). Из-за важности алгоритма конкретные варианты и стили реализации стали известны под собственными именами, как описано ниже.

Поскольку алгоритм Кули-Тьюки разбивает ДПФ на более мелкие ДПФ, его можно произвольно комбинировать с любым другим алгоритмом ДПФ. Например, алгоритм Рейдера или Блюстейна можно использовать для обработки больших простых множителей, которые не могут быть разложены по методу Кули-Тьюки, или алгоритм простых множителей можно использовать для большей эффективности при выделении относительно простых множителей.

Алгоритм вместе с его рекурсивным применением был изобретен Карлом Фридрихом Гауссом . Кули и Тьюки независимо друг от друга заново открыли и популяризировали его 160 лет спустя.

История

Этот алгоритм, включая его рекурсивное применение, был изобретен около 1805 года Карлом Фридрихом Гауссом , который использовал его для интерполяции траекторий астероидов Паллады и Юноны , однако его работа не получила широкого признания (опубликована только посмертно и на неолатинском языке ). ^[1]^[2] Однако Гаусс не анализировал асимптотическое время вычислений. Различные ограниченные формы также несколько раз открывались заново на протяжении XIX и начала XX веков. ^[2] БПФ стали популярными после того, как Джеймс Кули из IBM и Джон Тьюки из Принстона опубликовали в 1965 году статью, заново изобретающую ^[2] алгоритм и описание того, как удобно его выполнить на компьютере. ^[3]

Сообщается, что Тьюки пришла в голову эта идея во время заседания Научно-консультативного комитета президента Кеннеди, где обсуждались способы обнаружения испытаний ядерного оружия в Советском Союзе с помощью сейсмометров, расположенных за пределами страны. Эти датчики будут генерировать сейсмологические временные ряды. Однако анализ этих данных потребует быстрых алгоритмов расчета ДПФ из-за количества датчиков и продолжительности времени. Эта задача имела решающее значение для ратификации предлагаемого запрета ядерных испытаний, чтобы любые нарушения можно было обнаружить без необходимости посещать советские объекты. ^[4]^[5] Другой участник этой встречи, Ричард Гарвин из IBM, осознал потенциал метода и познакомил Тьюки с Кули. Однако Гарвин позаботился о том, чтобы Кули не знал первоначальной цели. Вместо этого Кули сказали, что это необходимо для определения периодичности ориентации спинов в трехмерном кристалле гелия-3 . Кули и Тьюки впоследствии опубликовали свою совместную статью, и вскоре последовало широкое распространение благодаря одновременной разработке аналого-цифровых преобразователей, способных осуществлять выборку с частотой до 300 кГц.

Тот факт, что Гаусс описал тот же алгоритм (хотя и без анализа его асимптотической стоимости), был осознан только через несколько лет после статьи Кули и Тьюки 1965 года. ^[2] В их статье в качестве вдохновения упоминалась только работа И. Дж. Гуда о том, что сейчас называется алгоритмом БПФ с простыми факторами (PFA); ^[3] хотя первоначально считалось, что алгоритм Гуда эквивалентен алгоритму Кули-Тьюки, быстро стало понятно, что PFA - это совершенно другой алгоритм (работающий только для размеров, которые имеют относительно простые множители и основанный на китайской теореме об остатках , в отличие от поддержки любого алгоритма Гуда). составной размер по Кули-Тьюки). ^[6]

Случай DIT с основанием 2

БПФ по основанию 2 с прореживанием во времени ( DIT ) является самой простой и наиболее распространенной формой алгоритма Кули-Тьюки, хотя высокооптимизированные реализации Кули-Тьюки обычно используют другие формы алгоритма, как описано ниже. DIT по основанию-2 делит ДПФ размера N на два чередующихся ДПФ (отсюда и название «основание-2») размера N /2 на каждом рекурсивном этапе.

Дискретное преобразование Фурье (ДПФ) определяется формулой:

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

где $k$ целое число от 0 до $N-1$ .

DIT Radix-2 сначала вычисляет ДПФ входных данных с четным индексом. $(x_{2m}=x_{0},x_{2},\ldots ,x_{N-2})$ и входных данных с нечетным индексом $(x_{2m+1}=x_{1},x_{3},\ldots ,x_{N-1})$ , а затем объединяет эти два результата для получения ДПФ всей последовательности. Затем эту идею можно реализовать рекурсивно , чтобы сократить общее время выполнения до O( N log N ). Эта упрощенная форма предполагает, что N является степенью двойки ; поскольку количество точек выборки N обычно может свободно выбираться приложением (например, путем изменения частоты выборки или окна, заполнения нулями и т. д.), это часто не является важным ограничением.

Алгоритм DIT по основанию 2 перестраивает ДПФ функции. $x_{n}$ на две части: сумму по четным индексам $n={2m}$ и сумма по нечетным индексам $n={2m+1}$ :

{\begin{matrix}X_{k}&=&\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N}}(2m)k}+\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N}}(2m+1)k}\end{matrix}}

Можно факторизовать общий множитель $e^{-{\frac {2\pi i}{N}}k}$ из второй суммы, как показано в уравнении ниже. Тогда ясно, что две суммы представляют собой ДПФ четной части. $x_{2m}$ и ДПФ нечетной части $x_{2m+1}$ функции $x_{n}$ . Обозначим ДПФ . входных данных, индексированных по четности $x_{2m}$ к $E_{k}$ и ДПФ Odd входных данных с индексом $x_{2m+1}$ к $O_{k}$ и мы получаем:

{\begin{matrix}X_{k}=\underbrace {\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N/2}}mk}} _{\mathrm {DFT\;of\;even-indexed\;part\;of\;} x_{n}}{}+e^{-{\frac {2\pi i}{N}}k}\underbrace {\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N/2}}mk}} _{\mathrm {DFT\;of\;odd-indexed\;part\;of\;} x_{n}}=E_{k}+e^{-{\frac {2\pi i}{N}}k}O_{k}\qquad {\text{ for }}k=0,\dots ,{\frac {N}{2}}-1.\end{matrix}}

Заметим, что равенства справедливы для $k=0,\dots ,N-1$ , но суть в том, что $E_{k}$ и $O_{k}$ рассчитываются таким образом для $k=0,\dots ,{\frac {N}{2}}-1$ только. Благодаря периодичности комплексной экспоненты , $X_{k+{\frac {N}{2}}}$ также получено из $E_{k}$ и $O_{k}$ :

{\begin{aligned}X_{k+{\frac {N}{2}}}&=\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N/2}}m(k+{\frac {N}{2}})}+e^{-{\frac {2\pi i}{N}}(k+{\frac {N}{2}})}\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N/2}}m(k+{\frac {N}{2}})}\\&=\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N/2}}mk}e^{-2\pi mi}+e^{-{\frac {2\pi i}{N}}k}e^{-\pi i}\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N/2}}mk}e^{-2\pi mi}\\&=\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N/2}}mk}-e^{-{\frac {2\pi i}{N}}k}\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N/2}}mk}\\&=E_{k}-e^{-{\frac {2\pi i}{N}}k}O_{k}\end{aligned}}

Мы можем переписать $X_{k}$ и $X_{k+{\frac {N}{2}}}$ как:

{\begin{matrix}X_{k}&=&E_{k}+e^{-{\frac {2\pi i}{N}}{k}}O_{k}\\X_{k+{\frac {N}{2}}}&=&E_{k}-e^{-{\frac {2\pi i}{N}}{k}}O_{k}\end{matrix}}

Этот результат, выражающий ДПФ длины N рекурсивно через два ДПФ размера N /2, является основой быстрого преобразования Фурье ДИТ по основанию 2. Алгоритм увеличивает скорость за счет повторного использования результатов промежуточных вычислений для вычисления нескольких выходных данных ДПФ. Обратите внимание, что окончательные результаты получаются комбинацией +/- $E_{k}$ и $O_{k}\exp(-2\pi ik/N)$ , который представляет собой просто ДПФ размера 2 (иногда называемый бабочкой в этом контексте ); когда это обобщается на более крупные радикалы ниже, ДПФ размера 2 заменяется более крупным ДПФ (которое само по себе можно оценить с помощью БПФ).

Диаграмма потока данных для N = 8: БПФ с прореживанием во времени по основанию 2 разбивает ДПФ длины N на два ДПФ длины N /2 с последующим этапом объединения, состоящим из N /2 ДПФ размера 2, называемым «бабочка». операции (так называемые из-за формы диаграмм потоков данных).

Этот процесс является примером общей техники алгоритмов «разделяй и властвуй» ; однако во многих традиционных реализациях явной рекурсии избегают, и вместо этого вычислительное дерево обходит в ширину .

Вышеупомянутое перевыражение ДПФ размера N в виде двух ДПФ размера N /2 иногда называют Дэниэлсона – Ланцоша леммой , поскольку идентичность была отмечена этими двумя авторами в 1942 году. ^[7] (под влиянием Рунге 1903 г.) работы ^[2]). Они применили свою лемму «обратно» рекурсивным способом, неоднократно удваивая размер ДПФ до тех пор, пока спектр преобразования не сошелся (хотя они, очевидно, не осознавали линейную асимптотическую сложность (т. е. порядка N log N ), которой они достигли). Работа Дэниэлсона-Ланцоша предшествовала широкому распространению механических или электронных компьютеров и требовала ручных вычислений (возможно, с использованием механических средств, таких как арифмометры ); они сообщили о времени вычисления 140 минут для ДПФ размера 64, работающего на реальных входных данных с 3–5 значащими цифрами. В статье Кули и Тьюки 1965 года сообщалось о времени работы 0,02 минуты для комплексного ДПФ размером 2048 на IBM 7094 (вероятно, с 36-битной одинарной точностью , ~ 8 цифр). ^[3] При масштабировании времени по количеству операций это примерно соответствует коэффициенту ускорения около 800 000. (Для сравнения: 140 минут для размера 64 соответствуют в среднем максимум 16 секундам на операцию с плавающей запятой, около 20% из которых — умножения.)

Псевдокод

В псевдокоде можно записать следующую процедуру: ^[8]

X_0,...,N−1 ← ditfft2(x, N, s):             DFT of (x₀, x_s, x_2s, ..., x_(N-1)s):
    if N = 1 then
        X₀ ← x₀                                      trivial size-1 DFT base case
    else
        X_{0,...,N/2−1} ← ditfft2(x, N/2, 2s)             DFT of (x₀, x_2s, x_4s, ..., x_(N-2)s)
        X_N_/2,...,N−1 ← ditfft2(x+s, N/2, 2s)           DFT of (x_s, x_s_+2s, x_s_+4s, ..., x_(N-1)s)
        for k = 0 to N/2−1 do                        combine DFTs of two halves into full DFT:
            p ← X_k
            q ← exp(−2πi/N k) X_k_+N/2
            X_k ← p + q 
            X_k_+N/2 ← p − q
        end for
    end if

Здесь, ditfft2( x , N ,1), вычисляет X =DFT( x ) неуместно с помощью DIT FFT по основанию 2, где N — целая степень 2, а s =1 — шаг входного x массива . x + s обозначает массив, начинающийся с x _s .

(Результаты находятся в правильном порядке по X , и дальнейшая перестановка битов не требуется; часто упоминаемая необходимость отдельной стадии реверса битов возникает только для определенных алгоритмов на месте, как описано ниже.)

Высокопроизводительные реализации БПФ вносят множество изменений в реализацию такого алгоритма по сравнению с этим простым псевдокодом. Например, можно использовать базовый вариант большего размера, чем N = 1, чтобы амортизировать накладные расходы на рекурсию, коэффициенты поворота $\exp[-2\pi ik/N]$ могут быть предварительно вычислены, и более крупные радиусы часто используются по кэширования причинам ; вместе эти и другие оптимизации могут повысить производительность на порядок и более. ^[8] (Во многих реализациях учебников рекурсия в глубину устраняется в пользу нерекурсивного подхода в ширину , хотя утверждается, что рекурсия в глубину имеет лучшую локальность в памяти . ^[8]^[9]) Некоторые из этих идей более подробно описаны ниже.

Идея

Основной шаг БПФ Кули-Тьюки для общих факторизаций можно рассматривать как переинтерпретацию 1d ДПФ как нечто вроде 2d ДПФ. Входной массив 1d длиной N = N ₁ N ₂ переинтерпретируется как матрица 2d N ₁ × N _2, хранящаяся в порядке по столбцам . Один выполняет меньшие 1d ДПФ вдоль *направления N* ₂ (несмежное направление), затем умножает на фазовые коэффициенты (коэффициенты вращения) и, наконец, выполняет 1d ДПФ вдоль *направления N* ₁ . Шаг транспонирования может быть выполнен в середине, как показано здесь, или в начале или в конце. Это делается рекурсивно для меньших преобразований.

В более общем смысле, алгоритмы Кули-Тьюки рекурсивно повторно выражают ДПФ составного размера N = N ₁ N ₂ как: ^[10]

Выполните N ₁ ДПФ размера N ₂ .
Умножьте на комплексные корни из единицы (часто называемые коэффициентами вращения ).
Выполните N ₂ ДПФ размера N ₁ .

Обычно либо N ₁ , либо N ₂ представляет собой небольшой множитель ( не обязательно простой), называемый системой счисления (который может различаться на разных этапах рекурсии). Если N ₁ является основанием системы счисления, это называется алгоритмом прореживания по времени (DIT), тогда как если N ₂ является основанием системы счисления, это прореживание по частоте (DIF, также называемый алгоритмом Санде-Тьюки). Представленная выше версия представляла собой алгоритм DIT по основанию 2; в окончательном выражении фаза, умножающая нечетное преобразование, является коэффициентом поворота, а комбинация +/- ( бабочка ) четного и нечетного преобразований представляет собой ДПФ размера 2. (Маленькое ДПФ системы счисления иногда называют « бабочкой » из-за формы диаграммы потока данных для случая системы счисления 2.)

Вариации

Существует множество других вариантов алгоритма Кули – Тьюки. Реализации со смешанной системой счисления обрабатывают составные размеры с множеством (обычно небольших) коэффициентов в дополнение к двум, обычно (но не всегда) с использованием O( N ²) алгоритм для простых базовых случаев рекурсии (также можно использовать алгоритм N log N для простых базовых случаев, такой как алгоритм Радера или Блюстейна ). Разделенное основание системы счисления объединяет основания 2 и 4, используя тот факт, что первое преобразование системы счисления 2 не требует коэффициента поворота, чтобы достичь того, что долгое время было наименьшим известным числом арифметических операций для размеров степени двойки, ^[10] хотя в недавних вариациях счетчик еще меньше. ^[11]^[12] (На современных компьютерах производительность определяется в большей степени соображениями кэша и конвейера ЦП , чем строгим подсчетом операций; хорошо оптимизированные реализации БПФ часто используют более крупные вычисления и/или жестко запрограммированные преобразования базового случая значительного размера. ^[13]).

Другой способ взглянуть на алгоритм Кули-Тьюки состоит в том, что он повторно выражает размера N одномерное ДПФ размером N ₁ на N ₂ как двумерное ДПФ (плюс твиддлы), где выходная матрица транспонируется . Конечный результат всех этих транспозиций для алгоритма счисления 2 соответствует битовому обращению входных (DIF) или выходных (DIT) индексов. Если вместо использования небольшого основания системы счисления используется основание примерно √ N и явные транспозиции матриц ввода-вывода, это называется четырехшаговым алгоритмом БПФ (или шестишаговым , в зависимости от количества транспозиций), первоначально предложенным для улучшения локальности памяти, ^[14]^[15] например, для оптимизации кэша или работы вне ядра , и позже было показано, что это оптимальный алгоритм, не обращающий внимания на кэш . ^[16]

Общая факторизация Кули – Тьюки переписывает индексы k и n как $k=N_{2}k_{1}+k_{2}$ и $n=N_{1}n_{2}+n_{1}$ , соответственно, где индексы k _a и n _a изменяются от 0 до N _a -1 (для a, равного 1 или 2). То есть он переиндексирует входные ( n ) и выходные ( k ) N ₁ на N ₂ двумерные массивы в порядке по столбцам и по строкам соответственно; разница между этими индексациями представляет собой транспозицию, как упоминалось выше. Когда эта переиндексация подставляется в формулу ДПФ для nk , $N_{1}n_{2}N_{2}k_{1}$ перекрестный член обращается в нуль (его экспонента равна единице), а остальные члены дают

X_{N_{2}k_{1}+k_{2}}=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}x_{N_{1}n_{2}+n_{1}}e^{-{\frac {2\pi i}{N_{1}N_{2}}}\cdot (N_{1}n_{2}+n_{1})\cdot (N_{2}k_{1}+k_{2})}

=\sum _{n_{1}=0}^{N_{1}-1}\left[e^{-{\frac {2\pi i}{N_{1}N_{2}}}n_{1}k_{2}}\right]\left(\sum _{n_{2}=0}^{N_{2}-1}x_{N_{1}n_{2}+n_{1}}e^{-{\frac {2\pi i}{N_{2}}}n_{2}k_{2}}\right)e^{-{\frac {2\pi i}{N_{1}}}n_{1}k_{1}}

=\sum _{n_{1}=0}^{N_{1}-1}\left(\sum _{n_{2}=0}^{N_{2}-1}x_{N_{1}n_{2}+n_{1}}e^{-{\frac {2\pi i}{N_{2}}}n_{2}k_{2}}\right)e^{-{\frac {2\pi i}{N_{1}N_{2}}}n_{1}(N_{2}k_{1}+k_{2})}

.

где каждая внутренняя сумма представляет собой ДПФ размера N ₂ , каждая внешняя сумма представляет собой ДПФ размера N ₁ , а член [...] в квадратных скобках представляет собой коэффициент вращения.

Можно использовать произвольную систему счисления r (а также смешанные системы счисления), как показали Кули и Тьюки. ^[3] а также Гаусс (который привел примеры ступеней по основанию счисления-3 и основания-6). ^[2] Кули и Тьюки первоначально предположили, что для системы счисления «бабочка» требуется O( r ²) работают и, следовательно, посчитали, что сложность системы счисления r равна O( r ² N / r log _r N ) = O( N log ₂ ( N ) r /log ₂ r ); в результате расчета значений r /log ₂ r для целых значений r от 2 до 12 оптимальное основание счисления равно 3 (ближайшее целое число к e , которое минимизирует r /log ₂ r ). ^[3]^[17] Однако этот анализ был ошибочным: система счисления-бабочка также является ДПФ и может быть выполнена с помощью алгоритма БПФ за O( r log r ) операций, следовательно, система счисления r фактически сокращается со сложностью O( r log( r ) N / r log _r N ), а оптимальное r определяется из более сложных соображений. На практике достаточно большие значения r (32 или 64) важны для эффективного использования, например, большого количества регистров процессора в современных процессорах. ^[13] и даже неограниченное основание системы счисления r = √ N также достигает сложности O( N log N ) и имеет теоретические и практические преимущества для больших N , как упоминалось выше. ^[14]^[15]^[16]

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

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

Самый известный метод переупорядочения включает явный переворот битов для алгоритмов счисления 2 на месте. Реверс битов — это перестановка , при которой данные с индексом n , записанные в двоичном формате с цифрами b ₄ b ₃ b ₂ b ₁ b ₀ (например, 5 цифр для N =32 входов), переносятся в индекс с перевернутыми цифрами b ₀ b. ₁ б ₂ б ₃ б ₄ . Рассмотрим последний этап алгоритма DIT по основанию 2, подобный представленному выше, где выходные данные записываются поверх входных: когда $E_{k}$ и $O_{k}$ комбинируются с ДПФ размера 2, эти два значения перезаписываются выходными данными. Однако два выходных значения должны находиться в первой и второй половинах выходного массива, что соответствует старшему биту b 4 ₍ для N =32); тогда как два входа $E_{k}$ и $O_{k}$ чередуются четные и нечетные элементы, соответствующие младшему биту b ₀ . Таким образом, чтобы получить результат в правильном месте, b ₀ должен занять место b ₄ , и индекс станет b ₀ b ₄ b ₃ b ₂ b ₁ . И для следующего рекурсивного этапа эти 4 младших бита станут b ₁ b ₄ b ₃ b ₂ . Если вы включите все рекурсивные этапы алгоритма DIT по основанию 2, все биты должны быть поменяны местами, и, следовательно, необходимо предварительно обработайте ввод ( или постобработку вывода) с небольшим изменением бита, чтобы получить упорядоченный вывод. (Если каждое подпреобразование размера N /2 должно работать с смежными данными, вход DIT предварительно обрабатывается путем переворота битов.) Соответственно, если вы выполняете все шаги в обратном порядке, вы получаете алгоритм DIF по основанию 2. с перестановкой битов при постобработке (или предварительной обработке соответственно).

Логарифм (log), используемый в этом алгоритме, представляет собой логарифм по основанию 2.

Ниже приведен псевдокод итеративного алгоритма БПФ по основанию 2, реализованного с использованием перестановки битов. ^[18]

algorithm iterative-fft is
    input: Array a of n complex values where n is a power of 2.
    output: Array A the DFT of a.
 
    bit-reverse-copy(a, A)
    n ← a.length 
    for s = 1 to log(n) do
        m ← 2^s
        ω_m ← exp(−2πi/m) 
        for k = 0 to n-1 by m do
            ω ← 1
            for j = 0 to m/2 – 1 do
                t ← ω A[k + j + m/2]
                u ← A[k + j]
                A[k + j] ← u + t
                A[k + j + m/2] ← u – t
                ω ← ω ω_m
   
    return A

Процедура обратного копирования битов может быть реализована следующим образом.

algorithm bit-reverse-copy(a,A) is
    input: Array a of n complex values where n is a power of 2.
    output: Array A of size n.

    n ← a.length
    for k = 0 to n – 1 do
        A[rev(k)] := a[k]

В качестве альтернативы, некоторые приложения (например, свертка) одинаково хорошо работают с данными с инвертированными битами, поэтому можно выполнять прямое преобразование, обработку, а затем обратные преобразования без реверсирования битов для получения окончательных результатов в естественном порядке.

Однако многие пользователи БПФ предпочитают выходные данные в естественном порядке, и отдельный этап явного обращения битов может оказать немаловажное влияние на время вычислений. ^[13] даже несмотря на то, что реверсирование битов может быть выполнено за время O( N ) и было предметом большого количества исследований. ^[19]^[20]^[21] Кроме того, хотя в случае системы счисления 2 перестановка представляет собой перестановку битов, в более общем случае это перестановка произвольных цифр (смешанной базы) для случая смешанной системы счисления, и алгоритмы перестановки становятся более сложными для реализации. Более того, во многих аппаратных архитектурах желательно переупорядочить промежуточные этапы алгоритма БПФ, чтобы они работали с последовательными (или, по крайней мере, более локализованными) элементами данных. С этой целью был разработан ряд альтернативных схем реализации алгоритма Кули-Тьюки, не требующих отдельной перестановки битов и/или предполагающих дополнительные перестановки на промежуточных этапах.

Проблема значительно упрощается, если она неуместна : выходной массив отличается от входного массива или, что то же самое, доступен вспомогательный массив равного размера. автосортировки Стокхэма Алгоритм ^[22]^[23] выполняет каждый этап БПФ неуместно, обычно записывая туда и обратно между двумя массивами, транспонируя одну «цифру» индексов на каждом этапе, и особенно популярен в SIMD . архитектурах ^[23]^[24] Еще большие потенциальные преимущества SIMD (больше последовательных доступов) были предложены для алгоритма Пиза . ^[25] который также переупорядочивает неуместные значения на каждом этапе, но этот метод требует отдельного переворота бит/цифр и хранения O( N log N ). Можно также напрямую применить определение факторизации Кули-Тьюки с явной рекурсией ( сначала в глубину ) и небольшими корнями, что дает неуместный результат естественного порядка без отдельного шага перестановки (как в приведенном выше псевдокоде) и можно утверждать, что чтобы иметь преимущества локальности без учета кэша в системах с иерархической памятью . ^[9]^[13]^[26]

Типичная стратегия для алгоритмов на месте без вспомогательной памяти и без отдельных проходов обращения цифр включает небольшие транспозиции матриц (которые меняют местами отдельные пары цифр) на промежуточных этапах, которые можно комбинировать с базовыми бабочками, чтобы уменьшить количество проходов по данные. ^[13]^[27]^[28]^[29]^[30]

Ссылки

^ Гаусс, Карл Фридрих (1866). «Теория интерполяции метода нова трактата» [Теория нового метода интерполяции]. Усадьба (Неопубликованная рукопись). Сочинения (на латыни и немецком языке). Том 3. Геттинген, Германия: Королевское общество наук в Геттингене. стр. 265–303.
^ Jump up to: ^а ^б ^с ^д ^и ^ж Хайдеман, М.Т., Д.Х. Джонсон и К.С. Буррус , « Гаусс и история быстрого преобразования Фурье », журнал IEEE ASSP Magazine, 1, (4), 14–21 (1984).
^ Jump up to: ^а ^б ^с ^д ^и Кули, Джеймс В.; Тьюки, Джон В. (1965). «Алгоритм машинного вычисления комплексных рядов Фурье» . Математика. Вычислить. 19 (90): 297–301. дои : 10.2307/2003354 . JSTOR 2003354 .
^ Кули, Джеймс В.; Льюис, Питер AW; Уэлч, Питер Д. (1967). «Исторические заметки о быстром преобразовании Фурье» (PDF) . Транзакции IEEE по аудио и электроакустике . 15 (2): 76–79. CiteSeerX 10.1.1.467.7209 . дои : 10.1109/tau.1967.1161903 .
^ Рокмор, Дэниел Н., Comput. наук. англ. 2 (1), 60 (2000). БПФ — алгоритм, которым может пользоваться вся семья. Специальный выпуск о «десятке лучших алгоритмов века». Барри А. Сипра. «Лучшее в 20-м веке: редакторы назвали 10 лучших алгоритмов» (PDF) . СИАМ Новости . 33 (4). Архивировано из оригинала (PDF) 7 апреля 2009 г. Проверено 31 марта 2009 г.
^ Джеймс В. Кули, Питер А.В. Льюис и Питер В. Уэлч, «Исторические заметки о быстром преобразовании Фурье», Proc. IEEE , том. 55 (№ 10), с. 1675–1677 (1967).
^ Дэниэлсон, Г.К. и К. Ланцос, «Некоторые улучшения в практическом анализе Фурье и их применении к рассеянию рентгеновских лучей в жидкостях», J. Franklin Inst. 233 , 365–380 и 435–452 (1942).
^ Jump up to: ^а ^б ^с С. Г. Джонсон и М. Фриго, « Реализация БПФ на практике », в книге «Быстрые преобразования Фурье » (ред. CS Burrus), гл. 11, Университет Райса, Хьюстон, Техас: Connexions, сентябрь 2008 г.
^ Jump up to: ^а ^б Синглтон, Ричард К. (1967). «О вычислении быстрого преобразования Фурье» . Коммун. АКМ . 10 (10): 647–654. дои : 10.1145/363717.363771 . S2CID 6287781 .
^ Jump up to: ^а ^б Дюамель П. и М. Веттерли, «Быстрые преобразования Фурье: обзор учебного пособия и современное состояние», Signal Processing 19 , 259–299 (1990).
^ Ланди, Т. и Дж. Ван Баскирк, «Новый матричный подход к реальным БПФ и сверткам длины 2». ^к», Computing 80 , 23–45 (2007).
^ Джонсон, С.Г. и М. Фриго, « Модифицированное БПФ с разделением системы счисления с меньшим количеством арифметических операций », IEEE Trans. Сигнальный процесс. 55 (1), 111–119 (2007).
^ Jump up to: ^а ^б ^с ^д ^и Фриго, М.; Джонсон, С.Г. (2005). «Проектирование и реализация FFTW3» (PDF) . Труды IEEE . 93 (2): 216–231. Бибкод : 2005IEEP..93..216F . CiteSeerX 10.1.1.66.3097 . дои : 10.1109/JPROC.2004.840301 . S2CID 6644892 .
^ Jump up to: ^а ^б Джентльмен В.М. и Г. Санде, «Быстрое преобразование Фурье — для развлечения и прибыли», Proc. AFIPS 29 , 563–578 (1966).
^ Jump up to: ^а ^б Бейли, Дэвид Х., «БПФ во внешней или иерархической памяти», J. Supercomputing 4 (1), 23–35 (1990).
^ Jump up to: ^а ^б М. Фриго, К.Э. Лейзерсон, Х. Прокоп и С. Рамачандран. Алгоритмы, не обращающие внимания на кэш. В материалах 40-го симпозиума IEEE по основам информатики (FOCS 99), стр. 285–297. 1999. Расширенный реферат в IEEE , в Citeseer .
^ Кули, Дж.В., П. Льюис и П. Уэлч, «Быстрое преобразование Фурье и его приложения», IEEE Trans on Education 12 , 1, 28–34 (1969)
^ Кормен, Томас Х.; Лейзерсон, Чарльз; Ривест, Рональд; Стоун, Клиффорд (2009). Введение в алгоритмы (3-е изд.). Кембридж, Массачусетс: MIT Press. стр. 915–918. ISBN 978-0-262-03384-8 .
^ Карп, Алан Х. (1996). «Перестановка битов на однопроцессорах». Обзор СИАМ . 38 (1): 1–26. CiteSeerX 10.1.1.24.2913 . дои : 10.1137/1038001 . JSTOR 2132972 .
^ Картер, Ларри; Гатлин, Кан Су (1998). «На пути к оптимальной программе перестановки битов». Материалы 39-го ежегодного симпозиума по основам информатики (кат. № 98CB36280) . стр. 544–553. CiteSeerX 10.1.1.46.9319 . дои : 10.1109/SFCS.1998.743505 . ISBN 978-0-8186-9172-0 . S2CID 14307262 .
^ Рубио, М.; Гомес, П.; Друиш, К. (2002). «Новый сверхбыстрый алгоритм перестановки битов». Международный журнал адаптивного управления и обработки сигналов . 16 (10): 703–707. дои : 10.1002/acs.718 . S2CID 62201722 .
^ Первоначально приписывается Стокхэму в WT Cochran et al. , Что такое быстрое преобразование Фурье? , учеб. IEEE том. 55, 1664–1674 (1967).
^ Jump up to: ^а ^б П. Н. Шварцтраубер, Алгоритмы БПФ для векторных компьютеров , Parallel Computing vol. 1, 45–63 (1984).
^ Шварцтраубер, ПН (1982). «Векторизация БПФ» . В Родриге, Г. (ред.). Параллельные вычисления . Нью-Йорк: Академическая пресса. стр. 51–83 . ISBN 978-0-12-592101-5 .
^ Пиз, MC (1968). «Адаптация быстрого преобразования Фурье для параллельной обработки» . Дж. АКМ . 15 (2): 252–264. дои : 10.1145/321450.321457 . S2CID 14610645 .
^ Фриго, Маттео; Джонсон, Стивен Г. «FFTW» . Бесплатная ( GPL ) библиотека C для вычисления дискретных преобразований Фурье в одном или нескольких измерениях произвольного размера с использованием алгоритма Кули – Тьюки.
^ Джонсон, HW; Буррус, CS (1984). «БПФ по основанию-2 на месте». Учеб. ICASSP : 28A.2.1–28A.2.4.
^ Темпертон, К. (1991). «Быстрое преобразование Фурье с самосортировкой на месте». Журнал SIAM по научным и статистическим вычислениям . 12 (4): 808–823. дои : 10.1137/0912043 .
^ Цянь, З.; Лу, К.; Ан, М.; Толимьери, Р. (1994). «Алгоритм БПФ с самосортировкой на месте и минимальным рабочим пространством». IEEE Транс. АССП . 52 (10): 2835–2836. Бибкод : 1994ITSP...42.2835Q . дои : 10.1109/78.324749 .
^ Хегланд, М. (1994). «Алгоритм быстрого преобразования Фурье с самосортировкой на месте, подходящий для векторной и параллельной обработки». Нумерическая математика . 68 (4): 507–547. CiteSeerX 10.1.1.54.5659 . дои : 10.1007/s002110050074 . S2CID 121258187 .

Внешние ссылки

«Быстрое преобразование Фурье – БПФ» . Техника Кули-Тьюки . Статья. 10. Простой педагогический алгоритм по основанию 2 на C++.
«КИССФФТ» . Гитхаб . 11 февраля 2022 г. Простая реализация Кули – Тьюки со смешанной системой счисления на C.
Dsplib на GitHub
«Алгоритм БПФ прореживания по основанию 2 во времени» . Архивировано из оригинала 31 октября 2017 года. "Алгоритм БПФ по основанию два с прореживанием по времени" (in Russian).
«Алгоритм прореживания по основанию 2 в частотном БПФ» . Архивировано из оригинала 14 ноября 2017 года. "Алгоритм БПФ по основанию два с прореживанием по частоте" (in Russian).

[Gauss_1866-1] Гаусс, Карл Фридрих (1866). «Теория интерполяции метода нова трактата» [Теория нового метода интерполяции]. Усадьба (Неопубликованная рукопись). Сочинения (на латыни и немецком языке). Том 3. Геттинген, Германия: Королевское общество наук в Геттингене. стр. 265–303.

[Heideman84-2] Jump up to: ^а ^б ^с ^д ^и ^ж Хайдеман, М.Т., Д.Х. Джонсон и К.С. Буррус , « Гаусс и история быстрого преобразования Фурье », журнал IEEE ASSP Magazine, 1, (4), 14–21 (1984).

[CooleyTukey65-3] Jump up to: ^а ^б ^с ^д ^и Кули, Джеймс В.; Тьюки, Джон В. (1965). «Алгоритм машинного вычисления комплексных рядов Фурье» . Математика. Вычислить. 19 (90): 297–301. дои : 10.2307/2003354 . JSTOR 2003354 .

[4] Кули, Джеймс В.; Льюис, Питер AW; Уэлч, Питер Д. (1967). «Исторические заметки о быстром преобразовании Фурье» (PDF) . Транзакции IEEE по аудио и электроакустике . 15 (2): 76–79. CiteSeerX 10.1.1.467.7209 . дои : 10.1109/tau.1967.1161903 .

[5] Рокмор, Дэниел Н., Comput. наук. англ. 2 (1), 60 (2000). БПФ — алгоритм, которым может пользоваться вся семья. Специальный выпуск о «десятке лучших алгоритмов века». Барри А. Сипра. «Лучшее в 20-м веке: редакторы назвали 10 лучших алгоритмов» (PDF) . СИАМ Новости . 33 (4). Архивировано из оригинала (PDF) 7 апреля 2009 г. Проверено 31 марта 2009 г.

[6] Джеймс В. Кули, Питер А.В. Льюис и Питер В. Уэлч, «Исторические заметки о быстром преобразовании Фурье», Proc. IEEE , том. 55 (№ 10), с. 1675–1677 (1967).

[7] Дэниэлсон, Г.К. и К. Ланцос, «Некоторые улучшения в практическом анализе Фурье и их применении к рассеянию рентгеновских лучей в жидкостях», J. Franklin Inst. 233 , 365–380 и 435–452 (1942).

[Johnson08-8] Jump up to: ^а ^б ^с С. Г. Джонсон и М. Фриго, « Реализация БПФ на практике », в книге «Быстрые преобразования Фурье » (ред. CS Burrus), гл. 11, Университет Райса, Хьюстон, Техас: Connexions, сентябрь 2008 г.

[Singleton67-9] Jump up to: ^а ^б Синглтон, Ричард К. (1967). «О вычислении быстрого преобразования Фурье» . Коммун. АКМ . 10 (10): 647–654. дои : 10.1145/363717.363771 . S2CID 6287781 .

[DuhamelVe90-10] Jump up to: ^а ^б Дюамель П. и М. Веттерли, «Быстрые преобразования Фурье: обзор учебного пособия и современное состояние», Signal Processing 19 , 259–299 (1990).

[11] Ланди, Т. и Дж. Ван Баскирк, «Новый матричный подход к реальным БПФ и сверткам длины 2». ^к», Computing 80 , 23–45 (2007).

[12] Джонсон, С.Г. и М. Фриго, « Модифицированное БПФ с разделением системы счисления с меньшим количеством арифметических операций », IEEE Trans. Сигнальный процесс. 55 (1), 111–119 (2007).

[FrigoJohnson05-13] Jump up to: ^а ^б ^с ^д ^и Фриго, М.; Джонсон, С.Г. (2005). «Проектирование и реализация FFTW3» (PDF) . Труды IEEE . 93 (2): 216–231. Бибкод : 2005IEEP..93..216F . CiteSeerX 10.1.1.66.3097 . дои : 10.1109/JPROC.2004.840301 . S2CID 6644892 .

[GenSande66-14] Jump up to: ^а ^б Джентльмен В.М. и Г. Санде, «Быстрое преобразование Фурье — для развлечения и прибыли», Proc. AFIPS 29 , 563–578 (1966).

[Bailey90-15] Jump up to: ^а ^б Бейли, Дэвид Х., «БПФ во внешней или иерархической памяти», J. Supercomputing 4 (1), 23–35 (1990).

[Frigo99-16] Jump up to: ^а ^б М. Фриго, К.Э. Лейзерсон, Х. Прокоп и С. Рамачандран. Алгоритмы, не обращающие внимания на кэш. В материалах 40-го симпозиума IEEE по основам информатики (FOCS 99), стр. 285–297. 1999. Расширенный реферат в IEEE , в Citeseer .

[17] Кули, Дж.В., П. Льюис и П. Уэлч, «Быстрое преобразование Фурье и его приложения», IEEE Trans on Education 12 , 1, 28–34 (1969)

[clrs-18] Кормен, Томас Х.; Лейзерсон, Чарльз; Ривест, Рональд; Стоун, Клиффорд (2009). Введение в алгоритмы (3-е изд.). Кембридж, Массачусетс: MIT Press. стр. 915–918. ISBN 978-0-262-03384-8 .

[19] Карп, Алан Х. (1996). «Перестановка битов на однопроцессорах». Обзор СИАМ . 38 (1): 1–26. CiteSeerX 10.1.1.24.2913 . дои : 10.1137/1038001 . JSTOR 2132972 .

[20] Картер, Ларри; Гатлин, Кан Су (1998). «На пути к оптимальной программе перестановки битов». Материалы 39-го ежегодного симпозиума по основам информатики (кат. № 98CB36280) . стр. 544–553. CiteSeerX 10.1.1.46.9319 . дои : 10.1109/SFCS.1998.743505 . ISBN 978-0-8186-9172-0 . S2CID 14307262 .

[21] Рубио, М.; Гомес, П.; Друиш, К. (2002). «Новый сверхбыстрый алгоритм перестановки битов». Международный журнал адаптивного управления и обработки сигналов . 16 (10): 703–707. дои : 10.1002/acs.718 . S2CID 62201722 .

[22] Первоначально приписывается Стокхэму в WT Cochran et al. , Что такое быстрое преобразование Фурье? , учеб. IEEE том. 55, 1664–1674 (1967).

[Swarztrauber84-23] Jump up to: ^а ^б П. Н. Шварцтраубер, Алгоритмы БПФ для векторных компьютеров , Parallel Computing vol. 1, 45–63 (1984).

[24] Шварцтраубер, ПН (1982). «Векторизация БПФ» . В Родриге, Г. (ред.). Параллельные вычисления . Нью-Йорк: Академическая пресса. стр. 51–83 . ISBN 978-0-12-592101-5 .

[25] Пиз, MC (1968). «Адаптация быстрого преобразования Фурье для параллельной обработки» . Дж. АКМ . 15 (2): 252–264. дои : 10.1145/321450.321457 . S2CID 14610645 .

[26] Фриго, Маттео; Джонсон, Стивен Г. «FFTW» . Бесплатная ( GPL ) библиотека C для вычисления дискретных преобразований Фурье в одном или нескольких измерениях произвольного размера с использованием алгоритма Кули – Тьюки.

[27] Джонсон, HW; Буррус, CS (1984). «БПФ по основанию-2 на месте». Учеб. ICASSP : 28A.2.1–28A.2.4.

[28] Темпертон, К. (1991). «Быстрое преобразование Фурье с самосортировкой на месте». Журнал SIAM по научным и статистическим вычислениям . 12 (4): 808–823. дои : 10.1137/0912043 .

[29] Цянь, З.; Лу, К.; Ан, М.; Толимьери, Р. (1994). «Алгоритм БПФ с самосортировкой на месте и минимальным рабочим пространством». IEEE Транс. АССП . 52 (10): 2835–2836. Бибкод : 1994ITSP...42.2835Q . дои : 10.1109/78.324749 .

[30] Хегланд, М. (1994). «Алгоритм быстрого преобразования Фурье с самосортировкой на месте, подходящий для векторной и параллельной обработки». Нумерическая математика . 68 (4): 507–547. CiteSeerX 10.1.1.54.5659 . дои : 10.1007/s002110050074 . S2CID 121258187 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]