Прокис Дж. Цифровая связь (2000) (1151856), страница 25
Текст из файла (страница 25)
Алгоритм К средних может быть описан так, как дано ниже [Макхоул и др. (1985)). (3.4.40) !05 пространства на ячейки (С„, 1</г <Е~, когда СФПВ Р(Х) известна. Ясно, что указанные два условия обобщают задачу оптимального квантования скалярной величины оптимизации на случай квантования и-мерного вектора.
В общем, мы ожидаем, что кодовые векторы более тесно группируются в областях, где СФПВ р(Х) велика, и, наоборот, разрежены в областях, где р(Х) мала. В качестве верхней границы искажений векторного квантования мы можем использовать величину искажений оптимального скалярного квантователя, и эту границу. можно применить для каждой компоненты вектора, как было описано в предыдущем разделе, С другой стороны, наилучшие характеристики, которые могут быть достигнуты оптимальным векторным квантователем, определяются функцией скорость-искажение или, что эквивалентно, функцией искажение-скорость. Функция искажение-скорость, которая была введена в предыдущем разделе, может быть определена в контексте векторного квантования следующим образом. Предположим, мы формируем вектор Х размерности и из и последовательных отсчетов ~х„~. Вектор Х квантуется в форму Х = фХ), где Х— вектор, образованный рядом 1Х„„1< я < Е~ Как было описано выше, среднее искажение В, получаемое при представлении Х через Х, равно Е~Ы(Х,Х)), где И(Х, Х)-это искажение на одно измерение.
Например, Ы(Х,Х) = — „'> (х„-х„)". Л ~ Минимально достижимая средняя битовая скорость, с которой могут быть переданы векторы 1Х„„1 < и < Х~, равна Алгоритм К средних Шаг 1. Инициализируется начальный номер итерации 1=0, Выбирается ряд выходных векторов Х„(0), 1<х < Х. Ф Шаг2. Обучающие векторы (Х(т),1<и< М) классифицируются в группы (С„) посредством правила ближайшего соседа: Хн С,(1) если 13(Х,Х (1)) < 13(Х,Х,(1)) для всех 7с ~ 7'.
Шаг 3. Пересчитываются (для (1+1)-го шага) выходные векторы каждой группы путем вычисления центроида для обучающих векторов, которые попадают в каждую группу. Кроме того, рассчитывается результирующее искажение 13(1) на 1-й итерации. Шаг 4. Заканчивается тестирование, если В(1-1) — 13(1) относительно мало. В противном случае следует идти к шагу 2. Алгоритм К средних приводит к локальному минимуму (см. Андерберг, 1973; Линде и др., 1980).
Начиная этот алгоритм различными рядами начальных выходных векторов (Хе(0)) и каждый раз выполняя оптимизацию, описанную алгоритмом К средних, можно найти глобальный оптимум. Однако вычислительные затраты этой поисковой процедуры могут ограничить поиск немногими инициализациями. Если мы один раз выбрали выходные векторы ~Х„1<7г<Т.~, каждый сигнальный вектор Х(т) квантуется в выходной вектор, который является ближайшим к нему с точки зрения выбранной меры искажения. Если вычисление включает в себя оценку расстояния между Х(т) и каждым из Х возможных выходных векторов (Х„~, процедура образует полный иоисх. Если предположим, что каждое вычисление требует п умножений и сложений, то общее требуемое число вычислений для полного поиска равно Ж=лЕ (3.4.43) умножений и сложений на входной вектор.
Если мы выбрали Т. как степень 2, то 1о8, Т. определяет число бит, требуемых для представления каждого вектора. Теперь, если Я обозначает битовую скорость на отсчет 1на компоненту или на измерение Х(т)1, имеем пЯ = 1о8, 1 и, следовательно, вычислительные затраты Ю = п2ке (3.4.44) Заметим, что число вычислений растет экспоненциально с параметром размерности и и битовой скорости л на измерение. Вследствие этого экспоненциального роста вычислительных затрат' векторное квантование применяется в низкобитовых кодерах источника, таких как кодирование коэффициентов отражения или логарифмических отношений в линейном кодировании речи с предсказанием.
Вычислительные затраты, связанные с полным поиском, можно уменьшить при помощи изящного субоптимального алгоритма (см. Чанг и др., 1984; Гершо, 1982). Чтобы продемонстрировать пользу векторного квантования по сравнению со скалярным квантованием, мы представим следующий пример, взятый у Макхоула н др.
(1985). 106 Пример 3.4.1. Пусть Х! и Хз являются двумя случайными величинами с равномерной СФПВ: (3.4.45) где С вЂ” прямоугольная область, показанная на рис, 3.4.4. Заметим, что прямоугольник повернут на 45 относительно горизонтальной оси. На рис. 3.4.4 показаны ' также собственные плотности вероятности р(х!) и р(хз).' хз х а+Ь а ! 2'!2 а-Ь 2Г2 0 ' х!2~а ! в р(х,) а+Ь 2 ~2 а+Ь „ Ь -!-Ь 2!2 2'Г2 2'Г2 Рис.
3.4.4. Равномерная ФПВ в двух измерениях (Маахоуя и др.,! 985) Если мы квантуем х! и хз раздельно, используя одинаковые интервалы квантования длины л, то требуемое число уровней квантования хз =хз = (3.4.46) "«Г2Л Следовательно, для кодирования вектора Х=[х! хз) потребуется число бит к„=Я, +Аз =108, Е, +!ой,Х,„ + Ь)2 ы' (3.4.47) Таким образом, скалярное квантование каждой компоненты эквивалентно векторному квантованию с общим числом уровней (3.4.48) Видим, что это приближение эквивалентно покрытию большой площади, которая !07 Т; а+Ь ~ 2~Г2 — (Хн С), 1 р(х„х,) = р(Х) = аЬ О (для других Х), р(х„) ! ч2/а охватывает прямоугольник посредством квадратных ячеек, причем каждая ячейка представляет одну из /„ областей квантования. Поскольку р(Х)=0, за исключением Х я С, такое кодирование является расточительным и приводит к увеличению битовой скорости.
Если же мы покроем только область, где р(Х) ~ О, квадратиками, имеющими площадь д2, то общее число уровней, которые образуются, определяется площадью прямоугольника, деленной на л2, т.е. (3.4.49) Следовательно, разница в битовой скорости при скалярном и векторном методах квантования равна- + д)2 я„- г„'= 1082 (3.4.50) Для случая, когда а=4/2, разница в битовой скорости ߄— /1„'=1,б4 бит/вектор. Следовательно, векторное квантование на 0,82 бит/отсчет лучше, чем скалярное, при тех же искажениях. Интересно заметить, что линейное преобразование (поворот на 45 ) декоррелирует Х1 и Х2 и делает две случайные величины статистически независимыми.
Тогда скалярное квантование и векторное квантование достигают одинаковой эффективности. Хотя линейное преобразование может декоррелировать вектор случайных величин, оно не приводит к статистически независимым случайным величинам в общем случае.
Следовательно, векторное квантование будет всегда равняться или превосходить по характеристикам скалярный квантователь (см. задачу 3.40). Векторное квантование применяется при различных методах кодирования речи, включая сигнальные методы и методы базовых моделей, которые рассматриваются в разд. 3.5.
В методах, основанных на базовых моделях, таких как линейное кодирование с предсказанием, векторное квантование делает возможным кодирование речи на скоростях ниже 1000 бит/с (см. Бузо и др., 1980; Роукос и др., 1982; Пауль, 1983). Если использовать методы кодирования сигналов, возможно получить хорошее качество речи на скоростях передачи 16 000 бит/с, что эквивалентно скорости кодирования Я=2 бит/отсчет. За счет дополнительных вычислительных усложнений в будущем станет возможным использовать сигнальные кодеры, обеспечивающие хорошее качество речи при скорости кодирования Я=1 бит/отсчет. 3.5. ТЕХНИКА КОДИРОВАНИЯ АНАЛОГОВЫХ ИСТОЧНИКОВ За последние 40 лет было разработано много технических приемов для кодирования аналоговых источников.
Большинство из них использованы для кодирования речи и изображений. В этом разделе мы сжато опишем несколько из этих методов и используем кодирование речи как пример при оценивании их характеристик. Удобно разделить методы кодирования аналоговых источников на три вида. Один вид назван временное сигнальное кодирование.
При этом виде кодирования кодер источника проектируется так, чтобы представить в цифрах временные характеристики сигнала источника. Второй тип кодирования источника — спектральное сигнальное кодирование..В этом случае сигнал обычно подразделяется на различные частотные полоски и либо сигнал каждой полоски, либо его спектральные характеристики кодируются для передачи.
Третий тип кодирования источника базируется на математической модели источника, и он называется кодирование на базовой модели. 108 где хд представляет квантованное значение х„, а !7„ — ошибку квантования, которую мы трактуем как аддитивный 1пум. Предположим. что используется равномерное квантование, имеющее характеристику вход-выход, показанную на рис.
3.5.1, тогда шум квантования хорошо характеризуется статистически равномерной ФПВ 1 р(п)= —, --,'А<) —,'л, (3.5.2) Л где размер шага квантования Л = 2 ". выход д — Ф Рис. 3.5.1. Характеристика вход-выход для равномерного квантователя Средний квадрат ошибки квантования Ю(П') = —,', Л' = —,', х 2-1". (3.5.3) Средний квадрат ошибки в децибелах равен 10!8 ' 1~6 101я( — 'х 2 'и) = — бЯ вЂ” 10,8 дБ.
(3.5.4) Заметим, что шум квантования уменьшается на 6дБ на каждый используемый в ИКМ, ДИКМ (дифференциальная ИКМ) и АДИКМ (адаптивная ДИКМ) относятоя к технике кодирования источника. Они не являются методами цифровой модуляции. 109 3.5.1. Временное сигнальное кодирование Имеется несколько технологических приемов кодирования источника, которые используют временные характеристики сигнала. Наиболее широко использующийся метод описывается в этом разделе. Импульсно-кодовая модуляция (ИКМ). Пусть х(г) обозначает реализацию сигнала, 1 выдаваемого источнйком, и пусть х„обозначает отсчет, взятый со скоростью стробирования /;>211; где гг'- наивысшая частота в спектре х(г).
В ИКМ каждый отсчет сигнала квантуется в один из 2 уровней, где Я вЂ” число двоичных цифр, используемых для представления каждого отсчета. Следовательно, скорость источника равна Я 1;, бит/с. Процесс квантования можно представить математически как х„=хо+до, (3.5.1) квантователе бит. Например, 7-битовый квантователь вызывает мощность шума квантования в -52,8 дБ. Для многих сигналов источника, таких как речевые сигналы, характерно то, что маленькие уровни сигнала появляются более часто, чем большие.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
