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

ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Диссертационная работа посвящена исследованию комбинаторных методов декодирования линейных блоковых кодов, а именно построению конечных декодеров конкретных кодов в полунепрерывном канале. Также рассматривается эффективность кодирования на транспортном уровне сети передачи данных с коммутацией пакетов. Комбинаторное декодирование используется при этом как специальная процедура сборки сообщений… Читать ещё >

Разработка и исследование методов комбинаторного декодирования для каналов с непрерывным выходом (реферат, курсовая, диплом, контрольная)

Содержание

ГЛАВА 1. Комбинаторное декодирование линейных блоковых кодов в дискретном канале
- 1. 1. Основные определения и понятия
- 1. 2. Алгоритм J 1е вити на-Хартм ана
- 1. 3. Декодирование по информационным совокупностям
  - 1. 3. 1. Заранее выбранные покрывающие множества
  - 1. 3. 2. Нижние границы для числа покрывающих множеств
  - 1. 3. 3. Метод случайного выбора множеств
- 1. 4. Алгоритм, основанный на сортировке
- 1. 5. Декодирование с помощью укорочений и надкодов
- 1. 6. Выводы
ГЛАВА 2. Декодирование по информационным совокупностям в канале с непрерывным выходом
- 2. 1. Переборные алгоритмы, использующие надежности
  - 2. 1. 1. Алгоритмы, типаЧейза
  - 2. 1. 2. Алгоритм декодирования Лина
  - 2. 1. 3. Декодирование по обобщенной информационной совокупности
- 2. 2. Почти оптимальные алгоритмы
  - 2. 2. 1. Алгоритм Витерби
  - 2. 2. 2. Градиентный метод декодирования
  - 2. 2. 3. Декодирование с помощью весового разбиения
- 2. 3. Декодирование по информационной совокупности в канале с непрерывным выходом
  - 2. 3. 1. Декодирование по максимуму правдоподобия
  - 2. 3. 2. Модификация алгоритма Думера для кодов конечной длины
  - 2. 3. 3. Зависимый выбор информационной совокупности
  - 2. 3. 4. Оценки сложности алгоритмов
    - 2. 3. 4. 1. Сложность алгоритма №
    - 2. 3. 4. 2. Сложность алгоритма №
    - 2. 3. 4. 3. Сложность алгоритма №
  - 2. 3. 5. Декодирование с помощью укорочений
- 2. 4. Выводы
ГЛАВА 3. Кодирование на транспортном уровне сети передачи данных
- 3. 1. Сеть с коммутацией пакетов. Основные допущения
- 3. 2. Избыточное кодирование как средство уменьшения задержки сообщения
- 3. 3. Оценки эффективности кодирования на транспортном уровне при неэкспоненциальных моделях задержки
  - 3. 3. 1. Математическое введение. Основные определения и понятия
  - 3. 3. 2. Слабая сходимость для к-тых экстремальных значений
  - 3. 3. 3. Скорость сходимости
  - 3. 3. 4. Моменты распределения
  - 3. 3. 5. Модели для зависимых случайных величин
  - 3. 3. 6. Решение поставленной задачи при неизвестном исходном распределении задержки пакетов
  - 3. 3. 7. Экспоненциальный тип распределения
- 3. 4. Методика выбора оптимального кода
- 3. 5. Выводы

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

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

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

Для достижения поставленной цели в работе решались следующие основные задачи:

1. Модификация асимптотических методов декодирования по информационным совокупностям в канале с непрерывным выходом конкретных кодов конечной длины.

2. Исследование выгодности кодирования на транспортном уровне сети передачи данных, методика отыскания оптимального кода.

Методы исследования.

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

Научная новизна работы заключается в следующем:

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

2. Предложен алгоритм декодирования по информационным совокупностям с зависимым выбором в полунепрерывном канале.

3. Предложен алгоритм декодирования по укорочениям в полунепрерывном канале.

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

5. Предложена методика выбора оптимального кода при кодировании на транспортном уровне сети передачи данных.

Практическая ценность и внедрение работы.

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

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

Результаты диссертационной работы использованы в научно-исследовательских работах и внедрены во ВНИИРА (г. Санкт-Петербург), а также в учебном процессе СПГУАП.

Использование результатов подтверждено соответствующими актами. Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались:

III, IV, V научных сессиях аспирантов ГУАП (г. Санкт-Петербург 2000,2001,2002);

Ш международной школы-семинара Бикамп-01 (г. Санкт-Петербург);

VIII International Workshop «Algebraic and Combinatorial Coding Theory» (Царское село, 2002);

На семинарах кафедры «Безопасность информационных систем», «Информационные системы» СПГУАП (2000;2002).

Публикации. По теме диссертации опубликовано 5 печатных работ. Основные положения диссертации, выносимые на защиту:

1. Декодирование по информационным совокупностям в полунепрерывном канале.

2. Декодирование с помощью укорочений в полунепрерывном канале.

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

Работа построена следующим образом:

В первой главе дается введение в теорию общих методов декодирования. Даются основные определения и понятия теории кодирования. Формулируются известные комбинаторные методы декодирования в дискретном канале — градиентный метод декодирования, основанный на геометрических свойствах кода [32,33,41]- усовершенствование синдромного декодирования — алгоритм, основанный на сортировке и разбиение синдрома на две части [66]- декодирование по информационным совокупностям [9,10,13,45,51,81,86]- декодирование с помощью укорочений и надкодов [3,67]. Глава носит обзорный характер. Приводится сравнительный анализ сложности данных алгоритмов.

Вторая глава посвящена декодированию в полунепрерывном канале. Рассматриваются переборные алгоритмы, использующие надежности: алгоритмы типа Чейза [11], Лина [27,28], декодирование по обобщенной информационной совокупности. Описываются алгоритмы декодирования по максимуму правдоподобия в полунепрерывном канале: декодирование по информационным совокупностям [18]- декодирование с помощью решетки [56]. Вводится понятие почти оптимального алгоритма, в качестве примера рассматривается алгоритм декодирования с помощью весового разбиения [19]. Основная часть данной главы посвящена построению конечных декодеров конкретных кодов. Предлагаются алгоритмы декодирования по информационным совокупностям для конкретных кодов, алгоритм декодирования с зависимым выбором информационной совокупности, а также алгоритм декодирования с помощью укорочений.

Третья глава посвящена рассмотрению возможностей применения комбинаторного декодирования для сборки сообщений на транспортном уровне сети передачи данных с коммутацией пакетов. Данный метод был предложен в работах [74,75,76,83,84,85], где предлагалось условие выгодности кодирования при гипотезе об экспоненциальном характере 8 задержки пакетов. В настоящей главе приводится условие выгодности кодирования при произвольном распределении задержки пакетов, приводится методика выбора оптимального кода, в смысле минимизации задержки сообщения.

В заключении приводятся основные результаты исследования.

Основные результаты исследования могут быть сформулированы следующим образом:

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

3. Предложен алгоритм декодирования по укорочениям в полунепрерывном канале.

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

Заключение

1. Разработка эффективных декодеров конкретных кодов в полунепрерывном канале.

2. Исследование выгодности кодирования на транспортном уровне сети передачи данных.

В главе 1 рассматриваются известные комбинаторные методы декодирования в дискретном канале. Глава 2 посвящена комбинаторным методам декодирования в полунепрерывном канале и построению конечных декодеров конкретных кодов. Глава 3 охватывает вопросы кодирования на транспортном уровне сети передачи данных.

Показать весь текст

Список литературы

Ashikhmin A. and Barg A. Minimal vectors in linear codes// 1. EE Trans. Inform. Theory. — Sept. 1998. -Vol. 44. -P.2010−2017.
Barg A. Complexity issues in coding theory// In Handbook of Coding Theory, vol.1, V. Pless and W.C.Huffman, Eds., Amsterdam, The Netherlands: Elsevier Science. 1998. -P. 649−754.
Barg A., Krouk E.A., van Tilborg H.C.A. Remarks on the hard-decision decoding of linear codes // Proc. IEEE Intern. Inform. Sympos. Inform. Theory. -Ulm. 1997. -P.31.
Barg A., Krouk E. and Henlc C.A. van Tilborg. On the complexity of Minimum Distance Decoding of Long Linear Codes //IEEE Trans. Inform. Theory. July 1999. -Vol. 45. No.5. -P. 1392−1405.
Bahl L.R., Cocke J., Jelinek F. and Raviv J. Optimal decoding of linear codes for minimizing symbol error rate// IEEE Trans. Inform. Theory. -1974. Vol. IT-20. P.284−287.
Baumert L.D. and McEliece R.J. Soft decision decoding of block codes //DSN Progress Report 42−47. Jet Propulsion Laboratory, California Institute of Technology, Pasadena. -California. July and August 1978. -P.879−882.
Berlekamp E.R., McEliece R.J. and H.C.A. van Tilborg. On the inherent intractability of certain coding problem// IEEE Trans. Inform. Theory. -1978. -Vol. IT-29. P. 384−386.
Blinovski V.M. Asymptotic combinatorial coding theory.-Klawer: Boston.-1997.-P.345.
Canteaut A. and Chabaud F. A new algorithm for finding minimum-weight words in a linear code: Application to McEliece’s cryptosystem and to narrow-sense BCH codes of length 511// IEEE Trans. Inform. Theory. Jan. 1998. -Vol. 44. -P. 367−378.
Coffey J.T., Goodman R.M.F. and Farrell P. New approaches to reduced complexity decoding// Discr. Appl. Math. -1991. Vol.33. -P.43−60.
Coffey J.T. and Goodman R.M.F.The complexity of information set decoding// IEEE Trans. Inform. Theory, Sept. -1990. -Vol.35. -P.1031−1037.
Davis R.C. Approximate APP threshold decoding. A radiation Inc. Technical Memorandum. March 1971 (Harris Corporation. Government Systems Group. Melbourne. Florida).
Dulte Jose de Barros M.E.E. Soft decision information set decoding of long block codes: Ph.D. dissertation, Darmstadt University of Technology, June 2000. -P.128//in German.
Dumer I. Covering lists in maximum likelihood decoding // Proc. 34 Annual Allerton Conf. On Commun., Control, and. Сотр.-1996. -Monticello, II. Oct. 2−4. -P.683−692.
Dumer I. Maximum likelihood decoding with presorting// manuscript (1997), also Proc. IEEE Intern. Sympos. Inform. Theory. Ulm. -1997.- P.396.
Dumer I. Soft-decision decoding via sphero-ellipsoidal coverings // In Proceedings of the Sixth International Workshop on Algebraic and Combinatorial Coding Theory. September 1998.- Pskov.- Russia. -P.98−102.
Dumer I. Suboptimal decoding of linear codes: Partition technique// IEEE Trans. Inform. Theory. -Nov. 1996. Vol. 42. — P.1971−1986.
Dumer I. Ellipsoidal lists and maximum-likelihood decoding// IEEE Trans. Inform. Theory. March, 2000. -Vol. IT-46. -P.649−655.
Dumer I. Sort-and-match algorithm for soft-decision decoding// IEEE Trans. Inform. Theory. Nov., 1999, — Vol. IT-45. -P.2333−2338.
Enns V.I. New bounds of decoding domain for certain methods of error correction with soft decision // Abstracts of papers. Ill International Workshop on Information Theory «Convolutional codes- multi-user communication». -1987. P. 347−350.
Forney G.D. Study of correlation decoding. Technical Report No. RADC-TR-67−410. Technical Report to Rome Air Development Center. Griffits Air Force Base. New York. -1967.
Forney G.D. Generalized minimum distance decoding// IEEE Trans. Inf. Theory. April, 1966. — IT-12. -P.125−131.
Fossorier M.P.C. and Lin S. Soft-decision decoding of linear block codes based on ordered statistics// IEEE Trans. Inform. Theory. Sept., 1995. — Vol. 41. -P. 1379−1396.
Fossorier M.P.C. and Lin S. Computationally efficient soft-decision decoding of linear block codes based on ordered statistics// IEEE Trans. Inform. Theory. -May, 1996. -Vol. 42. -No. 3. -P.738−750.
Gordon D.M. Minimal permutation sets for decoding the binary Golay code// IEEE Trans. Inform. Theory. -May, 1982. Vol. IT-28. -P. 541−543.
Greenberger H. An iterative algorithm for decoding block codes transmitted over a memoryless channel, JPL DSN Progress Report 42−47, Jet Propulsion Laboratory, California Institute of Technology, Pasadena. California, July and August. 1978.
Hartman C.R.P and Rudolph L.D. An optimum symbol-by-symbol decoding rule for linear codes// IEEE Trans. Inf. Theory. Sept., 1976. — IT-22. -P. 514 517.
Hwang T.Y. Efficient optimal decoding of linear block codes// IEEE Trans. Inform. Theory. May, 1980. -IT-26. -P. 603−606.
Hwang T.Y. Decoding linear block codes for minimizing word error rate // IEEE Trans. Inform. Theory. -June, 1979. -IT-25. -P. 733−737.
Kabatyanslcii G. About metrics and decoding domains of Forney’s algorithm// Proceedings of the Fifth Joint Soviet-Swedish International Workshop on Information Theory at Moscow. -USSR. January 1991. -P. 81−85.
G.A.Kabatyanskii. On decoding concatenated codes in certain spaces. Proceedings of the Fifth Joint Soviet-Swedish International Workshop on Information Theory at Moscow. USSR. January 1991. -P. 86−89.
Kabatianslcii G., Krouk E. Coding decreases delay of messages in network// Proceedings of 1993 IEEE International Symposium on Information Theory, San- Antonio, Texas. U.S.A. -P. 13−17.
Kasami T. A Gilbert-Varshamov Bound For Quasi-Cyclic Codes of rate XAH IEEE Trans. Inform.Theory. May, 1974. -Vol. 20. — P.679.
Krouk E. On the probability of the error decoding in the Gilbert channel //Proc. Of International Workshop on Information Protection. M. -1993. -P.56.
Lafourcade A. and Vardy A. Lower bounds on trellis complexity of block codes// IEEE Trans. Inform. Theory. June, 1995. — IT-41. -P. 1938−1959.
Lazareva S.V. Soft decision information set decoding algorithms // Eighth International Workshop Algebraic and Combinatorial Coding Theory. Proceedings. 2002. — 8−14 September. — Tsarsckoe Selo. -P. 181−185.
Levitin L. and Hartman C.R.P.A new approach to the general minimum distance decoding problem: The zero-neighbors algorithm// IEEE Trans. Inform. Theory. -March, 1985. IT-31. -P. 378−384.
Mac Williams F.G. Permutation decoding of systematic codes// Bell Syst. Tech. J. 1964.-Vol. 43. -P.485−505.
Massey J.L., Threshold Decoding. -Cambridge, Massachusetts: MIT Press, 1963.
Pinsker M. Exponential size of discrete ellipsoid// private communication, 1995.
Prange E. The use of information sets in decoding cyclic codes// IRE Trans. Inform. Theory. 1962. -Vol. IT-8. -P. S5-S9.
Rizzo L., Vicisano L. RMDP: a FEC-based reliable multicast protocol for wireless environments// Mobile Computing and Communications Review. -February, 1998. -Vol.2. -P. 1−10.
Schonhein J. On coverings //Рас. J. Math. -1964. -14. -P.1405−1411.
Snyders J. and Be’ery Y. Maximum likelihood soft decoding of binary block codes and decoders for the Golay codes // IEEE Trans. Infrom. Theory. Sept. 1989.-Vol. 35.-P. 963−975.
Tanaka H. and Kakigahara K. Simplified correlation decoding by selecting codewords using erasure information // IEEE Trans. Inform. Theory. Sept, 1983.-Vol. IT-29. — P.743−748.
Van Tillburg J. On the McEliece public-key cryptosystem // Advances in Cryptology (Crypto'88), S. Goldwasser, ed., Lecture Notes in Comput. Sci. Springer. New York. — 1990. — Vol. 403.
Vardy A. And Be’ery Y. More efficient soft decoding of the Golay codes// IEEE Trans. Inform. Theory. -1991. Vol. IT-37. -P.667−672.
Vardy A. And Be’ery Y. Maximum likelihood soft decision decoding of BCH codes// IEEE Trans. Inform. Theory. 1994. — Vol. IT-40. — P.546−554.
Weldon E.J. Jr. Decoding binary block codes on Q-ary output channels// IEEE Trans. Inf. Theory. Nov., 1971. — IT-17. -P. 713−718.
Wolf J.K. Efficient maximum likelihood decoding of linear block codes using a trellis// IEEE Trans. Inform. Theory. Jan., 1978. -Vol. IT-24. — P.76−80.
Wolfman J. A permutation Decoding of the (24,12,8) Goley code// IEEE Trans. Inform. Theory. -May, 1983.-Vol. 29.-P.748−751.
Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.-576с.
Блиновский В. Нижняя асимптотическая граница для числа слов в произвольной сфере с заданным радиусом из F//Проблемы передачи информации 1987.-Т.23.- № 2. -С. 50−53.
Введенская Н.Д. Большая система обслуживания с передачей сообщения по нескольким путям//Проблемы передачи информации. 1998. -Том 34.-Выпуск 2, — С.98−108.
Габидулин Э.М. Комбинаторные метрики в теории кодирования // В кн.: 2 Международный симпозиум по теории информации. Цехкадзор.-1972,-С.173−175.
Галамбош Я. Асимптотическая теория экстремальных порядковых статистик. М.: Наука, 1984.-303с.
Галлагер Р. Теория информации и надежная связь. -М.: Советское радио, 1974.-719с.
Градштейн И.С., Рыжик И. Р. Таблицы интегралов, сумм, рядов, и произведений. М.: Физматгиз, 1963.-1100с.
Гумбель Э. Статистика экстремальных значений.- М.: Мир, 1965.-237с.
Думер И. Два алгоритма декодирования линейных кодов// Проблемы передачи информации Т.25.- № 1. -С. 24−32.
Думер И. Декодирование линейных кодов по минимуму расстояния // TP. V Междунар. Семинара по теории информации «Сверточные коды- связь с многими пользователями», тез. докл. Москва.- 1990. -С. 50−52.
Дэйвид Д. Порядковые статистики М.: Наука. 1979. -335с.
Евсеев Г. О сложности декодирования линейных кодов// Проблемы передачи информации.- 1983.- Т. 19, — № 1. -С.3−8.
Евсеев Г. С., Крук Е. А. Об одном алгоритме декодирования KB кодов //В кн. Тр. VI Всесоюз. Симпоз. по проблеме избыточности в информационных системах.-1974.- Ленинград.- Ч.1.- С.26−30.
Кабатянский Г. А., Крук Е. А. Кодирование уменьшает задержку// В кн. «X Всесоюзная школа-семинар по вычислительным сетям» 4.2.- Москва-Тбилиси,-1985.-С.23−26.
Кабатянский Г. А., Крук Е. А. Об избыточном кодировании на транспортном уровне сети передачи данных// Помехоустойчивое кодирование и надежность ЭВМ. М.: Наука, 1987.
Кабатянский Г. А., Крук Е. А. Кодирование сообщений в сети ЭВМ// В кн. Труды IX Всесоюзной конф. по теории кодирования и передачи информации. М, — Одесса.-1988.-С. 175−179.
Кларк Дж., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. М: Радио и связь, 1987. -391с.
Клейнрок Л. Вычислительные системы с очередями. М: Мир, 1979.-600с.
Клейнрок Л. Коммуникационные сети. Стохастические потоки и задержки сообщений. -М.: Наука, 1970. -124с.
Колесник В.Д., Полтырев Г. Ш. Курс теории информации. -М.:Наука, 1982.-416с.
Крук Е., Граница для сложности декодирования линейных блоковых кодов//Пробл. Передачи информации.-1989.- Т.25.-№ 3.-С.103−107.
Крук Е.А. Надежные методы передачи, хранения и обработки информации. Учебное пособие.- ЛИАП.-1990.-90с.
Крук Е.А., Семенов С. В. Уменьшение задержки сообщения в пакетных радиосетях с помощью кодирования на транспортном уровне// Электросвязь, — № 9.- 1994.-С.25−27.
Крук Е.А., Семенов С. В. К вопросу об эффективности кодирования на транспортном уровне сети // В кн.: IX Всесоюз. Сипозиум по пробл. избыточ. в информ. системах. Л. -1986.
Крук Е.А., Федоренко С. В. Декодирование по обобщенным информационным совокупностям // Проблемы передачи информации.-1995.-Т. 31.-№ 2.- с.54−61.
Лазарева С.В. Методика выбора оптимального кода при введении кодирования на транспортном уровне сети передачи данных. // Ш Международная Школа-Семинар «Бикамп' 01»: Тр. конф. -Санкт-Петербург, 2001.-С. 162−165.
Мак-Вильямс Ф.Дж., Слоэн Н.Дж. Теория кодов, исправляющих ошибки. М.: Связь, 1979.-744с.
Мизин И.А., Богатырев В. А., Кулешов А. П. Сети коммутации пакетов.- М: Радио и связь, 1986.-408с.
Мизин И.А., Уринсон Л. С., Храмешин Г. К. Передача информации в сетях с коммутацией сообщений. -М.:Связь.1977.-321с.

Заполнить форму текущей работой