В качестве одного из решений можно назвать FFTW (The Fastest Fourier Transform in the West) - разработку, выполненную Маттео Фриго (Matteo Frigo) и Стивеном Джонсоном из Массачусетского технологического института. Это переносимая (способная работать на множестве платформ) библиотека, написанная на C, свободная (GPL) и доступная ( [ ]), позволяющая вычислять одно- и многомерные дискретные преобразования Фурье по алгоритму Кули-Тьюки. Изюминка FFTW заключается в очень хитрой технологии оптимизации вычисления БПФ в зависимости от особенностей процессора и длины реализации. На этапе компиляции библиотеки генерируются вычислительные примитивы (codelets) на С, учитывающие особенности процессора. Затем на этапе выполнения для заданного размера выборки планировщик (planer) соединяет эти примитивы оптимальным образом (генерируя байт-код алгоритма). А исполнительный блок (executor) этот план реализует, обращаясь к вычислительным примитивам. Получается, что программа сама приспосабливается к условиям и работает оптимально на любом процессоре без переписывания исходника. Авторы утверждают, что интерпретация байт-кода не слишком накладна («наши результаты противоречат обывательской теореме, что байт-код медленный»).
Но тут возникает проблема: а как его запрограммировать для целей обработки сигналов?
Конечно, уже написано множество программ для обработки сигналов и изображений. Но бывает, что возникают задачи, которые еще не решены, либо требуется встраивание средств обработки в программную систему, либо нужно создать специализированный инструмент (опять возвращаемся от универсального к специализированному, но на программном уровне). Что для этого требуется? Приобретать специализированный DSP-процессор плюс средства разработки для него? Не обязательно. Многие задачи можно успешно решать на уже имеющемся компьютере с процессором Intel inside.
С другой стороны, технология изготовления универсальных процессоров тоже не стоит на месте. Тактовая частота зашкаливает за гигагерц. Набор команд универсальных процессоров дополняется подмножествами команд, правильно, цифровой обработки сигна лов. Для процессоров Intel эти расширения называются MMX, Streaming SIMD Extensions, SSE2. Мультимедиа, Win-модемы, DVD- и MPEG-проигрыватели, распознавание речи и многие другие технологии широко используют эти расширения.
В свое время даже делали специализированные устройства для выполнения БПФ (я помню еще сделанные на россыпи, чуть ли не на 155-й серии). Потом появились специализированные одночиповые DSP-процессоры. Они приспособлены для быстрого выполнения примитивов цифровой обработки сигналов, часто используется конвейерная обработка. Характерная их особенность - специализированный набор команд, что в ряде случаев вызывает потребность в универсальном процессоре для взаимодействия с внешним миром. Бывает, что DSP-процессоры содержат встроенные АЦП и ЦАП. Специализированные устройства, как правило, имеют более высокое быстродействие, чем универсальные. Все это хорошо, но, как правило, дорого, требует специальных навыков и инструментов разработки для создания законченного изделия и оправданно лишь при массовом серийном производстве или для специальных применений.
Так сложилось, что хорошо разработанным (традиционным) приемом анализа и обработки сигналов (и аналоговых, и цифровых) стало разложение по базису синусов-косинусов - преобразование Фурье. В условиях линейности и стационарности это очень удобный инструмент как для обработки детерминированных, так и стохастических сигналов. Но если линза выполняет преобразование Фурье мгновенно, то выполнение преобразования Фурье для цифрового сигнала на классическом последовательном процессоре требует времени. Кули и Тьюки, разработав в свое время алгоритм быстрого преобразования Фурье (БПФ) и приведя вычислительные затраты к соотношению O(Nlog2N), сделали революцию в цифровой обработке сигналов. Но аппетиты растут, и умножать все равно надо много и быстро.
Благодаря ряду преимуществ основным способом обработки сигналов стал цифровой. Электрические сигналы от датчиков (обычно аналоговые, непрерывные во времени и по уровню, если мы не измеряем заряд электрона) подвергаются квантованию (приведению к дискретным значениям по уровню) и дискретизации (привязыванию к фиксированным моментам времени) и превращаются в поток цифр. Как правило, используется равномерная шкала, хотя бывает полезна и неравномерность (например логарифмическая). Сам по себе этот переход небезболезненный, но если верить Котельникову (или Найквисту, на выбор), при определенных условиях цифровой сигнал хорошо соответствует исходному аналоговому. И анализируя цифровой сигнал, мы можем многое сказать об исходном, аналоговом. Реализацию (запись) цифрового сигнала достаточно легко сохранить надолго и без искажений. Теперь осталось лишь его обработать.
Как правило, обработку сигналов и изображений разделяют. Под «сигналами» обычно подразумевают (одномерные) изменения величины во времени, а под «изображениями» - (двумерные) поля в пространстве. Тем не менее, методы их обработки близки и часто основаны на одних и тех же операциях и преобразованиях, хотя, конечно, каждое из направлений имеет свою специфику.
Тактов на пиксел
Время вычисления, с
Построение гистограммы
Дискретное косинусное преобразование
Быстрое преобразование Фурье
Характеристики сигналов нужно измерить (выразить количественно), сами сигналы нужно сохранять, часто их можно изучить, только отделив от других, не интересных в данных момент сигналов, или приведя к другому представлению. Обработка сигналов - фундаментальная задача человека. Типичные примеры сигналов - речь (звук), изображение (фотография), поля температуры, рентгеновские снимки, радиосигналы внеземных цивилизаций, сигнал обычного модема.
Окружающую реальность мы воспринимаем с помощью «датчиков» разных типов (органов чувств), на выходе которых в конце концов оказываются электрические сигналы. Процессор, расположенный между ушей, худо-бедно справляется с приходящим к нему потоком сигналов. Но человеческое любопытство идет дальше, за пределы возможностей своих естественных датчиков и собственного процессора. Кроме того, развитие вычислительной техники уже давно привело к тому, что многие виды человеческой деятельности перекладываются на плечи машин. А раз компьютеры должны взаимодействовать с миром, то они должны получать из него информацию сами. Еще один важный аспект - взаимодействие человека и компьютера. Естественные для человека способы коммуникации требуют того же - обработки сигналов.
А что такое реально? Как определить, что реально? Если ты говоришь про то, что можно потрогать, почувствовать, увидеть, тогда реальность - это всего лишь электрические сигналы, которые интерпретирует наш мозг. Морфей (персонаж фильма «Матрица»)
Опубликовано в журнале
Ключи и отмычки DSP
05 февраля 2013 года
Ключи и отмычки DSP - Журнал "Компьютерра"
Комментариев нет:
Отправить комментарий