3.4.3. Векторное квантование

В предыдущих разделах мы рассмотрели квантование выходного сигнала непрерывного источника для случая, когда квантование выполняется последовательно по отдельным отсчётам, т.е. скалярное квантование. В этом разделе мы рассмотрим совместное квантование блока символьных отсчётов или блока сигнальных параметров. Этот вид квантования называется блоковым или векторным квантованием. Оно широко используется при кодировании речи в цифровых сотовых системах связи.

Фундаментальный результат теории искажения заключается в том, что лучшую характеристику можно достичь векторным, а не скалярным квантованием, даже если непрерывный источник без памяти. Если, кроме того, отсчёты сигнала или параметры сигнала статистически зависимы, мы можем использовать зависимость посредством совместного квантования блоков отсчётов или параметров и таким образом достичь большей эффективности (более низкой битовой скорости) по сравнению с той, которая достигается скалярным квантованием.

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

, (3.4.31)

где - выход квантователя, когда на вход поступает вектор .

В принципе векторное квантование блоков данных можно рассматривать как проблему распознавания образов, включающую в себя классификацию блоков данных через дискретное количество категорий или ячеек в соответствии с некоторым критерием точности, таким, например, как среднеквадратическая погрешность. Для примера рассмотрим квантование двумерных векторов . Двумерное пространство разделяют на ячейки, как показано на рис. 3.4.3, где мы имеем произвольно выбранные шестиугольные ячейки . Все входные векторы, которые попадают в ячейку , квантуются в вектор , который на рис. 3.4.3 отмечен как центр шестиугольника. В нашем примере иллюстрируются векторов, один для каждой из 37 ячеек, на которые разбито двумерное пространство. Обозначим ряд возможных выходных векторов как .

Рис. 3.4.3. Пример квантания в двухмерном пространстве

В общем, квантование -мерного вектора в -мерный вектор ведёт к ошибке квантования или искажению . Среднее искажение по ряду входных векторов равно

, (3.4.32)

где - вероятность того, что вектор попадёт в ячейку , а - СФПВ случайных величин. Как и в случае скалярного квантования, мы можем минимизировать путём выбора ячеек при заданной ФПВ . Обычно используемая мера искажений - среднеквадратическая ошибка ( - норма) определяется как

(3.4.33)

или, в более общем виде, взвешенная среднеквадратическая ошибка

, (3.4.34)

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

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

. (3.4.35)

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

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

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

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

, . (3.4.36)

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

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

, , . (3.4.37)

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

. (3.4.38)

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

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

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

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

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

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

. (3.4.40)

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

, (3.4.41)

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

, (3.4.42)

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

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

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

Шаг 1. Инициализируется начальный номер итерации . Выбирается ряд выходных векторов , .

Шаг 2. Обучающие векторы классифицируются в группы посредством правила ближайшего соседа:

если для всех .

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

, ,

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

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

Шаг 4. Заканчивается тестирование, если относительно мало. В противном случае следует идти к шагу 2.

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

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

(3.4.43)

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

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

. (3.4.44)

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

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

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

Пример 3.4.1. Пусть и являются двумя случайными величинами с равномерной СФПВ:

(3.4.45)

где - прямоугольная область, показанная на рис. 3.4.4. Заметим, что прямоугольник повёрнут на 45º относительно горизонтальной оси. На рис. 3.4.4 показаны также собственные плотности вероятности и .

Рис. 3.4.4. Равномерная ФПВ в двух измерениях (Макхоул и др., 1985)

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

. (3.4.46)

Следовательно, для кодирования вектора потребуется число бит

. (3.4.47)

Таким образом, скалярное квантование каждой компоненты эквивалентно векторному квантованию с общим числом уровней

. (3.4.48)

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

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

. (3.4.49)

Следовательно, разница в битовой скорости при скалярном и векторном методах квантования равна

. (3.4.50)

Для случая, когда , разница в битовой скорости

бит/вектор.

Следовательно, векторное квантование на 0,82 бит/отсчёт лучше, чем скалярное, при тех же искажениях.

Интересно заметить, что линейное преобразование (поворот на 45º) декоррелирует и и делает две случайные величины статистически независимыми. Тогда скалярное квантование и векторное квантование достигают одинаковой эффективности. Хотя линейное преобразование может декоррелировать вектор случайных величин, оно не приводит к статистически независимым случайным величинам в общем случае. Следовательно, Векторное квантование будет всегда равняться или превосходить по характеристикам скалярный квантователь (см. задачу 3.40).

Векторное квантование применяется при различных методах кодирования речи, включая сигнальные методы и методы базовых моделей, которые рассматриваются в разд. 3.5. В методах, основанных на базовых моделях, таких как линейное кодирование с предсказанием, векторное квантование делает возможным кодирование речи на скоростях ниже 1000 бит/с (см. Бузо и др., 1980; Роукос и др., 1982; Пауль, 1983). Если использовать методы кодирования сигналов, возможно получить хорошее качество речи на скоростях передачи 16 000 бит/с, что эквивалентно скорости кодирования бит/отсчёт. За счёт дополнительных вычислительных усложнений в будущем станет возможным использовать сигнальные кодеры, обеспечивающие хорошее качество речи при скорости кодирования бит/отсчёт.