Проекти

Математиците от MIT ускориха 10 пъти бързото преобразуване на Фурие

CIO Media

ФуриеИзследователи от Масачузетския технологичен институт са разработили алгоритъм за бързи изчисления на дискретно преобразуване на Фурие, който за определени задачи работи 10 пъти  по-бързо от създадения още през 60-те години класически вариант.
Накратко, преобразуване на Фурие е математическа операция, която трансформира дадена функция в друга. Дискретно преобразуване на Фурие (ДПФ) е сходна операция, но изисква дискретна входна функция, чиито ненулеви стойности имат ограничена продължителност. Бързото преобразуване на Фурие представлява ефикасен алгоритъм за изчисление на ДПФ  и обратната трансформация.

Дискретното преобразуване на Фурие (ДПФ) е един от стълбовете на цифровата обработка на сигнали. Този модел се прилага в алгоритми за компресиране на JPEG изображения и звукови файлове MP3. През годините са правени опити за ускоряване на ДПФ, но досега не бяха постигнати съществени резултати.

Принципът на действие на ДПФ се свежда до преобразуване на цифровия сигнал, представляващ набор от дискретни стойности на честоти в среднопретеглена сума на тези стойности. При това част от стойностите на честотите се считат за незначителни и се игнорират. Сигналите, съдържащи относително малък брой значими честоти, учените наричат “разредени” (sparse). Новият алгоритъм е ориентиран именно към работа с такива сигнали. Според авторите, повечето срещани в практиката сигнали са разредени, поради което в много случаи техният алгоритъм ще работи по-бързо от традиционния.


X