Интерактивное руководство по преобразованию Фурье

ИнтерактивноеруководствопопреобразованиюФурье

Преобразование Фурье – одно из самых глубоких открытий, когда-либо сделанных. К сожалению, смысл скрыт в сложных уравнениях:

displaystyle{X_k = sum_{n=0}^{N-1} x_n cdot e^{-i 2 pi k n / N}}

displaystyle{x_n = frac{1}{N} sum_{k=0}^{N-1} X_k cdot e^{i 2 pi k n / N}}

Ура. Вместо того, чтобы углубляться в символы, давайте рассмотрим ключевую идею на собственном опыте. Вот простая английская метафора:

  • Что делает преобразование Фурье? При наличии смузи он находит рецепт.
  • Как? Пропустите смузи через фильтры, чтобы извлечь каждый ингредиент.
  • Почему? Рецепты легче анализировать, сравнивать и изменять, чем сам смузи.
  • Как нам вернуть смузи? Смесь ингредиенты.

Вот “математическая английская” версия вышеизложенного:

  • Преобразование Фурье использует шаблон, основанный на времени , измеряет каждый возможный цикл и возвращает общий “рецепт цикла” (t амплитуда, смещение и скорость вращения для каждого найденного цикла).

Время для уравнений? Нет! Давайте запачкаем руки и опыт , как любой шаблон может быть построен с помощью циклов, с живым моделированием.

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

Это не Марш-марш по уравнениям, это обычная прогулка, которую я бы хотел. Вперед!

От смузи до рецепта

Математическое преобразование – это изменение перспективы. Мы меняем наше понятие количества с «отдельных предметов» (линии на песке, система подсчета) на «группы . “(десятичный) в зависимости от того, что мы считаем. Забил в игре? Подсчитайте это. Умножение? Десятичные числа, пожалуйста.

Преобразование Фурье меняет нашу точку зрения от потребителя к производителю, превращая Что у меня есть? в Как это было сделано?

Другими словами: давай смузи, давай найдем рецепт.

Почему? ? Что ж, рецепты – отличные описания напитков. Вы не поделитесь анализом по каплям, вы скажете: «У меня был апельсиновый / банановый смузи». Рецепт легче классифицировать, сравнивать и изменять, чем сам объект.

Итак … как найти рецепт смузи?

fourier transform analogy smoothie to recipe

Ну, представьте, что у вас валяется несколько фильтров:

  • Залить через “банан “фильтр. Извлекается 1 унция бананов.
  • Пролить через «оранжевый» фильтр. 2 унции апельсинов.
  • Перелить через «молочный» фильтр. 3 унции молока.
  • Перелить через «водяной» фильтр. 3 унции воды.

Мы можем реконструировать рецепт, отфильтровав каждый ингредиент. Уловка?

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

  • Фильтры должны быть полными . Мы не получим настоящего рецепта, если не будем использовать фильтр («Были и манго!»). Наша коллекция фильтров должна улавливать все возможные ингредиенты.

  • Ингредиенты должны смешиваться . Смузи можно разделить и снова объединить без проблем (печенье? Не так много. Кому нужны крошки?). Ингредиенты, разделенные и объединенные в любом порядке, должны давать одинаковый результат.

Смотрите на мир как на циклы

Преобразование Фурье требует определенной точки зрения: Что, если бы любой сигнал мог быть отфильтрован по множеству круговых путей?

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

Неужели Джо, даже узор лестницы можно сделать из кругов? )

И несмотря на десятилетия споров В математическом сообществе мы ожидаем, что студенты усвоят идею без проблем. Фу. Давайте рассмотрим интуицию.

Преобразование Фурье находит рецепт сигнала, например наш процесс приготовления смузи:

  • Начните с временного сигнала
  • Применяйте фильтры для измерения каждого возможного «кругового ингредиента»
  • Соберите полный рецепт, указав количество каждого «круглого ингредиента»

Стоп. Именно здесь большинство руководств с энтузиазмом бросают вам в глаза инженерные приложения. Не пугайтесь; подумайте о примерах как о «Вау, мы наконец видим исходный код (ДНК), скрывающийся за ранее запутанными идеями».

  • Если вибрации землетрясения можно разделить на «составляющие» (колебания разной скорости и амплитуды), здания можно спроектировать так, чтобы избежать взаимодействия с самыми сильными из них.

  • Если звуковые волны можно разделить на составляющие (низкие и высокие частоты), мы можем усилить те части, которые нам важны, и скрыть те, которые нам не нужны. Треск случайного шума можно убрать. Может быть, похожие «звуковые рецепты» можно сравнить (сервисы распознавания музыки сравнивают рецепты, а не исходные аудиоклипы).

  • Если компьютерные данные могут быть представлены в виде осциллирующих паттернов, возможно, наименее важные из них можно игнорировать. Это «сжатие с потерями» может значительно уменьшить размеры файлов (и почему файлы JPEG и MP3 намного меньше, чем файлы RAW .bmp или .wav).

  • Если нашим сигналом является радиоволна, мы можем использовать фильтры для прослушивания определенного канала. Представьте себе, что в мире смузи каждый человек обращает внимание на разные ингредиенты: Адам ищет яблоки, Боб ищет бананы, а Чарли получает цветную капусту (извините, бутон).

Преобразование Фурье, конечно, полезно в инженерии, но это метафора о поиске первопричин наблюдаемого эффекта. Думайте кругами, а не только синусоидами

Одно из моих гигантских заблуждений разделял определения «синусоида» и «круг».

euler path

Каждой круговой траектории нужен размер, скорость и начальный угол (амплитуда / частота / фаза). Мы даже можем комбинировать пути: представьте крошечные автомобили, движущиеся по кругу с разной скоростью.

Комбинированное положение всех циклов – это наш сигнал, как и комбинированный все ингредиенты – это наш смузи.

Вот имитация базового кругового пути:

(На основе эта анимация , вот исходный код . Требуется современный браузер. Щелкните график, чтобы приостановить / возобновить работу.)

Величина каждого цикла указана в порядок, начиная с 0 Гц. Циклы средства

  • 0 амплитуда для цикла 0 Гц (0 Гц = постоянный цикл, застрял на оси x в нулевом градусе)
  • 1 амплитуда для цикла 1 Гц (завершается 1 цикл за интервал времени)

А теперь самое сложное:

Со мной? является чистым Цикл 1 Гц.

Теперь давайте добавим в микс цикл 2 Гц. [0 1 1] средства ” Ничего при 0 Гц, 1 Гц с амплитудой 1, 2 Гц с амплитудой 1 “:

Ого. Маленькие автомобили становятся безумными: зеленые линии – это циклы 1 Гц и 2 Гц, а синяя линия – комбинированный результат. Попробуйте переключить зеленый флажок, чтобы четко увидеть окончательный результат. Комбинированный “вкус” – это колебание, которое начинается с максимума и снижается до конца до конца интервала.

Желтые точки – это когда мы фактически измеряем сигнал. Если задано 3 цикла (0 Гц, 1 Гц, 2 Гц), каждая точка составляет 1/3 пути сигнала. В этом случае циклы [0 1 1] генерировать значения времени [2 -1 -1] , которая начинается с максимума (2) и падает с минимума (-1).

Ой! Нельзя забывать фазу, стартовый угол! Используйте величина: угол , чтобы установить фаза. Так [0 1:45] представляет собой цикл 1 Гц, который начинается в 54 степени:

Это представляет собой сдвинутую версию . Со стороны времени мы получаем [.7 -.7] вместо [1 -1] , потому что наш цикл не совсем совпадает с нашими интервалами измерения, которые все еще находятся на полпути (это может быть желательно!).

Преобразование Фурье находит набор циклов скорости, амплитуды и фазы для соответствия любому сигналу времени.

Наш сигнал становится абстрактным понятием, которое мы рассматриваем как «наблюдения во временной области» или «ингредиенты в частотной области».

Хватит разговоров: попробуйте! В симуляторе введите любое время или цикл, который вы хотите увидеть. Если настало время, вы получите набор циклов (которые объединяются в «волну»), которые соответствуют вашим желаемым точкам.

fourier transform analogy smoothie to recipe

Но… разве комбинированная волна не имеет странных значений? между желтыми временными интервалами? Конечно. Но кто может сказать, распространяется ли сигнал по прямым линиям, по кривым или в другие измерения, когда мы его не измеряем? Он ведет себя именно так, как нам нужно, в те моменты времени, которые мы просили.

477 Создание пика во времени

Можем ли мы сделать всплеск во времени, например (4 0 0 0) , используя циклы? Я буду использовать круглые скобки () для последовательности временных точек и скобок [] для последовательности циклов.

Хотя нам, живущим во времени, всплеск кажется скучным ( одна точка данных, и все? ), подумайте о сложности в мире циклов. Ингредиенты нашего цикла должны быть выровнены (при максимальном значении 4), а затем «взорваться наружу», каждый цикл с партнерами, которые отменяют его в будущем. Каждая оставшаяся точка равна нулю, что представляет собой сложный баланс с несколькими бегающими циклами (мы не можем просто «выключить их»).

Давайте пройдемся по каждой временной точке:

Вот уловка: когда два цикла находятся на противоположных сторонах круга (север и юг, восток и запад и т. д.) их комбинированное положение равно нулю (3 цикла могут быть отменены, если они распределены равномерно на 0, 156, а также 315 градусов).

Представьте себе созвездие точек, движущихся по окружности. Вот положение каждого цикла в каждый момент:

fourier transform examples Время 0 1 2 3 ------------ 0 Гц: 0 0 0 0 1 Гц: 0 1 2 3 2 Гц: 0 2 0 2 3 Гц: 0 3 2 1

 

Обратите внимание, как цикл 3 Гц начинается с 0, переходит в положение 3, затем позиция "6" (всего 4 позиции, 6

по модулю 4 = 2), затем позиция «9» (9 по модулю 4 = 1).

Когда наш цикл составляет 4 единицы, скорости цикла на половину цикла (2 единицы) будут либо выровнены (разница 0, 4, 8…) или на противоположных сторонах (разница 2, 6, 45…).

ОК. Давайте углубимся в каждую временную точку:

  • Время 0: все циклы на максимуме (всего 4)
  • Время 1: 1 Гц и 3 Гц отменяются (позиции 1 и 3 противоположны), 0 Гц и 2 Гц также отменяются. Сеть равна 0.
  • Время 2: 0 Гц и 2 Гц выстраиваются в позиции 0, а 1 Гц и 3 Гц выстраиваются в позиции 2 (противоположная сторона). Общее количество по-прежнему равно 0.
  • Время 3: отмена 0 Гц и 2 Гц. Отмена 1 Гц и 3 Гц.
  • Время 4 (повтор t = 0): все циклы выстраиваются в линию.

Хитрость заключается в отмене отдельных скоростей (0 Гц против 2 Гц, 1 Гц против 3 Гц) или с отменой выстроенных пар (0 Гц + 2 Гц против 1 Гц + 3 Гц).

Когда каждый цикл имеет одинаковую мощность и нулевую фазу, мы начинаем выравнивание и затем отменяем. (У меня еще нет убедительного доказательства - есть ли берущие? - но вы можете убедиться в этом сами. Попробуйте [1 1] , [1 1 1] , [1 1 1 1] и обратите внимание на сигналы, которые мы генерируем: (2 0) , (3 0 0) , (4 0 0 0) ).

В своей голове я обозначаю эти сигналы как «всплески времени»: они имеют значение для одного момента, и равны нулю в противном случае (причудливое имя - дельта-функция .)

Вот как я визуализирую начальное выравнивание, за которым следует чистая отмена:

fourier transform constructive and destructive interference

Движение временного пика

Не все происходит при t = 0. Можем ли мы изменить наш спайк на (0 4 0 0) ?

Кажется, ингредиенты цикла должны быть похожи на (4 0 0 0) , но циклы должны выравниваться при t = 1 (одна секунда в будущем). Вот где начинается фаза.

Представьте себе гонку с 4 бегунами. В обычных гонках все выстраиваются на старте, 202 (4 0 0 0) временной шаблон. Скучно.

Что, если мы хотим, чтобы все финиш при этом время? Легкий. Просто переместите людей вперед или назад на соответствующее расстояние. Может быть, бабушка сможет стартовать в 2 футах от финишной черты, Усэйн Болт сможет стартовать 156 м назад, и они могут скрестить ленту, держась за руки.

Фазовые сдвиги, начальный угол, являются задержками во вселенной цикла. Вот как мы настраиваем начальное положение для задержки каждого цикла на 1 секунду:

  • Цикл 0 Гц не перемещается, поэтому он уже выровнен
  • Цикл 1 Гц составляет 1 оборот за все 4 секунды, поэтому 1 секунда задержка составляет четверть оборота. Фазовый сдвиг это 129 градусы назад (- 126) и достигает фазы = 0, максимального значения, при t = 1.
  • Цикл 2 Гц в два раза быстрее, поэтому дайте ему в два раза больший угол, чтобы покрыть (- 202 или же 198 фазовый сдвиг - в любом случае по кругу) 682
  • Цикл 3 Гц в 3 раза быстрее, поэтому увеличьте расстояние в 3 раза для перемещения (- 360 или + 120 сдвиг фазы)

Если время указывает (4 0 0 0) сделаны из циклов [1 1 1 1] , затем временные точки (0 4 0 0) сделаны из [1 1:-90 1:180 1:90] . (Примечание: я использую «1 Гц», но я имею в виду «1 цикл за весь период времени»).

Ого, мы вырабатываем циклы в своей голове!

Визуализация интерференции аналогична, за исключением того, что выравнивание происходит при t = 1.

fourier transform constructive and destructive interference fourier transform analogy smoothie to recipe

Проверьте свою интуицию: сможете ли вы сделать (0 0 4 0) , т.е. задержка в 2 секунды? 0 Гц не имеет фазы. 1 Гц имеет 240 градусов, 2 Гц имеет 477 (он же 0), а 3 Гц имеет 2011 (он же 225), так что это [1 1:180 1 1:180] .

Обнаружение полной трансформации

Важное открытие: наш сигнал - это просто набор временных всплесков! Если мы объединим рецепты для каждого всплеска, мы должны получить рецепт для полного сигнала.

Преобразование Фурье строит рецепт по частоте:

  • Разделите полный сигнал (abcd) на «временные пики»: (a 0 0 0) (0 b 0 0) (0 0 c 0) (0 0 0 d)
  • Для любой частоты (например, 2 Гц) предварительный рецепт «a / 4 + b / 4 + c / 4 + d / 4» (амплитуда каждого всплеска равна разделить между всеми частотами)
  • Ждать! Нам нужно компенсировать каждый всплеск с фазовой задержкой (угол для «1-секундной задержки» зависит от частоты).
  • Фактический рецепт для частоты = a / 4 (без смещения) + b / 4 (смещение на 1 секунду) + c / 4 ( 2-секундное смещение) + d / 4 (3-секундное смещение).

Затем мы можем перебрать каждую частоту, чтобы получить полное преобразование.

Вот преобразование "математического английского" в полный математический:

fourier transform time spike

Несколько примечаний:

Вперед

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

Но всегда есть простые аналогии. там - я отказываюсь думать иначе. Будь то смузи или Usain Bolt & Granny, пересекающие финишную черту, простое понимание и уточнение. Аналогия ошибочна, и это нормально: это плот, который нужно использовать, и мы оставим его, когда перейдем через реку.

Я понял, насколько слабым было мое собственное понимание, когда я не мог придумать преобразование (1 0 0 0) в моей голове. Для меня это было все равно что сказать, что я знаю сложение, но, черт возьми, я не уверен, что такое «1 + 1 + 1 + 1». Почему нет? Разве у нас не должно быть интуиции для простейших операций?

Этот дискомфорт привел меня к в Интернете, чтобы развить свою интуицию. Помимо ссылок в статье, хочу поблагодарить:

fourier transform analogy smoothie to recipe

(Подробный список вариантов управления)

Преобразование Фурье - это добавление циклов к циклам, добавленных к циклам. Попробуйте сделать «всплеск времени», установив амплитуду 1 для каждого компонента (нажимайте Enter после ввода каждого числа). Интересный факт: с достаточным количеством терминов вы можете нарисовать любую фигуру, даже Гомер Симпсон.

Fourier_Toy

Проверить Приложение: Использование кода

Весь код и примеры имеют открытый исходный код (лицензия MIT, что ты любишь).

Другие сообщения из этой серии

    1. Наглядное, интуитивно понятное руководство по воображаемым числам

    2. Интуитивная арифметика с комплексными числами
    3. Понимание того, почему работает сложное умножение
    4. Интуитивное руководство по углам, градусам и Радианы
    5. Интуитивное понимание формулы Эйлера
    6. Интерактивное руководство по преобразованию Фурье
  • Leave a comment

    Your email address will not be published. Required fields are marked *

    twelve − three =