2„(X,X) = (X-Xf W(X-X), (3.4.34)

где W - положительно определённая взвешивающая матрица. Обычно мера W выбирается как обратная по отношению к матрице ковариаций входных данных X .

Другая мера искажений, которая иногда используется, является частным случаем нормы и определяется как

ДХ,Х)=:-Х x.-xl". (3.4.35) .

" к]

Частный случай, когда р = 1, часто используется как альтернатива случаю р=2.

Векторное квантование не ограничивается квантованием блока сигнальных отсчётов источника сигнала. Его можно использовать для квантования ряда параметров, извлечённых из данных. Например, при линейном кодировании с предсказанием (ЛКП), описанном в разделе 3.5.3, параметры, извлечённые из сигнала, являются коэффициентами предсказания, которые являются коэффициентами для всеполюсной фильтровой модели источника, который генерирует наблюдаемые данные. Эти параметры можно рассматривать как блок и квантовать как блок символов, используя некоторую подходящую меру искажений. В случае кодирования речи подходящей мерой искажений, которую предложили Итакура и Саити (1986, 1975), является взвешенная среднеквадратическая ошибка, где взвешивающая матрица W выбрана как нормированная матрица автоковариации Ф наблюдаемых данных.

При кодировании речи альтернативным рядом параметров, которые могут быть квантованы как блок и переданы к приёмнику, могут быть коэффициенты отражения (см. ниже) {fly, \<i<m}.

Еще один ряд параметров, которые иногда использ>тотся для векторного квантования при линейном кодировании с предсказанием речи, содержит логарифмические отношения {/•д}, которые выражаются через коэффициенты отражения

=log-, \<к<т. (3.4.36)

Теперь вернемся к математической формулировке векторного квантования и рассмотрим разбиение и-мерного пространства на l ячеек {Q , 1 < А: < Z,} с точки зрения

минимизации среднего искажения по всем, Z-уровневым квантователям. Имеется два условия для минимизации. Первое заключается в том, что оптимальный квантователь использует селекцию по правилу ближайшего соседа, которое можно выразить математически как

е(Х)=х,,

если, и только если

Z)(X,XJ<D(X,X), kj, \<j<l. (3.4.37)

Второе условие, необходимое для оптимизации, заключается в том, что каждый выходной вектор Х. выбирается так, чтобы минимизировать среднее искажение в ячейке С/с- Другими словами, - это вектор в Q. который минимизирует

£)=£[(Х,Х)ХеС,]= f d(x,x)p(x)cdi. (3.4.38)

Вектор Х., который минимизирует Dk. назван г/ентроидом ячейки.

Таким образом, эти условия оптимизации определяют разбиение п-мерного

пространства на ячейки {Q, 1<A;<Z,}, когда СФПВ р{х) известна. Ясно, что указанные

два условия обобщают задачу оптимального квантования скалярной величины оптимизации на случай квантования и-мерного вектора. В общем, мы ожидаем, что кодовые векторы более тесно группируются в областях, где СФПВ р{х) велика, и, наоборот, разрежены в областях, где р{х) мала.

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

из п последовательных отсчётов jxj. Вектор X квантуется в форму X = Q{X), где X -вектор, образованный рядом х„,, 1<т<1, Как было описано выше, среднее искажение

D, получаемое при представлении X через X, равно Е d{x,X) , где <i(x, х)-это искажение на одно измерение. Например,

Минимально достижимая средняя битовая скорость, с которой могут быть переданы векторы х„,, \<т<£, равна

R = бит/отсчет, (3.4.39)

где Я(х) - энтропия квантованного выходи источника, определяемая как

Я(Х) = -р(Х,)1оЕ,/(Х,). (3.4.40)

Для данной средней скорости R минимально достижимое искажение

D,XR) = mm E[d(X,X)], (3.4.41)

где R > н{х)/п и минимум в (3.4.41) берётся по всем возможным отображениям (Х). В пределе, когда размерность п стремится к бесконечности, получаем

D(R) = UmD,XR), (3.4.42)

Н->со

где D(R) - это функция искажение-скорость, которая была введена в предыдущем разделе. Из этого изложения очевидно, что функция искажение-скорость может быть как угодно приближена к пределу путём увеличения размерности п векторов.

Изложенный выше подход приемлем в предположении, что СФПВ р(Х) вектора данных известна. Однако на практике СФПВ р(Х) данных может быть неизвестна. В этом случае, возможно адаптивно выбрать квантованные выходные векторы с использованием ряда обучающих векторов Х{т). Конкретнее, предположим, что мы имеем ряд из М векторов, причём М намного больше, чем L (M»L). Итеративный групповой алгоритм, названный алгоритмом К средних, где в нашем случае K=L, может быть применён к обучающим векторам. Этот алгоритм итеративно делит М обучающих векторов на L групп так, что два необходимых условия оптимальности выполняются. Алгоритм К средних может быть описан так, как дано ниже [Макхоул и др. (1985)].

Алгоритм К средних

Шаг 1. Инициализируется начальный номер итерации /=0. Выбирается ряд выходных векторов Х(о), 1<х< L .

Шаг 2. Обучающие векторы {х(/и). 1 < «г < М] классифицируются в группы {Q } посредством правила ближайшего соседа:

X е Q (О если D(X, Х (/)) < D{X, Х (/)) для всех кФ].

ШагЗ. Пересчитываются (для (/+1)-го шага) выходные векторы каиодой группы путём вычисления центроида

для обучающих векторов, которые попадают в каждую группу.

Кроме того, рассчитывается результирующее искажение D(/) на /-Й итерации.

Шаг 4. Заканчивается тестирование, если D{i-\)-D(i) относительно мало. В противном случае следует идти к шагу 2.

Алгоритм К средних приводр1т к локальному минимуму (см. Андерберг, 1973; Линде и др., 1980). Начиная этот алгоритм различными рядами начальных выходных векторов {Х;(0)} и каждый раз выполняя оптимизацию, описанную алгоритмом К средних, можно найти глобальный оптимум. Однако вычислительные затраты этой поисковой процедуры могут ограничить поиск немногими инициализациями.

Если мы один раз выбрали выходные векторы \к,\<к<L, каждый сигнальный

вектор Х(т) квантуется в выходной вектор, который является ближайшим к нему с точки зрения выбранной меры искажения. Если вычисление включает в себя оценку расстояния между Х(т) и каждым из L возможных выходных векторов {х, процедура образует

полный поиск. Если предположим, что каждое вычисление требует п умножений и сложений, то общее требуемое число вычислений для полного поиска равно

& = nL (3.4.43)

умножений и сложений на входной вектор.

Если мы выбрали L как степень 2, то log, L определяет число бит, требуемых для представления каждого вектора. Теперь, если R обозначает битовую скорость на отсчёт [на компоненту или на измерение Х{т)], имеем пК = log, L и, следовательно, вычислительные затраты

& = п2""\ (3.4.44)

Заметим, что число вычислений растёт экспоненциально с параметром размерности п и битовой скорости R на измерение. Вследствие этого экспоненциального роста вычислительных затрат векторное квантование применяется в низкобитовых кодерах источника, таких как кодирование коэффициентов отражения или логарифмических отношений в линейном кодировании речи с предсказанием.

Вычислительные затраты, связанные с полным поиском, можно уменьшить при помощи изящного субоптимального алгоритма (см. Чанг и др., 1984; Гершо, 1982).

Чтобы продемонстрировать пользу векторного квантования по сравнению со скалярным квантованием, мы представим следующий пример, взятый у Макхоула и др. (1985).