Max Home IndustryЧто-то, называемое быстрым преобразованием Фурье, сейчас работает на вашем мобильном телефоне. БПФ, как известно, представляет собой алгоритм обработки сигналов, который вы используете больше, чем вы думаете. Согласно названию одной исследовательской работы, это «алгоритм, который может использовать вся семья».
Александр Стойчев, доцент кафедры электротехники и вычислительной техники в Университете штата Айова, который также связан с университетским центром приложений виртуальной реальности, его аспирантской программой взаимодействия человека с компьютером и факультетом информатики, говорит, что алгоритм БПФ и его инверсии (известные как ОБПФ) лежат в основе обработки сигналов.
И поэтому «это алгоритмы, которые сделали возможной цифровую революцию», — сказал он.
Они участвуют в потоковой передаче музыки, звонят по мобильному телефону, просматривают Интернет или делают селфи.
Алгоритм БПФ был опубликован в 1965 году. Четыре года спустя исследователи разработали более универсальную, обобщенную версию, названную z-преобразованием chirp (CZT). Но подобное обобщение обратного алгоритма БПФ оставалось нерешенным в течение 50 лет.
До тех пор, пока Стойчев и Владимир Сухой, докторант штата Айова, со специализацией в области электротехники и вычислительной техники, а также взаимодействия человека с компьютером, не работали вместе, чтобы придумать долгожданный алгоритм, называемый обратным чириканьем. z-преобразование (ICZT).
Как и все алгоритмы, это пошаговый процесс решения проблемы. В этом случае он отображает выход алгоритма CZT обратно на его вход. По словам Стойчева, эти два алгоритма немного похожи на серию из двух призм: первая разделяет длины волн белого света на спектр цветов, а второй обращает процесс вспять, объединяя спектр обратно в белый свет.
Стойчев и Сухой описывают свой новый алгоритм в статье, недавно опубликованной в Интернете в журнале Nature Research Scientific Reports . В их статье показано, что алгоритм соответствует вычислительной сложности или скорости своего аналога, что он может использоваться с экспоненциально убывающими или растущими частотными компонентами (в отличие от IFFT) и что он был протестирован на числовую точность.
Стойчев сказал, что он наткнулся на идею попытаться сформулировать недостающий алгоритм, одновременно ища аналогии, чтобы помочь аспирантам в его курсе «Вычислительное восприятие» понять быстрое преобразование Фурье. Он прочитал много литературы по обработке сигналов и не смог найти ничего об обратном к соответствующему z-преобразованию chirp.
«Мне стало любопытно», — сказал он. «Это потому, что они не могли этого объяснить, или потому, что этого не существует? Оказалось, что этого не существует».
И поэтому он решил попробовать найти быстрый обратный алгоритм.
Сухой сказал, что обратный алгоритм представляет собой более сложную проблему, чем исходный прямой алгоритм, и поэтому «нам нужны были более точные и более мощные компьютеры для его атаки». Он также сказал, что ключевым моментом является видение алгоритма в математической структуре структурированных матриц.
Даже тогда было проведено множество компьютерных тестов, «чтобы показать, что все работает — мы должны были убедить себя, что это можно сделать».
Чтобы продолжать бороться с этой проблемой, требовалось мужество, — сказал Джеймс Оливер, директор Студенческого инновационного центра штата Айова и бывший директор университетского центра приложений виртуальной реальности. Стойчев и Сухой благодарят Оливера в своей статье «за создание исследовательской среды, в которой мы могли бы продолжить эту работу в течение последних трех лет».
Оливер сказал, что Стойчев заслужил свою поддержку в решении математической и вычислительной задачи, которую не решали в течение 50 лет: «Алекс всегда поражал меня своей страстью и стремлением решать сложные исследовательские задачи. В исследованиях и исследованиях всегда есть риск. это требует мужества, чтобы посвятить годы упорного труда к фундаментальной проблеме. Алекс является одаренным и бесстрашный исследователь «.