Обработка информации при передаче LDPC-кодами по дискретным и полунепрерывным каналам тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Овчинников, Андрей Анатольевич

• Овчинников, Андрей Анатольевич
• кандидат технических наук
• 2004

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

Введение

1 Коды с малой плотностью проверок на четность

1.1 Обзор существующих результатов.

1.1.1 Основные понятия.

1.1.2 Известные результаты.

1.2 Декодирование LDPC-кодов.

1.2.1 Декодирование в дискретном канале.

1.2.2 Декодирование в полунепрерывном канале.

1.3 Анализ и построение нерегулярных LDPC-кодов.

1.3.1 Процедура "Density evolution".

1.3.2 Конструкция PEG.

1.4 Конструкции регулярных LDPC-кодов.

1.4.1 Конструкции, основанные на конечных геометриях

1.4.2 Евклидово-геометрические LDPC-коды.

1.4.3 Проективно-геометрические LDPC-коды.

1.4.4 Конструкция, основанная на кодах Рида-Соломона

Введение диссертации (часть автореферата) на тему «Обработка информации при передаче LDPC-кодами по дискретным и полунепрерывным каналам»

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

Такими кодами являются коды с малой плотностью проверок на четность (LDPC-коды), впервые рассмотренные Р.Галлагером. LDPC-коды обладают простыми и эффективными методами кодирования и декодирования, могут использоваться для исправления как независимых, так и пакетирующихся ошибок без применения процедур интерливинга, показывают хорошие практические результаты при моделировании в канале с АБГШ. Известны асимптотические результаты, показывающие, что среди LDPC-кодов есть хорошие коды, то есть такие, для которых отношение минимального расстояния к длине кода не стремится к нулю с ростом длины кода.

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

В настоящей работе рассматривается задача разработки эффективных методов построения LDPC-кодов, и получение оценок для дистанционных свойств этих кодов. Производится анализ LDPC-кодов для исправления пакетов ошибок. Рассматривается применение низкоплотностных кодов для обработки информации в конкретном канале связи с памятью на примере канала неэкра-нированной витой пары (UTP).

Основной целью работы является построение эффективных LDPC-кодов и их применение для обработки информации в дискретных и полунепрерывных каналах связи.

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

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

1. Получены оценки минимального расстояния и длины минимального цикла кодов Гилберта.

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

3. Для ряда Евклидово-геометрических кодов получено точное описание их спектра, получены оценки минимального расстояния ряда укороченных Евклидово-геометрических кодов.

4. Получены точные выражения исправляющей пакеты способности кодов Гилберта.

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

Результаты работы использовались в разработках АО "Институт информационных систем и технологий" и в учебном процессе Санкт-Петербургского государственного политехнического университета.

Публикации. Материалы, отражающие основное содержание и результаты диссертационной работы, опубликованы в 7 печатных работах.

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

1. Метод построения обобщенных кодов Гилберта, позволяющих получить эффективные LDPC-коды для передачи по реальным каналам связи

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

3. Метод вычисления точной исправляющей пакеты способности кодов Гилберта и обобщенных кодов Гилберта

Структура работы. Первый раздел работы посвящен обзору известных результатов в области LDPC-кодов, рассмотрению некоторых конструкций и их свойств. Рассматриваются как нерегулярные, так и регулярные LDPC-коды, с примерами конкретных конструкций.

Во втором разделе рассматриваются две конструкции — кодов, основанных на кодах Гилберта, и кодов, основанных на Евклидовых геометриях, производится анализ свойств этих конструкций, оптимизация их параметров, сравнение с кодами, описанными в первом разделе, в канале с Гауссовским шумом. Рассматриваются методы построения новых кодов, позволяющие повысить эффективность передачи по каналу с АБГШ.

Третий раздел рассматривает применение LDPC-кодов для исправления пакетов ошибок. Анализируются коды Гилберта, их исправляющая пакеты способность. Рассматриваются модификации кодов Гилберта и их свойства.

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

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Овчинников, Андрей Анатольевич

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

1. Получены оценки спектра кодов на основе конечных Евклидовых плоскостей EG(2,ps) при р > 2, получены выражения для минимального расстояния этих кодов

2. Проанализированы дистанционные свойства кодов на основе Евклидовых плоскостей EG(2,2s), приведены условия существования слов минимального веса

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

4. Рассмотрены дистанционные свойства кодов Гилберта, предложена общая конструкция на основе кодов Гилберта

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

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

7. Предложены коды для исправления пакетов ошибок, основанные на кодах Гилберта, проанализирована их исправляющая пакеты способность

8. Рассмотрено применение LDPC-кодов для обработки информации в канале со сложной структурой на примере канала неэкранированной витой пары

Заключение

В данной работе рассматривалась обработка информации с помощью кодов с низкой плотностью проверок на четность. Основное внимание уделялось кодам на основе Евклидовых геометрий, кодам Гилберта и их обобщениям. Анализировались дистанционные характеристики кодов, а также LDPC-коды для исправления пакетов ошибок. Были предложены эффективные методы укорочения Евклидово-геометрических LDPC-кодов, предложены коды на основе кодов Гилберта, проанализированы дистанционные свойства предложенных конструкций, проведено моделирование в канале с АБГШ. Моделирование показывает, что предложенные конструкции обеспечивают повышение эффективности передачи, то есть вероятность ошибки, сравнимую с лучшими из известных конструкций, при уменьшении сложности декодирования.

Список литературы диссертационного исследования кандидат технических наук Овчинников, Андрей Анатольевич, 2004 год

1. Р. Блейхут. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.

2. Р. Грэхем, Д. Кнут,, О. Паташник. Конкретная математика. Основание информатики. М.: Мир, 1998.

3. В.В. Зяблов, М.С. Пинскер. Оценка сложности исправления ошибок низ-коплотностными кодами Галлагера. Проблемы передачи информации, Х1(1), 1975.

4. Т. Касами, Н. Токура, Е. Ивадари,, Я. Инагаки. Теория кодирования. М.: Мир, 1978.

5. Р. Кеннеди. Каналы связи с замираниями и рассеянием. М.: Советское радио, 1973.

6. Дж. Кларк, мл., Дж. Кейн. Кодирование с исправлением ошибок в системах цифровой связи. М.: Радио и связь, 1987.

7. В.Д. Колесник, Е. Т. Мирончиков. Декодирование циклических кодов. М.: Связь, 1968.

8. В.И. Коржик, J1.M. Финк. Помехоустойчивое кодирование дискретныж сообщений в каналах со случайной структурой. М.: Связь, 1975.

9. Е. Крук. Комбинаторное декодирование линейных блоковых кодов. Диссертация на соискание ученой степени доктора технических наук, СПбГУАП, 1999.

10. Ф.Дж. Мак-Вильямс, Н.Дж.А. Слоэн. Теория кодов, исправляющих ошибки. М.: Связь, 1979.

11. И. А. А. Овчинников. Об одном классе кодов, исправляющих пакеты ошибок. Тез. докл. Второй международной школы-семинара БИКАМП'99, СПб, 1999.

12. А. А. Овчинников. Моделирование канала связи для систем MC-CDMA. V Научная сессия аспирантов СПбГУАП: Тез. докл. СПб, 2002.

13. А. А. Овчинников. Марковские метрики в каналах с памятью. Труды конференции Четвертой международной школы-семинара БИКАМП'ОЗ, СПб, 2003.

14. А. А. Овчинников. Метрики для марковских каналов. VI Научная сессия аспирантов СПбГУАП: Тез. докл. СПб, 2003.

15. А. А. Овчинников. Некоторые замечания о спектральных свойствах EG-кодов. VII Научная сессия аспирантов СПбГУАП: Тез. докл. СПб, 2004.

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

17. Дж. Прокис. Цифровая связь. М.: Радио и связь, 2000.

18. А. Н. Banihashemi. Iterative Coding for Broadband Communications: New Trends in Theory and Practice. Broadband Communications and Wireless Systems (BCWS) Centre Dept. of Systems and Computer Engineering Carleton University.

19. B. Arazi. The Optimal Burst Error-Correcting Capability of the Codes Generated by f(x) = (жр+1)(^+1)/(я+1). Inform, and Contr., 39(3):303-314, 1978.

20. L. R. Bahl, R. T. Chien. On Gilbert Burst-Error-Correcting Codes. IEEE Transactions on Information Theory, 15(3), May 1969.

21. A. Burr. Modulation and Coding for Wireless Communication. Prentice Hall, 2001.

22. D. Burshtein, M. Krivelevich, S. Litsyn,, G. Miller. Upper bounds on the rate of ldpc codes. IEEE Transaction on Information Theory, 48(9):2437, Sept. 2002.

23. D. Burshtein, G. Miller. Bounds on the performance of belief propagation decoding. IEEE Trans. Inform. Theory, 48:112-122, Jan. 2002.

24. G. Caire, G. Taricco,, E. Biglieri. Bit-interleaved coded modulation. IEEE Trans. Inform. Theory, 44(3):927-946, May 1998.

25. C.-L. Chen. On Majority-Logic Decoding of Finite Geometry Codes. IEEE Transactions on Information Theory, IT-17(3):332-336, May 1971.

26. J. Chen, M. P. C. Fossorier. Decoding low-density parity-check codes with normalized APP-based algorithm, in Proc. IEEE Globecom, pages 1026-1030, Nov. 2001.

27. M. C. Davey, D. J. C. MacKay. Low density parity check codes over GF(q). IEEE Communications Letters, 2(6): 165-167, June 1998.

28. I. Djurdjevic, J. Xu, K. Abdel-Ghaffar,, S. Lin. A Class of Low-Density Parity-Check Codes Constructed Based on Reed-Solomon Codes With Two Information Symbols. IEEE Communications Letters, 7(7), July 2003.

29. A. W. Eckford, F. R. Kschischang,, S. Pasupathy. Analysis of LDPC Codes in Channels with Memory. In 21st Biennial Symposium on Communications, Kingston, Ontario, Canada, 2002.

30. A. W. Eckford, F. R. Kschischang,, S. Pasupathy. Designing Very Good Low-Density Parity-Check Codes for the Gilbert-Elliott Channel. In 8th Canadian Workshop on Information Theory, Waterloo, Ontario, Canada, 2003.

31. E. Eleftheriou, T. Mittelholzer,, A. Dholakia. Reduced-complexity decoding algorithm for low-density parity-check codes. IEE Electronics Letters, 37:102104, Jan. 2001.

32. E. O. Elliott. Estimates of error-rates for codes on burst-noise channels. Bell Sys. Tech. J., 42:1977-1997, Sept. 1963.

33. G. D. Forney, T. J. Richardson, R. L. Urbanke,, S.-Y. Chung. On the Design of Low-Density Parity-Check Codes within 0.0045 db of the Shannon Limit. IEEE Communications Letters, 5(2), Feb. 2001.

34. M. Fossorier, M. Mihaljevic,, H. Imai. Reduced Complexity Iterative Decoding of Low-Density Parity-Check Codes Based on Belief Propagation. IEEE Transactions on Communications, 47(5), May 1999.

35. G. D. Forney Jr. Codes on graphs: Normal realizations. IEEE Trans. Inform. Theory, 47, Feb. 2001.

36. R. G. Gallager. Low density parity check codes. IRE Transactions on Information Theory, Jan. 1962.

37. R. G. Gallager. Low Density Parity Check Codes. Cambridge, MA: MIT Press, 1963.

38. E.N.Gilbert. Capacity of a burst-noise channel. Bell Sys. Tech. J., 39:12531265, Sept. 1960.

39. E. N. Gilbert. A problem in binary encoding. In Proceedings of the Symposium in Applied Mathematics, volume 10, pages 291-297, 1960.

40. J. Hou, P. H. Siegel,, L. B. Milstein. Performance Analysis and Code Optimization of Low Density Parity-Check Codes on Rayleigh Fading Channels. IEEE Journal on Selected Ares in Communications, 19:924-934, May 5.

41. J. Hou, P. H. Siegel, L. B. Milstein,, H. D. Pfister. Capacity-approaching bandwidth-efficient coded modulation schemes based on low-density parity-check codes. IEEE Transactions On Information Theory, 49(9):2141—2155, September 2003.

42. X.-Y. Ни, E. Eleftheriou,, D.-M. Arnold. Regular and Irregular Progressive Edge-Growth Tanner Graphs. IBM Research, Zurich Research Laboratory, 2003.

43. D. Husli, E. Svensson,, D. Arnold. High-rate low-density parity-check codes: construction and application, in Proc. 2nd Int. Symposium on Turbo Codes and Related Topics, Brest, France, pages 447-450, Sept. 2000.

44. H. Imai, S. Hirakawa. A new multilevel coding method using error correcting codes. IEEE Transactions on Information Theory, 23(3):371-377, May 1977.

45. T. Kasami, S. Lin. On Majority-Logic Decoding for Duals of Primitive Polynomial Codes. IEEE Transactions on Information Theory, IT-17(3):322-331, May 1971.

46. Т. Kasami, S. Lin,, W. W. Peterson. Polynomial Codes. IEEE Transactions on Information Theory, 14, 1968.

47. Y. Kou, S. Lin,, Marc P.C.Fossorier. Low-Density Parity-Check Codes Based on Finite Geometries: A Rediscovery and New Results. IEEE Transactions on Information Theory, 47(7), Nov. 2001.

48. Y. Kou, S. Lin,, M.P.C. Fossorier. Construction of low-density parity-check codes: A geometric approach. In Proc. 2nd Int. Symp. Turbo Codes and Related Topics, pages 137-140, Brest, France, Sept. 2000.

49. E. A. Krouk, S. V. Semenov. Low-density parity-check burst error-correcting codes. In 2 International Workshop "Algebraic and combinatorial coding theory", Leningrad, pages 121-124, 1990.

50. F. R. Kschischang, B. Frey„ H.-A. Loeliger. Factor graphs and the sum-product algorithm. IEEE Trans. Inform. Theory, 47(2), 2001.

51. G. Lechner. Convergence of Sum-Product Algorithm for Finite Length Low-Density Parity-Check Codes. Winter School on Coding and Information Theory, Monte Verita, Switzerland, Feb. 24-27, 2003.

52. S. Lin. On the Number of Information Symbols in Polynomial Codes. IEEE Transactions on Information Theory, 18(6):785-794, Nov. 1972.

53. S. Lin. Shortened Finite Geometry Codes. IEEE Transactions on Information Theory, 18(5):692-696, Sept. 1972.

54. S. Litsyn, V. Shevelev. On ensembles of low-density parity-check codes: distance distributions. IEEE Trans. Inform. Theory, submitted for publication.

55. M. Luby, М. Mitzenmacher, A. Shokrollahi, D. Spielman,, V. Stemann. Practical loss-resilient codes, in Proc. 29th Annual ACM Symp. Theory of Computing, pages 150—159, 1997.

56. M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi,, D. A. Spielman. Improved low-density parity-check codes using irregular graphs and belief propagation. In Proceedings of the IEEE International Symposium on Informati on Theory (ISIT), page 117, 1998.

57. R. Lucas, M. P. C. Fossorier, Y. Kou,, S. Lin. Iterative decoding of one-step majority logic decodable codes based on belief propagation. IEEE Trans. Commun., 48(6) :931—937, June 2000.

58. D. MacKay. Good error correcting codes based on very sparse matrices. IEEE Transactions on Information Theory, 45, Mar. 1999.

59. D. MacKay, R. Neal. Near Shannon Limit Performance of Low-Density Parity-Check Codes. IEEE Transactions on Information Theory, 47(2), Feb. 2001.

60. D. J. C. MacKay, S. T. Wilson,, M. C. Davey. Comparison of constructions of irregular Gallager codes, in Proc. 36th Allerton Conf. Communication, Control, and Computing, Sept. 1998.

61. Y. Mao, A. H. Banihashemi. Decoding low-density parity-check codes with probabilistic scheduling. IEEE Commmunications Letters, 5:414-416, Oct. 2001.

62. G. Miller, D. Burshtein. Bounds on the maximum likelihood decoding error probability of low density parity check codes. IEEE Trans. Inform. Theory, 47:2696-2710, Nov. 2001.

63. P. G. Neumann. A note on Gilbert burst-correcting codes. IEEE Transactions on Information Theory, IT-11:377, July 1965.

64. H. Niu, M. Shen, J. Ritcey,, H. Liu. Iterative Channel Estimation and LDPC Decoding over Flat-Fading Channels: A Factor Graph Approach. 2003 Conference on Information Sciences and Systems, The Johns Hopkins University, March 12-Ц, 2003.

65. A. Ovchinnikov. A class of binary burst error-correcting codes. In EuroXChange, volume 2, 1999.

66. A. Ovchinnikov. About modification of one class of burst error-correcting codes. In EuroXChange, volume 3, 2000.

67. L. Ping, W. K. Leung. Decoding low density parity check codes with finite quantization bits. IEEE Commun. Lett., 4:62-64, Feb. 2000.

68. E. A. Ratzer. Low-density parity-check codes on Markov channels. In Second IMA Conference on Mathematics in Communications, Dec. 2002.

69. S. Reiger. Codes for the Correction of "clustered" Errors. IRE Trans. Inform. Theory, IT-6:16-21, May 1960.

70. Т. J. Richardson, R. L. Urbanke. The Capacity of low-Density Parity-Check Codes Under Message-Passing Decoding. IEEE Transactions on Information Theory, 47(2), Feb. 2001.

71. T. J. Richardson, R. L. Urbanke. Efficient Encoding of Low-Density Parity-Check Codes. IEEE Transactions on Information Theory, 47(2), Feb. 2001.

72. T. J. Richardson, R. L. Urbanke,, S.-Y. Chung. Analysis of Sum-Product Decoding of low-Density Parity-Check Codes Using a Gaussian Approximation. IEEE Transactions on Information Theory, 47(2), Feb. 2001.

73. T. J. Richardson, R. L. Urbanke,, M. A. Shokrollahi. Design of Capacity-Approaching Irregular low-Density Parity-Check Codes. IEEE Transactions on Information Theory, 47(2), Feb. 2001.

74. J. Rosenthal, P. O. Vontobel. Constructions of LDPC codes using Ramanujan graphs and ideas from Margulis. Proc. 38th Allerton Conference on Communications, Control and Computing, Oct. 2000.

75. D. A. Spielman. Finding good LDPC codes, in Proc. 36th Allerton Conf. Commun. Contr., and Comput., Sept. 1998.

76. M. Tanner. A Recursive Approach to Low Complexity Codes. IEEE Transactions on Information Theory, IT(27):533-547, Sept. 1981.

77. M. Tanner. Minimum distance bounds by graph analysis. IEEE Trans. Inform. Theory, 47:808-821, Feb. 2001.

78. T. Tian, C. Jones, J. Villasenor,, R. Wesel. Construction of Irregular LDPC Codes with Low Error Floors. In Proceedings of ICC'2003, pages 3125-3129, 2003.

79. G. Ungerboeck. Trellis-coded modulation with redundant signal sets Part I: Introduction. IEEE Communications Magazine, 25(2):5 -11, February 1987.

80. G. Ungerboeck. Trellis-coded modulation with redundant signal sets Part II: State of the art. IEEE Communications Magazine, 25(2):12—21, February 1987.

81. U. Wachsmann, R. F. H. Fischer,, J. Huber. Multilevel codes: Theoretical concepts and practical design rules. IEEE Transactions On Information Theory, 45(5):1361—1391, July 1999.

82. T. Woerz, J. Hagenauer. Iterative decoding for multilevel codes using reliability information. In Proceedings of GLOBECOM'92, volume 3, pages 1779-1784, December 1992.

83. W. Zhang, J. Wolf. A Class of Binary Burst Error-Correcting Quasi-Cyclic Codes. IEEE Transactions on Information Theory, IT-34:463-479, May 1988.