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

Введение.

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

§ 1.1 Развитие теории помехоустойчивого кодирования.

§ 1.2 Помехоустойчивое кодирование в телекоммуникационных системах.

Термины и определения.

§ 1.3 Основные классы кодов.

§ 1.5 Методы списочного мягкого декодирования блочных кодов.

§1.6 Постановка задачи.

Глава 2. Метод перестановочного мягкого декодирования линейных блочных кодов с использованием конечного множества тестовых кодовых последовательностей.

§ 2.1 Общие принципы, определения, отличительные особенности.

§ 2.2 Алгоритм декодирования.

§ 2.3 Исследование построения тестовых последовательностей.

§ 2.4 Вычислительная сложность алгоритма.

§ 2.5 Методика предварительной оценки производительности кодов.

Глава 3. Система автоматизированной разработки помехоустойчивых кодов и алгоритмов декодирования - СОДЕК

§ 3.1 Эффективная разработка помехоустойчивых решений.

§ 3.2 Основные возможности среды СОДЕК.

§ 3.3 Объектно-ориентированное проектирование и анализ.

§ 3.4 Язык командного интерпретатора СОДЕК.

Глава 4. Математическое обеспечение среды СОДЕК.

§ 4.1 Модели каналов.

§ 4.2 Модели цифровых модемов.

§ 4.3 Нижняя граница Шеннона для АБГШ канала.

Глава 5. Исследование алгоритма перестановочного мягкого декодирования линейных блочных кодов с использованием конечного множества тестовых последовательностей в программной среде СОДЕК.

§ 5.1 Вычисление нижней границы Шеннона.

§ 5.2 Анализ предварительных вероятностных характеристик кодов исследованием набора тестовых конфигураций ошибок.

§ 5.3 Вероятностные характеристики кодов в каналах с независимыми ошибками.

§ 5.4 Влияния метрики канала при использовании различных типов модуляции.

§ 5.5 Вероятностно-временные характеристики блочных кодов в каналах с пакетами ошибок.

Работа посвящена разработке методов и средств автоматизированного анализа помехоустойчивых линейных блочных кодов и оптимизации алгоритмов декодирования в соответствии с требованиями к проектируемым системам связи. Проведен анализ требований к инструментальным средствам изучения характеристик кодеков и предложены подход и технология разработки ПО, способствующие повышению эффективности исследований канальных кодеков. На основе результатов анализа разработана программная среда СОДЕК, включающая в себя: интерпретатор специализированного языка; модели каналов, вносящих независимые и пакетные ошибки; инструментарий для вычисления нижних теоретических границ производительности кодов и средства систематизации результатов исследований.

Предложен и исследован алгоритм мягкого декодирования коротких линейных блочных кодов. Полученные характеристики декодирования некоторых кодов близки к нижним теоретическим пределам. Показано, что сложность предложенного алгоритма для рассмотренных коротких кодов меньше сложности известных алгоритмов. Проведены исследования кодеков в каналах с аддитивным белым гауссовским шумом (АБГШ), каналах с замираниями и продемонстрирована способность предложенного алгоритма исправлять как независимые, так и пакеты ошибок.

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

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

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

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

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

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

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

1. Разработан алгоритм мягкого декодирования линейных двоичных блочных кодов, имеющий низкую сложность и вероятностные характеристики, сопоставимые с декодированием по методу максимального правдоподобия в АБГШ канале.

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

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

4. Разработано математическое и программное обеспечение САПР кодеков и методы автоматизации процессов их исследования.

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

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

Основные результаты получены автором на кафедре «ПКИМС» Московского государственного института электронной техники (МГИЭТ) и в фирме «Кедах Электронике Инжиниринг». На основе результатов исследования в разработанной среде предложенного кодека квадратично-вычетного кода (48,24,12) были выданы рекомендации для реализации аппаратной версии данного кодека.

Основными из полученных автором результатов, являются:

1. Алгоритм мягкого перестановочного декодирования двоичных линейных блочных кодов.

2. Методика предварительной оценки сложности алгоритма и близости вероятностных характеристик некоторого кода с параметрами (n,k) к характеристикам мягкого декодирования по методу максимального правдоподобия данного кода.

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

4. Технология и методы автоматизации исследования канальных кодеков.

5. Среда СОДЕК для автоматизированного исследования характеристик канальных кодеков.

На защиту выносится:

1. Среда проектирования канальных кодеков СОДЕК.

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

3. Методика предварительных взаимообратных оценок вероятностных характеристик кодов и заданной сложности декодирования.

Основные научные и практические результаты диссертационной работы докладывались и обсуждались на заседаниях кафедры «ПКИМС», на научно-технических совещаниях фирмы КЕЕ, опубликованы в одной статье, а также в трудах пяти всероссийских и международных научно-технических конференциях.

Аннотация глав

Заключение

В ходе работы удалось в некоторой степени расширить список кодов с характеристиками близкими к теоретически возможным при декодировании предложенным алгоритмом в пределах несовершенства до 1 дБ (см. рис.). Для кода КВ(48,24) полученные вероятностные характеристики совпадают с предыдущими результатами декодирования алгоритмом А*, но сложность предложенного алгоритма для этого кода существенно ниже.

12 16 20 24 28 32 36 40 44 48 52 56 60 64 68

Длина информационного бппкя к

Рис. 11. Несовершенство кодов с учетом результатов полученных в данной работе (BLOCK (new)).

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

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

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

146

1. С. Е. Shannon, A Mathematical Theory of Communication, Bell System Technical Journal, Vol. 27, 1948.

2. Питерсон У., Коды, исправляющие ошибки. М: Мир, 1964.

3. Mac Williams J. "Permutation Decoding of Systematic Codes". Bell Systems Techn. J., 1964, 43, 1, part 2, 485-505.

4. R. G. Gallager, "Low-density parity-check codes," IRE Transactions on Information Theory, vol. IT-8, pp. 21-28, Jan. 1962.

5. G. D. Forney, Jr., Concatenated Codes, Cambridge, Massachusetts: Massachusetts Institute of Technology, 1966.

6. G. D. Forney, Jr., Generalized Minimum Distance Decoding IEEE Trans. Inform. Theory, pp. 125(131, April 1966.

7. JI.M. Финк Теория передачи дискретных сообщений. М, 1970.

8. Johnson, Norman, and Kotz, Samuel, "Distributions in Statistics: Continuous Univariate Distributions-2", Wiley 1970 p. 205.

9. Блох Э.Л., Попов O.B., Турин В.Я., Модели источников ошибок в каналах передачи цифровой информации, М., «Связь», 1971.

10. D. Chase, A Class of Algorithms for Decoding Block Codes with Channel Measurement Information IEEE Trans. Inform. Theory, pp. 170{ 181, January 1972.

11. Турин В.Я., Передача информации по каналам с памятью, М., «Связь», 1977.

12. Питерсон Уэлдон, Коды, исправляющие ошибки. М: Мир, 1978.

13. J. К. Wolf, Efficient Maximum Likelihood Decoding of Linear Block Codes Using a Trellis IEEE Trans. Inform. Theory, pp. 76-80, January 1978.

14. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1. Синтаксический анализ, 612 е.; Т.2. Компиляция, 487 е., М.: Мир, 1978.

15. Зюко А.Г. Помехоустойчивость и эффективность систем передачи информации. М: Радио и связь, 1985.

16. И.Н. Бронштейн, К.А. Семендяев, Справочник по математике, М, Наука, 1986.

17. Brooks, F., No Silver Bullet: Essence and Accidents of Software Engineering. IEEE Computer vol.20(4), p. 12. April 1987.

18. Bertrand Meyer. Object-Oriented Software Construction. Prentice Hall, 1988.

19. Jack W. Crenshaw, Let's Build A Compiler!, 1988.

20. Захарченко H.B., Пудельман П.Я., Канонович В.Г. Основы передачи дискретных сообщений. М: Радио и связь, 1990.

21. D. J. Taipale and М. В. Pursley, An Improvement to Generalized-Minimum-Distance Decoding IEEE Trans. Inform. Theory, pp. 167172, January 1991.

22. Ralf E. Johson, Vincent F. Russo, Reusing Object-Oriented Design, University of Illinois Tech Report, May 1991.

23. William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery, Numerical Recipes In С -The Art Of Scientific Computing, Cambridge University Press, Second Edition 1992.

24. C. Berrou, A. Glavieux, and P. Thitimajshima, "Near Shannon limit error-correcting coding and decoding: Turbo-codes," in ICC'93, Geneva, Switzerland, May 93, pp. 1064-1070

25. Y. S. Han, C. R. P. Hartmann, and C.-C. Chen, Efficient Priority-First Search Maximum-Likelihood Soft-Decision Decoding of Linear Block Codes IEEE Trans. Inform. Theory, pp. 1514-1523, September 1993.

26. Y. S. Han, C. R. P. Hartmann, and C.-C. Chen, Efficient Priority-First Search Maximum-Likelihood Soft-Decision Decoding of Linear Block Codes IEEE Trans. Inform. Theory, pp. 1514-1523, September 1993.

27. Evans, Merran, Hastings, Nicholas and Peacock, Brian, "Statistical Distributions, Second Edition", Wiley 1993 pp. 147-148.

28. Y. S. Han, Efficient Soft-Decision Decoding Algorithms for Linear Block Codes Using Algorithm A*, PhD thesis, School of Computer and Information Science, Syracuse University, Syracuse, NY 13244, 1993.

29. Т. Kaneko, T. Nishijima, H. Inazumi, and S. Hirasawa, An Efficient Maximum-Likelihood Decoding Algorithm for Linear Block Codes with Algebraic Decoder IEEE Trans. Inform. Theory, pp. 320-327, March 1994.

30. Webb W.T., Hanzo L. Modern quadrature amplitude modulation -Pentech Press, London, 1994.

31. R. Pyndiah, A. Picart, and A. Glavieux "Performance of block turbo coded 16-QAM and 64-QAM modulations," Proceedings of GLOBECOM'95, pp. 1039-1043.

32. Proakis J.G. Digital communication. McGraw-Hill, New York, 1995.

33. M. P. C. Fossorier and S. Lin, Soft-Decision Decoding of LinearBlock Codes Based on Ordered Statistics IEEE Trans. Inform. Theory, pp. 1379-1396, September 1995.

34. S. Sivaprakasam, K.S. Shanmugan, An equivalent Markov model for burst errors in digital channels, IEEE Transactions on Communications ,vol.43,no.2/3/4,pp.l347-1355, 1995.

35. L. Ekroot and S. Dolinar, A* Decoding of Block Codes IEEE Trans on Communications, pp. 1052-1056, September 1996.

36. P.D. Terry, Compilers and Compiler Generators, Rhodes University, 1996

37. T.S.Rappaport, Wireless Communications: Principles and Practice, New Jersey Prentice Hall, 1996.

38. M. P. C. Fossorier and S. Lin, Computationally Efficient Soft-Decision Decoding of Linear Block Codes Based on Ordered Statistics IEEE Trans. Inform. Theory, pp. 738-751, May 1996.

39. S. Benedetto, G. Montorsi, D. Divsalar and F. Pollara, "Serial concatenation of interleaved codes: Performance Analysis, Design, and Iterative Decoding", JPL TDA Progress Report 42-126, August 15, 1996.

40. J Hagenauer, E. Offer and L. Papke, "Iterative decoding of binary block and convolutional codes", IEEE Transactions on Information Theory, vol. 42, pp.429-445, March 1996.

41. P. Jung, "Comparison of turbo-code decoders applied to short frame transmission systems," IEEE J. Select. Areas Commun., vol. 14, no. 3, pp. 530-537, 1996.

42. Т. Kaneko, T. Nishijima, and S. Hirasawa, An Improvement of Soft-Decision Maximum-Likelihood Decoding Algorithm Using Hard-Decision Bounded-Distance Decoding IEEE Trans. Inform. Theory, pp. 1314-1319, July 1997.

43. R. Pyndiah, "Iterative Decoding of Product Codes" in Proc. Int Symp. on Turbo Codes andRelated Topics, (Brest, France), pp. 7179, Sept. 1997.

44. Samuel J. MacMullan, Oliver M. Collins, "A Comparison of Known Codes, Random Codes, and the Best Codes", IEEE transactions on information theory, vol. 44, no. 7, November 1998.

45. S. Dolinar, D. Divsalar, F. Pollara, "Code Performance as a Function of Block Size", TMO Progress Report 42-133, May 15, 1998.

46. Буч Г. Объектно-ориентированный анализ и проектирование, Пер. с англ., Москва, Бином, 1998 г., 559 с.

47. Б.К. Мартыненко, И.Э. Косинец, К обоснованной реализации языков программирования: построение и тестирование конечных процессоров. Деп. в ВИНИТИ, № 6909-84. 96 с.

48. Б.К.Мартыненко, Синтаксически управляемая обработка данных, издательство С.Петербургского Университета, 1997

49. W.Turin, R.Nobelen, Hidden Markov modeling of flat fading channels,"IEEE Journal on Selected Areas in Communications, vol.16, no.9, pp.1809-1817, December 1998.

50. Palle Nowack, Structures and Interactions—Characterizing Object-Oriented Software Architecture, Ph.d. dissertation, University of Southern Denmark, 1999

51. Связь России в XXI веке. М.: MAC, 1999. - 737 с.

52. Архипкин В.Я., Дмитриев О.Ф., Нестратов М.В., Соколов А.Г., «Коррекция ошибок короткими блочными кодами в WLL системах», «Радиолокация, навигация, связь», Воронеж, 2000, том 2, стр. 943-948.

53. Нестратов М.В. Организация транспортной системы CDMA связи, «Информатика и электроника», всероссийская конференция, 2000 г., Москва

54. Страуструп Б. Язык программирования С++, Пер. с англ., Москва, Бином, 2000 г., 991 с.

55. Дональд Э. Кнут, Искусство программирования, Основные алгоритмы, Вильяме Москва, 2000.

56. Дональд Э. Кнут, Искусство программирования, Сортировка и поиск, Вильяме Москва, 2000.

57. Дональд Э. Кнут, Искусство программирования, Получисленные алгоритмы, Вильяме Москва, 2000.

58. Брукс Ф., Мифический человеко-месяц или как создаются программные системы, 2000 г., Симво, Санкт-Петербург.

59. D. Agrawal and A. Vardy, Generalized Minimum Distance Decoding in Euclidean Space: Performance Analysis IEEE Trans. Inform. Theory, pp. 60-83, January 2000.

60. Anwer A.Khan, Iterative Decoding and Channel Estimation overHidden Markov Fading Channels, Blacksb rg,Virginia, May, 2000

61. Б.Я. Советов, C.A. Яковлев, Моделирование систем, M. Высш. шк., 2001.

62. Нестратов М.В., Дмитриев О.Ф. Коррекция пакетных ошибок квадратично-вычетным расширенным кодом (48,24,12) «Информатика и электроника», всероссийская конференция, Москва, 2001 -с23 7.

63. Быховский М.А. Круги памяти: очерки истории развития радиосвязи и вещания в XX столетии. М.: Информ.-техн. центр "Мобильные коммуникации", 2001. - 223 с.

64. Нестратов М.В. Построение программной среды для разработки помехоустойчивых кодов, Докл. VIII между нар. науч.-техн. конф. «Радиолокация, навигация, связь», Воронеж: ВГУ, 2002, том 2 с930-936.

65. Нестратов М.В., Дмитриев О.Ф. Программная модель модифицированного алгоритма мягкого декодирования разделимых и неразделимых блочных кодов, Докл. IV междунар. науч.-техн. конф. "Цифровая обработка сигналов и ее применение", Москва, 2002 с26-28.

66. Б.Б. Самсонов, Е.М. Плохов, А.И. Филоненков, Т.В. Кречет, теория информации и кодирование, Феникс, Ростов-на-Дону, 2002.