В настоящее время происходит интенсивное развитие различных цифровых систем передачи данных, таких как космическая, спутниковая, мобильная связь и др. Все подобные системы используют для передачи данных беспроводные каналы, в которых на передаваемый сигнал действуют помехи различной физической природы. Это приводит к тому, что принятые данные с достаточно большой вероятностью будут содержать ошибки. В то же время для многих практических приложений допустима лишь очень небольшая доля ошибок в обрабатываемых дискретных данных. В результате возникает проблема обеспечения надежной передачи цифровой информации по каналам с шумами.
Важнейший вклад в решение данной проблемы вносит теория помехоустойчивого кодирования. На ее основе разрабатываются методы защиты от ошибок,  базирующиеся на применении помехоустойчивых кодов. Использование этих кодов позволяет получить энергетический выигрыш кодирования (ЭВК), который характеризует степень возможного снижения энергетики передачи при кодировании по сравнению с отсутствием кодирования, если достоверность передачи в обоих случаях одинакова. Этот выигрыш можно использовать для улучшения параметров и характеристик многих важных свойств систем передачи данных, например, для уменьшения размеров очень дорогих антенн, повышения дальности связи, увеличения скорости передачи данных, снижения необходимой мощности передатчика и т.д.
Сформулируем задачи, для которых найдены решения средствами помехоустойчивого кодирования:
  • кодирование для обеспечения надежной передачи в каналах передачи данных (физический уровень сети);
  • кодирование в системах с обратной связью (уровень звена передачи данных);
  • кодирование на транспортном уровне сети;
  • кодирование для защиты от несанкционированного доступа (уровень приложений);
  • кодирование для сжатия информации с потерями (уровень приложений).
На сегодняшний день теории кодирования известно много кодов и методов их декодирования, различающихся энергетическим выигрышем, вносимой избыточностью, сложностью реализации и рядом других параметров [турбо-коды, каскадные коды, низкоплотностные коды (LDPC-коды) и многие другие].  
В данной работе  нас будут интересовать LDPC-коды.
Коды с малой плотностью проверок на четность (LDPC-код от англ. Low-density parity-check code, LDPC-code, низкоплотностный код) были впервые предложены Робертом Галлагером и позднее исследовались во многих научных работах. Несмотря на то, что в течение долгого времени LDPC-коды были практически исключены из рассмотрения, в последние годы наблюдается увеличение количества исследований в этой области. Это связано с тем, что, обладая плохим минимальным расстоянием, коды с малой плотностью, тем не менее, обеспечивают высокую степень исправления ошибок при весьма малой сложности их декодирования. Было показано, что с ростом длины некоторые LDPC-коды могут превосходить турбо-коды и приближаться к пропускной способности канала с аддитивным белым гауссовским шумом (АБГШ). Вместе с тем многие предложенные конструкции LDPC-кодов являются циклическими или квазициклическими, что позволяет производить не только быстрое декодирование, но и эффективные процедуры кодирования. Кроме того, даже для LDPC-кодов, не обладающих свойством цикличности, были предложены эффективные процедуры кодирования.
В 1948 году  Клод Элвуд Шеннон  опубликовал свою работу по теории передачи информации. Одним из ключевых результатов работы считается теорема о передачи информации для канала с шумами, которая говорит о возможности свести вероятность ошибки передачи по каналу к минимуму при выборе достаточного большой длины ключевого слова — единицы информации передаваемой по каналу.
Рисунок 1. Упрощённая схема передачи информации по каналу с шумами. 
При передаче информации её поток разбивается на блоки определённой (чаще всего) длины, которые преобразуются кодером (кодируются) в блоки, называемыми ключевыми словами. Ключевые слова передаются по каналу, возможно с искажениями. На принимающей стороне декодер преобразует ключевые слова в поток информации, исправляя (по возможности) ошибки передачи.
Теорема Шеннона утверждает, что при определённых условиях вероятность ошибки декодирования (то есть невозможность декодером исправить ошибку передачи) можно уменьшить, выбрав большую длину ключевого слова. Однако, данная теорема (и работа вообще) не показывает, как можно выбрать большую длину, а точнее как эффективно организовать процесс кодирования и декодирования информации с большой длиной ключевых слов. Если предположить, что в кодере и декодере есть некие таблицы соответствия между входным блоком информации и соответствующим кодовым словом, то такие таблицы будут занимать очень много места. Для двоичного симметричного канала без памяти (если говорить упрощённо, то на вход кодера поступает поток из нулей и единиц) количество различных блоков составляет 2n, где n — количество бит (нулей или единиц) которые будут преобразовываться в одно кодовое слово. Для 8 бит это 256 блоков информации, каждый из которых будет содержать в себе соответствующее кодовое слово. Причём кодовое слово обычно большей длины, так как содержит в себе дополнительные биты для защиты от ошибок передачи данных. Поэтому одним из способов кодирования является использование проверочной матрицы, которые позволяют за одно математическое действие (умножение строки на матрицу) выполнить декодирование кодового слова. Аналогичным образом каждой проверочной матрице соответствует порождающая матрица, аналогичным способом одной операцией умножения строки на матрицу генерирующей кодовой слово.
Таким образом, для сравнительно коротких кодовых слов кодеры и декодеры могут просто содержать в памяти все возможные варианты, или даже реализовывать их в виде полупроводниковой схемы. Для большего размера кодового слова эффективнее хранить порождающую и проверочную матрицу. Однако, при длинах блоков в несколько тысяч бит хранение матриц размером, соответственно, в мегабиты, уже становится неэффективным. Одним из способов решения данной проблемы становится использования кодов с малой плотностью проверок на чётность, когда в проверяющей матрице количество единиц сравнительно мало, что позволяет эффективнее организовать процесс хранения матрицы или же напрямую реализовать процесс декодирования с помощью полупроводниковой схемы.
Первой работой на эту тему стала работа Роберта Галлагера «Low-Density Parity-Check Codes» 1963 года (основы которой были заложены в его докторской диссертации 1960 года). В работе учёный описал требования к таким кодам, описал возможные способы построения и способы их оценки. Поэтому часто LDPC-коды называют кодами Галлагера. В русской научной литературе коды также называют низкоплотностными кодами или кодами с малой плотностью проверок на чётность.
Однако, из-за сложности в реализации кодеров и декодеров эти коды были позабыты. Лишь много позже, с развитием телекоммуникационных технологий, снова возрос интерес к передаче информации с минимальными ошибками. Несмотря на сложность реализации по сравнению с турбо-кодом, отсутствие преград к использованию (незащищённость патентами) сделало LDPC-коды привлекательными для телекоммуникационной отрасли.
Появление новых эффективных алгоритмов декодирования стимулировало и повышение интереса к методам построения недвоичных LDPC-кодов. Первоначально построение недвоичных LDPC кодов осуществлялось путем замены ненулевых элементов в проверочной матрице двоичных LDPC-кодов на случайные элементы конечного поля. Позднее Лиин (Lin) предложил методы алгебраического построения квазициклических недвоичных LDPC-кодов (QC NB-LDPC).
LDPC-коды становятся востребованными в системах передачи информации, требующих максимальной скорости передачи при ограниченной полосе частот. Основным конкурентом LDPC-кодов на данный момент являются турбо-коды, которые нашли свое применение в системах спутниковой связи, ряде стандартов цифрового телевидения и мобильных системах связи третьего поколения. Однако LDPC-коды по сравнению с турбо-кодами имеют ряд преимуществ.
Во-первых, LDPC-коды обгоняют турбо-коды по скорости декодирования.
Во-вторых, LDPC-коды более предпочтительны в каналах с меньшими вероятностями ошибок. С развитием методов передачи информации каналы передачи улучшаются, что дает хорошую перспективу для развития LDPC-кодов.
Применение методов итеративного декодирования к данным кодам позволяет практически вплотную приблизиться к пропускной способности канала при относительно небольшой сложности реализации. В связи с этим во многих новых стандартах передачи различного рода данных (DVB-S2, 802.11n, 802.16e) именно LDPC- коды рекомендованы для исправления ошибок LDPC- коды представляют собой линейные блоковые коды, задаваемые с помощью проверочной матрицы H, характеризуемой относительно малым (<10) числом единиц в строках и столбцах. Проверочной матрице кода ставится в соответствие граф Таннера, в котором для представления строк и столбцов проверочной матрицы используются определенным образом связанные между собой битовые и проверочные узлы. Например, для кода с матрицей H с рисунке 2.  
Рисунок 2. Проверочная матрица и граф Таннера LDPC- кода
Для декодирования LDPC- кодов обычно используются разновидности sum-product и min-sum алгоритмов, работающих с графом Таннера кода. Данные алгоритмы отличаются сложностью реализации и эффективностью декодирования. В основе работы данных методов лежит итеративный обмен мягкими решениями между битовыми (нижними на рис. 2) и проверочными (верхними на рис. 2) узлами графа кода. При правильном выборе кода (проверочной матрицы) удается получить близкие к оптимальным результаты. Данный алгоритм позволяет получить достаточно хорошие результаты при меньшей сложности реализации.
Рис. 3. Характеристики малоизбыточных помехоустойчивых кодов 
Пояснения к рисунку 3:
  1. РС+АВ(R=0.87,n=16К)» - характеристики каскадного кода, состоящего из кода Рида-Соломона и сверточного кода с общей кодовой скоростью R=0.87 и длиной блока порядка 16 тысяч битов.
  2. Многопороговые декодеры (МПД)
  3. TCC- Turbo Convolutional Code- турбо- код
  4. TPC- Turbo Product Code- турбо- коды произведения
  5. LDPC-коды
Характеристики малоизбыточных LDPC- кодов, применяемых в стандарте DVB-S2, представлены на рис. 3 кривой «4» LDPC(R=0.88,n=16K)». И при такой кодовой скорости эффективность LDPC близка к предельной.
Рисунок 4. Характеристики помехоустойчивых кодов с R≈1/2
Пояснения к рисунку 4:
  1. Декодер Витерби
  2. Последовательный декодер
  3. Код Рида-Соломона (РС)
  4. Многопороговые декодеры (МПД)
  5. МПД (ИКИ)- приведены характеристики декодера МПД сверточного кода с 40 итерациями декодирования
  6. МПД+КК3 показаны возможности каскадной схемы, использующей МПД во внутренних каскадах
  7. МПД+НЭК- МПД алгоритмы для каналов с неравномерной энергетикой
  8. TCC- Turbo Convolutional Code- турбо- код
  9. TPC- Turbo Product Code- турбо- коды произведения
  10. LDPC-коды
  • кода длиной 1000000 битов
  • характеристики используемых в стандартах IEEE 802.16e и DVB-S2 LDPC кодов длиной 2304 и 64800.
На рис. 4 кривой «10» LDPC(n=1000000)» показаны характеристики очень длинного LDPC кода длиной 1000000 битов. Видно, что данный код способен работать примерно в 0.1 дБ от пропускной способности канала, хотя, конечно, его реализация слишком сложна для практического применения. Характеристики используемых в стандартах IEEE 802.16e и DVB-S2 LDPC кодов длиной 2304 и 64800 битов представлены на рис. 4 кривыми «11»  802.16e LDPC(n=2304)» и «12» DVB-S2 LDPC(n=64800)». Видно, что данные коды показывают сопоставимую с турбо- кодами эффективность, но при этом сложность их реализации оказывается в несколько раз меньшей. 
Следует заметить, что представленные для турбо и LDPC кодов результаты относились к наилучшим алгоритмам их декодирования, работающим с неквантованными решениями демодулятора. При аппаратной реализации декодера часто из-за различных ограничений это оказывается недопустимым. При переходе к более простым алгоритмам, работающим с квантованными на несколько уровней решениям демодулятора возможны потери от 0.5 до 1 дБ и даже более. Характеристики же многопороговые декодеры (МПД) и остальных алгоритмов получены с учетом требований аппаратной реализации. 
Преимущества LDPC-кодов, их применение и перспективы развития
LDPC-коды в современных системах передачи информации занимают нишу, аналогичную турбо-кодам. Оба эти класса кодов используются в системах, где требуются повышенные скорости передачи данных при ограниченной полосе пропускания канала. К числу таких систем можно отнести, например, спутниковую связь, цифровое телевидение (в том числе высокой четкости), а также каналы передачи в электронно-вычислительных машинах и их сетях. LDPC-кодеры могут обеспечивать поистине колоссальную скорость передачи данных (до 40 Гб/с), что обусловлено простотой их реализации. Наиболее быстрыми декодерами разумно было бы считать многопороговые декодеры (МПД), декодирующие по одноименному алгоритму, о котором говорилось выше. В МПД могут легко декодироваться длинные коды, в широком диапазоне кодовых скоростей при использовании как жесткого, так и мягкого модемов. При этом МПД выполняет только простейшие операции сложения и сравнения небольших целых чисел, что обуславливает его крайнюю простоту при всех вариантах программной или аппаратной реализации. Например, МПД может быть реализован с использованием линейных сдвиговых регистров – самых быстрых аппаратных элементов.
Следует отметить, что LDPC-кодирование не является сугубо теоретической разработкой, а уже активно используется и введено в некоторые стандарты. Например, в 2003г. LDPC-код вместо турбо-кода стал частью стандарта DVB-S2 спутниковой передачи данных для цифрового телевидения. Аналогичная замена произошла и в стандарте DVB-T2 для цифрового наземного телевизионного вещания. Также LDPC-коды вошли в стандарт IEEE 802.3an сети Ethernet 10G и другие.
По результатам исследования среди кодов для включения в стандарт DVB-S2 были отмечены следующие преимущества:
  • отставание от границы Шеннона всего на 0,6–0,8 дБ;
  • преимущество на 0,3 дБ по сравнению с лучшим из представленных турбо-кодов;
  • преимущество на 2,5–3,0 дБ, т. е. 30-процентный прирост в мощности, по сравнению  со стандартом DVB-S.
Были проведены моделирование работы недвоичных LDPC-кодов и сравнение их производительности с производительностью кодов Рида–Соломона. Результаты моделирования показали, что недвоичные LDPC-коды имеют существенное преимущество над кодами Рида–Соломона. Это преимущество увеличивается по мере увеличения длины кода и разрядности символа.
Рисунок. 5. Сравнение производительности NB-LDPC и кодов Рида–Соломона при средней длине блока 
Современные исследования в основном сосредоточены на создании LDPC-кодов с улучшенными характеристиками, а также методов их декодирования. Например, кодов на базе евклидовых геометрий. Для таких кодов также создаются и развиваются специальные методы декодирования и ускоренного декодирования с приемлемыми потерями в вероятности декодирования, и они показывают неплохие результаты. Дальнейшее развитие в рамках данной проблематики заключается в отработке современных алгоритмических решений в области кодирования и декодирования LDPC-кодов, а также в эмпирической проверке результатов современных теоретических исследований в этой области.
Используемые материалы:
  1. http://ru.wikipedia.org/wiki/LDPC
  2. http://www.mtdbest.ru/articles/obzor_dvoichnie_kodi_2.pdf
  3. Овчинников А. К вопросу о построении LDCP-кодов на основе евклидовых геометрий // Вопросы передачи и защиты информации: Сборник статей под ред. А. Крука. СПбГУАП. СПб., 2006.