Вся музыка, все фотографии и весь Wi-Fi работают на одном трюке. Ему 200 лет

Откройте ваш плейлист и нажмите play на любом треке.

Эта песня попала в ваши наушники благодаря одной идее. Той самой, за которую француза в 1807 году высмеяли на заседании Парижской академии наук. Лаплас был «за», но Лагранж встал и сказал: «Это невозможно.»

Француза звали Жан-Батист Жозеф Фурье. Его идея была настолько простой, что учёные отказались ей поверить.

Сейчас она обрабатывает каждую фотографию на вашем телефоне. Каждый пакет Wi-Fi. Каждый звонок. Каждый JPEG. Каждый MP3. Каждое MRI-сканирование. Каждую команду Siri. Каждый кадр на стриминговых платформах.

Идея, которая звучит слишком просто

Фурье утверждал:

Любой сигнал — каким бы сложным он ни был — можно разложить на сумму простых синусоид.

Звук скрипки, визг болгарки, голос вашей мамы по телефону, радиоволна от роутера, чёрно-белое фото котика. Что угодно.

Возьмите сигнал ? разложите на набор синусоид (каждая со своей частотой, амплитудой и фазой) ? получите полное описание. И это без потери информации и обратимо.

Любой сигнал = sin(f?) ? a? + sin(f?) ? a? + sin(f?) ? a? + ...  где f — частота, a — амплитуда  Вот вся идея. И Лагранж сказал "невозможно" на ЭТО.

Это как если бы вам сказали: «Любое блюдо — борщ, том-ям, тирамису — можно описать как список ингредиентов с пропорциями.» И вы бы ответили: «Ну... да, очевидно?»

Только в 1807 году это было совсем не очевидно. Потому что из этой простой идеи вытекают последствия, которые меняют вообще всё.

MP3: выкинь то, что ухо не слышит

1991 год, немецкий институт Фраунгофера, команда инженеров пытается решить задачу: CD-качество звука — это 1.4 мегабита в секунду. Интернет работает на 56 килобитах. Как передать музыку?

Ответ: Фурье.

Берём звук ? раскладываем на частоты (FFT, Fast Fourier Transform) ? смотрим, что получилось ? выкидываем то, что человеческое ухо не услышит.

# Грубо, но суть: frequencies = fft(audio_signal)  for f in frequencies:     if f.frequency > 20000:     # ухо не слышит выше 20 кГц         f.amplitude = 0     if f.is_masked_by(louder_neighbor):  # психоакустическая модель         f.amplitude = 0          # тихий звук рядом с громким — не слышен     if f.amplitude < threshold:  # слишком тихо         f.amplitude = 0  compressed = encode(remaining_frequencies) # 1.4 Мбит/с ? 128 Кбит/с. В 11 раз меньше. # И вы не слышите разницы.

Мы с вами знаем, из каких частот состоит звук (спасибо, Жан-Батист), и мы знаем, какие частоты ухо игнорирует (спасибо, психоакустика). Убираем вторые и готово наше MP3.

Каждый раз, когда вы слушаете музыку в наушниках — Фурье разобрал звук на частоты, психоакустическая модель выкинула лишнее, а ваш плеер собрал обратно. И это все за миллисекунды.

JPEG: та же идея, но для пикселей

1992 год, уже другие люди и другая задача, но тот же трюк.

Фотография — это двумерный сигнал. Яркость пикселей меняется по горизонтали и вертикали. Это тоже «волна», просто двумерная.

JPEG берёт изображение, разбивает на блоки 8?8 пикселей и к каждому блоку применяет DCT — Discrete Cosine Transform. Это двоюродный брат Фурье (если быть педантичным — частный случай с косинусами вместо синусов, что помогает для дискретных данных; суть та же).

Блок 8?8 пикселей     ? DCT: разложение на "визуальные частоты"     ? Низкие частоты = плавные градиенты, общие формы Высокие частоты = острые края, мелкие детали, шум     ? Выкинуть высокие частоты (глаз не заметит на фото заката)     ? Сжатое изображение, в 10–20 раз меньше оригинала

Те самые «квадратики» на пережатом JPEG? Это блоки 8?8, из которых выкинули слишком много высокочастотных компонентов. Вы буквально видите границы Фурье-разложения.

Каждый раз, когда вы отправляете фото в мессенджере — Фурье разбирает картинку на частоты, кодек выкидывает те, которые ваш глаз не заметит, и пересобирает обратно.

Wi-Fi: а вот тут Фурье уже не сжимает, а создаёт

Ваш роутер прямо сейчас вещает на частоте 5 ГГц. Одна несущая частота и один радиоканал. Через него идут ваши запросы в Google, TikTok ребёнка и обновление прошивки умной лампочки, и все это одновременно

Как? OFDM — Orthogonal Frequency Division Multiplexing.

OFDM берёт данные, разбивает на параллельные потоки и кодирует каждый поток на отдельной подчастоте. Десятки или сотни подчастот, каждая несёт свой кусочек данных. А «ортогональные» они потому, что подобраны так, чтобы не мешать друг другу — математически, это значит, что их произведение интегрируется в ноль (привет, ортогональность синусов, привет, Фурье).

Один Wi-Fi канал шириной 80 МГц:  [подч.1][подч.2][подч.3]...[подч.234]   ?       ?       ?            ?  данные  данные  данные  ...  данные  Все частоты передаются ОДНОВРЕМЕННО. Приёмник разделяет их обратно через... FFT.

На приёмной стороне ваш телефон делает обратное преобразование Фурье (IFFT) — и из каши радиоволн извлекает сотни отдельных потоков данных. Каждый Wi-Fi пакет разбирается и собирается через Фурье.

Wi-Fi 6 (802.11ax) делает 4096-QAM OFDMA — это 980 поднесущих частот, каждая модулирована с точностью до 4096 уровней. FFT, вычисляемый в реальном времени, на крошечном чипе, миллионы раз в секунду.

И это не только Wi-Fi. 4G LTE, 5G NR, DSL, DVB-T (цифровое ТВ), DAB (цифровое радио) — все используют OFDM. Все используют Фурье. Вся беспроводная связь на планете работает на идее, которую Лагранж назвал невозможной.

Shazam: и здесь тоже

Вы подносите телефон к колонке в баре. Через 3 секунды Shazam говорит что это за трек. Как?

1. Записать 3 секунды аудио 2. FFT ? спектрограмма (карта "какие частоты звучат в какой момент") 3. Найти пики на спектрограмме ? "отпечатки" (fingerprints) 4. Сравнить отпечатки с базой из 100+ миллионов треков 5. Совпадение ? результат

Шаг 2 — Фурье. Без него нет спектрограммы, без спектрограммы нет отпечатков, без отпечатков нет Shazam.

И заметьте: Shazam работает в шумном баре, с фоновым разговором, с искажённым звуком из дешёвой колонки. Потому что Фурье-пики на основных частотах мелодии устойчивы к шуму. Шум — это высокочастотный мусор, а основа трека — в характерных пиках. Фурье отделяет одно от другого.

MRI: Фурье смотрит внутрь вашего тела

Это самое интересное, имхо, применение.

МРТ-сканер — это гигантский магнит, который заставляет протоны водорода в вашем теле резонировать. Протоны в разных тканях резонируют чуть по-разному. Сканер записывает радиоволны, которые они испускают.

И вот ключевой момент: сканер НЕ получает изображение. Он получает набор пространственных частот. Данные записываются в «k-пространство» — это, по сути, Фурье-образ изображения.

Чтобы получить картинку вашего мозга, компьютер делает обратное преобразование Фурье из k-пространства. Буквально: ваш снимок МРТ — это результат работы алгоритма, придуманного в 1807 году.

Протоны резонируют ? радиоволны ? k-пространство (частоты)      ? Обратное преобразование Фурье      ? Изображение среза вашего мозга  Без Фурье МРТ невозможно. Не "сложно". Невозможно. Нет другого способа.

Когда врач смотрит на ваш снимок МРТ и говорит «всё чисто» — он смотрит на результат преобразования, которое его прибор выполнил несколько миллионов раз за время сканирования.

Масштаб

Давайте посчитаем, сколько раз прямо сейчас, в эту секунду, где-то на планете выполняется FFT:

• Музыка: ~600 миллионов пользователей стриминговых сервисов. Каждый MP3/AAC-поток декодируется через обратное FFT. ~600 млн FFT в секунду только от музыки.

• Фото: ~1.4 миллиарда фотографий делается в день. Каждая кодируется в JPEG через DCT. ~16 000 фото в секунду ? тысячи блоков 8?8 на фото = миллиарды DCT в секунду.

• Wi-Fi и сотовая связь: ~15 миллиардов подключённых устройств. Каждое выполняет OFDM-модуляцию/демодуляцию через FFT тысячи раз в секунду. Триллионы FFT в секунду.

• Голосовые помощники: каждый «Окей, Google» и «Привет, Siri» начинается с FFT входного аудио.

• Видео: каждый кадр каждого видео на YouTube, TikTok кодируется через DCT (в H.264, H.265, AV1 — везде).

Консервативная оценка: квадриллионы (10??) преобразований Фурье выполняются на планете каждую секунду.

Одна идея, одного человека из1807 года.

FFT: алгоритм, который сделал это возможным

Фурье придумал разложение, но вычислять его «в лоб» — это O(n?). Для сигнала из миллиона отсчётов — триллион операций.

В 1965 году Кули и Тьюки опубликовали алгоритм Fast Fourier Transform — FFT. Для миллиона отсчётов — 20 миллионов операций вместо триллиона (ускорение в 50 000 раз).

(На самом деле идею открывали несколько раз. Гаусс описал нечто похожее в 1805 году — до самого Фурье, но не опубликовал.)

FFT входит в любой топ «самых важных алгоритмов в истории». IEEE поставил его в один ряд с алгоритмами Дейкстры и PageRank.

# FFT за 12 строк. Рекурсивная версия. import numpy as np  def fft(x):     n = len(x)     if n == 1:         return x     even = fft(x[0::2])     odd = fft(x[1::2])     T = [np.exp(-2j * np.pi * k / n) * odd[k] for k in range(n // 2)]     return [even[k] + T[k] for k in range(n // 2)] +             [even[k] - T[k] for k in range(n // 2)]  # 12 строк. Квадриллион вызовов в секунду по всей планете.

Почему это работает вообще на всё

Остановитесь и подумайте: почему ОДНА математическая идея применима к звуку, изображениям, радиоволнам, медицине, сейсмологии, криптографии, квантовой механике, распознаванию речи, сжатию видео?

Физический мир состоит из волн. Звук — волны давления в воздухе. Свет — электромагнитные волны. Радио — электромагнитные волны. Колебания атомов, орбиты планет, биение сердца — периодические процессы.

Фурье показал, что любой периодический (и даже непериодический, с оговорками) процесс раскладывается на элементарные колебания. Это язык, на котором написана физика.

Мы не «применяем Фурье к звуку». Звук уже является суммой синусоид. Фурье просто дал нам способ это увидеть.

Лагранж был неправ

В 1807 году Лагранж голосовал против публикации работы Фурье. Рукопись пролежала в столе 15 лет, и была опубликована только в 1822 году (и то после многочисленных переработок).

Фурье к тому времени уже успел побывать на войне, в тюрьме (дважды — один раз от якобинцев, один раз при Наполеоне), стать губернатором провинции и руководить египетской экспедицией. Математику он делал, по сути, на сдачу от биографии авантюриста.

Он умер в 1830 году, так и не увидев ни одного практического применения своего преобразования. MP3, JPEG, Wi-Fi, MRI — всё это было через 150–190 лет после его смерти.

Если бы Фурье мог видеть, что квадриллион операций в секунду выполняется на основе его формулы — формулы, которую Лагранж назвал невозможной, — интересно, что бы он сказал.

Впрочем, я думаю, он бы просто пожал плечами.