|  | 21 января 2012 | Информационные технологии

Новое, более быстрое преобразование Фурье значительно ускорит один из фундаментальных алгоритмов.

Преобразование Фурье


Алгоритм, называемый Быстрым Преобразованием Фурье (БПФ, Fast Fourier Transform, FFT), является одним из самых важных аспектов "цифровой" жизни человечества. Но об этом мало кто знает и даже подозревает. БПФ - это основной базовый алгоритм, используемый для цифровой обработки сигналов, изображений, сжатия данных, аудио и видеоинформации, и другой сложной математики, позволяющей просмотреть очередной эпизод Вашего любимого сериала на экране смартфона или компьютера.

Основным назначением алгоритма БПФ является разложение сложных негармонических сигналов на несколько гармонических чистых сигналов, частот. Подобным образом один единственный сложный электрический сигнал, идущий по проводам от Вашего MP3-плеера к наушникам, превращается во множество различных звуков, которые составляют музыку.

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

Алгоритм БПФ и так в настоящее время оптимизирован по максимуму и выполняется крайне быстро, но, оказывается, его можно сделать еще быстрее. Команда исследователей из Массачусетского технологического института предоставила новый алгоритм, выполняющий функцию преобразования Фурье, который по скорости работы в большинстве случаев значительно превосходит стандартный алгоритм БПФ. Очень трудно недооценить важность такого достижения, ведь благодаря более быстрому преобразованию Фурье мобильные и передвижные электронные устройства смогут передавать и получать высококачественные видео- и аудио-сигналы, не увеличивая ширину полосы передачи и существенно экономя заряд аккумуляторных батарей.

Применение нового алгоритма преобразования Фурье и специальных процессоров цифровой обработки сигнала (Digital Signal Processor, DSP), реализующих этот алгоритм, позволит увеличить в несколько раз скорости передачи информации по радио- и оптическим каналам, а в некоторых случаях величина этого увеличения может составить в 10 раз и более. С учетом того, что алгоритмы преобразования Фурье и так выполняются достаточно быстро в настоящее время, то десятикратное ускорение - это весьма серьезное достижение.




Ключевые слова:
Быстрое, Преобразование, Фурье, БПФ, Fast Fourier Transform, FFT, Алгоритм, Скорость, Сигнал, Частота

Первоисточник

Другие новости по теме:
  • Видео из 100 тысяч кадров, являющееся результатом работы прогнозирующего ал ...
  • Новая оптическая система может принять единичные случайные радио-сигналы, п ...
  • Создан первый самообучающийся алгоритм распознавания объектов на фото и вид ...
  • Установлен рекорд скорости передачи данных, равный 26 терабит в секунду.
  • Вычислительный потенциал единственной молекулы - в тысячи раз быстрее обычн ...




  • 21 января 2012 07:14
    #1 Написал: volod

    Публикаций: 0
    Комментариев: 1489
    Сейчас любят все в деньгах измерять, посчитали бы мировые потери из-за несвоевременного внедрения доработанного алгоритма. А может об улучшенном алгоритме давно знают, да только под старый уже аппаратная поддержка всевозможного оборудования разработана и контракты на производство подписаны, новой технологии было не место.
        
    21 января 2012 08:23
    #2 Написал: ogost

    Публикаций: 0
    Комментариев: 0
    volod,
    к сожалению, второй сценарий - далеко не редкость в наши дни.
        
    21 января 2012 08:25
    #3 Написал: nobolu

    Публикаций: 0
    Комментариев: 0
    Жаль, что про сам алгоритм ничего не известно. Хоть бы в общих черах.
        
    21 января 2012 10:10
    #4 Написал: FomaNeverujuwij

    Публикаций: 0
    Комментариев: 3870
    Цитата: nobolu
    что про сам алгоритм ничего не известно. Хоть бы в общих черах.

    Весьма даже известно -
    http://arxiv.org/pdf/1201.2501v1.pdf
    http://web.mit.edu/newsoffice/2012/faster-fourier-transforms-0118.html


    --------------------
        
    21 января 2012 13:02
    #5 Написал: serji

    Публикаций: 0
    Комментариев: 0
    ничего не происходит просто так - пришло время и открыли. у каждой технологии своё место и время.
        
    21 января 2012 15:22
    #6 Написал: CoJIb

    Публикаций: 0
    Комментариев: 1155
    В мире торговли врем новых технологий тогда когда старые не продаются, и так будет до тех пор пока человечестов не вернется к рабству, где все будут делать роботы, а значит все будит на халяву, разве что придется неного вермени тратить чтобы сказать роботу что хочеш. И повезет тем кто выживет когда население прореживать начнут для более комфортной жизни новых богов am
        
    21 января 2012 17:59
    #7 Написал: flandger

    Публикаций: 0
    Комментариев: 0
    ничего не происходит просто так - пришло время и открыли. у каждой технологии своё место и время.

    Им нужен был пиар и деньги, вот и "открыли" что было давно известно.
        
    23 января 2012 09:33
    #8 Написал: Angmar

    Публикаций: 0
    Комментариев: 110
    в большинстве случаев значительно превосходит стандартный алгоритм БПФ

    Давным давно существует много методик его ускорения.
    Однако, большинство из них ведут к потерям/искажению информации. Против математики не попрёшь, если в общем случае будет ускорение, то в частных случаях это приведёт к значительным ошибкам.
        

    Информация

    Посетители, находящиеся в группе Гости, не могут оставлять комментарии к данной публикации.