Коды с низкой плотностью проверки четности (LDPC) стали краеугольным камнем современных цифровых систем связи, обеспечивая надежную передачу данных вблизи предела Шеннона. Впервые введенные Робертом Галлагером в его докторской диссертации 1963 года и позже вновь открытые в 1990-х годах, эти коды теперь являются неотъемлемой частью стандартов, таких как DVB-S2, Wi-Fi (IEEE 802.11n / ac /ax), 5G NR и связь в глубоком космосе. Возможность корректировать скорость кода - то есть отношение битов информации к общим передаваемым битам - имеет важное значение для адаптации к различным условиям канала и требованиям к качеству обслуживания. Два основных метода для корректировки скорости кода без изменения всей структуры кода - это пунктуация и сокращение. Оба метода изменяют эффективную скорость кода при использовании одной и той же базовой матрицы LDPC, предлагая гибкость для систем, совместимых с частотой. В этой статье рассматриваются принципы, детали реализации и практические компромиссы пунктуации и сокращения в контексте кодов LDPC.

Основы кодов LDPC

Код LDPC представляет собой линейный блок-код, определяемый разреженной матрицей проверки четности H, размером mn. Разреженность H означает, что он содержит очень мало алгоритмов, которые позволяют эффективно распространять убеждения (также известный как алгоритм сум-продукта), выполняемых на представлении графа Таннера.n битов кодового слова, а чековые узлы соответствуют m уравнениям проверки четности.H. Действительные кодовые слова удовлетворяют всем уравнениям проверки четности:HcT =

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

Зачем корректировать тарифы кода?

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

Техника пунктуации

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

Математически, если материнский код имеет длину n и k, пунктуирование k/npp, что даёт эффективную скорость k/, которая выше, чем скорость материнского кода.-битный набор переменных узлов — проколотые переменные узлы инициализируются с нулевыми коэффициентами лог-вероятности (LLR), что указывает на максимальную неопределенность (т.е., стирание). Во время итеративного декодирования сообщения от проверочных узлов могут предоставлять информацию о стертых узлах, часто позволяя успешное восстановление, если число проколотых битов не слишком велико относительно возможности кода исправления ошибок.

Проточные шаблоны и соображения дизайна

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

  • Регулярное прокалывание: Удалить биты по фиксированному периодическому шаблону. Это просто, но может быть не оптимальным.
  • Точечные узлы с массой колонки: Приоритетное прокалывание переменных узлов с меньшим весом колонки (меньше соединений для проверки узлов), потому что они вносят меньший вклад в декодирование.Точечные узлы с более высоким весом, как правило, вызывают более серьезную потерю производительности.
  • Пунктурирование с учетом восстановления: Разработайте шаблон так, чтобы проколотые узлы можно было быстро восстановить — обычно путем обеспечения того, чтобы каждый проколотый узел был подключен по меньшей мере к одному контрольному узлу, чьи другие соседи все передаются (т.е. «узел проверки восстановления»).

Одной из важных концепций является дерево восстановления : после определенного количества декодирующих итераций LLR проколотого переменного узла может стать ненулевым из-за внешней информации от контрольных узлов. Чем глубже дерево восстановления, тем больше итераций необходимо. Для совместимых с курсом семейств часто предварительно вычисляются «уровни прокола» для достижения диапазона целевых показателей с минимальным ухудшением производительности. Например, стандарт DVB-S2 определяет набор шаблонов прокола для своих кодов LDPC для получения нескольких частот кода из одного материнского кода.

Влияние на сложность декодирования

Прокалывание не увеличивает сложность декодирования на итерацию, поскольку в графе Таннера присутствует одинаковое количество переменных и контрольных узлов. Однако количество итераций, необходимых для конвергенции, может увеличиваться из-за начальных стираний. Кроме того, декодер должен знать шаблон прокалывания для соответствующей инициализации LLR. В целом, прокалывание является методом низкой сложности для достижения более высоких скоростей, что делает его популярным в адаптивных системах.

Техника сокращения

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

Рассмотрим материнский код с k информационными битами и n полными битами k/n. Если мы сокращаем s] битами информации, то фактически передаваемое кодовое слово состоит из k — s битов чётности и n — k битов чётности, для общего числа n — s. Эффективная скорость становится k — s/n — s, которая ниже, чем скорость чётности материнского кода. Декодер использует полную матрицу проверки чётности, но инициализирует LLR

Осуществление и результативность

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

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

Торговля и взаимодействие с пунктуированием

Укорочение и прокол часто объединяются для достижения точной адаптации скорости. Например, система может использовать материнский код со скоростью 1/2, затем применять прокол для повышения скорости до 2/3 или 3/4 и одновременно применять укорочение для снижения скорости до 1/3 или 1/4. Этот двойной подход позволяет одному декодеру покрывать широкий диапазон скоростей. Однако комбинация должна быть тщательно разработана: если много битов укорочены и проколоты (что было бы избыточным), производительность может пострадать. Как правило, системы либо сокращают информационные биты для снижения скорости, либо проколы четности битов для повышения скорости, но не оба на одних и тех же битах.

Один общий сценарий, где используются оба метода, заключается в постепенном резервировании (IR) гибридного автоматического повторного запроса (HARQ). Первоначально отправляется высокочастотное проколотое кодовое слово. Если декодирование не удается, дополнительные биты четности (которые были ранее проколоты) передаются в последующих ретрансляциях - это, по сути, ИК-схема, основанная на проколе. Укорочение может быть использовано для снижения эффективной скорости, если исходный материнский код слишком высок для канала.

Сравнение пунктуации и укорочения

AspectPuncturingShortening
Effect on code rateIncreases rate (less redundancy)Decreases rate (more redundancy)
Bits removed/not transmittedParity (or systematic) bits are omittedInformation bits are set to known value and omitted
State at decoderPunctured bits are erasures (LLR=0)Shortened bits have perfect LLR (large magnitude)
Performance trade-offHigher rate → less error correction; may need more iterationsLower rate → stronger error correction; increased overhead
ComplexitySame decoder graph; increased iterations possibleSame decoder graph; no extra iterations needed
Design challengePuncturing pattern must be optimized to avoid error floorMinimal design effort; works well for small shortening amounts
Common useAdaptive rate increase, ARQ, rate-compatible familiesFine rate reduction, code shortening for specific block sizes

Применение в современных стандартах

Как пунктуация, так и укорочение развернуты в основных стандартах связи. В DVB-S2 и его расширении DVB-S2X поддерживаются коды LDPC скорости 1/4-9/10. Они получены из общего набора материнских кодов с использованием пунктуации и укорочения. Стандарт определяет конкретные шаблоны для достижения каждой целевой скорости, обеспечивая почти оптимальную производительность. Аналогично, 5G NR использует коды LDPC для канала данных, с базовыми графами (BG1 и BG2), предназначенными для поддержки скорости-совместимости. Пунктуация используется для достижения самых высоких скоростей, в то время как укорочение (в сочетании с повторением) помогает достичь самых низких скоростей. Стандарт 5G также использует «блок CRC» и HARQ, который опирается на инкрементную избыточность с использованием проколотых битов четности.

В Wi-Fi 802.11n/ac/ax коды LDPC необязательны, но широко реализуются. Стандарт определяет набор частот кода (1/2, 2/3, 3/4, 5/6) для каждой длины блока. Эти скорости достигаются, начиная от материнского кода скорости-1/2 и прокалывания для получения более высоких частот или путем сокращения для получения более низких частот (хотя сокращение менее распространено в этом контексте). Рабочая группа IEEE 802.11 опубликовала оценки производительности, которые подтверждают использование проколотых кодов LDPC для сценариев с высокой пропускной способностью.

Глубоководные миссии, например, NASA, использующие стандарт CCSDS, также полагаются на коды LDPC с прокалыванием и укорочением для телеметрии и командных звеньев.Способность корректировать скорость кода без изменения аппаратного декодера неоценима для длительных миссий, где условия канала непредсказуемы.

Метрики производительности и оптимизация

При проектировании системы, совместимой со скоростью, с использованием пунктуации и укорочения, инженеры оценивают частоту ошибок битов (BER) и частоту ошибок кадра (FER) как функции отношения сигнал-шум (SNR). Цель состоит в том, чтобы приблизиться к пределу Шеннона для каждой эффективной скорости. Пунктура обычно вводит небольшое наказание по сравнению с выделенным материнским кодом той же скорости, но штраф может быть минимизирован посредством тщательного проектирования шаблона. Укорочение, поскольку оно добавляет известные биты, часто выполняет очень близко к естественному низкоскоростному коду того же измерения.

Другой важной метрикой является этаж ошибок — область с высокой SNR, где частота ошибок уплощается из-за наборов захватов или небольших циклов в графе Таннера. Прокалывание может поднять пол ошибок, если плохо спроектировано, особенно для кодов LDPC с умеренной длиной блока. Укорочение, с другой стороны, редко вводит новые наборы захватов, потому что это только уменьшает количество информационных битов без изменения топологии графа.

Исследователи предложили множество алгоритмов для совместной оптимизации шаблонов пунктуации, включая эволюцию плотности, диаграммы внешней передачи информации (EXIT) и генетические алгоритмы. Например, работа Ха, Кима и Маклафлина (] «Совместимость с прокалкой кодов с низкой плотностью с проверкой паритета с короткими блоковыми длинами» , IEEE Транзакции по теории информации, 2004) обеспечивает основополагающую основу для разработки хороших шаблонов прокалывания. Аналогично, для сокращения влияние на внешние сообщения декодера можно анализировать с использованием эволюции плотности, чтобы обеспечить отсутствие деградации.

Заключение

Прокалывание и укорочение являются важными инструментами для корректировки скорости кода кодов LDPC без необходимости множественных различных реализаций кодера и декодера. Прокалывание увеличивает эффективную скорость, опуская биты, превращая их в стирания на декодере, в то время как укорочение снижает скорость, фиксируя информационные биты к известным значениям и не передавая их. Оба метода сохраняют базовую структуру матрицы LDPC, обеспечивая гибкую совместимость скорости для адаптивных систем связи. Современные стандарты, такие как DVB-S2, 5G NR и Wi-Fi, полагаются на эти методы для обеспечения надежной производительности в широком диапазоне условий канала. При продолжающихся достижениях в оптимизации шаблонов и дизайне декодера, проколотые и укороченные коды LDPC остаются яркой областью исследований и практическим краеугольным камнем цифровых коммуникаций.