Прокис Дж. - Цифровая связь (1266501), страница 25
Текст из файла (страница 25)
' Таким образом. эти условия оптимизации определяют разбиение и-мерного !04 Частный случай, когда р = 1, часто используется как альтернатива случаю р — -.2. Векторное квантование не ограничиваегся квантованием блока .сигнальных отсчетов источника сигнала. Его можно использовать для квантования ряда параметров, извлеченных из данных, Например, при линейном кодировании с предсказанием (ЛКП), описанном в разделе 3.5.3, параметры, извлеченные из сигнала, являются коэффициентами предсказания, которые являются коэффициентами для всеполюсной фильтровой модели источника, который генерирует наблюдаемые данные. Эти параметры можно рассматривать как блок и квантовать как блок символов, используя некоторую подходящую меру искажений. В случае кодирования речи подходящей мерой искажений, которую предложили Итакура и Свити (1986, 1975), является взвешенная среднеквадратическая ошибка, где взвешивающая матрица ЪУ выбрана как нормированная матрица автоковариации Ф наблюдаемых данных.
При кодировании речи альтернативным рядом параметров, которые могут быть квантованы как блок и переданы к приемнику, могут быть коэффициенты отражения (см. ниже) 1а„, 1<1<си~. Еще один ряд параметров, которые иногда используются для векторного квантования при линейном кодировании с предсказанием речи, содержит логарифмические отношения (гс), которые вырахсаются через коэффициенты отражения 1+а,. („=1о8 ', 1</с<и. (3.4.3б) 1- аь (3.4.40) 105 пространства на ячейки (С„1< х < Х,1, когда СФПВ р(Х) известна. Ясно, что указанные два условия обобщают задачу оптимального квантования скалярной величины оптимизации на случай квантования и-мерного вектора.
В общем„мы ожидаем, что кодовые векторы более тесно группируются в областях, где СФПВ р(Х) велика, и, наоборот, разрежены в областях, где р(Х) мала. В качестве верхней границы иска'кений векторного квантования мы можем использовать величину искажений оптимального скалярного квантователя, и эту границу можно применить для кахщой компоненты вектора, как было описано в предыдущем разделе. С другой стороны„наилучшие характеристики, которые могут быть достигнуты оптимальным векторным квантователем, определяются функцией скорость-искажение или, что эквивалентно, функцией искажение-скорость.
Функция искажение-скорость, которая была введена в предыдущем разделе, может быть определена в контексте векторного квантования следующим образом. Предположим, мы формируем вектор Х размерности и из и последовательных отсчетов 1х„1. Вектор Х квантуется в форму Х = фХ), где Х— вектор, образованный рядом 1Х„„1< и < А~ Как было описано выше, среднее искажение Е), получаемое при представлении Х через Х, равно Е~Ы(Х,Х)], где Ы(Х,Х) — это искажение на одно измерение.
Например, Л Ы(Х,Х) = — ,'> (х„— х,) . п„, Минимально достихгимая средняя битовая скорость, с которой могут быть переданы векторы 1Х„„1< и <А~, равна и = — бит(отсчет, Н(Х) (3.4.39) ф Л где Н(Х) — энтропия квантованного выходЭисточника, определяемая как / Н(Х) --= — ~ р(Х, ) 1о8з Р(Х, ) . А! Для данной средней скорости Я минимально достижимое искажение П„(Я) = пип Е(Н(Х, Х)), (3.4.41) где Р > Н(Х)/и и минимум в (3.4.41) берется по всем возможным отображениям Д(Х).
В пределе, когда размерность л стремится к бесконечности, получаем 0(Р) =1нпй,,(Е), (3.4.42) Г1-> где П(Я) — это функция искажение-скорость, которая бьша введена в предыдущем разделе. Из этого излозкения очевидно, что функция искажение-скорость может быть как угодно приближена к пределу путем увеличения размерности и векторов.
Изложенный выше подход приемлем в предположении, что СФПВ р(Х) вектора данных известна. Однако на практике СФПВ р(Х) данных может быть неизвестна. В этом случае, возможно адаптивно выбрать квантованпые выходные векгоры с использованием ряда обучающих векторов Х(и). Конкретнее, предположим, что мы имеем ряд из М векторов, причем М намного больше, чем Л (М»А). Итеративный групповой алгоритм, названный аягоритио.и К средних, где в нашем случае К=А, может быть применен к обучающим векторам. Этот алгоритм итеративно делит М обучающих векторов на Л групп так, что два необходимых условия оптимальности выполняются.
Алгоритм К средних может быль описан так, как дано ниже 1Макхоул и др. (1985)1. Алгоритм К средних Шаг 1. Инициализируется начальный номер итерации 1--0. Выбирается ряд выходных векторов Х, (О), 1 < х ь Х, . Шаг 2. Обучающие векторы 1Х(т), 1 < т < М) классифицируются в группы (С„) посредством правила ближайшего соседа: Х и С„(г) если 73(Х, Х (1)) < )3(Х, Х,(1)) для всех Й ~е 7'. Шаг 3. Пересчитываются (для (1+1)-го шага) выходные векторы каждой группы путем вычисления цснтроида Хд(1) = — ~~> Х(т), 1 < к < Х„ хм:, для обучающих векторов, которые попадают в каждую группу.
Кроме того, рассчитывается результирующее искажение 73® на 1-й итерации. Шаг 4. Заканчивается тестирование, если 13(1 — 1) — 13(г) относительно мало. В противном случае следует идти к шагу 2. Алгоритм К средних приводит к локальному минимуму (см. Андерберг, 1973; Линде и др., 1980). 11ачиная этот алгоритм разлнчнымн рядами начальных выходных векторов (Х„(0)) и каждый раз выполняя оптимизацию, описанную алгоритмом К средних, можно найти глобальный оптимум. Однако вычислительные затраты этой поисковой процедуры могут ограничить поиск немногими инициализациями.
Если мы один раз выбрали выходные векторы (Х„1<1г <ф каждый сигнальный вектор Х(т) квантуется в выходной вектор, который является ближайшим к нему с точки зрения выбранной меры искажения. Если вычисление включает в себя оценку расстояния между Х(т) и каждым из 7. возможных выходных векторов ~Х„~, процедура образует полный поиск. Если предположим, что каждое вычисление требует и умножений и сложений, то общее требуемое число вычислений для полного поиска равно г (3.4.43) затраты Ф = и2""'. (3.4.44) Заметим, что число вычислений растет экспоненциально с параметром размерности п и битовой скорости Я на измерение.
Вследствие этого экспоненциального роста вычислительных затрат векторное квантование применяется в низкобитовых кодерах источника, таких как кодирование коэффициентов отражения или логарифмических отношений в линейном кодировании речи с предсказанием. Вычислительные затраты, связанные с полным поиском, можно уменьшить при помощи изящного субоптимального алгоритма (см. Чанг и др., 1984; Гершо, 1982). Чтобы продемонстрировать пользу векторного квантования по сравнению со скалярным квантованием, мы представим следующий пример, взятый у Макхоула и др.
(1985). 6' лЛ умножений и сложений на входной вектор. ,'1::, Если мы выбрали А как степень 2, то 1о8, 1. определяет число бит, требуемых для представления каждого вектора. Теперь, если Я обозначает битовую скорость на отсчет [на компоненту или на измерение Х(и)], имеем иЯ = 1о8, Ь и, следовательно, вычислительные 10б Пример 3.4.1. Пусть Х1 и Хз являются двумя случайными величинами с равномерной СФПВ: (3.4.45) где С вЂ” прямоугольная область, показанная на рис.
3.4.4. Заметим, что прямоугольник повернут на 45 относительно горизонтальной оси. На рис. 3.4.4 показаны также собственные плотности вероятности)з(х1) и р(хз).' и+Ь 2~Г2 а+Ь О о Ь а+6 2)2 Ж 2Ж Рис. 3.4.4. Равномерная ФПВ в двух измерениях (Мвкхоул и др., 1985) Если мы квантуем х~ и х2 раздельно, используя одинаковые интервалы квантования длины Ь, то требуемое число уровней квантования Л =Хз —— а+Ь (3.4.46) ,Ггл Следовательно, для кодирования вектора Х=(х1 хз1 потребуется число бит А,. = Я, + Я, = 1ойз Х, + 1ояз Х,, (а+ Ь) 2Л '(3.4.47) Таким образом, скалярное квантование каждой компоненты эквивалентно векторному квантованию с общим числом уровней А,=Х„Х,= (3.4.48) Видим, что это приближение эквивалентно покрытию большой площади, которая 1 р(х„хз) = р(Х) = аЬ О (ХнС), (для других Х), охватьгвает прямоугольник посредством квадратных ячеек, причем каждая ячейка представляет одну из (.„областей квантования.
Поскольку р(Х)=0, за исключением Х ~ С, такое кодирование является расточительным и приводит к увеличению битовой скорости. Если же мы покроем только область, где р(Х) ~ О„квадратиками, имеющими площадь л-', то общее число уровней, которые образуются, определяется площадью прямоугольника, деленной на л2, т.е. (3.4.49) Следовательно, разница в битовой скорости при скалярном и векторном методах. квантования равна (3.4.50) Для случая, когда а=4Ь, разница в битовой скорости (г, — (г,'= 1,64 бит(вектор. Следовательно, векторное квантование на 0,82 бит(отсчет лучше, чем скалярное, при тех же искажеггиях.
Интересно заметить, что линейное преобразование (поворот на 45 ) декоррелирует Х~ и Хз и делает две случайные величины статистически независимыми. Тогда скалярное квантование и векторное квантование достигают одинаковой эффективности. Хотя линейное преобразование может декоррелировать вектор случайных величин, опо нс приводит к статистически независимым случайным величинам в общем случае. Следовательно, векторное квантование будет всегда равняться или превосходить по характеристикам скалярный квантователь '(см. задачу 3.40).
Векторное квантование применяется при различных методах кодирования речи, включая сигнальные методы и методы базовых моделей, которые рассматриваются в разд. 3.5. В методах, основанных на базовых моделях, таких как линейное кодирование с предсказанием, векторное квантование делает возможным кодирование речи на скоростях ниже 1000 бит(с (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
