Обложка: концептуальная иллюстрация синтетического сигнала и его частотных составляющих, созданная ИИ. Она не изображает ни первоначальный компьютер, ни экспериментальные данные.
Услышать составляющие внутри сигнала
Представьте, что вы записываете музыкальный аккорд. Микрофон даёт последовательность амплитуд, а вас интересуют ноты внутри неё. Анализ Фурье устанавливает математическую связь между этими описаниями. Похожие вопросы возникают при изучении колебаний или узоров на изображении.
Дискретное преобразование Фурье, обозначаемое английской аббревиатурой DFT, представляет конечную последовательность через дискретные частотные составляющие. Быстрое преобразование Фурье, или FFT, — эффективный способ вычислить то же самое преобразование. Оно не создаёт новый вид спектра. Техническая документация NumPy описывает вход как сигнал во временной области, а выход — как его представление в частотной области. Документация DFT
Практическая трудность — в повторении операций. При прямом расчёте каждая входная точка сочетается с каждой выходной частотой. Удвойте число точек, и ведущая часть арифметической работы увеличится в четыре раза. Поэтому, если научная задача требует тысяч точек, математически простая формула может стать вычислительным препятствием.
Кули и Тьюки представили общую факторизацию и удобную реализацию для длин, равных степени двойки, включая способ повторно использовать память входного массива. В статье сообщается о программе для IBM 7094 и времени вычислений, а не только об абстрактном предложении. Редакция получила рукопись 17 августа 1964 года; статья вышла в апрельском выпуске Mathematics of Computation за 1965 год. Точный день публикации здесь не установлен. Оригинальная статья, университетская копия
Прорыв с долгой предысторией
Идея не возникла из ничего в 1965 году. Историки Майкл Хейдеман, Дон Джонсон и Сидни Бёррус изучили более ранние тексты и обнаружили эквивалентное разложение в работах Гаусса. Они предположили, что текст был написан примерно в 1805 году; сама рукопись не имела явной даты и была опубликована посмертно в 1866 году. В их исследовании рассматриваются и более поздние методы, в том числе работа Дэниелсона и Ланцоша 1942 года и подход Гуда на основе простых множителей. Ограничения метода Гуда отличаются от ограничений общей факторизации Кули–Тьюки. Историческое исследование и доступная авторская копия
В воспоминаниях 1993 года Кули и Тьюки описывают роль Ричарда Гарвина в объединении работы и содействии её развитию. Они также признают прежние открытия и объясняют, почему крупные электронные вычисления сделали подход ценным. Это ретроспективный рассказ участников, с ограничениями, присущими воспоминаниям. Рассказ Кули и Тьюки
Устойчивым поворотом стало распространение в практике многократно применимого вычислительного метода. В материале Принстонского университета о признании IEEE его связывают с научными вычислениями, обработкой сигналов, медицинской визуализацией и передачей данных. Эти приложения зависят также от приборов, физических моделей и других алгоритмов; FFT внесло мощный вычислительный строительный блок. Более позднее признание подтверждает историческую значимость, но не превращает недавнее памятное мероприятие в дату открытия. Принстонский университет и историческая веха IEEE
Четыре точки: увидеть повторное использование до общей формулы
Возьмём безразмерную последовательность [1, 2, 3, 4]. Этот намеренно небольшой пример — наш учебный расчёт, а не данные из статьи 1965 года. Пусть i обозначает мнимую единицу, для которой i² = −1. DFT без масштабирования и с отрицательным показателем экспоненты даёт четыре выхода:
| Индекс частоты | Выход |
|---|---|
| 0 | 10 |
| 1 | −2 + 2i |
| 2 | −2 |
| 3 | −2 − 2i |
Первый выход складывает все четыре входных значения. Остальные сочетают положительные, отрицательные и мнимые веса. Комплексный выход содержит две компоненты; его модуль и фаза вместе описывают частотную составляющую.
Теперь отделим значения с чётными индексами [1, 3] от значений с нечётными индексами [2, 4]. Для каждой пары нужны только сумма и разность:
- Чётная пара: E = [4, −2].
- Нечётная пара: O = [6, −2].
Объединим эти более короткие результаты. Первая «бабочка» даёт 4 + 6 = 10 и 4 − 6 = −2. Вторая сначала поворачивает нечётный результат с помощью −i, получая (−i)(−2) = 2i. Её два выхода — −2 + 2i и −2 − 2i.
«Бабочкой» называют эту парную операцию суммы и разности. Пересекающиеся линии на её схеме организуют вычисления, а не показывают физическую связь между волнами. Оба выхода повторно используют одни и те же промежуточные результаты. При большей длине каждое короткое преобразование можно снова разделить: повторное использование образует иерархию, а не разовое сокращение пути.
От примера к росту объёма вычислений
Для N входных значений определим используемое нами соглашение так:
Xk=n=0∑N−1xne−2πink/N.
Здесь n — индекс входа, k — индекс выхода; оба принимают значения от нуля до N − 1. Множители — комплексные повороты единичного модуля. Наше прямое преобразование не имеет нормирующего множителя; обратное использует положительный показатель экспоненты и множитель 1/N. Существуют другие соглашения. Оригинальная статья начинается с суммы Фурье с положительным показателем, поэтому знаки и нормировку необходимо сравнивать явно. Современное соглашение
При чётном N разделим сумму по чётным и нечётным индексам входа. Обозначим их преобразования длины N/2 как Eₖ и Oₖ и положим W_N = exp(−2πi/N). Для 0 ≤ k < N/2 восстановление имеет вид:
Xk=Ek+WNkOk,Xk+N/2=Ek−WNkOk.
Второе равенство использует смену знака множителя при повороте на половину окружности. Таким образом, мы вычисляем два коротких преобразования и выполняем число объединений, пропорциональное N. Повторяя разделение для N = 2ᵐ, получаем m = log₂N уровней.
На каждом уровне объём работы пропорционален длине последовательности. Следовательно, общий объём растёт как N log₂N. Обозначение O(N log N) описывает этот рост, а не точное число команд процессора или секунд. Учебная конструкция с основанием 2 ограничена степенями двойки; общие факторизации Кули–Тьюки допускают другие составные длины.
Скорость на реальном компьютере зависит также от размещения данных, обмена с памятью и реализации. Само по себе меньшее число арифметических операций не доказывает конкретного сокращения фактического времени на вашем устройстве.
Чего более быстрый расчёт не исправляет
Если равномерные измерения разделены интервалом Δt секунд, частота дискретизации равна 1/Δt герц, а шаг частотных отсчётов — 1/(NΔt) герц. Для интерпретации старших выходных индексов нужно учитывать выбранный порядок положительных и отрицательных частот. Соглашения о частотах
Конечная дискретизация по-прежнему ограничивает возможные выводы. Здесь t — время в секундах, f — частота сигнала в герцах, а fₛ = 1/Δt — частота дискретизации в герцах. Например, отсчёты cos(2πft) при t = n/fₛ не изменятся, если заменить f на f + fₛ: добавленная фаза равна 2πn. Никакой более быстрый алгоритм не различит эти два сигнала только по таким отсчётам. Шум и недостаточные модели измерений тоже остаются проблемами измерения.
Численная арифметика вводит ещё одно ограничение. Комплексные множители поворота, как правило, требуют численных приближений, а изменение порядка операций может изменить округление. В обсуждении точности FFTW подчёркивается важность точных множителей поворота и документируются различия между реализациями и средами. Математическая эквивалентность не обещает одинаковых битовых представлений чисел с плавающей точкой. Обсуждение точности
Проверить учебный расчёт
В нашей проверке использовались CPython 3.12.10 и только стандартная библиотека. Корни для четырёх точек [1, −i, −1, i] представлены точно, поэтому для этих небольших целочисленных входов уместно требовать точного равенства. Этот критерий нельзя механически переносить на более длинные преобразования с плавающей точкой.
В ходе документированной проверки были выполнены следующие основные вычисления:
ROOTS = (1, -1j, -1, 1j)
def direct(x, roots=ROOTS):
return [
sum(x[n] * roots[(n*k) % 4] for n in range(4))
for k in range(4)
]
def butterfly(x):
even = (x[0] + x[2], x[0] - x[2])
odd = (x[1] + x[3], x[1] - x[3])
return [
even[0] + odd[0], even[1] - 1j*odd[1],
even[0] - odd[0], even[1] + 1j*odd[1],
]Сравните обе функции на [1, 2, 3, 4], импульсе [1, 0, 0, 0], постоянной последовательности [1, 1, 1, 1], нулевой последовательности и [1+i, −2, 3−i, 2i]. Все пять результатов совпали точно. Первый также совпал с таблицей выше. Изменение знаков мнимых частей корней изменило спектр асимметричного случая, и проверка отвергла его как другое соглашение.
Это подтверждает заданные учебные случаи. Оно не доказывает правильность каждой реализации и не является независимым воспроизведением исторической производительности. Оригинальная статья не предоставляет полного текста программы, входов для бенчмарка или полных условий измерения времени, необходимых для такого воспроизведения.
Статья написана и переведена системой ИИ на основе указанных источников, с автоматическими проверками по редакционной методике News. Учебный расчёт выполнен так, как описано; это не экспертное рецензирование, не научная проверка человеком и не воспроизведение исторической программы.