Алгоритм, що називається Швидким Перетворенням Фур'є (ШПФ, Fast Fourier Transform, FFT), є одним із найважливіших аспектів "цифрового" життя людства. Але про це мало хто знає чи навіть підозрює. ШПФ - це основний базовий алгоритм, що використовується для цифрової обробки сигналів, зображень, стиснення даних, аудіо та відеоінформації, та іншої складної математики, що дозволяє переглянути черговий епізод Вашого улюбленого серіалу на екрані смартфона чи комп'ютера.
Основним призначенням алгоритму ШПФ є розкладання складних негармонійних сигналів на кілька гармонійних чистих сигналів, частот. Таким чином один єдиний складний електричний сигнал, що йде по проводам від Вашого MP3-плеєра до навушників, перетворюється у безліч різних звуків, які складають музику.
Не вдаючись глибоко у математичні нетрі алгоритміки перетворення Фур'є, розповімо, що перетворення Фур'є розкладає будь-який сигнал, радіосигнал, відео чи аудіо, на складові частоти. Отримавши таку розкладку, можна підсилити деякі частоти або повністю позбутися від небажаних складових сигналу. Застосовуючи після обробки зворотне перетворення Фур'є, знову утворюється вихідний сигнал, але повністю вільний від шумів, перешкод і перекручувань. При цьому відбувається лише незначна втрата якості (інформації) щодо вихідного сигналу.
Алгоритм ШПФ і так у цей час оптимізований по максимуму і виконується вкрай швидко, але, виявляється, його можна зробити ще швидшим. Команда дослідників із Масачусетського технологічного інституту представила новий алгоритм, який виконує функцію перетворення Фур'є, що по швидкості роботи у більшості випадків значно перевершує стандартний алгоритм ШПФ. Дуже важко недооцінити важливість такого досягнення, адже завдяки більш швидкому перетворенню Фур'є мобільні електронні пристрої зможуть передавати і одержувати високоякісні відео- та аудіо-сигнали, не збільшуючи ширину смуги передачі, істотно заощаджуючи заряд акумуляторних батарей.
Застосування нового алгоритму перетворення Фур'є та спеціальних процесорів цифрової обробки сигналу (Digital Signal Processor, DSP), що реалізують цей алгоритм, дозволить збільшити у кілька разів швидкості передачі інформації по радіо- й оптичним каналам, а у деяких випадках величина цього збільшення може скласти 10 разів і більше. З урахуванням того, що алгоритми перетворення Фур'є і так виконуються досить швидко на даний час, то десятикратне прискорення - це досить серйозне досягнення.
Докладний опис нового алгоритму англійською мовою доступний на сайті arXiv.org
|
