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