Быстрое преобразование Фурье (БПФ, или FFT) считается одним из важнейших алгоритмов современности, обеспечивающим работу Wi-Fi, мобильной связи 5G и алгоритмов сжатия данных. Однако мало кто знает, что его повторное открытие в 1960-х годах было продиктовано не развитием гражданских технологий, а острой необходимостью обнаружения секретных подземных ядерных испытаний в разгар Холодной войны. Автор канала Veritasium Дерек Маллер подробно разбирает, как чистая математика едва не остановила гонку вооружений и почему это открытие опоздало более чем на полтора века.
☢️ Упущенный шанс остановить ядерную гонку 0:00
После атомной бомбардировки Хиросимы и Нагасаки в 1945 году мировые державы осознали разрушительную силу нового оружия: сброшенная бомба высвободила в тысячу раз больше энергии, чем любой конвенциональный боеприпас того времени . Вопреки расхожему мнению о неизбежности ядерной гонки, США изначально были готовы обсуждать контроль над технологией . Американская делегация предложила «план Баруха», подразумевавший создание международного органа контроля над всеми радиоактивными материалами планеты и последующее уничтожение ядерного арсенала США . Однако СССР отклонил этот план, посчитав его попыткой закрепить американскую монополию, что дало старт полномасштабному противостоянию .
Испытания нового оружия проводились в удаленных районах Тихого океана, Арктики и на полигоне в Неваде, причем радиоактивные осадки от американских взрывов наносили ущерб самим же гражданам США . Переход от деления ядер к термоядерному синтезу ознаменовал еще один тысячекратный скачок мощности .
В марте 1954 года на атолле Бикини состоялось испытание термоядерного устройства Shrimp («Креветка») . Расчетная мощность взрыва составляла 6 миллионов тонн (мегатонн) в тротиловом эквиваленте . Из-за непредвиденной реакции изотопа лития-7 реальная мощность взрыва превысила ожидания в 2,5 раза, достигнув 15 мегатонн . Радиоактивный пепел накрыл обитаемые атоллы и японскую рыболовецкую шхуну «Фукурю-мару» (яп. «Счастливый дракон № 5»), экипаж которой серьезно пострадал, а один из рыбаков скончался через полгода .
Эти трагические события вызвали волну протестов по всему миру и привели к созданию знаменитого пацифистского символа борьбы за ядерное разоружение (сочетание семафорных букв N и D) . В 1958 году ядерные державы сели за стол переговоров в Женеве, объявив временный мораторий на испытания, из-за чего 1959 год стал единственным периодом в Холодной войне без ядерных взрывов .
🕵️♂️ Проблема верификации: как поймать подземный взрыв? 4:48
Главным камнем преткновения на переговорах стал вопрос взаимного доверия. Американская сторона опасалась тайного проведения испытаний Советами, а руководство СССР подозревало США в аналогичных намерениях . Для поиска компромисса была созвана специальная комиссия экспертов .
Верификация испытаний в разных средах имела разную сложность:
- Атмосферные взрывы: фиксировались по радиоактивным изотопам, разносимым ветром на тысячи километров .
- Подводные взрывы: легко регистрировались с помощью гидрофонов благодаря отличной проводимости звука в толще воды .
- Подземные взрывы: практически не поддавались дистанционному контролю, а советское руководство наотрез отказывалось допускать иностранных инспекторов на свою территорию, расценивая это как шпионаж .
В результате подписанный в 1963 году Договор о запрещении испытаний ядерного оружия оказался частичным: он запрещал взрывы в атмосфере, космосе и под водой, но оставлял лазейку для подземных испытаний .
Для фиксации подземных толчков ученые предложили использовать сеть сейсмографов за пределами тестирующих стран . Однако возникла колоссальная техническая сложность: ежедневно на Земле происходит около 300 землетрясений магнитудой 3 и выше . Сейсмический след взрыва зависит не только от мощности заряда, но и от глубины его заложения . Чтобы отличить природное колебание от искусственного и рассчитать параметры взрыва, ученым требовалось проанализировать частотный спектр полученного сейсмического сигнала .
📐 Математика волн: от Фурье до дискретных данных 7:22
Единственным способом расшифровать запутанную сейсмограмму было применение преобразования Фурье — математического метода разложения сложного сигнала на чистые синусоиды различной частоты и амплитуды .
Чтобы вручную определить присутствие конкретной волны в сигнале, необходимо умножить исходный график на синусоиду искомой частоты в каждой точке и сложить площади полученных фигур под кривой . Если частоты не совпадают, области выше и ниже оси абсцисс компенсируют друг друга, давая в сумме ноль . При совпадении частот произведение всегда остается положительным, и суммарная площадь указывает на амплитуду данной составляющей .
Для полной картины необходимо проводить умножение как на синусы, так и на косинусы (для определения фазы сдвига сигнала) , что математически выражается через формулу Эйлера с использованием комплексных чисел .
Однако реальные приборы фиксируют не бесконечную плавную волну, а дискретные отсчеты (точки данных) . Поэтому на практике применяется дискретное преобразование Фурье (ДПФ) . Количество частотных диапазонов («бин») в полученном спектре напрямую зависит от числа собранных точек $N$ .
Главная проблема классического ДПФ заключается в его квадратичной вычислительной сложности. Для обработки массива из $N$ точек требуется выполнить $N^2$ комплексных умножений . Если для массива из 8 точек требуется всего 64 операции, то для 1 миллиона отсчетов это число возрастает до 1 триллиона ($10^{12}$) . Компьютерам начала 1960-х годов потребовалось бы более трех лет непрерывных вычислений для анализа всего лишь одной сейсмограммы .
⚡ Алгоритм века: рождение и логика FFT 14:57
Прорыв произошел в 1963 году на заседании Научного консультативного комитета при президенте США Джоне Кеннеди . Физик Ричард Гарвин заметил, что его коллега, математик Джон Тьюки, во время скучного доклада что-то увлеченно рисовал в блокноте . Как выяснилось, Тьюки нашел способ кардинально сократить объем вычислений при дискретном преобразовании . Его метод снижал сложность с квадратичной ($N^2$) до квазилинейной ($N \log_2 N$) .
Суть быстрого преобразования Фурье (БПФ) строится на использовании периодической симметрии тригонометрических функций:
- Исходный массив из $N$ точек делится на два подмассива: с четными и нечетными индексами .
- Вычисления для второй половины частот дублируют значения первой половины (с точностью до знака или комплексного множителя) . Это позволяет использовать уже рассчитанные суммы повторно .
- Процесс деления пополам повторяется рекурсивно до тех пор, пока массив не сократится до единичных точек .
Благодаря этому алгоритму количество операций для миллиона отсчетов сократилось в 50 000 раз . Расчет, занимавший три года, теперь выполнялся за 35 минут .
Ричард Гарвин оперативно передал идею исследователю IBM Джеймсу Кули для написания компьютерного кода . В целях секретности Гарвин скрыл истинное оборонное назначение алгоритма, заявив программисту, что вычисления необходимы для исследования спинов в кристаллах гелия-3 . В 1965 году совместная статья Кули и Тьюки была опубликована, произведя революцию в прикладной математике .
🏛️ Утерянный манускрипт Карла Фридриха Гаусса 19:22
Историческая драма заключается в том, что БПФ был открыт слишком поздно для предотвращения витка гонки вооружений. После 1963 года ядерные державы, лишенные надежного метода удаленного контроля, перенесли все испытания под землю . За последующие 30 лет было взорвано около 1500 подземных зарядов (в среднем по одному в неделю) . Пик гонки пришелся на середину 1980-х, когда мировой арсенал достиг 70 000 боеголовок, а суммарные расходы США и СССР на ядерные программы превысили 10 триллионов долларов с каждой стороны .
Дерек Маллер лично спросил Ричарда Гарвина, мог ли алгоритм БПФ остановить это безумие, появись он на пару лет раньше . Физик согласился, что это могло бы переломить ход переговоров в Женеве .
Самое удивительное, что этот алгоритм уже был изобретен за 160 лет до публикации Кули и Тьюки. В 1805 году великий немецкий математик Карл Фридрих Гаусс рассчитывал орбиты недавно открытых астероидов Паллада, Церера и Юнона . Для определения орбиты Юноны он разработал точно такой же метод быстрого гармонического анализа, опередив даже публикацию самого Жозефа Фурье (1807 год) .
Однако Гаусс не опубликовал свое открытие при жизни. Оно появилось лишь посмертно в третьем томе его собрания сочинений, написанное на архаичной латыни и с использованием специфических обозначений XIX века, из-за чего осталось незамеченным научным сообществом .
📱 От сейсмографов к смартфонам: сжатие данных в XXI веке 22:00
Сегодня алгоритм БПФ используется повсеместно. Он лег в основу большинства современных форматов сжатия медиаданных . Дерек Маллер наглядно демонстрирует работу алгоритма на примере обработки графического изображения:
- Компьютер берет значения яркости пикселей в строках картинки и применяет к ним БПФ .
- Затем аналогичная процедура проводится для столбцов, создавая двумерный частотный спектр .
- В реальных фотографиях подавляющее большинство высокочастотных компонентов (отвечающих за резкие переходы на границах деталей) имеет значения, близкие к нулю .
- Алгоритм сжатия безболезненно отбрасывает до 99% этих малозначимых данных .
- При открытии файла компьютер выполняет обратное быстрое преобразование Фурье, восстанавливая изображение с минимальными потерями .
По мнению выдающегося математика Гилберта Стренга, БПФ по праву является самым важным численным алгоритмом нашего времени . Если бы записи Гаусса были вовремя переведены и поняты человечеством, технологический облик планеты и ее политическая история могли бы сложиться совершенно иным, более безопасным образом .
