Коды с малой плотностью проверок на чётность

Коды с малой плотностью проверок на чётность (LDPC-коды, от англ. Low-Density Parity-Check) — это класс линейных блоковых кодов, используемых для помехоустойчивого кодирования, которые характеризуются разрежённой (с малой плотностью ненулевых элементов) проверочной матрицей. Они относятся к группе кодов, исправляющих ошибки, и применяются в системах цифровой связи и хранения данных для обеспечения надёжности передачи информации при наличии шумов и искажений. Основное свойство LDPC-кодов — способность достигать пропускной способности канала (предела Шеннона) при достаточно больших длинах кодовых слов, что делает их одними из наиболее эффективных в современной теории кодирования.

История

Ранние работы

Концепция кодов с малой плотностью проверок на чётность была впервые предложена Робертом Галлагером в 1960 году в его докторской диссертации в Массачусетском технологическом институте (MIT). В 1963 году он опубликовал статью, в которой описал принципы построения таких кодов и методы их декодирования. Однако в то время вычислительные мощности были недостаточны для практической реализации, и коды оставались малоизвестными. В 1960-х годах также были предложены аналогичные идеи, но они не получили широкого распространения.

Возрождение интереса

Интерес к LDPC-кодам возродился в середине 1990-х годов благодаря работам Дэвида Маккея и Радигера Нила, которые независимо переоткрыли и усовершенствовали коды Галлагера. В 1996 году Маккей и Нил опубликовали статью, демонстрирующую, что LDPC-коды могут достигать производительности, близкой к пределу Шеннона, при использовании итеративных алгоритмов декодирования. Это стимулировало активные исследования в области кодирования, и к началу 2000-х годов LDPC-коды стали применяться в практических системах, таких как спутниковая связь и цифровое телевидение.

Современное состояние

С 2000-х годов LDPC-коды были стандартизированы в ряде международных стандартов, включая DVB-S2 (цифровое спутниковое телевидение), IEEE 802.11n (Wi-Fi), IEEE 802.16e (WiMAX), 5G NR (сети мобильной связи пятого поколения) и другие. Они также используются в системах хранения данных, таких как твердотельные накопители (SSD) и жёсткие диски, для коррекции ошибок при чтении/записи.

Определение и основные понятия

Линейные блоковые коды

LDPC-коды являются подклассом линейных блоковых кодов. В общем случае линейный блоковый код задаётся проверочной матрицей H размера \(m \times n\), где \(n\) — длина кодового слова, а \(m\) — количество проверочных уравнений. Кодовое слово x длины \(n\) удовлетворяет условию \(\mathbf{Hx} = \mathbf{0}\) (над полем GF(2)). Для LDPC-кодов матрица H является разрежённой, то есть содержит значительно меньше единиц, чем нулей. Обычно плотность единиц (отношение числа единиц к общему числу элементов) составляет менее 0,1, а для длинных кодов — менее 0,01.

Разрежённость

Разрежённость матрицы H — ключевое свойство, которое позволяет эффективно декодировать LDPC-коды с помощью итеративных алгоритмов, таких как алгоритм «сумма-произведение» (belief propagation). Разрежённость также упрощает аппаратную реализацию кодеров и декодеров.

Регулярные и нерегулярные коды

LDPC-коды делятся на два основных типа:

• Регулярные коды: в проверочной матрице каждый столбец имеет одинаковое количество единиц (степень столбца \(d_v\)), а каждая строка — одинаковое количество единиц (степень строки \(d_c\)). Например, регулярный (3,6)-код имеет степень столбца 3 и степень строки 6.
• Нерегулярные коды: степени столбцов и строк могут различаться. Нерегулярные коды часто обеспечивают лучшую производительность, так как позволяют оптимизировать распределение степеней для улучшения сходимости декодирования.

Устройство и характеристики

Проверочная матрица

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

Граф Таннера

LDPC-коды могут быть представлены в виде двудольного графа, называемого графом Таннера. Граф состоит из двух типов узлов:

• Узлы переменных (variable nodes) — соответствуют битам кодового слова (столбцам матрицы H).
• Узлы проверок (check nodes) — соответствуют проверочным уравнениям (строкам матрицы H).

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

Декодирование

Декодирование LDPC-кодов выполняется итеративно с использованием алгоритма «сумма-произведение» (belief propagation). Этот алгоритм основан на передаче сообщений между узлами графа Таннера. На каждой итерации:

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

Алгоритм продолжается до тех пор, пока не будет найдено допустимое кодовое слово или не будет достигнуто максимальное число итераций. Для ускорения декодирования часто используются упрощённые варианты, такие как минимально-суммовый алгоритм (min-sum algorithm).

Длина кодового слова

Производительность LDPC-кодов улучшается с увеличением длины кодового слова \(n\). Для достижения близкой к пределу Шеннона производительности обычно требуются коды длиной от нескольких тысяч до десятков тысяч бит. Однако длинные коды требуют больше вычислительных ресурсов для декодирования.

Применение

Цифровая связь

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

• Спутниковая связь: стандарт DVB-S2 (Digital Video Broadcasting — Satellite — Second Generation) использует LDPC-коды для обеспечения высокой надёжности передачи данных.
• Мобильная связь: в стандарте 5G NR (New Radio) LDPC-коды применяются для каналов передачи данных, обеспечивая высокую скорость и низкую задержку.
• Wi-Fi: стандарт IEEE 802.11n (и более поздние версии) включает LDPC-коды как опциональный метод кодирования для повышения производительности в условиях помех.

Хранение данных

В системах хранения данных, таких как твердотельные накопители (SSD) и жёсткие диски, LDPC-коды используются для коррекции ошибок, возникающих из-за износа ячеек памяти или дефектов поверхности диска. Например, в современных SSD контроллеры часто реализуют LDPC-декодирование для увеличения срока службы и надёжности.

Космическая связь

LDPC-коды применяются в космических миссиях для передачи данных на большие расстояния, где уровень шума высок. Например, НАСА использует LDPC-коды в некоторых спутниковых системах.

Цифровое телевидение

Стандарты DVB-T2 (наземное цифровое телевидение) и DVB-C2 (кабельное цифровое телевидение) также включают LDPC-коды для обеспечения устойчивости к помехам.

Сравнение с другими кодами

Свёрточные коды

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

Коды Рида — Соломона

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

Турбокоды

Турбокоды, разработанные в 1993 году, также являются итеративными и могут достигать производительности, близкой к пределу Шеннона. LDPC-коды и турбокоды имеют схожую производительность, но LDPC-коды часто проще реализовать в аппаратуре благодаря разрежённой структуре. В некоторых приложениях, таких как 5G NR, LDPC-коды были выбраны вместо турбокодов из-за лучшей масштабируемости и меньшей сложности декодирования.

Интересные факты

• LDPC-коды были впервые описаны Робертом Галлагером в 1960 году, но оставались невостребованными до 1990-х годов из-за ограниченных вычислительных возможностей.
• Термин «low-density parity-check» (малая плотность проверок на чётность) отражает ключевое свойство — разрежённость проверочной матрицы.
• В 2009 году LDPC-коды были включены в стандарт DVB-S2, что способствовало их широкому внедрению в спутниковое телевидение.
• Алгоритм декодирования «сумма-произведение» для LDPC-кодов является частным случаем общих методов вероятностного вывода на графах, используемых в машинном обучении.
• В 2016 году LDPC-коды были выбраны в качестве основного метода кодирования для каналов данных в стандарте 5G NR, заменив турбокоды, использовавшиеся в 4G LTE.

Источники

• Gallager, R. G. (1963). Low-Density Parity-Check Codes. MIT Press.
• MacKay, D. J. C., & Neal, R. M. (1996). Near Shannon limit performance of low density parity check codes. Electronics Letters, 32(18), 1645–1646.
• Richardson, T. J., & Urbanke, R. L. (2001). The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2), 599–618.
• 3GPP TS 38.212: Multiplexing and channel coding (5G NR).
• ETSI EN 302 307: Digital Video Broadcasting (DVB) — Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications (DVB-S2).