автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Обработка информации при передаче LDPC-кодами по дискретным и полунепрерывным каналам

На правах рукописи

Овчинников Андрей Анатольевич

ОБРАБОТКА ИНФОРМАЦИИ ПРИ ПЕРЕДАЧЕ LDPC КОДАМИ ПО ДИСКРЕТНЫМ И ПОЛУНЕПРЕРЫВНЫМ КАНАЛАМ

Специальность: 05.13.01 "Системный анализ, управление и обработка информации (в технике и технологиях)"

Автореферат диссертации на соискание ученой степени кандидата технических наук

Санкт- Петербург 2004

Работа выполнена на кафедре безопасности информационных систем Государственного образовательного учреждения высшего профессионального образования "Санкт-Петербургский государственный университет аэрокосмического приборостроения" (ГУАП)

Научный руководитель:

доктор технических наук, профессор Крук Евгений Аврамович

Официальные оппоненты:

доктор технических наук, профессор Ерош Игорь Львович кандидат физико-математических наук, старший научный сотрудник Кабатянский Григорий Анатольевич

Ведущая организация:

Ленинградский отраслевой научно-исследовательский институт связи

Защита состоится г. в 15 час. 00 мин. на засе-

дании диссертационного совета Д 212.233.02 при Государственном образовательном учреждении высшего профессионального образования "Санкт-Петербургский государственный университет аэрокосмического приборостроения" по адресу: 190000, г. Санкт-Петербург, ул. Большая Морская,

Д-67.

С диссертацией можно ознакомиться в библиотеке ГУАП

Автореферат разослан

Ученый секретарь диссертационног

Л

Л.А.Осипов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

• исследование конструкций LDPC-кодов;

• разработка новых методов построения LDPC-кодов;

• исследование и построение конструкций LDPC-кодов для каналов с памятью;

• исследование выгодности применения LDPC-кодов в реальных каналах связи.

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА С.Пете^бург /

09 280,

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

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

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

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

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

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

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

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

Апробация результатов работы.

Основные положения и результаты диссертации докладывались и обсуждались на V, VI, VII научных сессиях аспирантов ГУЛП (г. Санкт-Петербург 2002, 2003, 2004), II, IV международной школе-семинаре БИ-КАМГГ99 и БИКАМП'ОЗ (г. Санкт-Петербург), а также на семинарах кафедры "Безопасности информационных систем" ГУАП (2000-2004) и кафедры 'Распределенных вычислений и компьютерных сетей" СПбГПУ.

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

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

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

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

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

Структура работы. Диссертационная работа изложена на 141 странице и состоит из введения, 4-х глав с выводами, заключения, списка использованных источников литературы, включающего 84 наименования, и приложения. Основное содержание работы включает 37 рисунков и 9 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

В первом разделе дается обзор кодов с малой плотностью проверок на четность (LDPC-кодов). В параграфе 1.1 приводятся основные определения и результаты в области LDPC-кодов. В параграфе 1.2 кратко описаны стандартные процедуры декодирования для дискретных и полунепрерывных каналов без памяти. Параграф 1.3 рассматривает нерегулярные LDPC-коды, приводит известные результаты по оптимизации распределений весов строк и столбцов проверочной матрицы LDPC-кода, позволяющей снизить вероятность ошибки при декодировании в области малого отношения сигнал/шум, а также описывает конструкцию LDPC-кодов с заданными распределениями весов. Параграф 1.4 дает обзор регулярных конструкций LDPC-кодов, основанных на комбинаторных объектах: конечных геометриях и кодах Рида-Соломона.

Кодом с малой плотностью проверок на четность называется линейный код, проверочная матрица которого содержит мало единиц. Часто код задается графом инцидентности своей проверочной матрицы (т.н. графом Таннера). С помощью графа Таннера часто описывают процедуры декодирования LDPC-кодов, которые итеративно производят пересчет величин, приписываемых вершинам графа Таннера, и по которым затем посимвольно производится принятие решения о том, какой символ передавался.

LDPC-код называется регулярным, если веса строк р и столбцов 7 по-стоянпы, и нерегулярным, в противном случае. В общем случае веса строк и столбцов могут задаваться производящими функциями р[х) и А(ж). Известно, что с помощью оптимизации весовых распределений и можно получать коды, дающие выигрыш по вероятности ошибки на низких отношениях сигнал/шум в ряде каналов связи, в том числе канале с АБГШ. Однако, недостатки такого подхода связаны с тем, что во-первых, такие коде обычно оказываются неэффективными с ростом отношения сигнал/шум, и во-вторых — построение таких кодов связано с эвристическими конструкциями, параметры которых (спектр, минимальное расстояние) трудно оценить аналитически. Качество полученных таким образом кодов, как правило, определяется с помощью моделирования. Примером такой конструкции является конструкция PEG, описанная в параграфе 1.3.

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

подмножества:

^ _ 11, если объект г принадлежит подмножеству в противном случае

Часто полученные таким образом ЬБРС-коды являются циклическими или квазициклическими, что дает выигрыш в эффективности их кодирования, а также в представлении этих кодов при реализации. В параграфе 1.4 рассматриваются такие конструкции, основанные на конечных геометриях (Евклидовых и проективных) и кодах Рида-Соломона. При этом сформулированы свойства, которыми должны обладать регулярные конструкции ЬБРС-кодов:

1. Каждая строка проверочной матрицы Н имеет ровно р единиц;

2. Каждый столбец проверочной матрицы Н имеет ровно 7 единиц;

3. Число ненулевых позиций, в которых совпадают два различных столбца, не превышает единицы.

Свойства 1 и 2 обеспечивают требование регулярности, свойство 3 означает, что длина минимального цикла в графе Таннера больше 4. Наличие в графе Таннера циклов длины 4 может снизить эффективность работы декодера. Выполнение свойства 3 позволяет оценить минимальное расстояние й0 таких кодов: так как столбцы проверочной матрицы имеют не более одной общей ненулевой позиции, и содержат 7 единиц, для того, чтобы получить нулевой синдром, нужно сложить не менее столбцов, таким образом,

¿о>7 + 1- 0)

Однако, оценка (1) во многих случаях является неточной. С другой стороны, она не учитывает известных свойств объектов, положенных в основу ЬБРС-конструкций, это позволяет надеяться, что в ряде случаев оценка (1) может быть уточнена.

Таким образом, подход к построению хороших ЬБРС-кодов можно рассматривать как поиск и исследование конструкций, обладающих свойствами, позволяющими аналитически оценивать полученные коды.

Во втором разделе работы предлагается новая конструкция регулярных ЬБРС-кодов, а также производится анализ дистанционных свойств ряда Евклидово-геометрических ЬБРС-кодов и их укорочений. В параграфе 2.1 и 2.2 рассматриваются коды Гилберта, и на их основе предлагается обобщенная конструкция для построения ЬБРС-кодов, проводится анализ этой конструкции. В параграфе 2.3 получены результаты, улучшающие оценку (1) для ряда Евклидово-геометрических кодов. В параграфе 2.4 приводятся результаты моделирования всех рассматривавшихся конструкций в канале с АБГШ.

Коды Гилберта задаются своей проверочной матрицей

Рис. 1. Циклы в проверочной матрице

где 1т — единичная (т х т)-матрица, С — (т х т)-матрица циклической перестановки:

000

1 о о О 1 о

с =

ООО

1 о

(3)

при этом параметры выбираются так, что £ <т. Очевидно, коды Гилберта являются (2, £)-регулярными ГБРС-кодами с числом единиц в столбце 7 = 2 и в строке р = I. Длина этих кодов ран а число проверочных

символов оценивается как

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

Таким образом, минимальное расстояние ¿о кода Гилберта связано с минимальной длиной до цикла в графе на Рис. 1 а):

(4)

Анализируя расположение блоков в (2), можно доказать следующее утверждение.

Теорема 1 Пусть Я/ ~ матрица вида (2), Zl = {0,1,... ,1—1} —множество вычетов по модулю I. Тогда, если существуют наборы чисел {а<}, {6^ такие, что выполняется равенство:

и>-1

- Ъг) = 0 то<г т.

(5)

¿=о

где

то в коде с проверочной матрицей Н.1 есть слово веса 2и.

Из теоремы 1 следует, что минимальное расстояние и длина минимального цикла кодов Гилберта при £ >3 равны

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

Будем строить обобщения кодов Гилберта дописыванием новых полос к матрице (2). Тогда проверочная матрица таких кодов может быть записала как

Я,

1т 1т /« .. 1т

С0 С1 С2 .. с'-1

С1о3> С«'.31 с43> .. С'«-1

С* С'Г с*' !! с^

(6)

где Я^г — (зх£)-матрица, г^ € {0,... ,тп} — степень матрицы циклической перестановки С, стоящем в уом блоке к-ой полосы.

Очевидно, для существования линейно зависимой комбинации столбцов, граф. аналогичный показанному на Рис. 1 а), должен содержать в своих вертикальных ребрах единицы из всех полос. Если в некоторой матрице (б) с 5 полосами есть замкнутый цикл некоторой длины, то добавлением 1)-ой полосы замкнутый цикл может быть "разорван" (Рис. 1 Ь)). Это может приводить к исключению из кода слов малого веса.

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

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

Рис. 2. Построение кодового слова по графу Таннера

Рассмотрим граф Таннера для проверочной матрицы (6). Структура проверочной матрицы позволяет разбить проверочные вершины графа на 5 частей, Си..., С3, п ояве р ш и н в каждой. Тогда вершины из множества Сх соответствуют 1-й полосе матрицы (6). Аналогичным образом можно разбить символьные вершины на С множеств У1,...,У{, по т вершин в каждом. Тогда справедлива следующая теорема.

Теорема 2 Пусть VI,... ,уы — набор символьных вершин графа Таннера, соответствующего проверочной матрице (6), где и — четно. Пусть С,-, ¿=1,3 — множество проверочных вершин, соответствующих 1-й полосе матрицы (6), как было определено выше. Тогда, если для каждой пары (СьС^), у = 2, в, существует цикл длины 2и в графе Таннера, состоящий из и символьных вершин VI,..., и и проверочных вершин, принадлежащих (С\,С}), то двоичный вектор с ненулевыми позициями VI,... является кодовым словом кода (6) веса из.

Графически существование кодового слова в обобщенном коде Гилберта можно представить как на Рис. 2.

Очевидно, величина минимального расстояния обобщенных кодов Гилберта не превышает так как в коде (б) всегда есть слово такого веса.

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

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

В этом случае получим (7, р) ЬБРС-код с проверочной матрицей

Для случая простого тп можно оценить минимальное расстояние этого кода как

7 + 1 < ¿а < 2тп. (8)

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

В параграфе 2.3 рассматриваются Евклидово-геометрические коды, задаваемые проверочной матрицей

ЯЕС(г

если точка лежит на прямой в противном случае

Рассмотрим прямую в Евклидовой геометрии Прямая содер-

жит точек. Через каждую точку, не лежащую на прямой, можно провести единственную прямую, параллельную данной. Каждая такая прямая также содержит д точек. Так как в геометрии дта точек, всего существует дт-1 ПрЯМЫХ; параллельных друг другу. Назовем построенное таким образом множество прямых параллельным классом. Укорачивая проверочную матрицу Ев-кода на столбцы, соответствующие параллельным классам, мы будем получать код, в котором число единиц в строках и столбцах осталось равным, так как каждая точка геометрии присутствует в параллельном классе ровно один раз. При этом расстояние кода не ухудшилось, а число единиц в строке стало меньшим, что может улучшить работу итеративного декодера.

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

Рассмотрим отдельно случаи Пусть Далее, пусть

1=0

(10)

— весовая функция кода, где Л^ — число слов веса { в коде, х обозначает число нулей, у — число единиц. Тогда справедлива следующая теорема.

Рис. 3. Укорочения кода ЕС(3,23)

Теорема 3 Еслипроверочнаяматрица (9) Евклидово-геометрическогокода при т = 2, д — р", р ф 2, имеет полныйранг, тогда коэффициент А, весовой функции (10) вычисляется как

(11)

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

Следствие 1 Минимальное расстояние кода из Теоремы 3 равно

(12)

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

Теперь рассмотрим случай р = 2. Для поля характеристики 2 проверочная матрица (9) содержит линейно зависимые строки. Таким образом, слова, образованные параллельными классами, не являются всеми кодовыми словами. В этом случае можно сформулировать следующие утверждения. Теорема 4 Если код с проверочной матрицей (9) при т = 2,р = 2, имеет минимальное расстояние 9 + 1, тогда для слова веса 9 + 1 никакие две из линий, соответствующих ненулевым позициям этого слова, не лежат в одном параллельном классе.

Замечание 1 Доказательство теоремы 4указывает способ построения слова веса 1 в рассматриваемом коде. Однако, не доказано, что такой способвсегда существует. Тем неменее, эксперименты показывают, что для полей характеристики 2 это действительно так. Таким образом, возможно, Теорема 4задает точное минимальное расстояние.

(а) На длине 600 (Ь) На длине 1024 и 2048

Рис. 4. Коды, основанные на матрице Вандермонда, в канале с АБГШ

Следствие 2 Укорочение кода (9) при т = 2, р = 2 «а прямые, содержащие любой параллельный класс, приводит к коду с минимальным расстоянием

<*о><7 + 2. (13)

Мы рассмотрим два способа укорочения Евклидово-геометрических кодов: первый подразумевает укорочение на столбцы, соответствующие параллельным классам геометрий вида 2?С(2,рЛ) (EG-плоскостей) и ЕС(3,р*) (Ев-пространств). В этом случае сохраняется регулярность конструкции, то есть равенство весов строк и столбцов.

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

На Рис. 3 приведены результаты такого укорочения для геометрии Ев(З,23) (код ЕСяИЗ). Одновременно показаны результаты укорочеиия этого кода на 18 и 41 параллельный класс (соответственно 8Ы и 8И2). Укорочение 8Ы дает код с теми же параметрами, что и 8И3, их поведение в Гауссовском канале практически совпадает.

Здесь мы рассмотрим общую конструкцию, чья проверочная матрица состоит из блоков — степеней циклической матрицы перестановки (6). Эта матрица строится в соответствии с матрицей Вандермонда.

На Рис. 4 а) представлены результаты моделирования обобщенных кодов Гилберта с проверочной матрицей (7) для длин около 600 и скорости около 0.74. Конструкция задается параметрами (т,р, 7), и на графиках видно, что лучшее качество достигается при большем и меньшем параметре р. Это может объясняться тем, что работа декодера для низкоплот-ностных кодов чувствительна к числу единиц в проверочной матрице. Для кода, например, (25,24,7) доля единиц в проверочной матрице составляет

(а) На длине 1024 (Ь) На длине 2048

Рис. 5. Сравнение LDPC-кодов

0.016, а для кода (40,15,4) — 0.009, то есть почти в два раза меньше при тех же размерах проверочной матрицы.

На Рис. 4 Ь) представлены результаты моделирования для кодов с длинами 1024 и 2048. Здесь можно сделать аналогичные выводы о соотношении размера блока т и числа единиц в строке р и столбце 7 — код (32,32,15) показывает гораздо худший результат, чем код (64,16,4).

Приведем сравнительные графики рассмотренных конструкций на длинах около 1024 и около 2056. На Рис. 5 а) представлены результаты различных LDPC-конструкций на длинах около 1024. На таких длинах и высокой (примерно 0.76) скорости нерегулярная конструкция PEG не показывает хорошего результата. Остальные конструкции показывают примерно одинаковое качество, чуть лучшие показатели у конструкции RS-LDPC.

На Рис. 5 Ь) представлены результаты моделирования LDPC-кодов па длине около 2048. На низких отношениях сигнал/шум лучшие результаты показывают Евклидово-геометрические коды и PEG, однако с ростом отношения сигнал/шум конструкция PEG начинает сильно проигрывать всем остальным, которые показывают сравнимое качество. В заключение заметим, что конструкция, основанная на матрице Вандермонда, показывая результат, сравнимый с конструкциями EG-кодов, обладает более простой процедурой декодирования, так как содержит меньше единиц в проверочной матрице.

В третьем разделе работы рассматриваются LDPC-коды для исправления пакетов ошибок. Параграф 3.1 кратко описывает модели каналов с памятью, в параграфах 3.2 и 3.3 рассматриваются коды Гилберта для исправления пакетов ошибок и их обобщения, анализируется исправляющая пакеты способность этих кодов. Параграф 3.4 кратко описывает модифицированную процедуру декодирования кодов Гилберта.

Класс двоичных кодов дли исправления (одиночных) пакетов ошибок был предложен Гилбертом в 1960 году. Эти коды исследовались в ряде работ, однако, вопрос об истинной корректирующей способности этих кодов

оставался открытым до сих пор.

Коды Гилберта задаются своей проверочной матрицей Я/ (2). Для того, чтобы код исправлял пакеты ошибок длины 6, необходимо и достаточно, чтобы все пакеты ошибок длины b находились в разных смежных классах (и, следовательно, имели разный синдром). Это означает, что не должно найтись двух векторов ошибок ei и ег (образующих пакеты длины, не превышающей Ь), таких, что

ei ■ Н? = е2 • Hj. (14)

Так как вектора е\ и ti представляют собой пакеты ошибок (и на позициях, не входящих в пакет, содержат нули), то можно свести анализ соотношения (14) к рассмотрению подматриц матрицы Я/, состоящих из 2т строк и не более, чем b столбцов. Очевидно, что код с проверочной матрицей (2) не может исправлять пакеты ошибок длины т, так как сумма всех т столбцов любого из блоков матрицы Hi дает единичный вектор (вектор из всех единиц).

Рассмотрение структуры матрицы Hi приводит к следующему утверждению. Для того, чтобы два пакета длины b < т имели одинаковый синдром, необходимо и достаточно, чтобы нашелся многочлен

ТП—1

ум = Y1 Укхк>

к=О

такой, что

(у(x)\i) = (y{x)\j) ■ xi mod xm - 1 Vi = Vj = О где

i-l m-2

(y(z)\i) = + £ yk+ixk,

k=0 k=i

m — параметр кода Гилберта (размер блока), 7 — некоторое положительное целое число, i и j — взятые по модутю тп номера позиций, с которых начинаются два пакета ошибок. Тогда справедливы следующие утверждения.

Лемма 1 Если у(х) = ^'к=оУкхк — многочлен, удовлетворяющий уравнению (15), то для любого ненулевого у к выполняется одно из равенств

У к — У {к-7) mod m.

Ук ~ У{к-7+1) mod mi

Ук = У(к-7-1) modm-

Следствие 3 Для любого у{х), удовлетворяющего уравнению (15), найдутся такие неотрицательные а\, аг, ot 3, для которых справедливо равенство

<*i(7 + 1) +«27+ аз(7_ 1) = т (16)

Условие Дяива иеисправляемого пакета Коэффициенты уравнения (16) Значение 7

1 » = —V, ^ = —1 т — 7 — 1 а! = 0, аз = 0 1- 1

2 -1<»<0' + 7), ЗФ -1 т — 7 «1 Ф 0. <*з = 1 1-2

3 т — 7 + 1 «1 = 0, а3 ф 0 е-2

4 <=-1, т - 7 + 2 аг = 0, а3 ф 0 е-1

5 т - 7 + 1 а! ф 0, а3 = 0 е-2

Таблица 1. Связь параметров 7 и £

Коэффициенты ах, «21 из следствия 3, параметра также относительные начала пакетов г и 3 из (15) связаны с параметрами кода и задают минимальную длину неуправляемого пакета как функцию от параметров кода. Связь этих параметров приведена в таблице 1. Данные этой таблицы, вместе с результатами рассмотрения некоторых частных случаев, позволяют сформулировать теорему.

Теорема 5 Код с проверочной матрицей Н(, задаваемой выражением (2), может и справлять одиночные пакеты ошибок, длина которыхне превосходит Ье, гвыкусляется в соответствии с первым из выполнившихся условий:

1. Ьз = т — 1, т — нечетное

2. Если I > [т/2] + 1, то

\bi~m — [т/2] + 1, т нечетное 1 Ье = т/2 - 1, т четное

3. Если £ < [т/21 + 1, то

Ь( — т - ( + I, т:(£- 1),

Ь( = т-£ +1, Зк > 0: (тп — £ + 3 — к • (£ — 1)):(£ — 2),

Ь(=:тп-£ + 2, ЭА;>0:(т-/Иг-3)):(г-2),

Ье = т-£ + 2, Эк > 0: (т - к • (£ - 2)):(£ - 1),

Ь( = т-£ + 2, Зк>0:(т-к-(£- !)):(£ - 2)

4. В случае невыполнения всех предыдущих условий:

Коды, задаваемые матрицей (2), лежат на границе Рейтера при £ = 3 (мера неэффективности г равна для этих кодов 1), но с ростом £ параметр г ухудшается.

В параграфе 2.2 были заданы коды, основанные на конструкции Гилберта, путем добавления полос к проверочной матрице (б). В данном разделе мы будем рассматривать обобщенные коды Гилберта для случая в = 3 полос.

Обозначим через Р = {¿ьг'г,... ,г<} множество перестановок чисел от О до £ — 1. Зададим матрицу вида

(17)

Такие коды могут исправлять одиночные пакеты ошибок, большие, чем коды, задаваемые матрицей (2). Корректирующая способность этих кодов, очевидно, зависит от выбора перестановки Р. В некоторых частных случаях коды, задаваемые матрицей (17), могут исправлять пакеты ошибок длины т — 1 при £ —» т. Это максимальная длина пакета, который могут исправить рассматриваемые коды.

Обозпачим через Р' множество перестановок таких, что ни для каких элементов г* и tjt+i перестановки (то есть ни для каких соседних элементов последовательности) не выполняется равенство ik+i —ik= 1. Другими словами, ни одна степень матрицы циклической перестановки С из третьего ряда матрицы (17) не превосходит предыдущую степень па единицу. Тогда справедлива следующая теорема.

Теорема 6 Если т — простое и Р = Р' — перестановка, описанная выше, то коды, задаваемые проверочной матрицей (17), могут исправлять одиночные пакеты ошибок длины т —1 и меньше.

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

В четвертом разделе работы рассматривается применение LDPC-кодов в реальном канале связи со сложной структурой, на примере канала неэкранированпой витой пары (UTP). В параграфе 4.1 кратко описывается модель канала UTP, в параграфе 4.2 — схема многоуровневого кодирования с помощью LDPC-кодов, в параграфе 4.3 представлены результаты моделирования.

При полнодуплексной передаче в неэкранированном кабеле выделяют следующие типы помех: помехи на соседние пары, как со стороны самого терминала (ближняя помеха, NEXT), так и на другую его точку (дальняя помеха, FEXT); ближняя помеха от проводов соседних устройств (Alien NEXT); импульсная помеха от соседних электроприборов; ЛБГШ, производимый оборудованием самого терминала (обычно имеет меньшее влияние, чем вышеперечисленные помехи).

Для улучшения качества цифровой системы связи можно использовать идею кодовой модуляции. Идея многоуровневого кодирования (MLC) — за-

(а) Кодовая модуляция в канале с ЛБГШ (^Передача по каналу ОТР с помощью

Рис. б. Использование ЬБРС в канале иТР

щитить каждый адресный бит Xх сигнальной точки индивидуальным двоичным кодом С* на уровне г. Схема декодирования многоуровневого кода может быть следующей: каждый код декодируется индивидуально, начиная с нижнего уровня, и принимая во внимание решения на предыдущих шагах декодирования. Такую процедуру можно назвать многоступенчатым декодированием (М8Б).

При рассмотрении длин около 2000 хорошие показатели были получены с помощью следующих кодов:

1. РЕв(2048,1018) на первом уровне, и Я8-ЬБРС(2048,1921) на втором уровне. Третий уровень составляют некодировапные биты. Сигнальное множество РАМ-8 разбивается на два 4-уровневых подмножества, где для их выбора используется код РЕв(2048,1018); каждое 4-уровневое подмножество разбивается на 2-уровневые подмножества, выбираемые с помощью кода Я8-ЬБРС(2048Д921). Наконец, некоди-рованные биты выбирают сигнал для каждого подмножества.

2. Код Я8-ЬБРС(2048,1619) напервом уровне, и код Я8-ЬБРС(2048,1921) на втором уровне. Третий уровень остается также некодированным.

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

На Рис. 6 Ь) представлены результаты моделирования передачи по каналу ИТР, включая моделирование устройств модуляции/демодуляции и эквалайзера, при условии точного знания канала. Это условие не накладывает серьезных ограничений на модель, так как проводной канал ИТР имеет медленно меняющиеся характеристики, которые могут быть эффективно оценены в заданные моменты времени, и после этого считаться постоянными.

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

В заключении сформулированы основные результаты диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

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

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

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

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

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

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

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

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

Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Тираж 100 экз. Заказ

Отдел оперативной полиграфии ГОУ ВПО «СПбГУАП» 190000, Санкт-Петербург, ул. Б. Морская, 67

»16 079

Введение

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-кодов для исправления пакетов ошибок. Рассматривается применение низкоплотностных кодов для обработки информации в конкретном канале связи с памятью на примере канала неэкра-нированной витой пары (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-кодов, предложены коды на основе кодов Гилберта, проанализированы дистанционные свойства предложенных конструкций, проведено моделирование в канале с АБГШ. Моделирование показывает, что предложенные конструкции обеспечивают повышение эффективности передачи, то есть вероятность ошибки, сравнимую с лучшими из известных конструкций, при уменьшении сложности декодирования.

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.