Глава 1. Введение
Данная работа связана с анализом, кодированием и декодированием очень мощного и гибкого семейства кодов, контролирующих ошибки, называемых проверочными кодами с низкой плотностью (LDPC кодами). LDPC коды могут быть использованы для различных типов каналов с практической сложностью декодирования. Предполагалось, что они могут обеспечивать максимальную пропускную способность для различных типов каналов и, действительно, позже была доказана их способность обеспечить пропускную способность двоичного канала со стиранием (BEC канала), с помощью итеративного декодирования.
В этой главе рассматриваются некоторые понятия, которые исследуются в диссертации. Мы обсудим важность области исследования, интересные задачи, которые привлекают исследователей в этой области и некоторые нерешенные проблемы.
Коды, определенные на графах
С
1948 года, когда Клод Шеннон ввел понятие
пропускной способности канала [1],
конечная цель теории кодирования
заключалась в том, чтобы найти практический
потенциал пропускной способности кодов.
В соответствии с теоремой Шеннона о
пропускной способности канала, надежная
связь на скорости
(бит / канал использования) по каналу с
аддитивным белым гауссовским шумом
(AWGN каналу) обеспечивается
при определенном минимальном уровне
сигнал-шум, называемом пределом Шеннона.
В условиях нормированного уровня
отношения битов энергии к плотности
шума, надежная связь может иметь место
при условии скорости
где
есть средняя энергия, затрачиваемая на
один переданный бит, и
есть средняя дисперсия или спектральная
плотность шума. Требуемый минимум
называется пределом Шеннона.
Подойти к пределу Шеннона в несколько децибел (дБ) стало возможным благодаря практической сложности декодирования, с помощью сверточных кодов, но сокращение этого интервала требовало нереальной сложности до открытия турбо кодов [2]. Одним из важных нововведений в турбо кодах стало введение классов с низкой сложностью неоптимальных правил декодирования, т.е. итеративных алгоритмов передачи сообщений. Использование итеративного декодера передачи сообщений, турбо кодов обеспечивает малую вероятность ошибочного декодирования и небольшой интервал до предела Шеннона с низкой (практической) сложностью декодирования. На рис. 1.1 приведены типичные результаты вероятности ошибочного декодирования турбо кода и сверточного кода при передаче по каналу связи с аддитивным белым гауссовским шумом (см. [3, рис. 5], например). Эта удивительная низкая вероятность ошибочного декодирования турбо кодов обратила большое внимание к данной области исследования, которая вскоре расширилась на более широкий класс кодов называемых кодами, определенными на графах.
Коды, определенные на графах, могут быть декодированы алгоритмами передачи сообщений. Двумя важными особенностями декодирования такого типа, которые делают коды, определённые на графах, такими привлекательными являются близкая к оптимальной вероятность ошибочного декодирования и ее практическая сложность (для фиксированного числа итераций), которая возрастает линейно с длиной кода. Это, в свою очередь, позволяет использовать очень длинные коды. Таким образом, теперь, после 50 лет после работ Шеннона, специалисты кодирования могут найти коды вероятностью ошибочного декодирования близкой к пределу Шеннона и с разумной сложностью декодирования. Кроме того, для некоторых каналов они узнали, как может быть достигнута пропускная способность, хотя декодер и требует усложнения, так как вероятность ошибочного декодирования кода приближается к пропускной способности.