FFT: 60-летний алгоритм, лежащий в основе сегодняшней технологии

КТпотоковое видео и отправка изображений через Интернет не было бы возможно без Быстрое преобразование ФурьеПолем Обычно известный как FFT, компьютерный алгоритм, разработанный исследователями в Принстон Университет и IBM находится практически в каждом электронном устройстве, согласно записи в Инженерная и технологическая история викиПолем

Впервые продемонстрировано в 1964 году IEEE Fellows Джон Тьюки и Джеймс У. КулиАлгоритм разбивает сигнал – серию значений с течением времени – и преобразует его в частоты. FFT был в 100 раз быстрее, чем существующие Дискретное преобразование ФурьеПолем DFT также требует большей памяти, чем FFT, потому что он сохраняет промежуточные результаты при обработке.

FFT стал важным инструментом для манипулирования и анализа сигналов во многих областях, включая обработку звука, телекоммуникации, цифровые вещаниеи Анализ изображенийПолем Это помогает фильтровать, сжимать, устранять шум и изменить сигналы.

60-летний вездесущий компьютерный код также имеет приложения в современных передовых технологиях, таких как АйВ квантовые вычисленияВ Автомобили с самостоятельным вождениеми 5G Системы связи.

БПФ был отмечен IEEE Milestone Во время церемонии, состоявшейся в мае в Принстонский университетПолем

«Алгоритм Кули-Туки значительно ускорил расчет DFT», 2024 IEEE президент Том Кафлин сказал на церемонии. «Предыдущие методы требовали значительно большего количества вычислений, делая БПФ революционным прорывом. Используя алгебраические свойства и периодические свойства, FFT уменьшил количество операций, делая их особенно и практически возможными для повседневных задач, заменив менее эффективные методы аналоговых».

Новый математический инструмент

В 1963 году Тьюки, профессор Математика и статистика в Принстонучаствовал в собрании президента США Джона Ф. Кеннеди Научный консультативный комитет Чтобы обсудить способы обнаружения под землей ядерные испытаниясогласно заявлению ETHW.

Также присутствовал на этой встрече Ричард Гарвинфизик и инженер в IBM кто сыграл ключевую роль в разработке первого водород бомбить. Он умер в мае. Прочитайте о его увлекательной жизни в этом месяце В памятиПолем

Тьюки сказал Гарвину, что работает над ускорением расчета существующего метода – преобразования Фурье – то, что это может помочь с обнаружением. Его алгоритм Математически преобразован сигнал из исходного домена, такого как время или пространство, в частотную областьПолем

Гарвин признал свой потенциал и спросил IBM Чтобы выбрать математического аналитика для сотрудничества с Тьюки. Этот человек был Кули, сотрудника -исследователь, работающий над численным анализом и вычислительными проектами.

Если Фурье преобразование может быть сделан быстрее, сказал Гарвин, Сейсмометры могут быть посажены в земле в странах, окружающих Советский Союз Чтобы обнаружить ядерную взрывы Из испытаний на атомную бомбу, потому что Советы не разрешали бы испытания на месте, согласно Кули устная история в инженерии и Технологическая история Вики. А сейсмометр Измеряют наземные вибрации, которые преобразуются в электрические сигналы и регистрируются как сейсмограммы.

Для разработки датчиков для подземных ядерных испытаний, однако, «вам придется обработать все сейсмический Сигналы, и большая часть обработки может быть сделана с помощью преобразований Фурье », – сказал Кули в своей устной истории. Но« вычислительной мощности в то время было недостаточно для обработки всех сигналов, которые вам нужно сделать ».

FFT может рассчитать частоту сейсмического датчика и создавать образы, IEEE Life Fellow Гарольд С. Стоун сказал на мероприятии Milestone. Он обработка изображений исследователь и почетный человек в NEC Laboratories Америкав Принстоне, и бывший исследователь IBM.

Тьюки и Кули возглавляли команду, которая написала компьютерный код, который продемонстрировал силу БПФ.

«Демонстрация алгоритма Coley-Tukey показала, что это было в 100 раз быстрее»,-сказал Стоун. «Это было настолько быстро, что могло бы не отставать от сейсмических данных».

Датчики, использующие алгоритм, были посажены, и они обнаружили ядерные взрывы в радиусе 15 километров от того места, где они были взорваны, согласно записи ETHW.

«Используя алгебраические свойства и периодичность, FFT уменьшил количество операций, делая их особенно и практически возможным для повседневных задач, заменив менее эффективные аналоговые методы». –2024 Президент IEEE Том Кофлин

В 1965 году Кули и Тьюки опубликовали «Алгоритм расчета машины сложной серии Фурье”Описание процесса БПФ. Средняя статья побудила развитие Цифровая обработка сигнала технологии.

За его работу Тьюки был награжден США Национальная медаль науки в 1973 году. Он также получил 1982 год Медаль чести IEEE Для «вклада в спектральный анализ случайных процессов и алгоритма быстрого преобразования Фурье».

Кули, который получил 2002 год Медаль обработки сигналов IEEE Kilby Для новаторства FFT была ведущей фигурой в области цифрового обработка сигналаПолем Благодаря его участию в Комитете по обработке цифровых сигналов IEEE (сегодня известный как Общество обработки сигналов IEEE), он помог установить терминологию и предложил направления исследования.

Хотя не один из изобретателей, Гарвин приписывает признание того, что алгоритм имел более широкие приложения, особенно в научных и инженерных областях.

«В сегодняшнем Lingo Гарвин помог FFT« Go Viral », собрав Кули и Тьюки вместе», – сказал Стоун.

«Гарвин и Тьюки искали лучшую информацию, чтобы предотвратить и предотвратить войны», – добавил Фрэнк Анскомб, племянник Тьюки. «FFT Cooley-Tukey быстро продвигал эту причину, дав практическое, упрощающее решение для волнистых данных. Благодаря FFT, технологический Rubicon начал пересекать: аналого-цифровые машины».

Дух сотрудничества между академическими кругами и промышленностью

Как и многие инновации, FFT вышел из сотрудничества между промышленностью и академическими кругами, и это должно быть признано за это, Pellow Ieee Fellow Андреа Голдсмит сказал на церемонии. Она объяснила, что регулярно работает с FFT в своих исследовательских проектах. Во время мероприятия она была деканом инженерных и прикладных наук Принстона. В этом месяце она начала свою новую должность президента Университет Стоуни Брукв Нью -Йорке.

«Привлечение идей, которые мы имеем из базовых исследований в наших университетских лабораториях, общения с людьми в промышленности и понимание того, как проблемы исследований, над которыми мы работаем, могут принести пользу отрасли завтра или через пять лет или 20 лет, невероятно важно», – сказала она. «Некоторые люди думают о технике как скучной и сухой, и о том, что делают только ботаники, но во многих инновациях, которые мы разработали, есть такая красота и творчество, и я думаю, что БПФ является прекрасным примером этого».

FFT присоединяется к более чем 270 другими вехами IEEE. Они больше, чем маркер достижений, сказал старший член IEEE Life Бала С. Прасаннадиректор IEEE регион 1Полем

«Они являются свидетельством человеческой изобретательности, настойчивости и духа сотрудничества», – сказала Прасанна. «Эти вехи были больше, чем просто прорывы; они стали катализаторами для инноваций, обеспечивая прогресс способами, когда -то считавшись невозможным. Каждый из них гарантирует, что история этих инноваций сохраняется не только как история, но и как вдохновение для будущих поколений».

Другой церемония был проведен 11 июня в IBM Watson Исследовательский центр.

МИЛИАННЫЕ ПЛАТЫ, ЧТОБЫ ПОЗВОДЕНИЕ, ЧТОБЫ ДЕРЕВАТЬ В Лобби Принстона Школа инженерной и прикладной науки и в главном вестибюле у входа IBM Research центр.

Они читают:

«В 1964 году компьютерная программа внедряет высокоэффективную Анализ Фурье Алгоритм был продемонстрирован в IBM Research. Совместно разработанный Принстонским университетом и сотрудниками IBM, техника Кули-Туки рассчитывала дискретные порядок преобразования Фурье на величину быстрее, чем было продемонстрировано ранее. Известный как быстрое преобразование Фурье (FFT), его скорость повлияла на многочисленные приложения, включая компьютеризированные томографияаудио и сжатие видеообработка сигнала и потоковая передача данных в реальном времени ».

Управляется IEEE History Center и поддерживается донорыПрограмма Milestone признает выдающиеся технические события по всему миру. А IEEE Princeton Central Jersey Section спонсировал номинацию.