Skip to content
Назад к результатам поиска

Коды с низкой плотностью проверок на чётность (LDPC)

Автор метода
Robert Gallager
Год
1962
Тип
linear error-correcting code
Семейство
Coding theory

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Коды LDPC, изобретённые Робертом Галлагером в 1962 году и вновь открытые в 1990-х годах Маккеем, представляют собой линейные коды коррекции ошибок, определяемые разреженными матрицами проверок на чётность.

Они достигают производительности в пределах 0,4 дБ от предела Шеннона при итеративном декодировании с распространением свидетельств и стали стандартом для современных беспроводных систем (WiFi-6, 5G NR, Digital Video Broadcasting). В отличие от турбокодов, коды LDPC имеют более элегантную графовую структуру и более зрелый теоретический анализ.

Интуиция метода

Стандартные линейные коды используют плотные матрицы проверок на чётность, что делает декодирование вычислительно интенсивным. Коды LDPC переворачивают эту ситуацию: матрица проверок на чётность разрежена (большинство элементов равны нулю), поэтому каждая проверка на чётность включает лишь горстку битов. На приёмной стороне строится двудольный граф, где узлы переменных представляют передаваемые биты, а узлы проверок — ограничения на чётность. Декодирование становится итеративным прохождением сообщений по этому графу: каждый узел переменных собирает информацию от своих соседей, обновляет своё представление о значении бита и отправляет уточнённые оценки обратно. Разреженность обеспечивает быструю сходимость и производительность, близкую к пределу Шеннона.

История

Галлагер изобрёл коды LDPC в 1962 году, но теория отставала от практической реализации. В 1995 году Маккей заново открыл их и продемонстрировал их производительность, близкую к пределу Шеннона, с помощью симуляций. Обширные исследования в 2000-х годах разработали эффективные алгоритмы кодирования, декодирования и построения графов. Коды LDPC были приняты в стандарте WiFi-6 (802.11ax, 2021) и 5G NR (2018). Они стали более распространёнными, чем турбокоды, в новых системах благодаря лучшей производительности и более чистой структуре.

Когда применять

Коды LDPC предпочтительнее турбокодов в современных системах благодаря лучшей производительности и более простой архитектуре. Используйте LDPC для широких диапазонов отношения сигнал/шум (SNR) (без резкого порога); они хорошо работают как при низком, так и при высоком SNR. LDPC — стандарт для WiFi-6, спутниковой связи и 5G NR. Избегайте LDPC только в том случае, если требуется совместимость с устаревшими системами, использующими турбокоды. LDPC также подходит для очень коротких пакетов (>30 бит), поскольку структура кода является разделимой.

Ограничения и замечания

  • Построение графа и хранение матрицы становятся сложными для очень длинных кодов (>10 тыс. бит)
  • Производительность чувствительна к мелкомасштабным структурам графа (обхватам, поглощающим множествам); требует тщательного проектирования
  • Распространение свидетельств предполагает граф без циклов, но графы имеют циклы; сходимость к оптимальному решению не гарантируется
  • Задержка декодирования (итерации) растёт логарифмически с SNR; не является нулевой, как у некоторых классических кодов
  • Квантование сообщений (в аппаратуре с фиксированной точкой) влияет на производительность; требуется тщательное распределение битов

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Производительность в пределах 0,4 дБ от предела Шеннона (немного лучше, чем у турбокодов)
  • Более простая графовая структура; более чистый теоретический анализ, чем у турбокодов
  • Итеративное декодирование избегает резкого порогового поведения (в отличие от турбокодов)
  • Гибкая конструкция кода через построение графа; легко адаптируется к конкретным приложениям
  • Эффективное параллельное аппаратное декодирование; прохождение сообщений подходит для реализации на VLSI/GPU
  • Хорошо работает как для длинных, так и для умеренно коротких кодовых слов

Применение

  • WiFi-6 (802.11ax): высокоскоростные беспроводные локальные сети с LDPC, обеспечивающими надёжную доставку данных
  • 5G NR: кодирование каналов как для каналов данных, так и для каналов управления, заменяющее турбокоды из 4G
  • Спутниковая связь: цифровое видеовещание (DVB-S2) и миссии в дальний космос с использованием LDPC с длинными кодовыми словами
  • Коммуникации по силовым линиям (PLC): надёжная передача данных по зашумлённым электрическим сетям
  • Системы флэш-памяти: коррекция ошибок для хранения NAND flash без износа от частых обновлений

Как это работает

Как это работает

1

Информационные биты кодируются с использованием разреженной матрицы проверок на чётность H; закодированные биты являются решением уравнения H*c = 0 (mod 2), где c — кодовое слово.

2

Матрица проверок на чётность H имеет разреженную структуру (например, каждая строка/столбец имеет постоянный малый вес 3-5). Эта структура используется для эффективного кодирования.

3

Закодированные биты передаются по зашумлённому каналу; полученные биты являются мягкими значениями (отношениями правдоподобия или логарифмическими отношениями правдоподобия).

4

Строится двудольный граф: левые узлы = узлы переменных (биты), правые узлы = узлы проверок (уравнения на чётность). Ребра соединяют переменные с проверками, в которых они участвуют.

5

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

Частые ошибки

  • Использование плохо спроектированного разреженного графа с короткими циклами; короткие циклы вызывают колебания при распространении свидетельств
  • Чрезмерное количество итераций сверх сходимости; ненужные итерации тратят энергию без улучшения
  • Предположение, что декодирование по минимуму так же хорошо, как и по сумме-произведению; приближения приводят к потере производительности, особенно при низком SNR
  • Пренебрежение эффектами конечной длины; графы, разработанные для асимптотического анализа, могут показывать низкую производительность на коротких пакетах
  • Неучёт квантования при аппаратной реализации; симуляция в числах с плавающей запятой отличается от реальности с фиксированной точкой

Часто задаваемые вопросы

Что делает декодирование LDPC таким эффективным по сравнению с общими линейными кодами?

Разреженность матрицы проверок на чётность означает, что каждый бит участвует лишь в нескольких проверках на чётность. При декодировании прохождение сообщений по двудольному графу линейно по количеству ребер, а не по длине кода. Для плотных кодов декодирование потребовало бы обращения матрицы, что кубически зависит от длины кода. Разреженность делает декодирование квазилинейным и практичным для длинных кодов.

Что такое поглощающее множество и почему оно важно?

Поглощающее множество — это небольшое подмножество графа, которое может заблокировать декодирование методом распространения свидетельств, препятствуя сходимости к правильному решению. Они являются основной причиной ошибки на уровне (error floor) (неэкспоненциальное снижение частоты битовых ошибок (BER) при низком SNR). Разработчики кода избегают коротких поглощающих множеств путём тщательного построения графа; инструменты анализа (например, анализ множеств остановки) выявляют проблемные структуры.

Как LDPC сравниваются с полярными кодами?

Оба достигают производительности, близкой к пределу Шеннона. Полярные коды имеют рекурсивную структуру и доказуемую оптимальность при последовательном декодировании отмены при бесконечной длине кода. Коды LDPC более гибки и эмпирически показывают лучшую производительность при конечной длине. 5G NR использует полярные коды для каналов управления (короткие пакеты) и LDPC для каналов данных (длинные пакеты), используя сильные стороны каждого кода.

Почему обхват графа важен в кодах LDPC?

Обхват — это длина кратчайшего цикла в двудольном графе. Короткие циклы (обхват < 6) заставляют распространение свидетельств использовать коррелированную информацию (сообщения возвращаются по кругу), что ухудшает производительность. Коды с высоким обхватом (обхват ≥ 6) лучше разрывают корреляции. Коды часто проектируются так, чтобы максимизировать обхват при соблюдении ограничений на разреженность.

Похожие методы

Источники

  1. Gallager, R. G. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1), 21-28.

    Открыть ссылку DOI
    Скопировано.
  2. 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.

    Открыть ссылку DOI
    Скопировано.