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 бит/с, что эквивалентно скорости кодирования  бит/отсчёт. За счёт дополнительных вычислительных усложнений в будущем станет возможным использовать сигнальные кодеры, обеспечивающие хорошее качество речи при скорости кодирования  бит/отсчёт.