СПОСОБ БЫСТРОГО ПОИСКА В КОДОВОЙ КНИГЕ ПРИ ВЕКТОРНОМ КВАНТОВАНИИ Российский патент 2011 года по МПК G06F17/30 H03M7/00 

Изобретение относится к области радиотехники, а именно к методам кодирования декодирования и преобразования кода.

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

Известны способы векторного квантования для осуществления процедуры кодирования речи [Макхоул Д., Рукос С., Гиш Г. Векторное квантование при кодировании речи. // ТИИЭР. - 1985. - Т.73. - №11. - С.19-61]. Также известен способ поиска в глубину по алгебраической шифровальной книге [RU 2175454 С2 27.10.2001]. В нем для поиска предлагают некоторую древовидную структуру с заданным количеством уровней. В нем для осуществления процедуры поиска используют вероятностные методы, что может приводить к неверному выбору кодового вектора, также данный подход характеризуется большей вычислительной сложностью по сравнению со способом, представленным в [V. Ramasubramanian and Kuldip К. Paliwal «Fast Nearest-Neighbor Search Based on Voronoi Projections and Its Application to Vector Quantization Encoding» in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, vol.1, no.2, March 1999]. Описанный в статье метод характеризуется также достаточно большей вычислительной сложностью.

Наиболее близким по технической сущности к заявленному способу является метод быстрого поиска ближайшего вектора в кодовой книге, характеризующийся более низкой вычислительной сложностью, по сравнению с существующими аналогами, описание которого представлено в [D.Y.Cheng, A.Gersho, В.Ramamurthi, and Y.Shoham, "Fast search algorithms for vector quantization and pattern matching," in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, Mar. 1984, vol. 1, pp.9.11.1-9.11.4]. Основным недостатком прототипа является экспоненциальный рост памяти при увеличении размерности пространства. Количество требуемой памяти при этом описывается выражением (2N-1)^Kγ, где γ - средний размер памяти, требуемой для хранения итогового набора векторов кандидатов, N - общее количество кодовых векторов, а К - размерность пространства. Техническая реализация способа сопряжена с трудностями роста памяти, например, для 32 векторов в 10-мерном пространстве, при значении γ, равном двум байтам, необходимо 2⁴⁸ байт.

Способ, описанный в прототипе, заключается в том, что К-мерное пространство разделяют на гиперпрямоугольные ячейки путем построения проекций многоугольника Вороного для каждого кодового вектора на координатную ось j, j=1, образующих N перекрывающих интервалов проекций, которые образуют 2N границ проекций , таких что , при этом границы разбивают j-ю координатную ось на (2N-1) последовательных интервала {I^j(1),I^j(2), … I^j(2N-1)}, где , m - номер интервала, причем каждому интервалу соответствует набор индексов многоугольников Вороного, чьи интервалы проекций частично или полностью перекрываются с I^j(m), а набор кодовых векторов кандидатов связывают с каждой из гиперпрямоугольных ячеек, полученных в процессе предварительной обработки и хранящихся в некоторой таблице, что и выбирают итоговым набором векторов кандидатов, на этом малом наборе далее проводят поиск, при котором для каждого компонента входного вектора определяют интервал, в который попадает данный компонент. Причем гиперпрямоугольники получаются при выполнении описанной операции построения проекций на все оси.

Опишем прототип более подробно. При его реализации осуществляется использование информации о проекциях многоугольников Вороного, при этом К-мерное пространство разделяют на (2N-1)^K гиперпрямоугольных ячеек, содержащих набор итоговых кодовых векторов кандидатов. Многоугольник Вороного V_i, связанный с вектором кодовой книги содержит все точки в пространстве R^K, наиболее близкие к , чем к какому либо другому кодовому вектору. Таким образом, если кодовый вектор находится в многоугольнике V_i, то связанный кодовый вектор будет ближайшим.

Для построения структуры, на которой будет организован поиск, осуществляют предобработку в виде "разделения пространства R^K на гиперпрямоугольные ячейки". Для этого строят проекции многоугольника V_i на координатную ось j (фиг.1), получают интервал , с начальной и конечной точкой . Данную процедуру построения проекций осуществляют для всех N многоугольников, получают N перекрывающих интервалов проекций многоугольников Вороного , i=1, …, N, которые образуют 2N границ проекций таких что . Эти границы делят j-ю координатную ось на (2N-1) последовательных интервала {I^j(1),I^j(2), … I^j(2N-1)}, где . Каждому интервалу ставят в соответствие набор S^j(m) индексов многоугольников Вороного, чьи интервалы проекций частично или полностью перекрываются с I^j(m).

Набор индексов S^j(m_j), связанный с интервалом I^j(m_j), определяет кодовые векторы кандидаты, которые могут быть ближайшими к входному вектору . Эту операцию разделения на интервалы повторяют для всех К осей. Далее определяют гиперпрямоугольную ячейку по формуле (1)

Каждую ячейку связывают с итоговым набором кодовых векторов кандидатов , который получают по формуле (2):

Набор кодовых векторов кандидатов, связанных с каждой из (2N-1)^K гиперпрямоугольных ячеек, полученных в процессе предварительной обработки, хранят в некоторой таблице.

Поиск осуществляют следующим образом. Для каждой компоненты входного вектора определяют интервал, в который она попадает , т.е. компонент вектора x_j удовлетворяет условию , далее для всех К осей формируют интервалы I^j(m_j), j=1, …, K, содержащие компоненты вектора . Далее определяют гиперпрямоугольную ячейку, в которой лежит входной вектор , по формуле (1), затем с таблицы считывают соответствующий ей набор кодовых векторов кандидатов.

На этом малом наборе далее проводят поиск методом полного перебора. Данная процедура требует всего Klog(2N) сравнений для нахождения итогового набора. Однако недостатком прототипа является большое количество памяти необходимой для хранения таблицы (2N-1)^Kγ, а также достаточно высокая вычислительная сложность.

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

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

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

Рассмотрим заявленный способ подробнее. На первую из рассматриваемых осей строят проекции всех N многоугольников Вороного V_i. Получают N перекрывающих интервалов проекций, , i=1, …, N, которые образуют 2N границ проекций таких что . Эти границы разделяют рассматриваемую координатную ось на (2N-1) последовательных интервалов {I¹(1), I¹(2), … I¹(2N-1)}, где . Каждый интервал соответствует набору S¹(m) индексов многоугольников Вороного, чьи интервалы проекций частично или полностью перекрываются с I¹(m). Далее для каждого интервала I¹(m) m=1…(2N-1) на следующую рассматриваемую ось строят только проекции многоугольников Вороного, чьи интервалы проекций частично или полностью перекрываются с I¹(m), т.е. входящих в набор S¹(m). Получают N₁<N перекрывающих интервалов проекций , i=1, …, N₁, где N₁ - определяется количеством векторов, входящих в набор S¹(m). В итоге получают 2N₁ границ проекций таких, что . Эти границы разделяют рассматриваемую координатную ось на (2N₁-1) последовательных интервалов {I²(1), I²(2), … I²(2N₁-1)}, где . Каждому интервалу соответствует набор S²(m) индексов многоугольников Вороного, чьи интервалы проекций частично или полностью перекрываются с I²(m) и входят в набор S¹(m).

Процедуру повторяют для каждого интервала I²(m), m=1…(2N₁-1) и на следующую ось строят только проекции многоугольников Вороного из набора S²(m). Так последовательно рассматривают все К осей. В результате получают структуру данных для поиска в виде дерева, как показано на фиг.2.

Поиск реализуют в виде переходов по веткам дерева. Таким образом, входной вектор попадает в интервал , если компонент вектора . На следующем этапе рассматривают поддерево, порожденное узлом I¹(m) (фиг.2), таким образом, анализируют каждый компонент входного вектора, на последнем этапе интервал I^K(m), в который попадает компонент x_K, определяет концевой узел, который определяет итоговый набор С^'(х).

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

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

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

Заявленное техническое решение поясняется чертежами, на которых показаны:

фиг.1 - диаграмма Вороного для шестнадцати точек на плоскости, жирными линиями выделен многоугольник Вороного;

фиг.2 - иллюстрация структуры данных для поиска в виде дерева;

фиг.3 - функциональная схема осуществления процедуры формирования структуры данных и индексированной таблицы векторов кандидатов;

фиг.4 - функциональная схема осуществления процедуры поиска ближайшего кодового вектора.

Функциональная схема осуществления процедуры формирования структуры данных и индексированной таблицы векторов кандидатов показана на фиг.3. Она состоит из блока 1 построения диаграммы Вороного, на который поступает набор кодовых векторов, выход блока 1 соединен со входом блока 2 определения проекций многоугольников Вороного, на вход которого поступает набор многоугольников Вороного по оси у, выход блока 2 соединен с входом блока 3 упорядочивания точек проекций многоугольников Вороного по оси у, на вход которого поступают проекции многоугольников с блока 2, выходы блока 3 соединены со входами блока 4 определения пересечения многоугольников Вороного с полученными интервалами, которые поступают на вход блока 4 с блока 3, выход блока 4 соединен со входом блока 2 и блока 5 создания индексированной таблицы векторов кандидатов, на вход которого поступают многоугольники Вороного. Выходом блока 5 является набор итоговых кодовых векторов.

Рассмотрим реализацию процедуры формирования структуры данных и индексированной таблицы векторов кандидатов. На блок 1 поступает информация о векторах кодовой книги, блок 1 выполняет построение диаграммы Вороного и формирует на выходе набор многоугольников Вороного, соответствующих кодовым векторам, информация о которых подается на блок 2, который формирует проекции каждого многоугольника на оси, далее они поступают на вход блока 3, который упорядочивает точки проекций по оси и формирует набор интервалов, который подается на блок 4. Блок 4 для каждого полученного интервала определяет набор многоугольников, чьи координаты проекций пересекают данный интервал, причем в первоначальный набор для определения входят только те многоугольники, которые образовали данный набор интервалов. На выходе блока 4 формируют информацию о наборе многоугольников Вороного для каждого интервала. Если набор интервалов был построен для последней из рассматриваемых осей, то полученный набор многоугольников является итоговым, если нет, то информацию о наборе многоугольников подают на блок 2.

На фиг.4 показана функциональная схема осуществления процедуры поиска ближайшего кодового вектора. Она состоит из блока 101 определения интервала, на который поступают последовательно компоненты кодового вектора, выход блока 101 соединен со входом блока 102 определения ячейки таблицы конечных векторов, на который поступает последний определенный интервал, выход блока 102 соединен со входом блока 103 считывания с таблицы, выход блока 103 соединен с входом блока 104 хранения таблицы итоговых наборов кодовых векторов, а выход блока 104 соединен с входом блока 103, на выходе блока 103 - итоговый набор кодовых векторов кандидатов. Ее функционирование осуществляется следующим образом. На блок 101 последовательно поступают компоненты кодового вектора. Для каждой компоненты блок 101 последовательно определяет, в какой интервал она попадает, таким образом, происходит переход по узлам дерева (см. фиг.2). Последний определенный интервал поступает на блок 102 определения ячейки таблицы конечных векторов, где по данному интервалу определяется ячейка таблицы конечных векторов. Индекс определенной ячейки подается на блок 103 считывания с таблицы, который по данному индексу считывает из блока 104 хранения таблицы итоговых наборов кодовых векторов, в итоге на выходе блока 103 - итоговый набор кодовых векторов кандидатов.

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

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

Вычислительная сложность предложенного метода Z_n для поиска одного вектора находится с использованием следующего выражения:

где N_i изменяется, N_i=N…N_K, N…N_K - число векторов претендентов, оставшихся не исключенными после рассмотрения i-й оси, S - конечное число в С'(х) итоговом наборе векторов кандидатов, а δ - количество операций для вычисления расстояния до кодового вектора. Для сравнения вычислительная сложность Z, предложенного в прототипе:

Из выражения (3) и (4) получим выражение для полученного эффекта по вычислительной сложности:

Количество памяти, необходимое для реализации прототипа, оценивается выражением:

где γ - средний размер памяти, требуемой для хранения итогового набора векторов кандидатов.

Оценка использованной памяти предложенного способа М_n равна:

Из выражения (6) и (7) получим выражение для полученного эффекта по использованию памяти:

Рассмотрим пример, показывающий наглядно эффективность предложенного метода по отношению к прототипу для случая 32 векторов для четырехмерного пространства (N=32, К=4), по вычислительной сложности и использованию ресурсов памяти. По вычислительным ресурсам для прототипа:

Z=d·log₂·2·N+δ·S=4·6+δ·S=24+δ·S,

для предложенного способа:

Получим выигрыш по вычислительной сложности:

E_z=(Z/Z_n)=2,18, т.е на кодирование одного входного вектора, вектором из кодовой книги, для разработанного метода требуется в среднем в 2,18 раза операций меньше, чем методом, описанным в прототипе.

По использованию ресурсов памяти

M=(2N-1)^K γ=(2·32-1)⁴γ=15752961·γ

Получим выигрыш по вычислительной сложности:

Получим выигрыш по использованию ресурсов памяти:

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

Способ быстрого поиска в кодовой книге при векторном квантовании, заключающийся в том, что К-мерное пространство разделяют на гиперпрямоугольные ячейки путем построения проекций многоугольника Вороного для каждого кодового вектора на координатную ось j, j=l, образующих N перекрывающих интервалов проекций, которые образуют 2N границ проекций (,,…,), таких, что (≤≤…≤), при этом границы разбивают j-ю координатную ось на (2N-1) последовательных интервала {I^j(1),I^j(2), …, I^j(2N-1)}, где I^j(m)={(,)}, m - номер интервала, причем каждому интервалу соответствует набор индексов многоугольников Вороного, чьи интервалы проекций частично или полностью перекрываются с I^j(m), а набор кодовых векторов кандидатов связывают с каждой из гиперпрямоугольных ячеек, полученных в процессе предварительной обработки и хранящихся в некоторой таблице, что и выбирают итоговым набором векторов кандидатов, на этом малом наборе далее проводят поиск, при котором для каждого компонента входного вектора определяют интервал, в который попадает данный компонент, отличающийся тем, что в способе поиска в кодовой книге при векторном квантовании, используемом в прототипе, при построении проекций многоугольников Вороного на координатную ось j, j≠1, строят проекции для каждого интервала оси j-1 только тех многоугольников Вороного, которые входят в набор индексов этого интервала, т.е. для тех, чьи интервалы проекций частично или полностью перекрываются с рассматриваемым интервалом, далее на этапе поиска интервал, в который попадает компонент входного вектора определяют последовательно для всех осей, а последний интервал определяет гиперпрямоугольную ячейку с итоговым набором векторов кандидатов.