Векторное квантование на основе кодов, исправляющих ошибки тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Юрков, Кирилл Валерьевич

• Юрков, Кирилл Валерьевич
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Юрков, Кирилл Валерьевич

Введение

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. Заключение

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

Список литературы диссертационного исследования кандидат технических наук Юрков, Кирилл Валерьевич, 2008 год

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.