Быстрое преобразование Фурье (БПФ) – важнейший алгоритм всех времен. Его используют постоянно, например, при просмотре видео. Радары, гидролокаторы, 5G, Wi-Fi – везде, где нужна обработка сигналов, с большой вероятностью используется БПФ. Его открытие тесно связано с попытками обнаружить тайные испытания ядерного оружия.
Гонка вооружений
Гонка ядерных вооружений, начавшаяся после бомбардировки Хиросимы и Нагасаки, возможно, была не неизбежной. Мощность бомбы, сброшенной на Хиросиму, в тысячу раз превышала мощность самых мощных традиционных взрывчатых веществ. После войны Канада и Великобритания предложили переговоры о контроле над ядерным оружием, и США неожиданно согласились. Они пообещали уничтожить все ядерное оружие, если другие страны обяжутся его никогда не производить.
План Баруха и его последствия
Предложенный план Баруха, предполагавший международный контроль над добычей, обогащением и использованием урана, был отвергнут Советским Союзом. Это положило начало гонке вооружений, сопровождавшейся испытаниями в удаленных местах (Арктика, южная часть Тихого океана, Невада). В результате, помимо Японии, большая часть пострадавших от американского ядерного оружия – сами американцы.
Увеличение мощности и общественное мнение
Переход к термоядерному оружию, мощность которого увеличилась еще в тысячу раз, сделал возможным уничтожение всей жизни на Земле. Испытание термоядерного оружия («Креветка») на атолле Бикини в 1954 году, мощность которого оказалась в 2,5 раза больше ожидаемой (6 миллионов тонн тротилового эквивалента), привело к широкому распространению радиоактивных продуктов и острому общественному осуждению. В 1950-х годах появились призывы к полному запрету испытаний.
Конференция в Женеве и проблема контроля
Ядерные державы участвовали в Конференции по прекращению ядерных испытаний в Женеве (1958 год), приостановив испытания. 1959 год стал единственным годом без ядерных взрывов. Однако оставалась проблема контроля: как убедиться в соблюдении договора? Обнаружение атмосферных и подводных испытаний было относительно легко, а вот подземные представляли проблему.
Обнаружение подземных испытаний
В 1963 году был подписан частичный запрет на испытания в атмосфере, воде и космосе. Подземные испытания остались вне запрета из-за сложности их обнаружения. Ученые пытались использовать сейсмометры для обнаружения слабых толчков, но было неясно, как отличить вибрации от ядерных испытаний от землетрясений. Для решения этой задачи потребовалось преобразование Фурье.
Преобразование Фурье
Преобразование Фурье позволяет разложить сигнал на составляющие синусоиды с определенной амплитудой и частотой. Анализ спектра частот позволяет определить характеристики сигнала.
Дискретное преобразование Фурье (ДПФ) и Быстрое преобразование Фурье (БПФ)
Для обработки реальных сигналов используется дискретное преобразование Фурье (ДПФ). Быстрое преобразование Фурье (БПФ) значительно ускоряет вычисления ДПФ, сокращая их количество с N² до N log₂N.
БПФ: открытие и последствия
Алгоритм БПФ был опубликован в 1965 году, но к заключению договора о запрете ядерных испытаний ученые опоздали. Частичный запрет лишь перенес испытания под землю. Запасы ядерного оружия достигли пика в середине 80-х (70 000 боеголовок). Высокая стоимость гонки вооружений (по 10 триллионов долларов на США и СССР) подчеркивает важность своевременного обнаружения испытаний. Интересно, что Гаусс разработал ДПФ еще в 1805 году.
Применение БПФ
Сегодня БПФ используется в различных областях: сжатии данных (видео, изображения), решении дифференциальных уравнений, радарах, гидролокаторах, изучении структуры кристаллов, Wi-Fi, 5G и многих других. Гилберт Стрэнг назвал БПФ важнейшим численным алгоритмом нашего времени.