автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Векторное квантование на основе кодов, исправляющих ошибки

На правах рукописи

Юрков Кирилл Валерьевич

ВЕКТОРНОЕ КВАНТОВАНИЕ НА ОСНОВЕ КОДОВ, ИСПРАВЛЯЮЩИХ

ОШИБКИ

05 13.17 — Теоретические основы информатики

Автореферат диссертации на соискание учёной степени кандидата технических наук

Москва — 2008

003454720

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения» (ГУАП)

Научный руководитель'

Официальные оппоненты:

Ведущая организация

доктор технических наук, доцент Кудряшов Б. Д.

доктор физико-математических наук,

Блиновский Владимир Маркович

кандидат технических наук,

Ланге Михаил Михайлович

Московский физико-технический институт (государственный университет)

Защита состоится 2008г. в /у ч. ОО мин. на

заседании диссертационного совета Д 002.077 01 при Институте проблем передачи информации им. А. А Харкевича РАН по адресу: 127994, г. Москва, ГСП-4, Большой Каретный переулок, д 19, стр 1

С диссертацией можно ознакомиться в библиотеке ИППИ РАН.

Автореферат разослан " " М>с±/1р<9^ 2008.

Учёный секретарь диссертационного совета Д 002.077.01 доктор физико-математических наук

Цитович И И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования.

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

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

Теоретическая постановка задачи квантования была сформулирована независимо А.Н. Колмогоровым и К. Шенноном. В их работах было введено понятие функции ¿-энтропии у Колмогорова и функции скорость-искажение у Шеннона, как нижней границы скорости квантования при заданной ошибке При этом было дано доказательство достижимости данной функции для широкого класса источников. Однако, доказательство было не конструктивным, в том смысле, что оно не давало ответа на вопрос о том, как именно строить оптимальные квантователи Поиски решения для задачи квантования породили теорию, которая в русскоязычной литературе называется теорией кодирования с заданным критерием качества. Основоположниками теории сжатия с заданным критерием качества являются А.Н. Колмогоров, К. Шеннон, М.С. Пинскер, Р.Л. Добрушин, В.Н. Кошелев и др.

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

Наиболее простым по сложности решением задачи квантования является скалярное квантование, подразумевающее независимую обработку каждого символа источника. В работе В.Н Кошелева было показано,

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

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

Первые шаги в сторону уменьшения сложности векторного квантования основаны на использовании структурированных книг, а именно, числовых решеток. Значительный вклад в теорию числовых решеток был сделан Дж. Конвеем и Н. Слоэном. В работах В.Ф. Бабкина, М.М. Ланге и Ю.М. Штарькова, а также в работах П. Задора было показано существование оптимальных квантователей в классе числовых решеток.

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

Исследованию квантователей в классе решеток, порожденных, линейными кодами, посвящена данная работа.

Целью настоящего исследования является-1) поиск классов квантователей, среди которых можно найти конструкции близкие к оптимальным; 2) поиск в заданном классе оптимальных конструкций квантователей; 3) разработка алгоритмов квантования для различных классов источников.

В соответствии с поставленной целью были определены следующие задачи и вопросы.

1) Теоретический анализ класса квантователей в множестве решеток, порожденных ц-тчпьшя линейными блоковыми кодами.

2) Поиск сверточных кодов, порождающих числовые решетки с наилучшим значением второго нормализованного момента.

3) Разработка алгоритмов квантования для класса источников, на выходе

которых символы распределены по обобщенному гауссовскому закону.

4) Разработка алгоритмов квантования для класса источников Гаусса-Маркова.

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

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

Теоретическая и практическая ценность работы состоит в следующем.

• Исследована зависимость характеристик квантователя от характеристик линейного кода, порождающего решетку.

• Разработан метод поиска кодов, порождающих числовые решетки, обладающие наилучшими характеристиками для квантования.

• Предложен новый подход к задаче оптимизации квантования за счет введения многомерной нулевой зоны.

• В работе построены коды, достигающие рекордных характеристик квантования для широкого класса источников.

Положения, выносимые на защиту.

1. Граница кодирования для числовых решеток, порожденных q-ичными линейными блоковыми кодами.

2. Сверточные коды, порождающие числовые решетки с рекордными значениями второго нормализованного момента многогранника Вороного.

3. Обобщение способа расширения нулевой зоны на случай многомерных решеток.

4. Алгоритм квантования источников Гаусса-Маркова на основе ортогонального преобразования с перекрытиями.

Апробация работы.

Результаты диссертационной работы докладывались на российских и международных конференциях: 1) IEEE International Symposium on Information Theory (ISIT2007) 24th - 29th June 2007, Nice, France. 2) Tenth International Workshop on Algebraïc and Combmatorial Coding Theory, Zvenigorod,

Russia, 3-9 September, 2006. 3) Цифровая обработка сигналов и ее применение, Москва, Россия. 29-31 марта, 2006. 4) VIII, IX, X ежегодные научные сессии аспирантов ГУАП, Санкт-Петербург, 2005-2007.

Основные результаты диссертации обсуждались и были одобрены:

• на научных семинарах по теории кодирования Института Проблем Передачи Информации РАН, 2006г, 2008г.;

• на научных семинарах кафедры Информационных систем Санкт-Петербургского Государственного Университета Аэрокосмического Приборостроения, 2004-2008гг.;

Результаты работы были использованы в НИР

• НИР №465-2 "Низкоскоростиое кодирование аудиосигналов", Санкт-Петербургский Государственный Университет Аэрокосмического Приборостроения, 2006-2007гг.

• НИР №77815 "Кодирование аудиосигналов с малой сложностью", Санкт-Петербургский Государственный Университет Информационных Технологий, Механики и Оптики, 2007-2008гг.

Публикации.

По теме диссертации опубликовано 7 работ, из них 1 статья в журнале из списка ВАК, 3 статьи в сборниках трудов рецензируемых научных конференций, 3 доклада в трудах научных конференций ГУАП.

Структура и объем диссертации. Диссертация состоит из введения, 5 глав, заключения и списка литературы из 58 наименований. Объем диссертации составляет 136 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность темы, сформулирована цель и определены задачи исследования, дано краткое изложение полученных результатов и содержание диссертации.

В первой главе дана постановка задачи квантования. Приведены известные способы построения квантователей для разных размерностей. Введено понятие числовой решетки. Приведены данные сравнения известных типов квантователей с функцией e-энтропии для различных источников.

Будем полагать, что задано множество X С К — множество сообщений источника. Числовой решеткой с порождающей матрицей V называется множество вида

Л(К) = {Л е Kn|3z € Z" • Л = zV}. (1)

В работе рассматривается специальный класс числовых решеток Будем полагать, что задан q-ичный линейный блоковый {п,к)-код С над полем F? со скоростью г = к/п. Будем рассматривать только такие коды, для

которых размер алфавита q является простым числом. Числовой решеткой, порожденной кодом С называется множество вида

Л(С) = {Л е Z"|3c € С : Л = c(mod <?)}. (2)

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

пг é K{\i) = {у € М"|||у - А,||2 < ||у - А,-||2, VA, € Л(С), Аг Ф А,-},

которое называется многогранником Вороного точки решетки А,. Все многогранники Вороного точек числовой решетки конгруэнтны друг другу. Обозначим через Т1 = %о многогранник Вороного, содержащий 0, а объем многогранника Вороного через V(7Z).

Пусть задана n-мерная функция плотности распределения вероятностей /(ж) ua X", тогда ошибку n-мериого квантования можно вычислить как

Dq = М[\\х - Q{x)\\2\ = - Т í \\х - \||2f{x)dx.

71 i J^

Вероятности точек решетки можно вычислить как рг = f^f(x)dx. Используя методы энтропийного кодирования, скорость квантования можно сделать сколь угодно близкой к энтропии

Hq = ~]T]p¿bg рг.

г

Нижней границей для скорости квантования является информационно-теоретическая характеристика источника, которая называется функцией е-энтропии

H(D) = inf min I(Xn;Y% (3)

n <p-Dv<D

где I(Xn; Yn) — средняя взаимная информация между Хп и Yn, а минимум в правой части выражения берется по всем условным распределениям (р{у\х), для которых величина ошибки D¡p не превосходит D.

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

/(*) = С)\х - min , (4)

где т — математическое ожидание, а1 — дисперсия, а > 0 — параметр распределения, определяющий экспоненциальную скорость убывания,

7(а, а) — а 1

Г(3/а)

|T(l/a)J '

а Г(z) обозначает гамма функцию, определяемую равенством

/■оо

= / Г-1"-*«

J0

r(z) — / tz-le~4t.

Класс обобщенных гауссовских распределений включает в себя гауссовское распределение, при значении параметра а = 2, и распределение Лапласа, при значении параметра а = 1.

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

Для построения границы используется стандартное предположение теории квантования с высоким разрешением. Оно заключается в том, что ошибки квантования полагаются достаточно малыми для того, чтобы считать функцию плотности распределения вероятностей f(x) константой в каждом многограннике Вороного. При данном предположении верна следующая граница для скорости квантования, полученная независимо П. Задором и В.Н. Кошелевым'

H(D) <HQ< H(D) + \ log (2тгeGn), (5)

где величина Gn называется вторым нормализованным моментом (ВНМ) многогранника Вороного и определяется выражением

/ |\xtfdx

\ 1+2/тГ

I ^Х )

II J

Итак, наилучшим решетчатым квантователем будет квантователь, обладающий наименьшим значением второго нормализованного момента. Величина Gn инвариантна относительно линейных растяжений-сжатий многогранника Вороного и зависит лишь от его формы. Максимального значения второй нормализованный момент достигает при размерности п — 1 и оно равно Gi = 1/12. Наименьшим вторым нормализованным моментом

обладает n-мерная сфера при п —» оо, при этом lim Сп(сфера) = -—.

п-+оо 27ге

0)

Рис 1. Пример вычисления циклического расстояния между точками х, yi и х, ¡д-

Утверждение 1. Для ошибки квантования в условиях теории квантования с высоким разрешением верно следующее неравенство

D < Gn(1l)V{n)2?n,

при этом равенство имеет место, если существует множество Г2 = Щ, такое что /(ж) ф 0, если х £ Q, и f(x) = 0, если х П.

Предлагаемый в работе метод оценки второго нормализованного момента основан на вычислении оценки ошибки квантования и пересчете его в значения ВНМ. Воспользоваться для этого утверждением 1 напрямую не представляется возможным, так как необходимо вычислять ошибку квантования в некотором объединении многогранников Вороного. В работе показано, что при изменении функции расстояния можно свести задачу к вычислениям в гиперкубе [0,gj". Верна следующая теорема.

Теорема 2. Пусть Q = (^J 7Z(c). Верно следующее сес

• Существует взаимно однозначное отображение ф ■ Q —у [0, q]n.

• Существует функция /?(•, ■), такая что \/х € 1Z(c),c G С выполнено

\\х - с\\2 = р(ф(х),ф(с)).

Функция р(,-), удовлетворяющая условиям теоремы 2, является функцией циклического расстояния

п

р(х, с) = £ min{(c, - хг)2, (Iс, ~хг\- q)2}. (6)

i=i

Пример вычисления циклических расстояний р(х,у\) и р(х,уг) Для Ч — 5 приведен на рисунке 1.

Следствие 3. Из теоремы 2 следует

- V(n) = qn^-rl

- Если существует множество П = (J, TZt, такое что /(ж) ф 0, если ж 6 Ü, и j(x) = 0, если х $ П, то D — Gnq2^r\

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

• Случайная величина выбирается равномерно распределенной в гиперкубе [0, q]n.

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

• Квантование производится по минимуму циклического расстояния р.

• Оценка ошибки квантования пересчитывается в оценку второго нормализованного момента согласно формуле

В = Сп д2^. (7)

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

Теорема 4. Для заданного простого д, £ > 0 существует последовательность кодов С^С^Сз..где С,- — ц-ичпый код длины г со скоростью го, и число Ы, такие что, для всех п> N верно

\Gniq) - (¿од2(го_1)| < е, (8)

где Сг„(д) — второй нормализованный момент числовой решетки, порожденной кодом Сп, величина до является решением уравнения

8

г 1/2

g(s,x)

d - 2 / -

■d

r¡) определяется как

1 / 1 f1/2 Г° ~ íñg \ 2 ~ Уо Ь*М*

(9)

s=__i_

S 2do

(10)

где

1 Í_1

g(s, x) = -J2 esp[x'k\ p(x, y) = min{(z - y)\ {\x-y\- qf}. q '—'

4 k=0

Отметим, что теорема 4 дает прямую зависимость между достижимыми значениями ВНМ числовой решетки и основанием q порождающего кода. Значения достижимых ВНМ для разных q приведены в таблице 1. Также

Таблица 1 Нормализованный второй момент для различных значений q.

Q Goo{Q) Эн. выигрыш, дБ Опт. скорость кода

1 0.083333(1/12) 0 1

2 0.059831 1.4389 0.41

3 0.058683 1.5231 0.46

5 0.058551 1.5328 0.49

lim Gn = « 0.05855 П->СО Z7TR 1.5329

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

Я = -10 log10 ^ = -10 log10 \2Gn.

Физическим смыслом энергетического выигрыша является величина выигрыша построенного квантователя по отношению к равномерному скалярному квантователю, выраженная в децибелах. Из приведенных в таблице данных следует, что уже при q = 3 существуют линейные блоковые коды, порождающие числовые решетки, ВНМ которых близок к оптимальному значению.

Следствие 5. Для рассматриваемого класса квантователей верны следующие асимптотические значения.

lira Goo(g) = -i-, ?->oo 2ne

lim r0(q) = g-ка l

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

Рассматриваются сверточные коды со скоростью 1/2. Будем полагать, что генераторы кода (<7o>i7i) заданы в полиномиальной форме

9XZ)=9h+AZ + ...+9tmZm, г = 0,1.

Любая полубесконечная информационная последовательность в полиномиальной форме

u(Z) = и0 + щг+ u2Z2 +... (11)

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

v(Z) = va + vlZ + v2Z2 + ..., v, = (v},vi) (12)

уравнением вида

= и(г)с(г),

где С(Е') = — полиномиальная матрица генераторов.

Введем понятие усеченного сверточного кода. Формально усечение определим следующим образом. Для любого полинома а(¿?) = оо + + ... + a¿Zí + .. ■ обозначим через — а0 + + ■ ■ • + полином,

полученный из а^) отбрасыванием всех членов, степень которых больше гг. Кодовыми последовательностями усеченного сверточного кода будем называть все последовательности вида где — кодовое слово

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

Для поиска кодов с наименьшими значениями ВНМ будем использовать метод перебора генераторов. Для уменьшения перебора мы, без потери оптимальности, ограничимся перебором таких пар генераторов (<?о (2), #!(£)), для которых выполнены следующие условия:

• <?оо = 5ю - 1. с1еяЫ£>)) > <3её(51{£)).

• Если deg(go(D)) = с^(<7х(£))), то мы рассматриваем только такие пары

генераторов, для которых |до(-0)| > \д1(0)\, где

ае6(а(0))

|а(Л)| = £ ад*.

г=0

. нодыг>),(Й(1?)) = 1.

Для каждой пары генераторов производится оценка ошибки квантования случайной величины равномерно распределенной в гиперкубе [0, д]". При этом в качестве функции расстояния выбирается функция циклического расстояния />(•,•) из (6). Для поиска ближайшего кодового слова в гиперкубе используется алгоритм Витерби. Ошибка квантования пересчитывается в величину ВНМ согласно (7).

В таблицах 2, 3 и 4 приведены генераторы оптимальных кодов для 9 = 2, <7 = 3 и д — 5. Полученные коды порождают числовые решетки, являющиеся наилучшими по критерию ВНМ из известных на сегодняшний момент. Для сравнения приведем значение второго нормализованного момента решетки Лича Л24, порожденной (24,12)-кодом Голея. Для данной решетки значение ВНМ равно 0.0658, что соответствует энергетическому выигрышу в 1.0259 дБ. Заметим, что уже при количестве состояний равном 8 найден двоичный сверточный код, энергетический выигрыш для которого составляет 1.0657 дБ.

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

Таблица 2. Оптимальные двоичные сверточные коды со скоростью 1/2 и их вторые нормализованные моменты Генераторы представлены в восьмеричном виде.

Кол-во состояний. Генератор кода Эл. выигрыш, дБ

2 3;1 0.0733 0.5571

4 7;5 0.0665 0.9800

8 17;13 0.0652 1.0657

16 31;23 0.0643 1.1261

32 61;57 0.0634 1.1873

64 165;127 0 0628 1.2286

128 357,251 0.0623 1.2633

256 |625;467 0.0620 1.2843

512 [1207;1171| 0.0618 1.2983

00 — 0.0598 1.4389

Таблица 3. Оптимальные троичные сверточные коды со скоростью 1/2 и их вторые

нормализованные моменты

Кол-во состояний. Генератор кода Эн. выигрыш, дБ

3 112;11| 0.0720 0.6349

9 |121;111| 0.0663 0.9931

27 [1211;1112| 0.0641 1.1396

81 111222;10121| 0.0626 1.2424

243 |110221;101211] 0.0617 1.3053

729 |1000112;112122| 0.0614 1.3265

оо — 0.0586 1.5231

Таблица 4. Оптимальные пятеричные сверточные коды со скоростью 1/2 и их вторые

нормализованные моменты

Кол-во состояний. Генератор кода ип Эн. выигрыш, дБ

5 |14;13] 0.0716 0.6591

25 |131;102| 0.0642 1.1328

125 |1323;1031] 0.0622 1.2703

625 [10314,10133] 0 0613 1.3336

00 — 0.0585 1.5229

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

Числовую решетку, порожденную линейным блоковым кодом можно представить в виде

чк

л(С)= |j№n + <vb

771=1

где Ст — кодовые слова кода С, а Zn — n-мерная целочисленная решетка. Другими словами, числовая решетка Л(С) состоит из объединения qk смежных классов, лидерами которых являются кодовые слова из С.

Любой точке решетки А можно сопоставить пару (m, Ь), где т — номер кодового слова, а b — (bi, Ь2, • • •, bn) € Zn определяет точку из множества qZn. Точка решетки Л может быть получена из пары (т, Ь) по формуле

Л = Cm + qb.

Поиск ближайшей точки в решетке к заданной точке пространства х = (xi,...,xn) € R" сводится, к поиску вектора индексов Ь и номера кодового слова шЕ {0,..., qk — 1}, которые минимизируют величину ошибки d(x,X) = п-1||ж-Л||2 = n~l\\x — (cm+<jb)||2. Основной член вданнойзадаче минимизации можно представить в виде

71

шшЦж-ЛЦ2 = mmY]ß(xuCmt) = mrnti{x,cm),

А т т

где /i(-, •) — аддитивная функция расстояния вида

п

р(х,с) = ^2ß{xt>Ct), t=1

ц(х, с) = min(i - с - qb)2 = (х - с - qb0)2. (13)

ь

Индекс i>o в выражении (13) может быть получен при помощи операции скалярного квантования с шагом q, примененной к х — с.

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

Для передачи пары (т,Ь) декодеру используется алгоритм арифметического кодирования. Пусть u — (ui,u2,... ,Uk) — информационная

Input: Последовательность источника х = (х\,х2,-- - ,хп)-Output: Номер т кодового слова ст £ С, последовательность индексов Ь = (bj, Ь2,..., Ьп).

Вычисление метрик и индексов: for t = 1 to п do

for с — 0 to q - 1 do

= (it - с - qbt(c))2

end end

Поиск кодового слова:

Найти кодовое слово с,п = (c^i, ст2,. ■ ■, cmn), минимизирующее расстояние ц(х,Ст) = /^Ow)' используя любой алгоритм декодирования линейных кодов.

Результат:

Результатом алгоритма является номер m и вектор индексов Ъ = (i>i(ci),Ь2(с2), ■■,Ь»(сп)).

Рис. 2. Алгоритм поиска ближайшей точки в решетке

последовательность, соответствующая кодовому слову с^,. Кодирование пары (ст,Ь) эквивалентно кодированию пары (га,6) или пары (и,Ь).

Разобьем кодовое слово с номером т и вектор индексов Ь на пары, соответствующие информационным символам

с=(сьс2, ..,ск),с1={с1,<$), Ь=(Ь1,Ь2,...,Ьк),Ь1 = (Ь},с1).

Для кодирования пары (и, Ь) введем условные распределения

{ФМ = Ф1\с}М%\С1), ъ, = (61,6?) е с* = (сЬс?) е С^},

где <74 — состояние кодера сверточного кода в момент времени Считаем, что данные условные распределения известны кодеру и декодеру. Распределение вероятностей на парах (и, Ь) имеет вид

к

г=1

Введем понятие нулевой зоны для векторного квантования. Зафиксируем параметр алгоритма А и заменим входную случайную

величину х на другую случайную величину по следующему правилу

К новой случайной величине применим алгоритмы поиска ближайшей точки в числовой решетке и алгоритм кодирования пары (т, Ь) Параметр А различен для различных распределений. В приведенных далее результатах данный параметр выбирался из множества Д € {2~а}, й = 0,1,2,3.

Определим правило восстановления декодером аппроксимирующего вектора у — (гц,... ,уп) по принятой паре (т, Ъ — (61,..., Ъп)). Зафиксируем известный декодеру параметр Ь, и будем считать известными декодеру центрирующие значения, вычисленные с учетом наличия расширенной нулевой зоны как

где множества определены как = {фг = с, ^ = 6}.

После получения пары (т,Ь — (Ь\,Ь2,. ■ ■ ,ЬП)) декодер находит соответствующее кодовое слово Ст = (сть..,^) и определяет восстановленное значение у = (уу, 1/2, • ■., уп) как

В таблице 5 приведены данные квантования источника, имеющего гауссовское распределение вероятности. Оптимальный параметр нулевой зоны А для гауссовского распределения равен 0. Здесь и далее величина ошибки приведена в децибелах как —10 log10 D. В скобках приведены данные из работы [I]1. Так же в таблице приведены данные для оптимального скалярного квантователя из [2]2. Полученный по сравнению с [1] выигрыш составляет до 0 8 дБ.

В таблицах 6 и 7 приведены данные квантования распределения Лапласа и обобщенного гауссовского распределения с параметром а — 0.5.

'[I) Yang, L and Fischei, Т R. A new tiellis source code for mcmoryless sources IEEE Trans, on Inf Theory, 44(7)*3056-3063, November 1998

2[2| Farvaidin, N and Modestmo, J W. Optimum quantizer performance for a class of non-Gaussian mera-oiyless sources IEEE Tians on Inf Theoiy, IT-30(3)-485-497, May 1984.

' 0,

St6J,b Xt

ßcb = 'Jctl

6 = 0, с = 0, + A, 6e{l,...L}, c€ {0,..., g-1} или

ь-о, ce{i,...,ç-i}, -A, be{-L,...,-!}, ce {0.....g- 1},

yt = qbt - A, bt< -L,

qbt + A, bt> L.

Таблица 5 Гауссовское распределение В скобках приведены данные из (1)

Скорость Количество состояний ЩП) [2]

2 4 8 32 64 512

0.5 2.29 2 50 2.55 2.64 2 69 2.76 3.01 2.10

1 5.06 5.50 (5 33) 5.61 5.71 (5 64) 5 74 5 85 6.02 4.64

2 11.08 11.50 (11.15) 11.63 11.72 (11.37) 11.77 11 84 12.04 10.55

3 17 11 17.55 (16.71) 17.64 17 74 (16.96) 17.80 17.87 18.06 16.56

Приведены значения для случаев отсутствия нулевой зоны (Д = 0) и оптимального значения нулевой зоны из множества {2~5}>й = 0,1,2,3. Полученный по сравнению с [1] выигрыш достигает 1.3 дБ.

В пятой главе рассматривается квантование источников Гаусса-Маркова (ГМ). Исследованы теоретические характеристики квантователей на основе ортогональных преобразований для различных типов ГМ источников. Предложен алгоритм квантования источников ГМ на основе ортогонального преобразования с перекрытиями.

Источник Гаусса-Маркова задается авторегрсссионным процессом,

элементы которого определяются равенством р

хг = - ^аух^ + ги г=р + 1,р + 2,...,

где а3, у = 1,... ,р — фиксированные коэффициенты, а гг, г — р + 1 ,р + 2,.. — независимые случайные величины, распределенные по гауссовскому закону с нулевым математическим ожиданием и дисперсией аг. В работе нас будут интересовать источники ГМ со следующими коэффициентами

Теоретическим ответом на вопрос о квантовании источников ГМ является метод, основанный на преобразовании Карунена-Лоэва (КЛ) и последующем квантовании вектора независимых гауссовских величин с различными дисперсиями. Данный подход является неудовлетворительным, так как сложность преобразования КЛ равна п2.

В работе рассмотрены две альтернативы преобразованию КЛ. Это дискретное косинусное преобразование и ортогональное преобразование с перекрытиями (ОПП). При помощи моделирования показано, что ортогональное преобразование с перекрытиями длины 16 имеет теоретические характеристики для рассматриваемых источников близкие к величине е-энтропии.

Таблица 6 Распределение Лапласа Данные приведены для случая Д = 0 и оптимального значения Д из множества {2-'}, я = 0,1,2,3 В скобках приведены данные из [1].

Скорость д Количество состояний Я(£>) [2]

2 4 8 32 512

0.5 0 2.92 3.03 3 06 3.11 3.21 3.54 3 11

0.25 3.06 3.15 3.17 3 20

1 0 5.69 6.05 6.14 6.23 6.33 6.62 5.76

0.25 5.87 6.14 (5.93) 6.20 6.33 (6.07)

2 0 0.125 11.68 11.74 12.15 12.15 (11.49) 12.22 12.24 12.32 (11.72) 12.44 12.66 11.31

3 0 17.74 18.15 (17.00) 18.23 18.33 (17.15) 18.44 18.68 17.20

Таблица 7. Обобщенное гауссовское распределение с параметром а = 0 5 Данные приведены для случая Д = 0 и оптимального значения Д из множества {2~"}, я = 0,1,2,3 В скобках приведены

данные из [1].

Скорость д Количество состояний Н(Ю) [2]

2 4 8 16 32

0.5 0 4.74 4.81 4.83 4.83 4.84 5.62 5.37

0.5 5.19 5.22 5.23 5.23 5.24

1 0 8.00 8.13 8.18 8.22 8 22 9 21 8 61

0.5 8 53 8.53 8.62 8.64 8.64

(8.11) (8.29)

2 0 14.31 14.71 14.80 14.90 14.94 15.60 14.58

0.25 14.56 14.90 15.03 15.10 15.14

(14.13) (14.47)

3 0 20.54 20.96 21.04 21.10 21.16 21.70 20.49

0.25 20.62 21.06 21.14 21.20 21.26

(19 61) (19.92)

AP( 1) a! = 0.9

AP( 2) <2i = 1.515,02 = -0.752

AP{ 3) ai = 1.75, a2 = -1.22, a3 = 0 301

ОПП является линейным преобразованием. На каждом шаге на преобразование поступает блок данных длины Ь, на выходе преобразования оказывается блок длины N. В работе рассматривается случай, когда Ь = 2И. Формально коэффициенты матрицы ОПП имеют вид

Ч,п

h(n) cos

к + -

1

п + -

N + 1

где 0 < к < N — 1,0 < п < Ь— 1, /г(п) — весовая функция или функция окна. В работе в качестве весовой функции используется синусоидальное окно

h(k) = sin

, fc = 0,..., 27V — 1.

Для построения квантователя источника Гаусса-Маркова введем дополнительный параметр алгоритма, 0 < к < N. Векторы длины N, х3 = • • ■ = 1,---,п/ЛГ , полученные, после

ортогонального преобразования с перекрытиями, будем обрабатывать следующим образом. Подблоки 1^-1)^1^(7-1)^+1, ■ • • обработаем

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

В таблицах 8, 9 и 10 приведены результаты квантования источников АР(1), АР(2) и АР(3). Приведены данные из работы [З]3 для источников АР(1) и АР(2). Для источника АР(3) приведены данные из [4]4 Полученный выигрыш по сравнению с известными методами достигает 2 дБ.

В заключении сформулированы основные результаты диссертационной работы.

3[3] Lee, Cheng-Chieu and Laioia, R TMlis-based stalai vector quantization of souices with mernoiy IEEE Tiana. on. Inf Tlieoiy, 46(1) 153-170, Januaiy 2000.

4[4] Maicelljn, M and Fischer, M Tielli.s coded quantization of memoiyless and Gauss-Markov souices IEEE Trans Commun, COM-38(l) 82-93, January 1990

Таблица 8 Квантование источника АР(1) на основе ортогонального преобразования с

перекрытиями.

Скорость Количество состояний я(Ю [3]

2 4 8 16 32 512

1 12.37 12.53 12.6 12.62 12 64 12.69 13 23 12 14

2 17.93 18.37 18.46 18.52 18.56 18.67 19.25 18.31

3 24.13 24 53 24.62 24.69 24.73 24.85 25.27 24.38

Таблица 9 Квантование источника АР(2) па основе ортогонального преобразова?шя с

перекрытиями

Скорость Количество состояний Н(П) [3]

2 4 8 16 32 512

1 13.42 13 71 13.78 13.83 13.86 14.01 14.96 12.95

2 20.32 20.63^ 20.70 20.73 20.77 20.9 21.64 20.47

3 26 37 26 77 26.84 26.91 26 95 27.07 27.66 26.62

Таблица 10. Квантование источника АР(3) на основе ортогонального преобразования с перекрытиями В скобках приведены данные из [4]

Скорость Количество состояний Н(О)

2 4 8 16 32 512

1 13.57 13.78 13.82 13.85 13.88 13.94 14.59

— [11.03] [11.65] [12.24] [12.64] —

2 21.15 21.38 21.45 21.50 21.53 21.62 22.16

— [19.03] [19.74] [20.23] [20 54] —

3 26.81 27.2 27.35 27.41 27 45 27.57 28.18

— [25.42] [26.04] [26.38] [26.58] —

Основные результаты работы.

1. Разработан метод оценки второго нормализованного момента для числовых решеток, порожденных линейными блоковыми д-ичными кодами.

2. На основе предложенного метода построена граница для второго нормализованного момента числовых решеток, явно зависящая от величины д. При помощи полученной границы показано, что уже при д = 3 существуют линейные блоковые коды, порождающие числовые решетки, второй нормализованный момент которых близок к границе сферической упаковки. Показано, что полученная граница при ? стремящемся к бесконечности совпадает с границей сферической упаковки.

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

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

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

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

7. На основе ортогонального преобразования с перекрытиями разработан алгоритм квантования источников Гаусса-Маркова. На основании метода численного моделирования показано, что полученные результаты превосходят известные на величину до 2 дБ.

СПИСОК ПУБЛИКАЦИЙ

1 Кудряшов Б.Д., Юрков К.В. Границы случайного кодирования для второго момента многомерных числовых решеток // Пробл. передачи информ. 2007. т. 43. № 1. С. 67-79.

2. Kudryashov B.D., Yurkov K.V. Random coding bounds for the second moments of lattices // Proc of the Tenth International Workshop on Algebraic and Combinatorial Coding Theory(ACCT'2006). M.: ИТР RAS. 2006 Pp. 170-173.

3. Yurkov K.V., Kudryashov B.D. Random quantization bounds for lattices over q-ary linear code // Proc. of IEEE International Symposium on Information Theory (ISIT'2007). 2007. Pp. 236-240.

4. Юрков K.B., Кудряшов Б.Д. Эффективность векторного квантования на основе числовых решеток в системах сжатия видео информации // Сборник трудов 8-й международной конференции "Цифровая обработка сигналов и ее применение". М. 2006. С. 417-419.

5. Юрков К.В. Векторное квантование случайных последовательностей, распределенных по обобщенному гауссовскому закону // Научная сессия ГУАП. Ч II. Технические науки. С-П.: ГУАП. 2006. С. 359-362.

6. Юрков К.В., Кудряшов Б.Д. Вторые моменты решеток на основе сверточных кодов // Научная сессия ГУАП. Ч I. Технические науки. С-П.: ГУАП. 2007. С. 141-144.

7. Юрков К.В. Квантователи малых размерностей // Восьмая научная сессия аспирантов ГУАП. Ч I. Технические науки. С-П.: ГУАП. 2005. С. 394-397.

Подписано к печати 17.11.08. Формат 60x84 1\16 . Бумага офсетная. Печать офсетная. Тираж 100. экз. Заказ № 573.

Редакционно-издательский центр ГУАП 190000, Санкт-Петербург, Б. Морская ул., 67

Введение

1 Методы кодирования источников с заданным критерием качества

1.1 Модель системы связи.

1.2 Постановка задачи кодирования с заданным критерием качества.

1.3 Классификация квантователей. Сложность квантования.

1.4 Скалярное квантование.

1.5 Векторное квантование с фиксированной скоростью.

1.6 Структурированные книги для векторного квантования

1.6.1 Числовые решетки.

1.6.2 Числовые решетки, порожденные линейными блоковыми кодами.

1.7 Сравнение известных методов квантования.

1.8 Выводы.

2 Границы случайного кодирования для числовых решеток, порожденных линейными блоковыми кодами

2.1 Второй нормализованный момент числовой решетки.

2.2 Связь второго нормализованного момента и ошибки квантования для случая величин равномерно распределенных в гиперкубе.

2.3 Теорема о достижимых значениях второго нормализованного момента числовых решеток, порожденных линейными кодами

2.4 Выводы.

3 Характеристики числовых решеток, порожденных сверточными кодами

3.1 Сверточные коды.

3.2 Алгоритм поиска сверточных кодов с минимальным значением второго нормализованного момента.

3.3 Сравнение построенных числовых решеток на основе сверточных кодов и известных числовых решеток.

3.4 Выводы.

4 Векторное квантование стационарных источников без памяти на основе числовых решеток, порожденных сверточными кодами

4.1 Сведение поиска ближайшей точки числовой решетки к алгоритму Витерби.

4.2 Кодирование индексов точек числовой решетки и выбор аппроксимирующих значений

4.3 Квантование обобщенных гауссовских величин.

4.4 Нулевая зона для векторного квантования

4.5 Квантование обобщенных гауссовских величин с параметром формы меньше 0.5.

4.6 Задержка при квантовании реальных последовательностей.

4.7 Выводы.

5 Векторное квантование на основе числовых решеток, порожденных сверточными кодами, для источников Гаусса-Маркова

5.1 Функция е-энтропии источников Гаусса-Маркова.

5.2 Дискретное косинусное преобразование для квантования источников Гаусса-Маркова.

5.3 Ортогональное преобразование с перекрытиями.

5.4 Алгоритм квантования источников Гаусса-Маркова на основе ортогонального преобразования с перекрытиями.

5.5 Выводы.

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

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

Теоретическая постановка задачи квантования была сформулирована независимо А.Н. Колмогоровым и К. Шенноном в работах [6], [50]. Именно в этих работах было введено понятие функции er-энтропии у Колмогорова и функции скорость-искажение у Шеннона, как нижней границы скорости квантования при заданной ошибке. При этом, было дано доказательство достижимости данной функции для широкого класса источников. Однако, доказательство было не конструктивным, в том смысле, что оно не давало ответа на вопрос о том, как именно строить оптимальные квантователи. Поиски решения для задачи квантования породили теорию, которая в русскоязычной литературе называется теорией сжатия с заданным критерием качества. Основоположниками теории сжатия с заданным критерием качества являются А.Н. Колмогоров, К. Шеннон, М.С. Пинскер, P.JI. Добрушин, В.Н. Кошелев и др.

На начальном этапе развития теории квантования с заданным критерием качества наибольшие усилия были направлены на построение оценок е-энтропии функции для разных классов источников. Эти усилия увенчались успехом при достаточно общих предположениях. Данные предположения, фактически, являются предположениями о малости ошибок квантования, при которых полученные оценки верны. Результаты, полученные при этом предположении, называются результатами теории квантования с малыми ошибками или теории квантования с высокой скоростью. Наиболее значимые из них приведены в работах [18], [33], [35], [34]. Так же было показано, что свойства квантователя в предположениях теории квантования с малыми ошибками зависят лишь от величины второго нормализованного момента многогранника Вороного, [58].

Наиболее простым по сложности решением задачи квантования является скалярное квантвание, подразумевающее независимую обработку каждого символа источника отдельно. Оптимальный алгоритм построения скалярного квантователя предложен в работе [30]. В работах [7], [34], [58] было показано, что в предположениях теории квантования с малыми ошибками, при среднеквадратичной мере искажения, оптимальный скалярный квантователь асимптотически проигрывает оптимальному векторному квантователю 0.25 бита на отсчет.

При увеличении размерности квантователя возникает вопрос сложности квантования. Для произвольного квантователя размерности п сложность квантования очень велика и совпадает со сложностью перебора по кодовым словам, которая растет с увеличением размерности квантователя. Наиболее часто используемым неструктурированным квантователем является квантователь, построенный по алгоритму Линде-Бузо-Грея [45].

Первые шаги в сторону уменьшения сложности векторного квантования основаны на использовании структурированных книг, а именно числовых решеток, [23], [25], [24]. Доказательство существования оптимальных квантователей в классе числовых решеток было дано в [1]. В дальнейшем от произвольных числовых решеток произошел переход к решеткам, порожденным блоковыми, и далее, сверточными кодами, [47], [31], [29], [42], [46], [56]. Это дало возможность использовать обширные результаты из теории передачи в каналах с шумом для квантования. Заметим, однако, что приведенные в указанных работах квантователи не являются числовыми решетками.

В работе [28] было показано существование оптимальных для квантования решеток, порожденных линейными g-ичными блоковыми кодами. Однако, данный результат был получен в асимптотике при q стремящемся к бесконечности.

В данной диссертации рассматриваются квантователи на основе числовых решеток, порожденных блоковыми и сверточными д-ичными линейными кодами.

Актуальность темы исследования.

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

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

1. поиск классов квантователей, среди которых можно найти конструкции близкие к оптимальным;

2. поиск в заданном классе оптимальных конструкций квантователей;

3. разработка алгоритмов квантования для различных классов источников.

В соответствии с поставленной целью были определены следующие задачи и вопросы.

1. Теоретический анализ класса квантователей в множестве решеток, порожденных g-ичными блоковыми кодами.

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

3. Разработка алгоритмов квантования для класса источников, на выходе которых символы распределены по обобщенному гауссовскому закону.

4. Разработка алгоритмов квантования для класса источников Гаусса-Маркова.

Методами исследования для решения поставленных задач являются методы дискретной математики, алгебры, теории информации, теории вероятностей, линейной алгебры, комбинаторики.

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

1. Доказана граница, случайного кодирования для числовых решеток, порожденных g-ичными линейными блоковыми кодами. На основе данной границы доказано существование в рассматриваемом классе при больших q числовых решеток с оптимальными значениями второго нормализованного момента. Показано, что при этом скорость кода, порождающего решетку, стремится к 1/2.

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

3. Разработан метод, обобщающий понятие нулевой зоны для векторного квантователя. На основе предложенного метода получены лучшие на данный момент характеристики для квантования обобщенных гауссовских источников с параметрами формы 0.5 и 1.

4. Разработан алгоритм квантования источников Гаусса-Маркова на основе ортогональных преобразований с перекрытиями, достигающий наилучших на данный момент характеристик.

Теоретическая и практическая ценность.

• Исследована зависимость характеристик квантователя от характеристик линейного кода, порождающего решетку.

• Разработан метод поиска кодов, порождающих числовые решетки, обладающие наилучшими характеристиками для квантования.

• Предложен новый подход к задаче оптимизации квантования за счет введения многомерной нулевой зоны.

• В работе построены коды, достигающие наилучших характеристик квантования для широкого класса источников.

Апробация работы.

Результаты диссертационной работы докладывались на российских и международных конференциях:

• IEEE International Symposium on Information Theory (ISIT2007). 24th - 29th June 2007, Nice, France.

• Tenth International Workshop on Algebraic and Combinatorial Coding Theory, Zvenigorod, Russia, 3-9 September, 2006.

• Цифровая обработка сигналов и ее применение, Москва, Россия. 2931 марта, 2006.

• VIII, IX, X ежегодные научные сессии аспирантов ГУАП, Санкт-Петербург, 2005-2007.

Основные результаты диссертации обсуждались и были одобрены:

• на научных семинарах по теории кодирования Института Проблем Передачи Информации РАН, 2006г., 2008г.;

• на научных семинарах кафедры Информационных систем Санкт-Петербургского Государственного Университета Аэрокосмического Приборостроения, 2004-2007гг.;

Результаты работы были использованы в НИР:

• НИР №465-2. "Низкоскоростное кодирование аудиосигналов". Санкт-Петербургский Государственный Университет Аэрокосмического Приборостроения. 2006-2007гг.

• НИР №77815. "Кодирование аудиосигналов с низкой сложностью". Санкт-Петербургский Государственный Университет Информационных Технологий, Механики и Оптики. 2007-2008гг.

Публикации.

По теме диссертации опубликовано 7 работ, из них 1 статья в журнале из списка ВАК, 3 статьи в сборниках трудов рецензируемых научных конференций, 3 доклада в трудах научных конференций ГУАП. Положения, выносимые на защиту.

1. Граница кодирования для числовых решеток, порожденных q-ичными линейными блоковыми кодами.

2. Сверточные коды, порождающие числовые решетки с рекордными значениями второго нормализованного момента многогранника Вороного.

3. Обобщение способа расширения нулевой зоны на случай многомерных решеток.

4. Алгоритм квантования источников Гаусса-Маркова на основе ортогонального преобразования с перекрытиями.

Содержание работы.

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

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

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

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

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

В заключении сформулированы основные результаты диссертационной работы.

Полученные результаты, изложенные в диссертационной работе, опубликованы в [8], [57], [41], [11], [12], [13], [14].

Основные результаты, полученные в работе.

1. Разработан метод оценки второго нормализованного момента для числовых решеток, порожденных линейными блоковыми д-ичными кодами. На основе данного метода построена граница для второго нормализованного момента числовых решеток, явно зависящая от величины q. Показано, что данная граница при q стремящемся к бесконечности совпадает с границей сферической упаковки. При помощи полученной границы показано, что уже при q = 3 существуют линейные блоковые коды, порождающие числовые решетки, второй нормализованный момент которых близок к границе сферической упаковки.

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

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

4. На основе ортогонального преобразования с перекрытиями предложен алгоритм квантования источников Гаусса-Маркова. Методом численного моделирования показано, что полученные результаты квантования являются лучшими из известных на данный момент.

6. Заключение

Результаты, выносимые на защиту

1. Бабкин, В.Ф., Ланге, М.М., Штарьков Ю.М. О решетчатом кодировании источников с разностным критерием качества и фиксированной скоростью // Вопросы кибернетики выпуск 34. Проблемы избыточности в информационных системах. М.: 1977. С. 1030.

2. Блейхут, Р. Быстрые алгоритмы цифровой обработки сигналов // М.: Мир. 1989.

3. Галлагер, Р. Теория информации и надежная связь // М.: Советское радио. 1974.

4. Двайт, Г. Б. Таблицы интегралов и другие математические формулы // С.-П.: «Лань». 2005.

5. Колесник, В. Д., Полтырев, Г. Ш. . Курс теории информации // М.: Наука. 1982.

6. Колмогоров, А. Н. Теория передачи информации // Сессия АН СССР по научн. проблемам автоматизации производства. 1956.

7. Кошелев, В. Н. Квантование с минимальной энтропией // Проблемы передачи информации. 1963. т. 14. С. 151-156.

8. Кудряшов, Б. Д., Юрков, К. В. Границы случайного кодирования для второго момента многомерных числовых решеток // Пробл. передачи информ. 2007. т. 43. № 1. С. 67-79.

9. Мартон, К. Информация и информационная устойчивость эргодических источников // Проблемы передачи информации. 1972. т. 8. №3.

10. Пинскер, М. С. Источники сообщений (а), Гауссовские источники (б) // Проблемы передачи информации. 1963. т.14. С.5-20 (а). С. 59-100 (б).

11. Юрков, К.В., Кудряшов, Б.Д. Эффективность вектороного квантования на основе числовых решеток в системах сжатия видео информации // Сборник докладов 8-й международной конференции "Цифровая обработка сигналов и ее применение". 2006. С. 417-419.

12. Юрков, К.В. Квантователи малых размерностей // Восьмая научная сессия аспирантов ГУАП: Сб. докл.: Ч I. Технические науки. 2005. С. 394-397.

13. Юрков, К.В. Векторное квантование случайных последовательностей, распределенных по обобщенному гауссовскому закону // Научная сессия ГУАП: Сб. докл.: Ч II. Технические науки. 2006. С. 359-362.

14. Юрков, К.В. Вторые моменты решеток на основе сверточных кодов // Научная сессия ГУАП: Сб. докл.: В Зч. 41. Технические науки. 2007. С. 141-144.

15. N. Abramson. Information Theory and Coding // 1963. McGraw-Hill:New York.

16. Ahmed, N., Natarajan, Т., and Rao, K. R. Discrete cosine transform // IEEE Trans. Computers. 1974. Pp. 90-93. Jan.

17. Bazaraa, M. S. and Shetty, С. M. Nonlinear Programming // 1979. New York:Wiley.

18. W. R. Bennett. Spectra of quantized signals // Bell Syst. Tech. J. 1948. Vol. 27. Pp. 446-472. July.

19. T. Berger. Rate Distortion Theory: A Mathematical Basis for Data Compression// 1971. NJ:Prentice-Hall Englewood Cliffs.

20. R.E. Blahut. Computation of channel capacity and rate-distortion functions // IEEE Trans. Inform. Theory. 1972. Vol. 4 № 18. Pp. 460-473. Jul.

21. Calderbank, A. R., Fishburn, P. C., and Rabinovich, A. Covering properties of convolutional codes and associated lattices // IEEE Trans. Inform. Theory. 1995. Vol 41. № 3. Pp. 732-746. May.

22. Cleary, J. G., Witten, I. C., and Neal, R. M. Arithmetic coding for data compression // Communication of the ACM. 1987. Vol 6. № 30. Pp. 520540. June

23. Conway, J. H. and Sloane, N. J. Fast quantizing and decoding and algorithms for lattice quantizers and codes // IEEE Trans, on Inf. Theory. 1982. Vol. 28 № 2. Pp. 227-232. Mar.

24. Conway, J. II. and Sloane, N. J. Sphere Packings, Lattices, and Groups // 1993. New York: Springer-Verlag 2nd edition edition.

25. Conway, J. H. and Sloane, N. J. A. A fast encoding method for lattice codes and quantizers // IEEE Trans, on Inf. Theory. 1982. Vol. 29. Pp. 820-824. Nov.

26. Cooley, J. W. and Tukey, J. W. An algorithm for the machine calculation of complex Fourier series. // Math. Comput. 1965. Vol. 19. Pp. 297-301.

27. Cover, Т. M. and Thomas, J. A. Elements of Information Theory // 1991. New York: John Wiley & Sons.

28. Erez, U., Litsyn, S., and Zamir, R. Lattices which are good for (almost) everything // IEEE Trans, on Inf. Theory. 2005. Vol. 51. № 10. Pp. 34013416. Oct.

29. Eyuboglu, M. V. and Forney, G. D. Lattice and trellis quantization with lattice- and trellis-bounded codebooks—high-rate theory for memoryless sources // IEEE Trans. Inform. Theory. 1993. Vol. 39. № 1. Pp. 46-59. January.

30. Farvardin, N. and Modestino, J. W. Optimum quantizer performance for a class of non-Gaussian memoryless sources // IEEE Trans, on Inf. Theory. 1984. Vol. IT-30. № 3. Pp. 485-497. May.

31. Fischer, T. R. and Wang, M. Entropy-constrained trellis-coded quantization // IEEE Trans. Info. Th. 1992. Vol. IT-38. Pp. 415 426. Jan.

32. G. D. Forney. The viterbi algorithm // Proc. IEEE. 1973. Vol. 61. Pp. 268-278. March.

33. A. Gersho. Asymptotically optimal block quantization // IEEE Trans, on Inf. Theory. 1979. Vol 25. Pp. 373-380. July.

34. Gish, H. and Pierce, J.N. Asymptotically efficient quantizing / / IEEE Trans. Inf. Theory. 1968. Vol. 14. Pp. 676-683. Sep.

35. Gray, R. M. and Gray, A. H. Asymptotically optimal quantizers // IEEE Trans. Inf. Theory. 1977. Vol. IT-23. Pp. 143-144. Feb.

36. B. Hochwald. Tradeoff between source and channel coding on a gaussian channel. IEEE Trans. Inform. Theory. 1998. Vol. 44. № 7. Pp. 3044-3055. Nov.

37. Johannesson, R. and Zigangirov, K. Sh. Fundamentals of Convolutional Coding // 1999. IEEE Press, Piscataway, New York.

38. Korkine, A. and Zolotareff, G. Sur les formes quadratiques // Math. Ann. 1873. Vol 6. Pp. 366-389.

39. Krichevsky, R. E. and Trofimov, V. K. The performance of universal encoding // IEEE Trans, on Inf. Theory. 1981. Vol. IT-27. № 2. Pp. 199-207. March.

40. Kudryashov, B. D., Oh, E., and Porov, A. V. Scalar quantization for audio data coding // IEEE Trans. Acoustic, Speech, and Signal Processing. 2007. submitted for publication.

41. Kudryashov, B. D. and Yurkov, К. V. Random coding bounds for the second moments of lattices // X Workshop on Algebraic and Combinatorial Coding Theory. 2006. M.:IITP RAS. Pp. 170-173. Sep.

42. Laroia, R. and Farvardin, N. Trellis-based scalar-vector quantizer for mem-oryless sources // IEEE Trans. Inform. Theory. 1994. Vol. IT-40. Pp. 860 870. May.

43. Lee, Cheng-Chien and Laroia, R. . Trellis-based scalar vector quantization of sources with memory // IEEE Trans, on Inf. Theory. 2000. Vol. 46. № 1. Pp. 153-170. January.

44. Lenstra, A. K., Lenstra, H. W., and Lovasz, L. Factoring polynomials with rational coefficients // Math. Ann. 1982. Vol. 261. Pp. 515-534.

45. Linde, Y., Buzo, A., and Gray, R. M. An algorithm for vector quantizer design // IEEE Trans. Comm. 1980. Vol. 28. Pp. 84-95. Jan.

46. M. W. Marcellin. On entropy-constrained trellis-coded quantization // IEEE Trans. Comm. 1994. Vol. 42. Pp. 14-16. Jan.

47. Marcellin, M. and Fischer, M. . Trellis coded quantization of memorylessand Gauss-Markov sources // IEEE Trans. Commun. 1990. Vol. COM-38. № 1. Pp. 82-93. Jan.i

48. J. Max. Quantizing for minimum distortion // IEEE Trans. Inform. Theory. 1980. Pp. 7-12. Mar.

49. R. A. McDonald. Signal-to-quantization noise and idle channel performance of DPCM systems with particular application to voice signals // Bell Syst. Tech. J. 1966. Vol. 45. Pp. 1123-1151. Sept.

50. С. E. Shannon. Coding theorem for a discrete source with fidelity criterion. // RE Nat. Conv. Rec. 1959.

51. С. E. Shannon. A mathematical theory of communication // Bell Syst. Tech. J. 1948.

52. Soleymani, M. R. and Nassar, C. R. Trellis quantization with MAP detection for noisy channels // IEEE Trans, on Comm. 1992. Vol. 40. № 10. Pp. 1562-1565. Oct.

53. Temirlac, M. and Edler, B. Overlapping block transform: Window design, fast algorithm, and an image coding experiment // IEEE Trans, on Comm. 1995. Vol. 43. № 9. Pp. 2417-2425. Sep.

54. A. J. Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm // IEEE Trans. Inform. Theory. 1967. Vol. 13. № 2. Pp. 260-269. April.

55. Z. Wang. On computing the discrete Fourier and cosine transforms // IEEE Trans. Acoust., Speech, and Signal Processing. 1985. Vol. 37. Pp. 1341-1344. Oct.

56. Yang, L. and Fischer, T. R. . A new trellis source code for memorylesssources // IEEE TVans. on Inf. Theory. 1998. Vol. 44. № 7. Pp. 3056-3063. November.

57. Yurkov, К. V. and Kudryashov, B. D. Random quantization bounds for lattices over q-ary linear codes // Internatioanal Symposium on Information Theory (ISIT 2007). 2007. Pp. 236-240. June

58. P. L. Zador. Development and Evaluation of Procedures for Quantizing Multivariate Distributions // PhD thesis, Stanford Univ. 1963.