Корректирующие свойства недвоичных кодов с малой плотностью проверок тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Фролов, Алексей Андреевич

• Фролов, Алексей Андреевич
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Фролов, Алексей Андреевич

Содержание

Введение

Обзор литературы

Глава 1. Потенциальные корректирующие свойства недвоичных МПП-кодов

1.1. Введение

1.2. Структура МПП-кодов над полем

1.3. Нижняя оценка минимального кодового расстояния для МПП-кодов над полем

1.4. Верхняя оценка минимального кодового расстояния для МПП-кодов над полем

1.5. Анализ результатов

1.6. Выводы к главе

Глава 2. Реализуемые корректирующие свойства недвоичных МПП-кодов

2.1. Введение

2.2. Асимптотическая оценка доли ошибок, исправимых МПП-кода-

ми над полем

2.3. Результаты имитационного моделирования

2.4. Выводы к главе

Глава 3. Применение недвоичных МПП-кодов в сигнально-кодо-

вой конструкции для системы множественного доступа

3.1. Введение

3.2. Описание сигнально-кодовой конструкции для векторного дизъ-

юнктивного канала

3.3. Асимптотическая оценка относительной суммарной скорости передачи

3.4. Модифицированный вариант сигнально-кодовой конструкции

для векторного канала с АБГШ

3.5. Результаты имитационного моделирования

3.6. Выводы к главе

Заключение

Литература

Введение диссертации (часть автореферата) на тему «Корректирующие свойства недвоичных кодов с малой плотностью проверок»

Введение

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

Для исправления ошибок используют помехоустойчивые коды. Важнейшим обстоятельством при выборе той или иной кодовой конструкции на практике является наличие быстрых алгоритмов кодирования и декодирования. Двоичные коды с малой плотностью проверок (МПП-коды) удовлетворяют этому требованию. Однако не менее важно, чтобы алгоритмы декодирования были способны исправить большое число ошибок. Таким образом, главным вопросом является вопрос о том, насколько ухудшаются корректирующие свойства кодов при использовании простых алгоритмов декодирования. Исследованию двоичных МПП-кодов посвящено множество работ, среди которых следует особо отметить работы таких русских и зарубежных ученых, как Р. Дж. Галлагер, М. С. Пинскер, В. В. Зяблов, К. Ш. Зигангиров, А. М. Барг, Р. Таннер, Д. Спилман, Д. Маккей, Т. Ричардсон, Р. Урбанке, Д. Бурштейн, С. Л. Литсын, Ж. Земор. Доказано существование двоичных МПП-кодов, способных исправить линейно растущее с длиной кода число ошибок при сложности декодирования 0(п log2 п), где п - длина кода. Как результат, в настоящее время эти коды используются в стандартах подвижной беспроводной связи (например, LTE), цифровой телефонии; рекомендованы для использования в стандартах оптической связи, спутниковой связи, WiMAX, 802.lin.

Все исследования будем проводить для радиочастотного канала; пусть весь диапазон частот разбит на непересекающиеся частотные поддиапазоны

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

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

Цель диссертационной работы: исследовать корректирующие свойства недвоичных МПП-кодов теоретически и методом имитационного моделирования, а также разработать сигнально-кодовую конструкцию (СКК) на основе недвоичных МПП-кодов для системы множественного доступа.

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

о Исследовать потенциальные корректирующие свойства МПП-кодов над полем GF(q).

о Исследовать реализуемые корректирующие свойства МПП-кодов над

полем GF(q) теоретически и методом имитационного моделирования.

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

Научная новизна. В настоящей работе впервые:

о Теоретически исследованы потенциальные и реализуемые корректирующие свойства МПП-кодов над полем GF(q).

о Предложен алгоритм декодирования МПП-кодов над полем GF(q) с вводом стираний.

о МПП-коды над полем GF(q) использованы в СКК для системы множественного доступа.

Теоретическая и практическая ценность. Получены верхняя и нижняя границы минимального кодового расстояния для МПП-кодов над полем GF{q). Улучшена асимптотическая оценка доли ошибок, гарантированно исправимых МПП-кодами над полем GF(q) с помощью алгоритма, имеющего сложность 0(nlog2n). Получена нижняя оценка относительной суммарной скорости передачи для системы множественного доступа, использующей бесшумный векторный дизъюнктивный канал. Эта оценка асимптотически совпадает с верхней оценкой.

Результаты, полученные в процессе подготовки диссертационной работы, использованы в программе фундаментальных исследований Президиума РАН «Проблемы создания национальной научной распределенной информационно-вычислительной среды на основе GRID технологий и современных телекоммуникационных сетей» по направлению «Распределенная обра-

ботка данных. Информационная безопасность сетевых технологий» (№ Госрегистрации 01200965142), программе фундаментальных научных исследований ОНИТ РАН «Архитектура, системные решения, программное обеспечение стандартизация и информационная безопасность информационно-вычислительных комплексов новых поколений» по направлению № 3.1 «Обеспечение информационной безопасности распределенных информационно-вычислительных систем» (Регистрация РАН № 10002-251/ШТВС-04/103-96/260503-208) и разработках ЗАО «Телум», что подтверждено соответствующими актами.

На защиту выносятся следующие положения:

1. Верхняя и нижняя границы минимального кодового расстояния для МПП-кодов над полем GF(q).

2. Асимптотическая оценка доли ошибок, гарантированно исправимых МПП-кодами над полем GF(q) с помощью алгоритма декодирования, имеющего сложность 0(nlog2n).

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

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

Апробация работы. Основные результаты диссертации докладывались на следующих конференциях: IEEE International Symposium on Information Theory (2011); XII International Symposium on Problems of

Redundancy in Information and Control Systems (2009); XII International Workshop on Algebraic and Combinatorial Coding Theory (2010); конференциях молодых ученых и специалистов ИППИ РАН «Информационные технологии и системы» (2009-2011). Кроме того, основные результаты докладывались на семинарах по теории кодирования в ИППИ РАН.

Публикации. Материалы диссертации опубликованы в 10 печатных работах, из них 4 статьи [11, 14, 20, 21] в рецензируемых журналах и 6 статей [12, 13, 17, 47-49] в сборниках трудов конференций.

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

Структура и объем диссертации Диссертация состоит из введения, обзора литературы, трех глав, заключения и библиографии. Общий объем диссертации 117 страниц, включая 64 рисунка и 8 таблиц. Библиография включает 83 наименования на 10 страницах.

Обзор литературы

МПП-коды были предложены Р. Дж. Галлагером в [7] в 1960 году. В этой работе были получены нижняя оценка минимального кодового расстояния и оценка вероятности ошибки при декодировании по минимуму расстояния. Кроме того были предложены алгоритмы декодирования, подходящие для практического применения (алгоритм распространения доверия1 и мажоритарный алгоритм). В 1974 г. В. В. Зяблов и М. С. Пинскер доказали существование МПП-кодов, способных исправить линейную долю стираний при декодировании с помощью алгоритма, имеющего сложность 0(nlog2n). В 1975 г. ими был получен аналогичный результат для ошибок. В 1981 г. в работе [77] Р. Таннер предложил метод построения длинных кодов из коротких кодов компонентов. Конструкция МПП-кодов Галлагера является частным случаем конструкции Таннера и получается из нее, если использовать код с двоичной проверкой на четность в качестве компонентного кода. Таким образом, коды построенные Таннером можно назвать обобщенными МПП-кодами. После этого ввиду слабого развития вычислительной техники МПП-коды были на долгое время забыты.

Активное исследование МПП-кодов началось в середине 90-х годов в связи с появлением работ М. Сипсера, Д. Спилмана [74, 76] и Д. Маккея [61]. Можно выделить несколько основных направлений исследований этих кодов:

о исследование мажоритарного алгоритма декодирования [10, 15];

о исследование алгоритма распространения доверия [27, 32, 35, 37, 38, 54, 62, 69];

о исследование исправления стираний [9, 41];

1 в англоязычной литературе используется термин "belief propagation"

о исследование вероятности ошибочного декодирования [23, 29-31, 72];

о исследование распределения весов [33, 42, 56, 66];

о исследование нерегулярных МПП-кодов [57, 60, 61, 71];

о исследование сложности кодирования МПП-кодов [58, 70];

о построение явных конструкций МПП-кодов [16, 59];

о построение проверочных матриц МПП-кодов со специальными свойствами [22, 36, 44-46, 50].

Недвоичные МПП-коды впервые рассмотрены в работе М. Дэви и Д. Маккея [39]. В этой работе предложен алгоритм декодирования, являющийся обобщением алгоритма распространения доверия для двоичного случая, и проведено исследование методом имитационного моделирования. Число работ, посвященных исследованию недвоичных МПП-кодов, сравнительно невелико. В существующих работах по этой теме [26, 40, 43, 51, 53, 64, 65, 67, 68, 73, 78-81] приводятся упрощенные варианты алгоритма декодирования и результаты исследований этих модифицированных алгоритмов методом имитационного моделирования.

Заключение диссертации по теме «Теоретические основы информатики», Фролов, Алексей Андреевич

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

1. Построены верхняя и нижняя границы минимального кодового расстояния для МПП-кодов над полем GF(q);

2. Предложен мажоритарный алгоритм декодирования МПП-кодов над полем GF(q);

3. Улучшена асимптотическая оценка доли ошибок, гарантированно исправимых с помощью алгоритма, имеющего сложность 0(nlog2n);

4. Предложен алгоритм декодирования с вводом стираний, способный работать в канале с ошибками и стираниями. Этот алгоритм лучше мажоритарного алгоритма при условии наличия только ошибок в принятом слове;

5. Показано, что МПП-коды над полем GF(q) гораздо более эффективны, чем двоичные, в qCK и канале с АБГШ при ЧПМ;

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

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

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Фролов, Алексей Андреевич, 2012 год

Литература

1. Бассалыго Л. А. Формализация задачи о сложности задания кода // Про-бл. передачи информ. 1976. Т. 12, № 4. С. 105-106.

2. Бассалыго Л. А. Модель ограниченного асинхронного множественного доступа при наличии ошибок // Пробл. передачи информ. 2009. Т. 45, № 1. С. 41-50.

3. Бассалыго Л. А., Пинскер М. С. Вычисление асимптотики суммарной пропускной способности М-частотного бесшумного канала с множественным доступом для Т пользователей // Пробл. передачи информ. 2000. Т. 36, № 2. С. 3—9.

4. Блох Э. Л., Зяблов В. В. Обобщенные каскадные коды. Москва: Связь, 1976.

5. Блох Э. Л., Зяблов В. В. Линейные каскадные коды. Москва: Наука, 1982.

6. Вильхельмссон Л., Зигангиров К. Ш. Об асимптотической пропускной способности одного многопользовательского канала // Пробл. передачи информ. 1997. Т. 33, № 1. С. 12-20.

7. Галлагер Р. Коды с малой плотностью проверок на четность. Москва: Мир, 1966.

8. Гобер П., ХанВинк А. Замечание к статье Л. Вильхельмссона и К.Ш. Зигангирова "Об асимптотической пропускной способности одного многопользовательского канала" // Пробл. передачи информ. 2000. Т. 36, № 1. С. 21-25.

9. Зигангиров Д. К., Зигангиров К. Ш. Декодирование низкоплотностных кодов с проверочными матрицами, составленными из перестановочных матриц, при передаче по каналу со стираниями // Пробл. передачи ин-форм. 2006. Т. 42, № 2. С. 44-52.

10. Зигангиров К. Ш., Лентмайер М. Математический анализ одного итеративного алгоритма декодирования низкоплотностных кодов // Пробл. передачи информ. 2000. Т. 36, № 4. С. 35-46.

11. Зяблов В. В., Рыбин П. С., Фролов А. А. Алгоритм декодирования с вводом стираний для МПП-кодов, построенных над полем СР^) // Информационно-Управляющие Системы. 2011. Т. 50, К2 1. С. 62-68.

12. Зяблов В. В., Фролов А. А. Сравнение корректирующей способности МПП-кодов с кодами-компонентами разной избыточности // Информационные технологии и системы (ИТиС'09), пос. д/о Бекасово, Россия. 2009. — Дек. С. 160-163.

13. Зяблов В. В., Фролов А. А. Исследование корректирующих свойств МПП-кодов с кодом-компонентом Рида-Соломона // Информационные технологии и системы (ИТиС'10), г. Геленджик, Россия. 2010. — Сент. С. 74-78.

14. Зяблов В. В., Фролов А. А. Сигнально-кодовая конструкция для системы множественного доспупа, использующей векторный канал с аддитивным белым гауссовским шумом // Информационные процессы. 2012. Т. 12, № 1. С. 98-104.

15. Ковалев С. И. Декодирование низкоплотностных кодов // Пробл. передачи информ. 1991. Т. 27, № 4. С. 51-56.

16. Маргулис Г. А. Явные конструкции расширителей // Пробл. передачи информ. 1973. Т. 9, № 4. С. 71-80.

17. Осипов Д. С., Фролов А. А., Зяблов В. В. Сигнально-кодовая конструкция на базе q-ичных кодов для защиты от сосредоточенных помех // Информационные технологии и системы (ИТиС'11), г. Геленджик, Россия. 2011.-Окт. С. 167-173.

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

19. Форни Д. Каскадные коды. Москва: Мир, 1970.

20. Фролов А. А., Зяблов В. В. Асимптотическая оценка доли ошибок, исправляемых q-ичными МПП-кодами // Пробл. передачи информ. 2010. Т. 46, № 2. С. 47-65.

21. Фролов А. А., Зяблов В. В. Границы минимального кодового расстояния для недвоичных кодов на двудольных графах // Пробл. передачи информ. 2011. Т. 47, № 4. С. 27-42.

22. Шридхаран А., Лентмайер М., Трухачев Д. В. и др. О минимальном расстоянии низкоплотностных кодов с проверочными матрицами, составленными из перестановочных матриц // Пробл. передачи информ. 2005. Т. 41, № 1. С. 39-52.

23. Barak О., Burshtein D. Lower Bounds on the Error Rate of LDPC Code Ensembles // IEEE Transactions on Inform. Theory. 2007. Vol. 53, no. 11. P. 4225-4236.

24. Barg A., Mazumdar A., Zemor G. Weight distribution and decoding of codes on hypergraphs // Advances in Mathematics of Communications. 2008. Vol. 2, no. 4. P. 433-450.

25. Barg A., Zemor G. Distance Properties of Expander Codes // IEEE Trans. Inf. Theory. 2006. Vol. 52, no. 1. P. 78-90.

26. Barnault L., Declercq D. Fast Decoding Algorithm for LDPC over GF(2q) // Proc. Inform. Theory Workshop. 2003. P. 70-73.

27. Bazzi L., Richardson T., Urbanke R. Exact thresholds and optimal codes for the binary-symmetric channel and Gallager's decoding algorithm A // IEEE Trans. Inform. Theory. 2004. Vol. 50, no. 9. P. 2010-2021.

28. Boutros J., Pothier O., Zemor G. Generalized Low Density (Tanner) Codes /'/ IEEE Int. Conf. Communications, Vancouver, BC, Canada. Vol. 1. 1999. P. 441—445.

29. Burshtein D., Barak O. Upper Bounds on the Error Exponents of LDPC Code Ensembles // Proc. IEEE International Symposium on Information Theory, Seattle, Washington. 2006.-July. P. 401-405.

30. Burshtein D., Krivelevich M., Litsyn S. L., Mille G. Upper bounds on the rate of LDPC codes // IEEE Trans. Inform. Theory. 2002. Vol. 48, no. 9. P. 2437-2449.

31. Burshtein D., Mille G. Bounds on the maximum-likelihood decoding error probability of low-density parity-check codes //' IEEE Transactions on Inform. Theory. 2001. Vol. 47, no. 7. P. 2696-2710.

32. Burshtein D., Miller G. Bounds on the performance of belief propagation decoding // IEEE Trans. Inform. Theory. 2002. Vol. 48, no. 1. P. 112-122.

33. Burshtein D., Miller G. Asymptotic enumeration methods for analyzing LDPC codes // IEEE Transactions on Inform. Theory. 2004. Vol. 50, no. 6. P. 1115-1131.

34. Chang S. C., Wolf J. K. On the T-User M-Frequency Noiseless Multiple-Access Channels with and without Intensity Information //' IEEE Trans. Inform. Theory. 1981. Vol. 27, no. 1. P. 41-48.

35. Chen J., Dholakia A., Eleftheriou E. et al. Reduced-complexity decoding of LDPC codes // IEEE Trans. Commun. 2005. Vol. 53, no. 8. P. 1288-1299.

36. Chung S. Y., Forney G. D.; Richardson T., Urbanke R. On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit // IEEE Commun. Lett. 2001. Vol. 5, no. 2. P. 58-60.

37. Chung S. Y., Richardson T., Urbanke R. Gaussian approximation for sum-product decoding of low-density parity-check code // Proc. of the IEEE Int. Symposium on Inform. Theory, Sorrento, Italy. 2000. — June. P. 318.

38. Chung S. Y., Richardson T., Urbanke R. Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation // IEEE Trans. Inform. Theory. 2001. Vol. 47, no. 2. P. 657-670.

39. Davey M., MacKay D. J. C. Low Density Parity Check Codes over GF(q) // IEEE Commun. Lett. 1998. Vol. 2, no. 6. P. 165-167.

40. Declercq D., Fossorier M. Decoding Algorithms for Nonbinary LDPC Codes Over GF(q) // IEEE Trans. Communications. 2007. Vol. 55, no. 4. P. 633-643.

41. Di C., Proietti D., Richardson T. et al. Finite Length Analysis of Low-Density Parity- Check Codes on the Binary Erasure Channel // IEEE Transactions on Information Theory. 2002. Vol. 48, no. 6. P. 1570-1579.

42. Di C., Richardson T., Urbanke R. Weight Distribution of Low-Density Parity-Check Codes // EEE Transactions on Inform. Theory 2006. Vol. 52, no. 11. P. 4839-4855.

43. Divsalar D., Dolecek L. Ensemble analysis of pseudocodewords of protograph-based non-binary LDPC codes // Proc. Information Theory Workshop. 2011. P. 340-344.

44. Divsalar D., Jones C. R., Dolinar S., Thorpe J. Protograph based LDPC codes with minimum distance linearly growing with block size // Proc. of GLOBECOM, St. Louis, Missouri. 2005.-Nov. P. 1152-1156.

45. Djurdjevic I., Xu J., Abdel-Ghaffar K., Lin S. A class of low-density parity-check codes constructed based on Reed-Solomon codes with two information symbols // IEEE Commun. Lett. 2003. Vol. 7, no. 7. P. 317-319.

46. Fossorier P. C. Quasi-cyclic low-density parity-check codes from circulant permutation matrices // IEEE Trans. Inform. Theory. 2004. Vol. 50, no. 8. P. 1788-1793.

47. Frolov A., Zyablov V. The Application of Q-ary LDPC-codes for Fiber Optic Lines // Proc. of XII International Symposium on Problems of Redundancy in Information and Control Systems, Saint-Petersburg, Russia. 2009. — May. P. 121-125.

48. Frolov A., Zyablov V. Insertion of Erasures as a Method of Q-ry LDPC Codes Decoding // Proc. of XII International Workshop on Algebraic and Combinatorial Coding Theory (ACCT 2010), Akademgorodok, Novosibirsk, Russia. 2010.-Sept. P. 138-143.

49. Frolov A., Zyablov V. Upper and Lower Bounds on the Minimum Distance of Expander Codes // Proc. of IEEE International Symposium on Information Theory (ISIT 2011), Saint-Petersburg, Russia. 2011. — Jul./Aug. P. 1302-1306.

50. Gabidulin E., Moinian A., Honary B. Generalized construction of quasi-cyclic regular LDPC codes based on permutation matrices // Proc. IEEE Int. Symp. Inf. Theory, Seattle, Washington. 2006. - July. P. 679-683.

51. Ganepola V. S., Carrasco R. A., Wassell I. J., Goff S. L. Performance study of non-binary LDPC Codes over GF(q) // Proc. International Symposium on Communication Systems. 2008. P. 585-589.

52. HanVinck A. J., Keuning J. On the Capacity of the Asynchronous T-User M-Frequency Noiseless Multiple-Access Channel without Intensity Information // IEEE Trans. Inform. Theory. 1996. Vol. 42, no. 6. P. 2235-2238.

53. Kelley C. A., Sridhara D., Rosenthal J. Pseudocodeword weights for non-binary LDPC codes // Proc. IEEE International Symposium on Information Theory. 2006. P. 1379-1383.

54. Kschischang F. R., Frey B. J., Loeliger H. A. Factor graphs and the sum-product algorithm // IEEE Trans. Inform. Theory. 2001. Vol. 47, no. 2. P. 498-519.

55. Lentmaier M., Zigangirov K. S. On Generalized Low-Density Parity-Check Codes Based on Hamming Component Codes // IEEE Commun. Lett. 1999. Vol. 3, no. 8. P. 248—260.

56. Litsyn S., Shevelev V. On Ensembles of Low-Density Parity-Check Codes: Asymptotic Distance Distributions // IEEE Transactions on Inform. Theory. 2002. Vol. 48, no. 4. P. 887-908.

57. Litsyn S. L., Shevelev V. S. Distance distribution in ensembles of irregular low-density parity-check codes // IEEE Trans. Inform. Theory. 2003. Vol. 49, no. 12. P. 3140-3159.

58. Lu J., Moura J. M. F. Linear Time Encoding of LDPC Codes // IEEE Trans. Inform. Theory. 2010. Vol. 56, no. 1. P. 233-249.

59. Lubotzky A., Phillips R., Sarnak P. Ramanujan graphs // Combinatorica. 1988. Vol. 8, no. 3. P. 261-277.

60. Luby M., Mitzenmacher M., Shokrollahi A., Spielman D. Improved low-density parity-check codes using irregular graphs // IEEE Trans, on Inform. Theory. 2001. Vol. 47, no. 2. P. 585-598.

61. MacKay D. J. C. Good error correcting codes based on very sparse matrices // IEEE Trans. Info. Theory. 1999. Vol. 45, no. 2. P. 399-431.

62. Mao Y., Kschischang F. R. On factor graphs and the Fourier transform // IEEE Trans. Inform. Theory. 2005. Vol. 51, no. 5. P. 1635-1649.

63. McEliece R., Rodemich E., Rumsey H., Welch L. New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities // IEEE Trans. Inform. Theory. 1977. Vol. 23, no. 2. P. 157-166.

64. Nozaki T., Kasai K., Sakaniwa K. Error floors of non-binary LDPC codes // Proc. IEEE International Symposium on Information Theory. 2010. P. 729-733.

65. Poulliat C., Fossorier M., Declercq D. Design of non binary LDPC codes using their binary image: algebraic properties // Proc. IEEE International Symposium on Information Theory. 2006. P. 93-97.

66. Rathi V. On the Asymptotic Weight and Stopping Set Distribution of Regular LDPC Ensembles // IEEE Transactions on Inform. Theory. 2006. Vol. 52, no. 9. P. 4212-4218.

67. Rathi V., Andriyanova I. Some Results on MAP Decoding of Non-Binary LDPC Codes Over the BEC // IEEE Trans. Inform. Theory. 2011. Vol. 57, no. 4. P. 2225-2242.

68. Rathi V., Urbanke R. Density evolution, thresholds and the stability condition for non-binary LDPC codes // IEE Proceedings Communications. 2005. Vol. 152, no. 6. P. 1069-1074.

69. Richardson T., Urbanke R. The Capacity of Low-Density Parity-Check Codes Under Message-Passing Decoding // IEEE Trans. Inform. Theory. 2001. Vol. 47, no. 2. P. 599-618.

70. Richardson T., Urbanke R. Efficient encoding of low-density parity-check codes // IEEE Trans. Inform. Theory. 2001. Vol. 47, no. 2. P. 638-656.

71. Richardson T. J., Shokrollahi M. A., Urbanke R. L. Design of capacity-approaching irregular low-density parity check codes. //' IEEE Trans, on Inform. Theory. 2001. Vol. 47, no. 2. P. 619-637.

72. Sason I., Shamai S. Improved upper bounds on the ensemble performance of ML decoded low density parity check codes // IEEE Comrnun. Lett. 2000. Vol. 4, no. 3. P. 89-91.

73. Savin V. Min-Max decoding for non binary LDPC codes // Proc. IEEE International Symposium on Information Theory. 2008. P. 960-964.

74. Sipser M., Spielman D. Expander codes // IEEE Trans. Inf. Theory. 1996. — Nov. Vol. 42, no. 6. P. 1710-1722.

75. Skachek V. Minimum distance bounds for expander codes // Information Theory and Applications Workshop. 2008. - Jan./Feb. P. 366-370.

76. Spielman D. A. Linear-time encodable and decodable error-correcting codes // IEEE Trans. Inf. Theory. 1996.-Nov. Vol. 42, no. 6. P. 1723-1731.

77. Tanner R. A recursive approach to low complexity codes /7 IEEE Trans. Inf. Theory. 1981. Vol. 27, no. 5. P. 533-547.

78. Voicila A., Declercq D., Verdier F. et al. Architecture of a low-complexity non-binary LDPC decoder // Proc. International Conference on Consumer Electronics. 2008. P. 1-2.

79. Voicila A., Declercq D., Verdier F. et al. Low-complexity decoding for non-binary LDPC codes in high order fields // IEEE Trans. Communications. 2010. Vol. 58, no. 5. P. 1365-1375.

80. Wymeersch H., Steendam H., Moeneclaey M. Log-Domain Decoding of LDPC Codes over GF(q) // The Proc. IEEE Intern. Conf. on Commun. 2004. P. 772-776.

81. Xinmiao Z., Fang C. Reduced-complexity extended Min-sum check node processing for non-binary LDPC decoding // Proc. IEEE International Midwest Symposium on Circuits and Systems. 2010. P. 737-740.

82. Zigangirov K. S. Theory of Code Division Multiple Access Communication. New Jersey: John Whiley and Sons, 2004.

83. Zyablov V., Potapov V., Groshev F. Low-complexity error correction in LDPC codes with constituent RS codes // Proc. of XI International Workshop on Algebraic and Combinatorial Coding Theory (ACCT'2008), Pamporovo, Bulgaria. 2008. - June. P. 348-353.