# Как быстрый алгоритм Фурье изменил технологии и почему он не оставил ядерную гонку

Источник: https://www.youtube.com/watch?v=nmgFG7PUHfo
Канал: Veritasium
Опубликовано: 03.11.2022

---

Быстрое преобразование Фурье (БПФ, или FFT) считается одним из важнейших алгоритмов современности, обеспечивающим работу Wi-Fi, мобильной связи 5G и алгоритмов сжатия данных. Однако мало кто знает, что его повторное открытие в 1960-х годах было продиктовано не развитием гражданских технологий, а острой необходимостью обнаружения секретных подземных ядерных испытаний в разгар Холодной войны. Автор канала Veritasium Дерек Маллер подробно разбирает, как чистая математика едва не остановила гонку вооружений и почему это открытие опоздало более чем на полтора века.

## ☢️ Упущенный шанс остановить ядерную гонку
[[JUMP:0:00]]

После атомной бомбардировки Хиросимы и Нагасаки в 1945 году мировые державы осознали разрушительную силу нового оружия: сброшенная бомба высвободила в тысячу раз больше энергии, чем любой конвенциональный боеприпас того времени [0:50]. Вопреки расхожему мнению о неизбежности ядерной гонки, США изначально были готовы обсуждать контроль над технологией [1:15]. Американская делегация предложила «план Баруха», подразумевавший создание международного органа контроля над всеми радиоактивными материалами планеты и последующее уничтожение ядерного арсенала США [1:28]. Однако СССР отклонил этот план, посчитав его попыткой закрепить американскую монополию, что дало старт полномасштабному противостоянию [1:40].

Испытания нового оружия проводились в удаленных районах Тихого океана, Арктики и на полигоне в Неваде, причем радиоактивные осадки от американских взрывов наносили ущерб самим же гражданам США [2:08]. Переход от деления ядер к термоядерному синтезу ознаменовал еще один тысячекратный скачок мощности [2:21]. 

В марте 1954 года на атолле Бикини состоялось испытание термоядерного устройства Shrimp («Креветка») [2:48]. Расчетная мощность взрыва составляла 6 миллионов тонн (мегатонн) в тротиловом эквиваленте [3:01]. Из-за непредвиденной реакции изотопа лития-7 реальная мощность взрыва превысила ожидания в 2,5 раза, достигнув 15 мегатонн [3:15]. Радиоактивный пепел накрыл обитаемые атоллы и японскую рыболовецкую шхуну «Фукурю-мару» (яп. «Счастливый дракон № 5»), экипаж которой серьезно пострадал, а один из рыбаков скончался через полгода [3:40].

Эти трагические события вызвали волну протестов по всему миру и привели к созданию знаменитого пацифистского символа борьбы за ядерное разоружение (сочетание семафорных букв N и D) [3:53]. В 1958 году ядерные державы сели за стол переговоров в Женеве, объявив временный мораторий на испытания, из-за чего 1959 год стал единственным периодом в Холодной войне без ядерных взрывов [4:34].

## 🕵️‍♂️ Проблема верификации: как поймать подземный взрыв?
[[JUMP:4:48]]

Главным камнем преткновения на переговорах стал вопрос взаимного доверия. Американская сторона опасалась тайного проведения испытаний Советами, а руководство СССР подозревало США в аналогичных намерениях [4:48]. Для поиска компромисса была созвана специальная комиссия экспертов [5:00]. 

Верификация испытаний в разных средах имела разную сложность:

*   **Атмосферные взрывы:** фиксировались по радиоактивным изотопам, разносимым ветром на тысячи километров [5:13].
*   **Подводные взрывы:** легко регистрировались с помощью гидрофонов благодаря отличной проводимости звука в толще воды [5:25].
*   **Подземные взрывы:** практически не поддавались дистанционному контролю, а советское руководство наотрез отказывалось допускать иностранных инспекторов на свою территорию, расценивая это как шпионаж [5:38].

В результате подписанный в 1963 году Договор о запрещении испытаний ядерного оружия оказался частичным: он запрещал взрывы в атмосфере, космосе и под водой, но оставлял лазейку для подземных испытаний [5:51].

Для фиксации подземных толчков ученые предложили использовать сеть сейсмографов за пределами тестирующих стран [6:17]. Однако возникла колоссальная техническая сложность: ежедневно на Земле происходит около 300 землетрясений магнитудой 3 и выше [6:31]. Сейсмический след взрыва зависит не только от мощности заряда, но и от глубины его заложения [6:43]. Чтобы отличить природное колебание от искусственного и рассчитать параметры взрыва, ученым требовалось проанализировать частотный спектр полученного сейсмического сигнала [7:10].

## 📐 Математика волн: от Фурье до дискретных данных
[[JUMP:7:22]]

Единственным способом расшифровать запутанную сейсмограмму было применение преобразования Фурье — математического метода разложения сложного сигнала на чистые синусоиды различной частоты и амплитуды [7:22]. 

Чтобы вручную определить присутствие конкретной волны в сигнале, необходимо умножить исходный график на синусоиду искомой частоты в каждой точке и сложить площади полученных фигур под кривой [8:03]. Если частоты не совпадают, области выше и ниже оси абсцисс компенсируют друг друга, давая в сумме ноль [8:41]. При совпадении частот произведение всегда остается положительным, и суммарная площадь указывает на амплитуду данной составляющей [8:55]. 

Для полной картины необходимо проводить умножение как на синусы, так и на косинусы (для определения фазы сдвига сигнала) [9:48], что математически выражается через формулу Эйлера с использованием комплексных чисел [10:15].

Однако реальные приборы фиксируют не бесконечную плавную волну, а дискретные отсчеты (точки данных) [11:10]. Поэтому на практике применяется дискретное преобразование Фурье (ДПФ) [11:36]. Количество частотных диапазонов («бин») в полученном спектре напрямую зависит от числа собранных точек $N$ [12:42]. 

Главная проблема классического ДПФ заключается в его квадратичной вычислительной сложности. Для обработки массива из $N$ точек требуется выполнить $N^2$ комплексных умножений [14:16]. Если для массива из 8 точек требуется всего 64 операции, то для 1 миллиона отсчетов это число возрастает до 1 триллиона ($10^{12}$) [14:30]. Компьютерам начала 1960-х годов потребовалось бы более трех лет непрерывных вычислений для анализа всего лишь одной сейсмограммы [14:30].

## ⚡ Алгоритм века: рождение и логика FFT
[[JUMP:14:57]]

Прорыв произошел в 1963 году на заседании Научного консультативного комитета при президенте США Джоне Кеннеди [14:57]. Физик Ричард Гарвин заметил, что его коллега, математик Джон Тьюки, во время скучного доклада что-то увлеченно рисовал в блокноте [15:09]. Как выяснилось, Тьюки нашел способ кардинально сократить объем вычислений при дискретном преобразовании [15:24]. Его метод снижал сложность с квадратичной ($N^2$) до квазилинейной ($N \log_2 N$) [16:44].

Суть быстрого преобразования Фурье (БПФ) строится на использовании периодической симметрии тригонометрических функций:

1.  Исходный массив из $N$ точек делится на два подмассива: с четными и нечетными индексами [17:10].
2.  Вычисления для второй половины частот дублируют значения первой половины (с точностью до знака или комплексного множителя) [17:49]. Это позволяет использовать уже рассчитанные суммы повторно [18:02].
3.  Процесс деления пополам повторяется рекурсивно до тех пор, пока массив не сократится до единичных точек [18:15].

Благодаря этому алгоритму количество операций для миллиона отсчетов сократилось в 50 000 раз [16:58]. Расчет, занимавший три года, теперь выполнялся за 35 минут [15:37]. 

Ричард Гарвин оперативно передал идею исследователю IBM Джеймсу Кули для написания компьютерного кода [18:54]. В целях секретности Гарвин скрыл истинное оборонное назначение алгоритма, заявив программисту, что вычисления необходимы для исследования спинов в кристаллах гелия-3 [19:07]. В 1965 году совместная статья Кули и Тьюки была опубликована, произведя революцию в прикладной математике [19:07].

## 🏛️ Утерянный манускрипт Карла Фридриха Гаусса
[[JUMP:19:22]]

Историческая драма заключается в том, что БПФ был открыт слишком поздно для предотвращения витка гонки вооружений. После 1963 года ядерные державы, лишенные надежного метода удаленного контроля, перенесли все испытания под землю [19:22]. За последующие 30 лет было взорвано около 1500 подземных зарядов (в среднем по одному в неделю) [19:50]. Пик гонки пришелся на середину 1980-х, когда мировой арсенал достиг 70 000 боеголовок, а суммарные расходы США и СССР на ядерные программы превысили 10 триллионов долларов с каждой стороны [20:03].

Дерек Маллер лично спросил Ричарда Гарвина, мог ли алгоритм БПФ остановить это безумие, появись он на пару лет раньше [20:29]. Физик согласился, что это могло бы переломить ход переговоров в Женеве [20:42]. 

Самое удивительное, что этот алгоритм уже был изобретен за 160 лет до публикации Кули и Тьюки. В 1805 году великий немецкий математик Карл Фридрих Гаусс рассчитывал орбиты недавно открытых астероидов Паллада, Церера и Юнона [20:54]. Для определения орбиты Юноны он разработал точно такой же метод быстрого гармонического анализа, опередив даже публикацию самого Жозефа Фурье (1807 год) [21:09]. 

Однако Гаусс не опубликовал свое открытие при жизни. Оно появилось лишь посмертно в третьем томе его собрания сочинений, написанное на архаичной латыни и с использованием специфических обозначений XIX века, из-за чего осталось незамеченным научным сообществом [21:23].

## 📱 От сейсмографов к смартфонам: сжатие данных в XXI веке
[[JUMP:22:00]]

Сегодня алгоритм БПФ используется повсеместно. Он лег в основу большинства современных форматов сжатия медиаданных [22:00]. Дерек Маллер наглядно демонстрирует работу алгоритма на примере обработки графического изображения:

*   Компьютер берет значения яркости пикселей в строках картинки и применяет к ним БПФ [22:13].
*   Затем аналогичная процедура проводится для столбцов, создавая двумерный частотный спектр [22:39].
*   В реальных фотографиях подавляющее большинство высокочастотных компонентов (отвечающих за резкие переходы на границах деталей) имеет значения, близкие к нулю [22:53].
*   Алгоритм сжатия безболезненно отбрасывает до 99% этих малозначимых данных [23:20].
*   При открытии файла компьютер выполняет обратное быстрое преобразование Фурье, восстанавливая изображение с минимальными потерями [23:33].

По мнению выдающегося математика Гилберта Стренга, БПФ по праву является самым важным численным алгоритмом нашего времени [23:46]. Если бы записи Гаусса были вовремя переведены и поняты человечеством, технологический облик планеты и ее политическая история могли бы сложиться совершенно иным, более безопасным образом [23:59].