Содержание к диссертации
Введение
1 Коды с малой плотностью проверок на четность 8
1.1 Обзор существующих результатов 9
1.1.1 Основные понятия 9
1.1.2 Известные результаты 13
1.2 Декодирование LDPC-кодов 15
1.2.1 Декодирование в дискретном канале 16
1.2.2 Декодирование в полунепрерывном канале 17
1.3 Анализ и построение нерегулярных LDPC-кодов 21
1.3.1 Процедура "Density evolution" 22
1.3.2 Конструкция PEG 26
1.4 Конструкции регулярных LDPC-кодов 29
1.4.1 Конструкции, основанные на конечных геометриях . 30
1.4.2 Евклидово-геометрические LDPC-коды 31
1.4.3 Проективно-геометрические LDPC-коды 36
1.4.4 Конструкция, основанная на кодах Рида-Соломона . 38
1.5 Заключение и выводы по разделу 42
2 Коды Гилберта и дистанционные свойства EG-кодов 44
2.1 Коды Гилберта 45
2.2 Обобщения кодов Гилберта 53
2.3 Анализ EG-LDPC кодов 60
2.4 Результаты моделирования в канале с АБГШ 69
2.4.1 Конструкция RS-LDPC 70
2.4.2 Конструкция PEG . 71
2.4.3 Конструкция EG 72
2.4.4 Укорочения EG-кодов 73
2.4.5 Обобщенные коды Гилберта 74
2.4.6 Сравнение конструкций 78
2.5 Заключение и выводы по разделу 79
3 LDPC-коды для исправления пакетов ошибок 81
3.1 Каналы связи с памятью 82
3.2 Коды Гилберта для исправления пакетов ошибок 85
3.2.1 Обзор известных результатов 85
3.2.2 Корректирующая способность кодов Гилберта 86
3.3 Обобщенные коды Гилберта для исправления пакетов ошибок 100
3.4 Декодирование LDPC-кодов для исправления пакетов ошибок 107
3.5 Заключение и выводы по разделу 108
4 Передача по каналу UTP 110
4.1 Канал UTP 110
4.2 Многоуровневое кодирование 113
4.3 Результаты моделирования 115
4.4 Заключение и выводы по разделу 116
Заключение 117
- Декодирование в полунепрерывном канале
- Конструкция, основанная на кодах Рида-Соломона
- Анализ EG-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-кодов в конкретной модели канала с памятью. Использована схема многоуровневой модуляции на основе кодов с малой плотностью, рассмотрены результаты моделирования при передаче по такому каналу с описанной схемой кодирования.
Декодирование в полунепрерывном канале
Однако, такое определение не задает конкретных способов построения проверочной матрицы, более того, часто при построении LDPC-кодов используются вероятностные методы. Тем не менее, при отсутствии четкого задания конструкции кода, существуют результаты, анализирующие коды с малой плотностью проверок на четность как отдельный класс кодов. Эти результаты основаны на рассмотрении ансамблей кодов, и оценке характеристик в среднем по ансамблю [71, 54]. Ансамбль LDPC-кодов задается, в первую очередь, весами строк и столбцов (7, р) проверочной матрицы (то есть параметрами, задающими число ненулевых элементов в проверочной матрице), длина кода п рассматривается как параметр, который обычно оценивается в асимптотике для данных весов.
В [37] Р.Галлагер показал, что для ансамбля (п,7? р)-кодов существует параметр Sjk, такой, что с ростом длины кода п, большинство кодов в ансамбле имеют минимальное расстояние nSjk, где Sjk не зависит от п, и следовательно, минимальное расстояние большинства кодов ансамбля увеличивается линейно с ростом п.
Галлагером были предложены алгоритмы декодирования LDPC-кодов, которые могут работать как с дискретным, так и с непрерывным выходом канала. Пинскером и Зябловым [3] было показано, что среди низкоплотностных кодов существуют коды с алгоритмом декодирования, обеспечивающим исправление ошибок кратности до 5п со сложностью п log п.
Ниже приведем еще несколько асимптотических результатов для LDPC-кодов [37, 71, 74]. 1. Концентрация. Данное свойство означает, что почти все коды ансамбля концентрируют свое поведение относительно некоторого среднего. Более точно, если ff() — ожидание числа ошибочных сообщений на -й итерации декодера (среднее берется по всему ансамблю, всем реализациям шума и всем возможным выборам сообщения), то для любого 6 О вероятность того, что действительное число ошибочных сообщений Р() на -й итерации отклонится от ожидаемого больше, чем на д, экспоненциально стремится к нулю с ростом п:
В качестве параметра канала а из п.З обычно рассматривают величину, рост которой "ухудшает" канал, то есть понижает его пропускную способность. Например, для канала ДСК — это переходная вероятность, для канала с АБГШ — дисперсия шума, и т.п.
В [71, 74, 73] приводится процедура, которая позволяет вычислять порог т для некоторых каналов, а также определять такие весовые распределения (7, р) (или (А(#),/ (#)), для нерегулярных кодов), которые максимизируют значение порога. Это позволяет находить весовые распределения, обеспечивающие хорошее качество кода, особенно при передаче в канале с параметром, близким к порогу (то есть, например, на низких отношениях сигнал/шум в АБГШ). Данная процедура получила название "density evolution", так как вычисляет изменение плотности вероятности числа ошибочных сообщений с ростом числа итераций декодирования.
Однако, данный анализ является асимптотическим, и не дает метода построения кодов по заданным весовым распределениям, при заданной длине. Некоторые эмпирические алгоритмы для решения этой задачи, равно как и основы процедуры "density evolution", кратко описаны в Разделе 1.3.
Процедуры декодирования LDPC-кодов были введены Галлагером как для дискретного, так и для полунепрерывного каналов [37]. Эти процедуры предназначены для исправления ошибок в каналах без памяти, где искажение некоторой позиции в передающемся кодовом слове не зависит от искажений, произошедших в других позициях. Декодеры для каналов с памятью будут подробнее рассмотрены в Главе 3, а модели дискретных и полунепрерывных каналов описаны в Разделах 2.4 и 3.1. Ниже описаны два наиболее часто использующихся алгоритма декодирования LDPC-кодов для дискретного и полунепрерывного каналов без памяти, основывающиеся на процедурах Галлагера, Эти декодеры использовались при моделировании различных конструкций LDPC-кодов, рассматривающихся в данной работе.
Идея работы декодера в дискретном канале ("жесткого" декодера) заключается в том, что в результате разреженности проверочной матрицы, особенно при условии отсутствия маленьких циклов в графе Таннера, для некоторого принятого символа d любой другой символ входит не более чем в одну проверку символа с%. Другими словами, множество проверок ортогонально относительно символа СІ [16, 1, 7]. Тогда столбцы проверочной матрицы имеют мало общих ненулевых позиций, и следовательно, невыполнившаяся проверка (элемент синдрома) более вероятно состояла из одного ошибочного символа, чем из суммы трех и более. Это приводит к следующей процедуре декодирования.
Конструкция, основанная на кодах Рида-Соломона
В этом разделе были введены основные понятия кодов с малой плотностью проверок на четность, сформулированы основные результаты. Были рассмотрены существующие на сегодняшний день подходы к анализу и построению как нерегулярных, так и регулярных LDPC-кодов, приведены примеры конструкций. Кратко рассмотрены алгоритмы декодирования LDPC-кодов. Сформулированы основные свойства регулярных конструкций, и параметры, по которым можно сравнивать различные кодовые схемы.
Однако, анализ LDPC-кодов обычно проводится в асимптотике, не применительно к конкретным конструкциям, и построение хорошего LDPC-кода на конечных длинах остается непростой задачей. Более того, даже для конкретных предлагаемых конструкций часто не проводится детального анализа, оценки дистанционных свойств кодов могут являться неточными, и качество той или иной конструкции определяется с помощью моделирования. Результаты такого моделирования (как правило, в канале с АБГШ) не всегда переносимы и сохраняются для разных каналов связи и разных процедур декодирования. В то же время, оценки дистанционных свойств и анализ самих конструкций может давать более объективную информацию о свойствах получаемых кодов.
Такому анализу для некоторых конструкций и посвящены следующие главы. Будут рассмотрены дистанционные характеристики Евклидово-геометри-ческих кодов, предложены методы их укорочения, предложены и рассмотрены другие конструкции LDPC-кодов, в том числе, для работы в каналах с памятью. 2 Коды Гилберта и дистанционные свойства EG-кодов
В данной главе описаны подходы к созданию конструкций регулярных LDPC-кодов, обладающих анализируемой структурой и хорошими для LDPC-кодов свойствами. Предложены некоторые конструкции, основанные на кодах Гилберта и матрице Вандермонда, проведен анализ их характеристик, получены результаты моделирования в канале с АБГШ. Рассматриваются дистанционные свойства Евклидово-геометрических кодов, рассматриваются методы их укорочения.
Как было показано в главе 1, для построения LDPC-кодов могут быть использованы как вероятностные методы (обычно ведущие к нерегулярным конструкциям), так и конструкции, задающие определенную структуру проверочной матрице кода (что обычно приводит к регулярным LDPC-кодам). Оценка параметров LDPC-кодов, то есть число единиц в строках и столбцах проверочной матрицы, минимальное расстояние кода, длина минимального цикла, возможности для выбора длин и скоростей зависят от конкретной конструкции. Такая оценка параметров может быть затруднительной или даже нереализуемой (например, для нахождения минимального расстояния кода) для кодов со случайной структурой. Наличие строгой структуры проверочной матрицы позволяет проводить анализ получаемых кодов, и получать конструкции на конечных длинах с заранее заданными параметрами.
Оценки минимального расстояния для регулярных конструкций часто являются неточными. В данной главе производится анализ спектральных и дистанционных свойств некоторых Евклидово-геометрических кодов, а также кодов Гилберта, и кодов, полученных на их основе.
В разделе 2.1 данной главы рассматриваются подходы к анализу кодов, основанных на конструкции, предложенной Гилбертом [39]. Показано, что, хотя сами коды Гилберта обладают плохими характеристиками с точки зрения исправления независимых ошибок, они дают возможность аналитического выражения параметров. Такой анализ, примененный к обобщениям структуры Гилберта, приведен в разделе 2.2. Кроме того, в разделе 2.2 предлагается общая конструкция для получения регулярных LDPC-кодов, основанная на матрице Вандермонда. Коды Гилберта и их обобщения могут рассматриваться как частный случай предлагаемой конструкции. Рассматриваются некоторые конкретные схемы, проводится анализ параметров полученных конструкций, моделирование в гауссовском канале и сравнение с существующими схемами.
Анализ EG-LDPC кодов
Для каждого конкретного кода ранг проверочной матрицы может быть вычислен экспериментально. Проведенные тесты показывают, что для рассматривавшихся параметров геометрий при т = 2, р ф 2 ранг проверочной матрицы действительно является полным.
В Табл. 2.3 приведены параметры некоторых LDPC-кодов, с их минимальными расстояними, полученными на основе результатов Теоремы 2.4. Здесь do означает оценку минимального расстояния, do — точное минимальное расстояние.
Теперь рассмотрим случай р = 2. Для поля характеристики 2 соотношение (2.16) не выполняется, то есть проверочная матрица (2.11) содержит линейно зависимые строки. Таким образом, слова, образованные параллельными классами, не являются всеми кодовыми словами. В этом случае можно сформулировать следующие утверждения. Теорема 2.5 Если код с проверочной матрицей (2.11) при т = 2, р = 2, имеет минимальное расстояние q+l, тогда для слова веса q+l никакие две из линий, соответствующих ненулевым позициям этого слова, не лежат в одном параллельном классе. Доказательство. Минимальное расстояние кода определяется минимальной линейной комбинацией столбцов проверочной матрицы, дающей в результате нулевой столбец-синдром. В случае рассматриваемых кодов, столбец проверочной матрицы соответствутет линии в Евклидовой геометрии. Каждая позиция синдрома соответствует точке Евклидовой плоскости, и является суммой позиций столбцов, вошедших в линейную комбинацию. Таким образом, чтобы позиция синдрома равнялась 0, необходимо, чтобы через соответствующую точку либо не проходило прямых из данной линейной комбинации, либо число прямых, проходящих через точку, было четным. То есть, чтобы построить кодовое слово, нужно найти множество прямых L такое, что через каждую точку геометрии либо не проходят прямые из L, либо в этой точке пересекается четное число прямых из L. Тогда нахождению слова минимального веса соответствует нахождение множества LQ минимальной мощности. Попробуем построить такое множество минимальной мощности. Допустим, что на некотором шаге к уже сформировано множество прямых LQ . Обозначим через те точки из щ , через которые проходит нечетное число прямых, через Р — те точки, через которые проходит четное число прямых. Чтобы число прямых в Lo было минимальным, необходимо, чтобы каждая следующая добавляемая прямая проходила через как можно большее число точек Р , не проходила через точки Р , и добавляла как можно меньшее число новых точек, которые на следующем шаге увеличат множество Р . Построение Lo закончится тогда, когда множество точек Р станет пустым. Это эквивалентно тому, что на шаге к новая прямая должна пересекать как можно большее число прямых, уже содержащихся в LQ , причем пересечение должно идти по точкам Р . Рассмотрим прямую № Евклидовой плоскости. Эта прямая содержит q точек, и принадлежит какому-то классу параллельности. Следующая проведенная прямая № может либо не пересечь данную, если она принадлежит тому же классу параллельности, что и 1 \ либо пересечь в одной точке, если не параллельна f\ Следующая проводимая прямая может пересечь либо одну прямую из уже выбранных, если она параллельна одной из них, либо пересечь обе, в противном случае. Пример построения множества Lo для случая q = 4 приведен на Рис. 2.11. Точки множества Р обведены на этом рисунке кругами (кроме заключительный фигуры). Таким образом, выбирая каждый раз прямую из еще не использовавшегося класса параллельности, мы будем пересекать все прямые, выбранные на предыдущих шагах. Добавление прямой к LQ \ в котором уже содержатся к прямых, добавляет q — к новых точек. Всего в LQ содержитс точек. Оценим число Щ точек типа Р на к-и шаге. На 0-м шаге LQ содержит единственную прямую, и все NQ = q точек являются Р -точками. На 1-м шаге добавляемая прямая пересекает уже выбранную в одной точке, таким образом, в LQ содержится одна точка типа Р и JVi — 1 точек типа Р . На 2-м шаге новая прямая пересекает две существующие еще в двух точках, и таким образом, в LQ содержится уже три точки типа Р и JV — 3 точек типа Р .
Корректирующая способность кодов Гилберта
В этой главе мы рассмотрим применение кодов с низкой плотностью проверок на четность в каналах с памятью. Такие коды рассматривались, например, в [65].
В реальных системах связи модели каналов, наиболее часто использующиеся для оценки качества той или иной кодовой схемы, а именно — двоично-симметричный канал (ДСК) или Гауссовский канал, часто оказываются неадекватными, так как это каналы, описывающие независимые ошибки. В реальности же в каналах происходит явление памяти, то есть ошибки в следующих символах зависят от ошибок в предыдущих. Для борьбы с такими группирующимися ошибками, используя традиционные помехоустойчивые коды, ориентированные на работу в метрике Хэмминга, обычно используют дополнительные преобразования, снижающие эффект группировки символов — процедуры интерливинга [17].
Однако, использование интерливинга приводит к тому, что теряется информация о типичных ошибках канала, канал фактически сводится к каналу с независимыми ошибками, скорость передачи по которому может быть ниже, процедура интерливинга вносит дополнительную сложность в устройство декодера, и приводит к большим задержкам на приемной стороне.
Использование кодов, ориентированных на исправление пакетов ошибок, то есть ошибок, характерных для данного типа каналов, может позволить осуществлять более эффективную передачу. Такие коды и рассматриваются в данной главе.
В разделе 3.1 рассматриваются основные модели каналов с памятью, в разделе 3.2 рассматриваются коды Гилберта, определенные в разделе 2.1.
Здесь находится точная исправляющая пакеты способность для этих кодов. Раздел 3.3 посвящен рассмотрению модификаций кодов Гилберта для исправления пакетов ошибок. Раздел 3.4 кратко описывает декодеры для рассматриваемых конструкций.
Для создания систем передачи информации по каналам связи используются модели каналов, описывающие основные свойства данного канала связи. Эти модели условно можно разделить на каналы полунепрерывные и дискретные, симметричные и несимметричные, каналы с памятью, и каналы с независимыми ошибками.
В этом разделе мы рассмотрим модели каналов с памятью. Самыми известными моделями являются модели каналов с конечным числом состояний, и заданными вероятностями переходов из состояния в состояние [9, 38, 32]. Эти модели являются дискретными. Непрерывные модели с памятью обычно представляют собой описание каналов с замираниями и рассеянием, и описываются, например, с помощью релеевского распределения [17, 5, 8, 12].
Мы опишем простейшую дискретную модель канала с памятью с двумя состояниями. Пусть Си В — состояния канала ("хорошее" и "плохое", соответственно), каждое из которых характеризуется вероятностью ошибки своего состояния PQ или Р#, PQ « Рв- Другими словами, каждому состоянию S соответствует модель ДСК с переходной вероятностью Ps.
Кроме того, заданы переходные вероятности PGB, PBG PGG = 1 — PGBI Рвв = 1 — PBG — то есть, вероятность Ров означает вероятность нахождения канала в состоянии Б, если в предыдущий (дискретный) момент времени канал находился в состоянии G, и так далее для всех вероятностей.
