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

13.5.1.1. Кодовые книги, древовидные и решетчатые кодеры

13.5.1.2. Совокупность кода

13.5.1.3. Поиск

Изучаемые до сих пор устройства квантования были скалярными по своей природе, поскольку они образовывали единственную выходную выборку, основанную на настоящей входной выборке и (возможно) N предшествующих выходных выборках. С другой стороны, блочные кодеры образуют вектор выходных выборок, основанный на настоящей и N предшествующих входных выборках. Эффективность кодирования (coding gain) сигнала представляет собой отношение входного SNR кодера к выходному. Если дисперсии шума на входе и выходе равны, эта эффективность просто представляет собой отношение входной дисперсии сигнала к выходной. Из данного отношения следует, что каждый бит разности между числом входных бит на выборку и средним числом выходных бит на выборку равносилен изменению эффективности на 6 дБ. Блочные кодеры могут давать впечатляющую эффективность кодирования. В среднем они могут представлять последовательности, квантованные по 8 бит, всего с 1 или 2 бит на выборку [8]. Технология блочного кодирования меняется, но общим является отображение входной последовательности в альтернативную систему координат. Это может быть отображение в подпространство большего пространства, так что отображение может быть необратимым [8]. В качестве альтернативы может быть использована информационно-зависимая схема редактирования для идентификации подпространства отображения, из которого получены квантованные данные. Технологии блочного кодирования часто классифицируются по своим схемам отображения, которые включают, например, векторные устройства квантования, кодеры различных ортогональных преобразований, кодеры с разделением по каналам, такие как кодер с многополосным кодированием. Блочные кодеры далее описываются через свои алгоритмические структуры, такие как кодовая книга, дерево, решетка, дискретное преобразование Фурье, дискретное косинус-преобразование, дискретное преобразование Уолша-Адамара (Walsh-Hadamard), дискретное преобразование Карунена-Лоэва (Karhunen-Loeve) и кодеры с блоком квадратурных зеркальных фильтров. Итак, изучим некоторые схемы блочного кодирования.

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

Векторные устройства квантования представляют собой, обобщение общепринятых скалярных устройств квантования. При скалярном квантовании для представления входной выборки скалярное значение выбирается из конечного множества возможных значений. Значение выбирается близким (в некотором смысле) к выборке, которую оно представляет. Мерой точности являются различные взвешенные среднеквадратические меры, которые поддерживают интуитивную концепцию расстояния в терминах обычной векторной длины. Обобщая, имеем, что в векторном квантовании вектор выбирается из конечного перечня возможных векторов, представляющих входной вектор выборки. Вектор выборки является близким (в некотором смысле) к вектору, который он представляет.

Каждый входной вектор может быть представлен точкой в N-мерном пространстве. Устройство квантования определяется с помощью деления этого пространства на множество неперекрывающихся объемов [14]. Эти объемы называются интервалами, полигонами и политопами, соответственно, для одно-, двух- и N-мерных векторных пространств. Задача векторного квантующего устройства состоит в определении объема, в котором расположен входной вектор. Выходом оптимального квантующего устройства является вектор, определяющий центр тяжести этого объема. Как и в одномерном квантующем устройстве, среднеквадратичсская ошибка зависит от расположения границы деления и многомерной функции плотности вероятности входного вектора.

Описание векторyого устройства квантования может рассматриваться как две точные задачи. Первая — это задача создания кода. Она связана с созданием многомерного объема квантования (или деления) и выбором допустимых выходных последовательностей. Вторая задача состоит в использовании кода и связана с поиском определенного объема при данном делении, который соответствует (согласно некоторому критерию точности) наилучшему описанию источника. Форма алгоритма, выбранного для контроля сложности кодирования и декодирования, может объединять две задачи — деление и поиск. Стандартными методами векторного кодирования являются алгоритмы кодовых книг, древовидные и решетчатые алгоритмы кодирования [15, 16].

13.5.1.1. Кодовые книги, древовидные и решетчатые кодеры

Кодеры, использующие кодовые книги, — это, по сути, алгоритмы поиска в таблице. Перечень возможных шаблонов (кодовых слов) внесен в память кодовой книги. Каждый шаблон снабжен адресом или точечным индексом. Программа кодирования ищет среди шаблонов тот, что расположен ближе всего к входному шаблону, и передает получателю адрес, сообщающий, где этот шаблон может быть найден в его кодовой книге. Древовидные и решетчатые кодеры являются последовательными. Таким образом, допустимые кодовые слова кода не могут выбираться независимо, они должны иметь структуру, которой можно управлять с помощью узловых точек. Это подобно структуре последовательных алгоритмов обнаружения-коррекции ошибок, которые обходят граф при образовании ветвящейся весовой аппроксимации входной последовательности. Древовидный граф подвержен экспоненциальному росту памяти при увеличении размерности или глубины. Решетчатый граф снижает проблему размерности, поскольку позволяет одновременно отслеживать выбранные траектории и связанные с ними траекторно-весовые метрики, называемые интенсивностью.

13.5.1.2. Совокупность кода

Кодовые векторы, внесенные в кодовую книгу, дерево или решетку, являются подобными или типичными векторами. Первый этап создания кода, в котором определяются вероятные кодовые векторы, называется заселением кода. Классические методы определения совокупности кодов есть детерминированными, стохастическими и итеративными. Детерминированная совокупность является перечнем предопределенных возможных выходов, основанных на простом субоптимальном или принятом пользователем критерии точности или на простом алгоритме декодирования. Примером детерминированного метода может служить кодирование выборок в трехмерном пространстве красного, зеленого и синего (RGB) компонентов цветного телевизионного сигнала. Для глаза не характерна одинаковая разрешающая способность для каждого цвета, так что кодирование может быть применено независимо к каждому цвету, чтобы отразить эту особенность восприимчивости. Результирующими объемами квантования могут быть прямоугольные параллелепипеды. Проблемой при независимом квантовании является то, что образы видны не в этой системе координат, а в координатах яркости, оттенка и насыщенности. Например, черно-белая фотография использует только координату яркости. Таким образом, независимо квантованные координаты RGB не приводят к уменьшению объема воспринимаемого пользователем искажения данного числа бит. Чтобы получить уменьшенное искажение, квантующие устройства должны разделить свое пространство на области, которые отражают деление в альтернативном пространстве. В качестве альтернативы, квантование может производиться независимо в альтернативном пространстве с использованием преобразующего кодирования, изучаемого в разделе 13.6. Детерминированное кодирование является наиболее простым для реализации, но дает наименьшую эффективность кодирования (наименьшее сокращение в скорости передачи бит при данном SNR).

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

13.5.1.3. Поиск

При данном входном векторе и заселенной кодовой книге, дереве или решетке, алгоритм кодера должен производить поиск для определения наиболее адекватного векторного представителя. Исчерпывающий поиск среди всех возможных представителей будет гарантировать наилучшее отображение. Работа кодера улучшается для пространств большей размерности, но это приводит к росту сложности. Исчерпывающий поиск в пространстве большей размерности может быть весьма трудоемким. Альтернатива — следовать неисчерпывающей, субоптимальной схеме поиска с приемлемо малыми ухудшениями формы оптимальной траектории. Вообще, при выборе алгоритмов поиска основными аргументами часто являются требования памяти и вычислительной сложности. Примеры алгоритмов поиска включают в себя алгоритмы единичной траектории (ветвь наилучшего, выживания), алгоритмы множественной траектории и двоичные (метод последовательной аппроксимации) алгоритмы кодовой книги. Большинство алгоритмов поиска делают попытку определить и отбросить нежелательные модели без проверки всей модели.