5,5 десятилетий цифровой обработки сигналов
Argc & аrgv. – Программирование / информационные технологии / стандарты. 2006. -No 1 . – С. 9-18.
5,5 десятилетий цифровой обработки сигналов
Трудно преувеличить значение цифровой обработки сигналов (ЦОС) для человечества. Можно индустриальную эру условно разделить на две эпохи: эпоху аналоговой и эпоху цифровой обработки сигналов. Грань между ними проходит в конце семидесятых – начале восьмидесятых годов прошлого столетия, когда в научно-технической печати нельзя было отдать безусловное предпочтение аналоговым или цифровым средствам обработки сигналов. Для большинства потребителей смена этих эпох произошла тогда, когда компакт-диски заменили собой виниловые диски.
В данной работе кратко изложена история ЦОС, ее появление, этапы развития, какие массовые применения ЦОС характерны для них. Такой анализ может дать ответы на вопросы, куда мы движемся дальше, где ожидать новых изобретений, прорывов, какова роль в этом программистов.
История обработки сигналов
Обработка сигналов, как временных рядов, ведется очень давно. Еще жрецы в Вавилоне, наблюдая движение диска Солнца, вычислили, что в круге – 360 градусов. Серьезная обработка временных рядов велась астрологами с целью предсказать будущие события в зависимости от прошедших.
Человечество долго шло к современному пониманию спектрального разложения сигналов. Двадцать шесть веков назад Пифагор обнаружил взаимосвязь между высотой тона колебания струны и ее длиной и распространил найденное эмпирическое соотношение на движение небесных тел. И. Ньютон три столетия назад ввел понятие спектра и объяснил математически периодическое волновое движение, т.е. то, что наблюдал Пифагор. Спустя сорок лет Д.Бернулли описал движение струны математической формулой, которая в последствии была названа рядом Фурье. А в 1755 г, т.е. еще через восемнадцать лет, Л.Эйлер вычислил значения коэффициентов уравнения Бернулли. Эти результаты были обобщены в 1822 г. французским инженером Ж.Б.Ж. Фурье в своей диссертации, где он показал, что бесконечным рядом Фурье можно представить любую функцию, заданную в равноотстоящих точках. После этого такие известные ученые, как лорд Кельвин, А.А. Майкельсон, пытались использовать разложение в ряд Фурье для прогнозирования приливов, солнечной активности, для чего были построены механические вычислители – гармонические анализаторы.
Английский статистик Дж.Юл также искал период солнечной активности, но подошел к этой проблеме с другой стороны. В 1927 г. он предложил находить гармоники сигнала как решение уравнения зависимости значения сигнала теперь от его значений в прошлом, т.е. уравнения регрессии. Этот метод потом лег в основу разработки цифровых фильтров, адаптивных фильтров с линейным предсказанием и параметрического метода спектрального анализа. Изучая законы расширения газов, в 1795 г. барон де Прони предложил метод точной подгонки суммы затухающих экспонент (в том числе и синусоидальных) к кривой, заданной несколькими точками. Это был подход, более общий, чем ряды Фурье, и о нем вспомнили сравнительно недавно [1].
ЦОС, как наука, основывается не только на спектральном представлении сигнала, но и на представлении его как случайного процесса. Еще в 1761 г. англичанин Т.Байес написал труд о решении задачи определения состояния изменяемого объекта, заложивший фундамент статистической обработки сигналов и в частности, теории оценки состояния наблюдаемых систем. К.Ф.Гаусс, используя понятие ошибки, введенное Лапласом, в 1795 г. предложил интерполяцию методом наименьших квадратов, которую успешно проверилна предсказании орбит небесных тел. В наше время стало обычным иметь дело с гауссовым распределением вероятности ошибок и отсчетов шумового сигнала.
В 1913 г. А.А.Марков на примере романа “Евгений Онегин” показал, что есть случайные процессы, в которых следующее состояние (следующее слово) с некоторой вероятностью зависит от предыдущих состояний (слов). В двадцатых годах прошлого столетия Н.Винер, описывая броуновское движение, ввел понятие винеровского случайного процесса. Наконец, он же в 1930 г. и независимо от него А.Я.Хинчин в 1933 г. свели вместе спектральный и статистический анализ. При этом ряд Фурье перерос в интеграл Фурье, были даны точные определения корреляции, спектральной плотности мощности, взаимосвязь которых выражена в теореме Винера-Хинчина. В развитие этого, в 1939 г. А.Н.Колмогоров сформулировал и решил задачу линейного предсказания для стационарного случайного процесса, основываясь на корреляционной функции [2]. Аналогичные задачи интерполяции, экстраполяции и сглаживания были решены Н.Винером в 1949 г. Сейчас фильтры Винера играют основную роль в задачах адаптивной фильтрации, восстановления сигналов, идентификации объектов.
Центральное место в ЦОС занимает теорема дискретизации. Еще в 1924 г. Г.Найквист заметил, что скорость телеграфирования ограничена половиной полосы частот передатчика. В.А.Котельников 1933 г., защищая диссертацию о пропускной способности линий электросвязи, доказал, что частота дискретизации не должна быть меньше удвоенной максимальной частоты в сигнале и дал метод восстановления дискретизованного сигнала. К.Е.Шеннон обобщил теорему Найквиста-Котельникова на передачу сигналов через канал с шумом и дал определение количества информации в 1949 г.
Таким образом, к середине прошлого века были получены все основные научные сведения об обработке квантованных сигналов. Сама же обработка велась aналитически или вручную, в лучшем случае – с помощью релейных схем, арифмометра или таблиц.
Первое устройство для ЦОС
Под ЦОС понимается обработка временных рядов данных (сигналов) с помощью цифровых вычислительных средств. Первые электронные компьютеры использовались для ЦОС только в той степени, в какой задача расчета, моделирования траектории снаряда, ракеты похожа на задачу обработки сигналов. Для ЦОС требовался дешевый и массовый вычислитель, способный конкурировать с аналоговыми средствами обработки.
Среди алгоритмов ЦОС знаковая корреляция – это один из простейших, но достаточно эффективный алгоритм. На входе такого коррелятора стоят компараторы – АЦП на один бит. В состав коррелятора входят схема Исключающее ИЛИ, служащая перемножителем входных сигналов и реверсивный счетчик – аккумулятор произведений. Один из сигналов задерживается в линии задержки на заданное число тактов. Такое устройство можно собрать из десятка логических элементов и нескольких десятков триггеров. В отличие от тогдашних компьютеров, занимающих целые залы, коррелятор мог поместиться на столе. Кроме того, такой коррелятор – это единственное устройство, способное в те годы работать в реальном масштабе времени с частотами до сотен килогерц.
Первый цифровой коррелятор был изготовлен и испытан Г.Синглтоном в 1949 г. Публикация о нем вышла в 1950 г. [3]. Это было первое устройство для ЦОС. Такие
устройства в последующее десятилетие активно использовались в большом количестве. Поэтому начало ЦОС следует отнести к этому событию.
Десятилетие корреляторов
Исходя из теоремы Винера-Хинчина, спектр сигнала находят как преобразование Фурье его автокорреляционной функции. Если на вход некоторого объекта подать
шумовой сигнал с широким спектром, то на его выходе будет окрашенный шум, спектр которого совпадает с амплитудо-частотной характеристикой объекта. Поэтому первыезнаковые корреляторы часто использовали в исследовательских целях для измерения корреляционных функций сигналов с различных объектов из которых затем высчитывали спектральные характеристики этих сигналов и объектов.
Корреляционную функцию Сxy(τ) можно трактовать как меру похожести двух сигналов x и y. Если сравниваемые синалы при определенной задержке τ одного из них максимально похожи, то и корреляция в этой точке (для такой задержки) достигает максимума. Один из сигналов может представлять собой смесь исходного сигнала c шумом x = s + n, а другой сигнал – копию или эталон исходного сигнала y = s. Тогда результирующая корреляционная функция после достаточного числа накоплений N будет иметь пик на своем месте, даже если уровень шума значительно выше уровня сигнала, т.е. |s| < |n|. При этом, если форма сигнала подобрана эффективно, отношение сигнал-шум возрастает приблизительно в √N раз. Поэтому знаковый коррелятор – это устройство, способное из шума, которым является последовательность нулей и единиц знака сигнала, добывать многоразрядную верную информацию.
После запуска первого спутника стала задача обеспечения дальней космической связи с высокоорбитальными и межпланетными искусственными объектами. Также
необходимо было определять точное расстояние до них. Так совпало, что эта проблема возникла в то время, когда электронный знаковый коррелятор был изобретен и использовался для научно-исследовательских целей. Этот коррелятор был выбран как оптимальное решение для приемника космической связи.
В качестве эталонного сигнала был принят псевдослучайный сигнал. Такой сигнал несложно генерировать с помощью m-разрядного сдвигового регистра с отводами, в обратной связи которого стоит схема Исключающее ИЛИ. Период псевдослучайной последовательности битов с выхода сдвигового регистра может достигать 2 m –1 отсчетов. При этом пик корреляции возникает строго в точке совпадения задержки. Таким образом, измеряя корреляционную задержку, несложно затем пересчитать ее в дальность до объекта, от которого приходит сигнал.
В [4] доцент Э. Витерби из Калифорнийского университета описал теорию и примеры систем космической связи на базе корреляторов, которые были разработаны с его участием в конце пятидесятых – начале шестидесятых годов. Такой приемник при m=11 и длине корреляции N=2047 обеспечивал улучшение отношения сигнал-шум в 45 раз. При дальней космической связи длина корреляции может достигать миллионов, благодаря чему сигнал усиливается в тысячи раз.
Долгие годы корреляционные приемники были незаменимым атрибутом военной и авиакосмической связной техники. Если эталонный сигнал – достаточно длинный и
случайный, то секретность связи обеспечивается естественным образом.
В наше время корреляционный прием стал естественным. Это такие области техники, как аппаратура спутниковой навигации GPS, системы связи с кодовым разделением каналов CDMA и многие другие.
Большие и маленькие ЭВМ
ЦОС характеризуется огромным количеством вычислений над большими объемами данных. Как известно, компьютеры первых поколений были слишком дороги, чтобы реализовать ЦОС в больших масштабах. К тому же, их быстродействия хватало лишь на обработку в реальном времени частот, ограниченных диапазоном единиц килогерц. Поэтому решение задач ЦОС в шестидесятых годах поводились на больших ЭВМ, в основном, в исследовательских целях и в замедленном масштабе времени. Как результат – появление большинства методов ЦОС, которые используются теперь. Это методы рекурсивной и нерекурсивной, адаптивной фильтрации, методы спектрального оценивания, закладка основ компрессии речи, звука, изображения.
Заметным событием стала публикация в 1965г. алгоритма быстрого пребразования Фурье (БПФ), называемого алгоритмом Кули-Тьюки. Этот алгоритм стал эффектным примером того, как сложное дискретное преобразование Фурье можно ускорить в сотни раз. В 1967 г. профессор Э. Витерби опубликовал свой алгоритм помехоустойчивого декодирования. Этот алгоритм использует ту особенность, что среди всевозможных цепочек передаваемых символов (по сути – разверток марковских цепей) можно вычислить наиболее вероятную цепочку, отбрасывая маловероятные. Сейчас без алгоритма Витерби не обходится ни один модем.
Успехи в разработке алгоритмов ЦОС не прошли незамеченными у геофизиков. Геологоразведка месторождений углеводородов заключается в возбуждении звуковых волн в породе, записи сигналов отраженных волн (трасс) многоканальным магнитофоном и последующей обработке трасс в комнатных условиях вычислительных центров (ВЦ). Сработала обратная связь: часть прибыли от открытых с помощью ЦОС месторождений идет на дорогостоящее оборудование ВЦ, с помощью которого открывают новые месторождения [5].
Можно предположить, что подавляющий объем задач ЦОС в шестидесятые годы решался на ВЦ геологических партий. Самые быстродействующие компьютеры трудились по 24 часа в сутки, чтобы открыть большинство крупных нефтегазовых месторождений в мире, которые эксплуатируются до сих пор. Наиболее массовой работой была свертка (convolution) сигнала трассы с импульсной реакцией восстанавливающего фильтра. Для ее ускорения использовались приставки к компьютерам, так называемые, конвольверы. Конвольвер – это один из первых спецпроцессоров для цифровой фильтрации, который был способен выполнять фильтрацию сигналов с частотами до десятков килогерц. Следует отметить, что первый отечественный суперкомпьютер ПС2000 специально разрабатывался и выпускался в Северодонецке для решения задач геологоразведки.
К концу шестидесятых годов самыми массовыми компьютерами были мини-ЭВМ. Наиболее распространенная архитектура мини-ЭВМ PDP-11 дала возможность сделать компьютер сравнительно малогабаритным и недорогим. Снабженные соответствующими устройствами ввода-вывода, мини-ЭВМ служили центральным звеном многих систем авторегулирования в производственных процессах. Здесь, можно сказать, ЦОС выполнялась в реальном времени с частотами дискретизации до десятков герц. На базе мини-ЭВМ были реализованы первые вычислительные анализаторы спектра, использующие алгоритм БПФ.
Специализированные компьютеры
Проект первого микропроцессора, разработанного в начале семидесятых годов, был задуман как проект универсального элемента для построения всевозможных кнопочных электронных калькуляторов. Вскоре микропроцессорная идея получила широкое распространение, результаты которого мы видим сегодня. Но в то время микропроцессоры, такие как Intel i4004, i8008, i8080, не могли быть использованы для широкого внедрения ЦОС. В те годы заказчики и потребители средств обработки сигналов уже вошли во вкус ЦОС и требовали вычислительные системы, работающие в реальном масштабе времени. А однокристальные микропроцессоры могли обеспечить обработку в реальном времени по простейшим алгоритмам с частотами всего лишь в десятки герц. Поэтому средства ЦОС обычно не реализовались на однокристальных микропроцессорах. Они представляли собой специализированные компьютеры, выполненные на базе микросхем малой и средней степени интеграции.
В середине семидесятых годов получили широкое распространение разрядно-модульные микропроцессоры серий i3000, AMD2900, аналоги которых в нашей стране имели наименования К589 и К1804. Они имели ту особенность, что в небольшой лаборатории или КБ можно было самостоятельно разработать микропроцессор, ориентированный на выполнение заданных алгоритмов ЦОС и поэтому имеющий требуемую производительность. В это время такие микропроцессоры стали внедряться впереносных цифровых измерительных приборах, таких как вычислительный анализатор спектра.
До начала восьмидесятых годов основной арифметической операцией, реализованной аппаратно в большинстве компьютеров, была операция типа сложения. Поэтому первые системы ЦОС характеризировались применением алгоритмов, в которых основное внимание уделялось минимизации числа операций умножения за счет увеличения числа сложений, логических операций. Так, часто применялись алгоритмы знаковой корреляции, преобразования Уолша, Адамара. В то время были найдены такие алгоритмы, как теоретико-числовые преобразования, преобразование Хартли, алгоритм Винограда, медианная фильтрация, многие из которых характеризуются рекордно малым числом приведенных сложений и большим отношением числа сложений к числу умножений [6].
Большие ЭВМ все так же продолжали использоваться в исследовательских целях. В те годы были заложены основы алгоритмов современной обработки и сжатия изображений. Много интелектуального труда уделялось решению обратной задачи распространения волн, например, для геофизики. Выдающимся достижением стало
внедрение этих методов в компьютерной томографии. Эти алгоритмы требуют большого объема точных вычислений с плавающей запятой, они часто реализовались на супер-ЭВМ и поэтому они не могли иметь широкого внедрения.
Сигнальные микропроцессоры
Цифровые фильтры имеют ряд неоспоримых преимуществ перед аналоговыми фильтрами: высокое качество амплитудо-частотной характеристики, отсутствие ручной трудоемкой настройки, высокая стабильность характеристик. Но у них была низкая частота обрабатываемых сигналов и самое главное – огромные габариты и стоимость.
В конце семидесятых годов рост степени интеграции достиг того предела, когда тот вычислитель, который имел качества мини-ЭВМ, стало возможным реализовать в одной дешевой микросхеме. Микросхема микропроцессора Intel i2920, появившаяся в 1979 г., была весомым аргументом в пользу цифровой фильтрации. В ее состав входили входной АЦП, выходной ЦАП, АЛУ на базе сумматора и сдвигателя, маленькое ОЗУ данных и примитивное программное устройство управления с программируемым ПЗУ программ. Главный эффект заключался в том, что одной этой микросхемой можно было сделать непосредственную замену аналогового фильтра из десятка усилителей и больших нестабильных конденсаторов.
С начала восьмидесятых годов стали массово внедряться СБИС, в структуру которых входили аппаратные блоки умножения. С тех пор остановились попытки экономить операции умножения в алгоритмах. Операция умножения на коэффициент с прибавлением результата к аккумулятору s = ax + y стала основной операцией в микропроцессорах, адаптированных к задачам ЦОС. Такие микропроцессоры сформировали отдельное множество, так называемых, DSP– или сигнальных микропроцессоров. Появившийся в 1992 г. микропроцессор TMS32010 считается сигнальным микропроцессором первого поколения.
Для получения максимальной пропускной способности в сигнальных микропроцессорах организуется конвейерная обработка данных в блоке умножителя с аккумулятором. Для этого микропроцессоры оснащают многопортовыми блоками памяти и генераторами адресных последовательностей для чтения-записи операндов. Таким образом, основной функцией, которую реализуют сигнальные микропроцессоры, является фунция свертки векторов данных, равная сумме парных произведений элементов векторов. На этой функции основаны вычисления цифровых фильтров, корреляции. Также через сумму произведений вычисляется базовая операция алгоритма БПФ. Для его поддержки в генератор адресных последоватедбностей встроена функция двоичной инверсии адреса. Все это привело к тому, что при фильтрации и реализации алгоритма БПФ в сигнальных микропроцессорах простои арифметичного устройства незначительны (около 60-90%).
Благодаря сигнальным микропроцессорам, получили широкое распространение телефонные модемы. В них микропроцессор выполняет алгоритмы адаптивной подстройки к параметрам канала связи, эхоподавления, демодуляции с алгоритмом Витерби, без которых невозможно получить частоты передачи выше 600 бит в секунду.
Сигнал можно дискретизовать с очень высокой частотой таким образом, чтобы максимальная частота сигнала была в сотни раз ниже частоты дискретизации, а энергия шума дискретизации собиралась на высоких частотах. Тогда разрядность квантования может быть равна единице, а отсчеты сигнала с точностью до 16 или даже 24 двоичных разрядов можно получать после цифровой фильтрации шума квантования. На этом принципе построены сигма-дельта АЦП и ЦАП. Они стали основой систем записи и проигрывания аудиоданных и остаются основой ввода-вывода аудиоинформации до сих пор. Без них не было бы такого бурного распространения компакт-дисков, появившихся в 1982 г.
В восьмидесятые годы оцифрованные сигналы сохранялись и передавались по каналам связи преимущественно с импульсно-кодовой модуляцией. Так, дискретизованный 12 разрядами с частотой 8 кГц звук телефонного разговора требовал для своей передачи цифровой канал с пропускной способностью 96 кбит/сек, а стереофонограмма с временем звучания 10 мин., дискретизованная шестнадцатью разрядами с частотой 48 кГц занимала объем памяти 100 Мбайт. Еще большие требования предъявлялись со стороны цифрового телевидения и цифровой фотографии. Такие высокие требования к каналам связи и памяти данных существенно тормозили широкое внедрение цифровых технологий в военных и гражданских отраслях.
В то время применялись некоторые алгоритмы компрессии, как наприкмер, α-, μ–компрессия, которая за счет логарифмирования сигнала способна сжать его в 1,5 раза. Сушествовало много наработок по компрессии речевого сигнала. Но, во-первых, эти алгоритмы не давали кардинального сжатия сигнала без существенной потери качества, во-вторых, они не были стандартными и не обеспечивали обмен информации среди широкого круга ее потребителей. Поэтому при поддержке министерства обороны США и НАТО в мире широко развернулись работы по поиску алгоритмов компрессии звука и изображений с целью выбора среди них наилучших для дальнейшей их стандартизации. В результате этого в начале девяностых годов почти одновременно появились стандарты компрессии сигнала в телефонных каналах, например, G723, сжатия фотографических изображений JPEG (JPEG – Joint Photographic Expert Group). Стандарт MPEG-1 относится к первому поколению стандартов компрессии, который разрабатывался комиссией экспертов по компрессии двигающихся изображений (MPEG- Moving Picture Expert Group) и предназначенный для передачи телевизионного сигнала обычного качества, включая стереозвук по каналам связи.
Однако производительности первого и второго поколений сигнальных микропроцессоров было недостаточно для реализации таких алгоритмов сжатия. Так, для реализации телефонного вокодера с линейным предсказанием требуется производительность порядка 20 mips. Поэтому новые стандарты компрессии ждали своего времени для реализации – середины девяностых годов.
Начало эпохи мультимедиа
Новые алгоритмы и стандарты сжатия дали толчок развитию всех современных мультимедийных технологий и средствам беспроводной связи. Стало возможным
записывать на дешевый носитель многочасовые кинофильмы, десятки часов стереозвука, сотни высококачественных цветных фотографий. Благодаря внедрению цифровых технологий уплотнения речевого сигнала, количество пользователей сотовой связи исчисляется сотнями миллионов.
Внедрение мультимедийных технологий в персональных компьютерах (PC) существенно повлияло на их архитектуру. Каждый микропроцессор стал оснащаться ускорителем мультимедийных приложений, как например, ММХ-ускоритель в платформеIntel Pentium. Такой ускоритель имеет структуру SIMD – процессора, состоящего из 8, 4 или 2 процессорных элементов, работающих параллельно. Каждый микропроцессор по производительности стал обходить самые быстрые сигнальные микропроцессоры. Правда, это достигается, в основном, за счет на порядок большей тактовой частоты.
Вышеупомянутые стандарты компрессии все время претерпевают модернизацию и расширение. В начале нынешнего столетия появился стандарт JPEG-2000, который
обеспечил эффективную упаковку изображений для цифровых фотокамер и их распространения средствами мультимедиа и интернета. В нем задействовано вейвлет-преобразование, которое было тщательно исследовано десятилетием ранее. На смену стандарту MPEG-1 пришли стандарты MPEG-2 и MPEG-4. Уплотнение голосового сигнала начало широко распространяться в технологии телефонной связи через интернет.
В большинстве случаев, кроме ПК, эти стандарты реализуются в сигнальных микропроцессорах третьего и четвертого поколений. Как и в восьмидесятых годах, эти микропроцессоры исполняются с архитектурой с разделенными ОЗУ команд и ОЗУ данных, отдельным АЛУ данных, которое выполняет в конвейерном режиме операцию ах+у. Изменения отразились лишь в повышении тактовой частоты (в 10 – 100 раз), объема внутренней памяти (в 100 раз), расширения номенклатуры периферийных устройств на кристалле ( в том числе добавление АЦП, ЦАП), уменьшения цены (в 10 раз). Сигнальные микропроцесоры серий TMS3205x фирмы TI, ADSP21xx фирми AD, DSP56xx фирмы Motorola получили широкое распространение благодаря тому, что они не меняют свою архитектуру в течение десятилетия. Поэтому они играют роль микропроцессорных платформ.
Также появились сигнальные микропроцессоры с несколькими однаковыми процессорными элементами. Существует тенденция распространения сигнальных микропроцессоров с архитектурой сверхдлинной команды (VLIW – very large instruction word). Такие микропроцессоры эквивалентны многопроцессорным системам, у которых суммарная длина команд минимизирована за счет того, что „сшиты” команды с однаковыми адресами, а также обобщены некоторые из их полей.
Высококачественное звуковоспроизведение заставило внедрять 24-разрядные, а затем – и 32-разрядные сигнальные микропроцессоры вместо 16- разрядных. Для этой цели удачно подошли RISC- микропроцессоры, для которых естественна такая разрядность. Наиболее распространенной платформой для этой цели стала платформа ARM. Не мене распростраенной платформой является IBM PowerPC.
Некоторые этапы алгоритмов MPEG требуют такого количества вычислений, какую сигнальные микропроцессоры не способны выполнить в реальном времени. Это,
например, поиск похожих фрагментов изображения в соседних кадрах, дискретное косинусное преобразование (ДКП). Поэтому эти фрагменты алгоритмов стараются
выполнить на специализированных вычислителях, которые все чаще появляются в составе современных сигнальных микропроцессоров.
Стандарт MPEG состоит из нескольких уровней (layers), задающих различные алгортмы кодирования для разных потоков информации с заданной степенью и/или качеством компрессии. Идеология стандартизации уровней имеет одинаковые черты: нет требований к аппаратуре реализации стандарта, алгоритм декодера задан наиболее точно, особенно в тех местах, которые задают распаковку входного битового потока, а алгоритм кодера задан в виде рекомендаций.
Для получения представления о сложности алгоритмов современной ЦОС рассмотрим стандарт одного из уровней, который сейчас у всех на слуху в прямом и переносном смысле. Алгоритм упаковки аудиоданных с учетом их частотного состава в зависимости от психофизических свойств слушателя и с использованием кодирования Хафмена, был стандартизирован в 1991 г. Этот стандарт получил название MPEG Layer-3 или сокращенно – МР3. Изначально этот стандарт был предназначен для кодирования звукового уровня в упакованных кинофайлах.
Хотя существует ряд патентов, защищающих этот алгоритм, МР3 определен как открытый стандарт и его спецификация доступна для каждого. Также широко доступны исходные програмыи кодирования-декодирования по этому стандарту, которые разъясняют все особенности алгоритма и служат для сравнения и испытаний моделей МР3-декодеров. Благодаря общепринятому формату МР3-файлов, не возникает проблем со стыковкой соответствующего оборудования и матобеспечения, разработанного в разных местах. Широкому распространению стандарта МР3 благоприятствовали также распространение аудиокарт в РС, то, что РС стали достаточно мощными, чтобы выполнять декодирование и даже кодирование в реальном времени, повышение пропускной способности каналов интернета, возможность записи и чтения файлов на компакт-дисках. Поэтому этот стандарт получил широкое распространение также при передаче высококачественной аудиоинформации по телефонным линиям, при пересылке музыкальных файлов через интернет, в цифровых аудиоплейерах. Теперь стандарт МР3 используется также в системах цифрового радио, как звуковой канал в цифровом телевидении, в портативной звукозаписывающей апаратуре, при сохранении и пересылке аудиофайлов в компьютерах и сетях. Стандарт MPEG-2 Advanced Audio Coding (AAC) был разработан на основе МР3 как его последователь и внедряется в новых поколениях звуковой аппаратуры.
В стандарте алгоритм МР3-декодера не задан с точностью до обработки каждого бита. В нем даны только формулы обработки данных для большинства этапов алгоритма, а также методика определения ошибки декодирования относительно результатов работы эталонного декодера. Такая стандартизация декодера дает возможность выбирать его реализацию по усмотрению разработчика. Так, его можно реализовать в арифметике как с плавающей, так и с фиксировнной запятой, как аппаратно, так и программно с произвольной разрядностью, обеспечивающей удовлетворительное качество воспроизведения. Например, считается приемлемой 20-разрядная арифметика с фиксированной запятой.
Алгоритм кодирования имеет те же этапы, что и алгоритм декодирования, кроме того, что параметры модели кодера адаптируются в сответствии с моделью восприятия декодированного звука человеком. Далее рассмотрим алгоритм декодирования. Он включает в себя последовательные этапы поиска и декодирования заголовка фрагмента звуковых данных и настройку синхронизации чтения входного битового потока, распаковки масштабных коэффициентов, декодирования по алгоритму Хафмена, обратного квантования, обратного ДКП, полифазной фильтрации результирующего сигнала.
МР3-файл считывается в декодер как непрерывный поток данных, организованный как цепочка из фрагментов звуковых данных, каждый из которых должен воспроизводиться в заданных промежутках времени. За заголовком в потоке данных следуют закодированые масштабные коэфициенты, кодирующие средний коэффициент усиления частотных составляющих звука. При поиске заголовка и распаковке масштабных коэффициентов многократно выполняются логические операции и проверяется правильность данных по алгоритму битовой свертки. Далее из потока выделяются закодированные нормированные частотные составляющие сигнала. Они декодируются по алгоритму Хафмена и их квантование восстанавливается. Декодирование Хафмена использует несколько кодирующих деревьев и сводится к поиску на деревьях листа, который побитно совпадает с фрагментом битового потока. Причем количество битов в этом фрагменте обратно пропорционально средней вероятности его встречи в потоке. Найденному листу отвечает код величины энергии данной частотной составляющей. Этот код с помощью соответствующего масштабирования преобразуется в целое число, которое ставится коэффициентом в спектральном представлении сигнала. При обратном квантовании величина спектрального коэффициента возводится в степень 4/3.
Как только восстановлены 576 спектральных линий з учетом масштабных коэффициентов и того, что большинство из них – нулевые, они обрабатываются по
алгоритму обратного ДКП. После него получается выходной сигнал в 32 частотных полосах одинаковой ширины. Результирующий поток 1024 временных отсчетов сигнала реконструируется, благодаря фильтрации и сложению результатов обратного ДКП банком полифазных полосовых фильтров. Таким образом, алгоритм декодирования имеет итерационный характер и включает интенсивное использование как логических операций, так и операций, характерных для ЦОС. Для его реализации в реальном времени необходима производительность не менее 20 mips.
Цифровая связь без проводов
Начиная с первых лет нового тысячелетия, бурно развиваются такие отрасли беспроводной связи, как цифровое радио (software defined radio), беспроводные локальные сети (WLAN), сотовые сети СDMA (Code Division Multiple Access). Эти отрасли основаны на алгоритмах формирования и дешифрации сигналов с широким спектром, которые ранее были невозможны из-за необходимости выполнения БПФ, цифровой фильтрации для сигналов с частотами дискретизации в десятки мегагерц с широким динамическим диапазоном в дешевых устройствах с малым энергопотреблением. Этому также содействовало появление скоростных многоразрядных АЦП.
Внедрение новых версий стандартов, как например, стандарта MPEG-4, связано с существенным увеличением необходимой производительности вычислительных средств. Современные сигнальные микропроцессоры не способны удовлетворить такой рост производительности без увеличения их числа в системе. С другой стороны, становится насущной потребность минимизировать энергопотребление при выполнении алгоритмов. Это исключительно важно для портативных устройств и не менее актуально для стационарных устройств, общее число которых достигает сотен миллионов. Далее будут рассмотрены особенности упомянутых стандартов и алгоритмов ЦОС.
В течение последнего десятилетия стандарты передачи цифровых сигналов стали заменять стандарты передачи аналоговых сигналов. Так, например, сейчас во многих регионах спутниковая телевизионная связь выполнена кодированной в стандарте MPEG-2 с квадратурно-импульсной модуляцией (QPSK), что в несколько раз увеличило число каналов, передаваемых через спутник. Также распространяется спутниковое радио (SDARDS) на частоте 2,3 ГГц, основаное на многополосной модуляции (Orthogonal Frequency Division Multiplexing – OFDM).
Еще быстрее развивалась система мобильной связи. Число ее пользователей достигло 18% населения Земли. Сейчас внедряется третье поколение (3G) стандарта этой связи. При этом, кроме стандарта Universal Mobile Telephone System (UMTS), распространяется широкополосное кодирование Coded Division Multiple Access (CDMA), в существующих каналах уплотняются потоки, благодаря стандарту General Packet Radio System (GPRS). В условиях распространения мобильной связи не мог не появиться мобильный интернет. Беспроводные локальные сети (Wireles Local Area Network – WLAN) – сейчас это основной сектор мобильного интернета. В этой отрасли используется стандарт IЕЕЕ 802.11, а именно, 802.11b в диапазоне 2,4 ГГц с модуляцией QPSK с управлением дополняющими кодами (Complementare Code Keying – CCK), 801.11а в диапазоне 5,3-5,8 ГГц с улучшенной модуляцией OFDM. Использование последней модуляции дает возможность увеличить пропускную способность каналов с 11 Мбит/с до 54 Мбит/с. Кроме того, распространяются локальные мобильные сети с меньшей пропускной способностью, так называемые, персональные сети (Wireless Personal Area Network – WPAN), которые заменяют собою короткие соединительные кабели, подходящие к РС. Так, стандарт Bluetooth при работе в диапазоне 2,4 ГГц обеспечивает связь со скоростью 750 кбит/с на расстояние до 10 м. Дальнейшим совершенствованием в этой отрасли может стать стандарт IЕЕЕ 802.15.3, которыйобеспечит передачу в диапазоне между 3 и 10 ГГц потоков с плотностью до 200 Мбит и более [7].
Внедряется идея передавать модулированные сигналы OFDM не через эфир, а через провода питания. Эта идея реализуется в технологии Powerline, которая позволяет соединить компьютеры и другие бытовые приборы в локальную сеть, подключившись к розетке 220 вольт.
Новые стандарты цифрового приема радиосигналов нуждаются в особенных алгоритмах цифровой обработки. Так, например, модуляция OFDM предусматривает несколько десятков несущих частот, передаваемых одновременно. По каждой несущей частоте передается свой параллельный поток бит с медленной частотой своего изменения. Благодаря этому, достигается значительно меньшая чувствительность к многолучевому распространению сигнала, используются более простые алгоритмы выравнивания АЧХ канала, упрощается синхронизация. Мощность сигнала в каждом канале может устанавливаться адаптивно. Некоторые из каналов используются для контроля. Эффективность OFDM основана на том, что при передаче сигналов на нескольких частотах, сигналы на них представляют собой ортогональные временные функции. Поэтому модулированные сигналы могут иметь перекрываемые АЧХ. Благодаря этому частотное расстояние между каналами существенно меньше, чем в случае обычных каналов связи с частотным разделением и общая пропускная способность канала увеличивается.
Всегда подразумевалось использование беспроводных каналов связи для передачи телевизионного изображения. MPEG-1 предназначен для передачи телевизионного
сигнала со скоростью около 1,5 Мбит/с. Для использования стандарта MPEG-2 необходима пропускная способность каналов до 10 Мбит/с., так как он используется как стандарт кодирования цифрового телевидения и телевидения высокой четкости (HDTV). Последний стандарт – MPEG-4 – имеет основную цель – обеспечить передачу видеосигналов с очень низкой скоростью – до 64 кбит/с.
Так получается, что чем больше компрессия сигнала – тем больше вычислительных затрат нужно приложить, чтобы ее выполнить в реальном времени. Уплотнение изображения основано на уменьшении избыточной информации в видеоданных. В видеосигнале есть пространственная и временная компоненты избыточности информации. Пространственная избыточность минимизируется следующим путем. Кадр изображения делят на макроблоки. В большинстве случаев каждый макроблок состоит из матрицы пикселов яркости размером 16х16 и двух матриц цветности размером 8х8. Основой компрессии является двумерное ДКП и обратное двумерное ДКП, выполняемые над блоками размером 8х8. Благодаря ДКП, информация, которая была распределена в матрицах изображения случайным образом, группируется в верхних левых углах матрицы их косинусного спектра.
Коэффициенты ДКП квантуются с учетом их значимости, что приводит к еще большей концентрации информации в углу спектральной матрицы и к появлению
большого числа нулевых результатов. Непосредственно компрессия достигается благодаря кодированию коэффициентов ДКП, которое увеличивает энтропию и которое выполняется в два этапа. На первом этапе коэффициенты кодируются парами: величина коэффициента – количество нулевых коэффициентов до следующего ненулевого коэффициента (run-length coding). На втором этапе каждая кодовая пара заменяется кодовым словом, длина которого обратно пропорциональна вероятности появления этой пары (variable-length coding).
Временная избыточность информации уменьшается, благодаря компенсации сдвига фрагментов изображения, которые одинаковы в соседних кадрах. Этот сдвиг выражается через векторы сдвига. При этом текущий кадр восстанавливается из предыдущего путем перемещения его макроблоков на расстояние, заданное векторами сдвига. Макроблоки, для которых не найдено похожих пар, кодируются как при пространственномкодировании. Процесс оценки межкадрового сдвига состоит в вычислении векторов сдвига для каждого макроблока. Этот процесс включает поиск пар наиболее похожих макроблоков в кодируемом и предыдущем кадрах. Иногда – в кодируемом и следующем кадрах. При этом чаще всего в качестве критерия похожести используется сумма абсолютных величин разниц между пикселами сравниваемых макроблоков. Координаты вектора сдвига находятся с точностью до полпиксела и даже до четверти пиксела. В результате, процедура поиска векторов сдвига – это наиболее сложная процедура по числу операций в алгоритме MPEG (см. табл. 1).
Кроме кодирования с учетом пространственной и временной избыточности информации, в стандарте MPEG-4 также используется кодирование, основанное на содержании образов (content-based coding). Этим, в основном, данный стандарт и отличается от MPEG-1 и MPEG-2. При этом используется концепция представления
изображения как совокупности плоскостей, точнее – фигур видеообъекта (video object plane – VOP). VOP – это часть изображения, которая имеет контур некоторой формы. Совокупность фигур видеообъекта, представленных во времени, формирует видеообъект. Также важное значение имеет понятие спрайта (sprite), представляющего собой большое панорамное изображение, которое чаще всего используется как задний план для нескольких видеообъектов. Таким образом, целый кадр изображения восстанавливается как совокупность фигур видеобъектов, которые установлены в заданных координатах общего плана, т.е. спрайта и клипированы границами кадра.
Каждый из VOP задается с помощью своей формы (shape) и текстуры (texture), которые кодируются особенным образом. Информация о форме кодируется в двоичном формате, т.е. как черная фигура с некоторым очертанием. Такая фигура называется бинарной альфа-фигурой (binary alpha plane). Эта фигура разбивается на бинарные альфа-блоки размером 16х16, каждый из которых отвечает макроблоку. Бинарная альфа-фигура представлена как прямоугольник, в который вложена черная фигура и его размеры кратны 16. Эта фигура может иметь также серый цвет. В этом случае степень ее закраски означает степень прозрачности фигуры.
Кодирование текстуры видеообъекта выполняется в зависимостьи от типа того или иного макроблока: макроблок может быть полностью покрыт альфа-фигурой, частично покрыт, т.е. через него проходит контур и макроблок находится вне альфа-фигуры, т.е. прозрачный. В последнем случае макроблоки вообще не кодируются. Полностью покрытые макроблоки кодируются так же, как в MPEG-1. А частично покрытые макроблоки могут кодироваться по различным алгоритмам, как например, алгоритм ДКП, адаптируемый к форме или алгоритм с низкочастотной экстраполяцией макроблоков фона (padding).
В отличие от ранних стандартов, в MPEG-4 объекты реальных сцен могут сочетаться с синтезированными объектами, например, мультипликационными марионетками. При этом вместо собственно видеообъекта кодируется его алгоритм компьютерной генерации и команды управления им во времени. Например, в видеотелефонной связи можно передавать модель головы собеседника и команды управления ее мимикой.
Алгоритмы MPEG-4 имеют большую сложность в сравнении с другими способами компрессии. В работах [8,9] для оценки сложности реализации алгоритмов они были промоделированы. Относительная сложность различных процедур алгорима при кодировании и декодировании телевизионного изображения приведены в таблице 1.
Таблица 1. Сложность процедур алгоритма MPEG-4, в процентах к общей сложности
| Кодер | Декодер | ||
| Определение векторов сдвига | 88 | Декодирование бинарных альфа-фигур | 38 |
| Кодирование бинарных альфа-фигур | 7 | Обратное ДКП | 16 |
| ДКП/обратное ДКП | 1 | Декодирование частично покрытых макроблоков | 13 |
| Компенсация сдвига | 1 | Компенсация сдвига | 11 |
| Остальные | 3 | Остальные | 22 |
Анализ таблицы 1 показывает, что при кодировании изображения наибольшие вычислительные затраты приходятся на определение векторов сдвига. А такие
относительно простые операции в кодере, как кодировани альфа-фигур, обратное ДКП и компенсация сдвига, становятся основными по сложности операциями в декодерах. Принимая во внимание, что при кодировании используется вдвое больше ДКП, чем обратных ДКП при декодировании, можно оценить, что процесс кодирования по крайней мере в 30 раз сложнее, чем процесс декодирования. С другой стороны, для реализации ДКП размером 8·8 необходимо 512 операций умножения и 640 операций сложения или 3072 и 3840 соответствующих операций на макроблок. Исходя из такой сложности, можно оценить, что для декодирования изображения размером 1024·768 необходимо приблизительно 133 млн. операций, т.е. 3300 млн. операций в секунду при потоке 25 кадров в секунду. Соответственно, для кодирования такого потока необходима вычислительная мощность 100 000 mips.
Выводы
Рассмотрев краткую историю цифровой обработки сигналов, можно сделать
следующий ряд полезных выводов.
В области ЦОС приблизительно каждое десятилетие происходил рывок в алгоритмах и технологии, дающий начало новому этапу развития. При этом в каждом новом этапе сложность алгоритмов и производительность аппаратуры возрастали на порядок. Судя по календарю, начало последнего этапа приходится на начало тысячелетия. Этот этап характеризуется развитием беспроводной цифровой связи и алгоритмов компрессии стандартов JPEG-2000, MPEG-4. Этим стандартам составляет конкуренцию набирающий силу стандарт DivX фирмы Microsoft.
История ЦОС двигается по спирали. Разработанные вначале знаковые корреляторы через десятки лет находят массовое внедрение в средствах GPS, CDMA, а алгоритм БПФ – в аппаратной реализации модемов OFDM. Поэтому следует ожидать аналогичных рывков в отношении других алгоритмов. Например, супердорогостоящие в 70-е годы методы вычислительной томографии сейчас могут быть внедрены в портативных приборах. Возможны самые неожиданные внедрения ЦОС. Так, например, в популярной теперь световой мыши используется принцип коррелятора.
Массовое внедрение новых алгоритмов вегда отставало от момента их разработки приблизительно на этап. Причиной этого было то, что алгоритмы разрабатывались с использованием вычислительной техники общего назначения, а аппаратура с соответствующей производительностью появлялась только на следующих этапах. Сейчас, когда во многих случаях для разработки и использования алгоритмов используются те же РС, новые алгоритмы можно внедрять немедленно.
Со сменой этапа меняется качество алгоритмов. Новые алгоритмы отличаются от старых не только увеличением количества вычислений, но и тем, что растет сложность управления, число логических операций, длина программ. Поэтому при проектировании средств ЦОС особенно возрастает роль программистов при неуменьшающеся роли проектировщиков аппарaтных средств.
Алгоритмы, обеспечивающие беспроводную связь и компрессию изображений, не могут быть реализованы на РС в реальном времени. Поэтому для их реализации нужно использовать современные заказные микросхемы, многопроцессорные сигнальные микропроцессоры, а также ПЛИС. В последних двух случаях программист, разработавший алгоритм, может его внедрить без промедления. С другой стороны, РС ждут, когда в них вмонтируют высокопроизводительное обрудование, которое можнолегко перепрограммировать на реализацию того или иного стандарта компрессии изображения или software defined radio.
Для получения высокой производительности придется переходить к программированию многопроцессорных параллельных систем. При числе процессоров более четырех их программирование превращается в очень трудоемкую рутину. Должна выработаться парадигма решения таких задач.
В стандарте MPEG-4 не регламентируются алгоритмы упаковки данных, а некоторые из его уровней, как например, уровень упаковки речи с ее распознаванием, уровень синтезируемых фигур, еще не имеют алгоритмов эффективной реализации. Это область для плодотворных поисков и внедрения новых более эффективных алгоритмов.
1. Марпл С.Л.-мл. Цифровой спектральный анализ и его приложения. – М.: Мир. – 1990. –584с.
2. Гнеденко Б.В. Очерк по истории теории вероятностей. Эдиториал УРСС. – 2001.- 88с.
3. Singleton,H.E. A digital electronic correlator // Proc.IRE ,138, -1950. –р.1422-1428.
4. Цифровые методы в космической связи /Под ред. С.Голомба. – М.:Связь. –1969. – 272с.
5. Обработка сейсмических сигналов. Тематический выпуск //ТИИЭР. –Т72.-No10. –1984.
6. Макклелан Дж.Д.,Рейдер Ч.М.Применение теории чисел в цифровой обработке сигналов.-М.: Радио и связь.-1983.-264с.
7. Hooijmans P.W., RF Front End Application and Technology Trends// DAC 2003, June 2-6, Anaheim, CA, USA, Proc. DAC. – 2003. –p.73-79.
8. Chang H.-C., Chen L.-G., Hsu M.-Y., Chang Y.-C. Performance analysis and architecture evaluation of MPEG-4 video codec system.// IEEE Int. Symp. Circuits and Systems, V.2, Geneva, -2000, p.449-452.
9. Vassiliadis S., Kuzmanov G., Wong S. MPEG-4 and the New Multimedia Architectural Challenges//