Краткая история графических кодов

Интересно, что графическое понимание этих кодов сформировалось за долго до того, как их назвали “графическими”. Более того, это понимание помогло теоретикам кодирования в анализе этих кодов и разработке алгоритмов декодирования, они также узнали, как создавать свои коды, чтобы извлечь наибольшую выгоду из данного алгоритма декодирования.

 

Рис 1.1. Иллюстрация вероятности ошибочного декодирования сверточных кодов и турбо кодов.

Графическое понимание кодов началось с графов Таннера для линейных кодов [4]. Позже Виберг обнаружил, что турбо декодер также может быть представлен графически [5]. Вскоре после этого открытия, как в [6] и [7], было показано, что алгоритм турбо декодирования представляет собой частный случай общих байесовских сетей [8].

Параллельно с исследованиями турбо кодов, в 1996 году МакКей и Нил [9], а также Сипсер и Шпильман в [10] обнаружили вновь давно забытый класс кодов, а именно LDPC коды. Этот класс кодов был первоначально предложен в 1962 году Галлагером[11], но считался слишком сложными в момент их открытия.

LDPC коды из-за малой вероятности ошибочного декодирования привлекли большое внимание к себе. Например, при передаче по каналу связи с аддитивным гауссовским шумом они могут быть кодированы так, что их вероятность ошибочного декодирования будет отличаться на несколько сотых долей дБ от предела Шеннона. Еще одной особенностью LDPC кодов является их простое графическое представление, основанное на представлении Таннера линейных кодов [4].

Эта простая конструкция позволяет производить точный асимптотический анализ LDPC кодов [12,13], а также кодировать неравномерные LDPC коды, оптимизированные под определенные ограничения.

С открытием LDPC кодов было проделано много научно-исследовательской деятельности и совершенствований технологий в области кодов, определённых на графах. Несомненно, что исследование LDPC кодов сыграло и продолжает играть главную роль в этой области, так как многие из новых классов кодов, которые определяются на графах, подвергаются влиянию структурой LDPC кодов. Примеры включают в себя RA коды (repeat-accumulate – повторяющиеся с накоплением) [14], преобразование кодов Люби [15] и каскадных древовидных кодов[16]. Некоторые из ключевых усовершенствований в области графических кодов и их значения приведены ниже.

•Неравномерные LDPC коды: Как показано в [17], неравномерные LDPC коды могут существенно превосходить обычные LDPC коды по ряду показателей. Все LDPC коды, которые могут приблизиться к пределу Шеннона на различных каналах, являются неравномерными LDPC кодами. Открытие неравномерных LDPC кодов повлияло на рассмотрение неравномерных структур других кодов, определенных на графах, таких как неравномерные турбо коды [18] и неравномерные RA коды[19].

•Повторяющиеся коды с накоплением: Одной из проблем LDPC кодов является сложность их кодирования. Люди рассматривали различные способы добавления структур в LDPC коды, чтобы сделать процесс кодирования менее сложным. Одним из лучших решений являются RA коды [14], которые, в отличие от LDPC кодов, имеют несколько иную структуру и меньшую вероятность ошибочного декодирования. Декодирующая сложность RA кодов растет линейно с длиной блока.

•Возможность LDPC кодов достигать пропускной способности ВЕС канала: Шокроллахи нашёл семейство неравномерных LDPC кодов, которые могли бы достичь пропускной способности ВЕС канала[20,21].

•Плотность эволюции анализа LDPC кодов: точный асимптотический анализ LDPC кодов в рамках различных схем декодирования стал возможным [13]. Идея состоит в том, чтобы проследить плотность эволюции сообщений в декодере. С помощью этого анализа кодирование хороших неравномерных LDPC кодов, которое уже было изучено для ВЕС канала, стало возможным и для других типов каналов.

•Гауссовский анализа турбо кодов и LDPC кодов [22-24]: Из-за сложности вычисления плотности эволюции, аппроксимации плотности эволюции привлекают многих исследователей. В частности, аппроксимация истинной плотности сообщений гауссовской плотностью оказалась очень эффективной.

• EXIT анализ диаграмм (Extrinsic Information Transfer - внешняя передача информации): EXIT анализ диаграмм [25] похож на плотность эволюции, за исключением того, что он следует за эволюцией одного параметра, который представляет плотность сообщений. Эта эволюция может быть визуализирована в графе, называемом EXIT диаграммой. EXIT диаграммы стали очень популярными, поскольку они обеспечивают глубокое понимание поведения итерационного декодера.

•LT коды (Luby Transform – преобразование Люби) [15]: Идея таких кодов - одно из последних изобретений в области теории кодирования. Такие коды полезны, когда у нас есть радиовещательный передатчик, чей канал для каждого приемника отличается от другого. В таких случаях не ясно, какой уровень кода должен быть использован для защиты данных. LT коды являются кодами, решающими эту проблему. Чтобы быть более конкретным, каждый получатель получает различные скорости передачи данных в зависимости от состояния канала.

Исследования в области графических кодов по-прежнему очень активны и многие вопросы всё ещё остаются в стадии изучения.

 

Обзор главной темы

 

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

LDPC коды уже используются в таких стандартах, как ETSI EN 302 307 для цифрового видео вещания [26] и IEEE 802.16 (Вещательное Рабочее Сообщество Беспроводного доступа) для кодирования OFDMA систем (orthogonal frequency division multiplexing access systems - ортогональные системы частотно-мультиплексного доступа) [27].

В области LDPC кодирования всё ещё остаётся много открытых вопросов. Данная работа ответит на многие вопросы, но в свою очередь откроет целый ряд новых.

 

Главная тема данной работы

 

В данной работе описываются эффективные методы кодирования и анализа LDPC кодов, а также их декодирования. Эти проблемы изучаются с практической точки зрения, а также будет поднят ряд новых интересных вопросов. Некоторые из этих вопросов получат ответ в данной работе, а некоторые останутся в качестве открытых. В данной работе рассматриваются три основные проблемы:

• эффективные методы для анализа LDPC кодов;

 

• эффективные методы кодирования неравномерных LDPC кодов;

• улучшенные способы декодирования LDPC кодов.

Хотя основной упор делается на LDPC коды, некоторые из этих проблем обсуждаются за пределами их применения к LDPC кодам. В этом разделе мы рассмотрим общую структуру данной работы, а также представим краткое описание главных результатов.

На рис. 1.2 показаны типичные представления неравномерных LDPC кодов длиной и с турбо кодами равной длины при передаче по каналу связи с аддитивным гауссовским шумом. Турбо коды могут превзойти LDPC коды на коротких длинах блоков, но как можно увидеть из рис. 1.2, если длина блока является большой (как правило, более 5000), неравномерные LDPC коды превосходят турбо коды равной длины. С увеличением длины кодов улучшается вероятность ошибочного декодирования. LDPC коды длиной могут быть надежно декодированы с помощью отношения с точностью, менее чем на 0,1 дБ отличающейся от предела Шеннона при передаче по каналу связи с аддитивным гауссовским шумом, а при длине блока отклонение от предела Шеннона может составлять менее 0,04 дБ [28].

Такая низкая вероятность ошибочного декодирования достигается за счет тщательной разработки неравномерности кода. К сожалению, за исключением нескольких случаев, эти методики расчета могут быть насыщены вычислениями. Традиционный метод кодирования заключается в создании некоторой неравномерности в коде, проверяющей работу с плотностью эволюции, и изменении неравномерности в коде до желаемой вероятности ошибочного декодирования. Интересная проблема, которая рассматривается в литературе, заключается в упрощении методики расчета LDPC кодов [24]. Это будет одним из основных направлений этой работы.

 

 

Рис. 1.2. Сравнение вероятностей ошибочного декодирования уровней ½ LDPC кодов различной длины с турбо кодами одинаковой длины.

 

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

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

Мы также рассмотрим некоторые практические проблемы, такие как применение LDPC кодов в частотно-селективных каналах. Мы покажем, что LDPC коды имеют некоторые особенности, которые делают их хорошим выбором для кодирования при передаче по таким каналам.

 

Организация данной работы

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

В главе 3 мы ознакомимся с LDPC декодированием с использованием алгоритмов двоичной передачи сообщений. Мы отслеживаем сообщение об ошибочной скорости, чтобы проанализировать декодер и изобразить EXIT диаграммы, основанные на сообщениях об ошибочной скорости. Также доказано, что алгоритм В Галлагера является, возможно, лучшим бинарным алгоритмом передачи сообщений. Мы используем EXIT диаграммы для разработки неравномерных LDPC кодов и, для того чтобы показать, что процесс кодирования может быть позиционирован ​​в качестве линейного программирования.

В главе 4 мы продолжим анализ главы 3. Опять же, мы используем EXIT диаграммы, основанные на сообщениях об ошибочной скорости, и покажем, как могут быть получены точные EXIT диаграммы. В то время как предыдущие работы по анализу LDPC кодов в AWGN каналах использовали наработки Гаусса для сообщений [24], мы избегаем предположений Гаусса о выходах проверочных узлов, которые на самом деле являются плохими предположениями. Мы называем наш метод «наполовину Гаусса», в отличие от «полного» метода Гаусса, который принимает все гауссовы сообщения. Мы показываем, что очень точный анализ и кодирование LDPC кодов можно осуществить с помощью приближения метода Гаусса. Опять же, мы используем EXIT диаграммы, чтобы уменьшить методику расчета неравномерных LDPC кодов до линейного программирования. Мы также дадим несколько советов по кодированию таких кодов. По сравнению с кодами, кодированными с помощью анализа плотности эволюции, наши коды будут выполнены всего лишь на несколько сотых долей дБ хуже.

В главе 5 мы рассмотрим класс алгоритмов декодирования, для которых анализ EXIT диаграмм декодера является точным (или имеет хорошее приближение). Мы рассматриваем общий случай кодирования кодов для желаемого поведения конвергенции и обеспечиваем необходимые и достаточные условия, для того чтобы были EXIT диаграммы удовлетворяли условию максимальной скорости LDPC кодов. Наши результаты обобщают некоторые из существующих результатов ВЕС.

В главе 6 мы применяем неравномерные LDPC коды для разработки многоуровневых схем кодирования с последующим их применением в DMT системах (discrete multi-tone systems - дискретные мультитональные системы). Мы используем комбинированную маркировку Грея/Ангербёка для QAM. Биты, маркированные по Грею, защищены, благодаря неравномерным LDPC кодам, в то время как другие биты защищаются с помощью высокой скорости кода Рида-Соломона с жёстким решением декодирования (или остаются не кодированными). Скорость LDPC кодов выбирается на основе анализа пропускной способности канала. Затем мы применяем эту схему кодирования для ансамбля частотно-селективных каналов с гауссовским шумом. Эта схема кодирования обеспечивает эффективное кодирование с приростом более чем на 7,5 дБ при вероятности ошибки , которая представляет собой разрыв в размере примерно 2,3 дБ от предела Шеннона при передаче по каналу связи с аддитивным гауссовским шумом. Этот интервал может быть уменьшен до 0,8-1,2 дБ.

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

В главе 8 мы предоставим краткий обзор данной работы и некоторые предложения для будущих работ.

 

 

Глава 2

LDPC коды и их анализ

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