QC-LDPC

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

История

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

Квазициклические LDPC-коды (QC-LDPC) стали развитием этой идеи. В начале 2000-х годов исследователи, в том числе Томас Ричардсон и Рудигер Урбанке, обратили внимание на то, что LDPC-коды с регулярной структурой, основанной на циклических сдвигах, могут быть реализованы с меньшими аппаратными затратами и более высокой скоростью, чем коды с произвольной (случайной) проверочной матрицей. Это привело к включению QC-LDPC в ряд промышленных стандартов, начиная с 2000-х годов.

Определение и структура

QC-LDPC-код определяется своей проверочной матрицей H размера \( m \times n \), где \( m \) — количество проверок на чётность, а \( n \) — длина кодового слова. Матрица H строится из квадратных подматриц (блоков) размера \( Z \times Z \), где \( Z \) — целое число, называемое размером циклического сдвига (или фактором расширения). Каждый блок является либо нулевой матрицей, либо циклически сдвинутой единичной матрицей.

Формально, пусть \( I \) — единичная матрица размера \( Z \times Z \). Тогда циклический сдвиг \( I \) на \( p \) позиций вправо (или влево) обозначается как \( I^p \). Если \( p = 0 \), то \( I^0 = I \). Если \( p = -1 \) (или другое специальное значение), то блок является нулевой матрицей \( \mathbf{0}_{Z \times Z} \). Таким образом, проверочная матрица QC-LDPC-кода имеет вид:

\[ H = \begin{pmatrix} I^{p_{1,1}} & I^{p_{1,2}} & \cdots & I^{p_{1,n_b}} \\ I^{p_{2,1}} & I^{p_{2,2}} & \cdots & I^{p_{2,n_b}} \\ \vdots & \vdots & \ddots & \vdots \\ I^{p_{m_b,1}} & I^{p_{m_b,2}} & \cdots & I^{p_{m_b,n_b}} \end{pmatrix} \]

где \( m_b = m / Z \) — количество блоков по вертикали, \( n_b = n / Z \) — количество блоков по горизонтали, а \( p_{i,j} \) — целые числа от \(-1\) до \( Z-1 \), определяющие сдвиг.

Свойства структуры

• Цикличность: Код называется квазициклическим, потому что любое циклическое кодовое слово, сдвинутое на \( Z \) позиций, также является кодовым словом. Это свойство упрощает реализацию кодеров и декодеров.
• Регулярность: QC-LDPC-коды могут быть как регулярными (каждая строка и каждый столбец матрицы H имеют одинаковое количество единиц), так и нерегулярными. Однако на практике часто используются нерегулярные коды для достижения лучшей производительности.
• Плотность: Матрица H остаётся разреженной (малая плотность единиц), так как большинство блоков являются нулевыми, а ненулевые блоки содержат ровно \( Z \) единиц.

Классификация

QC-LDPC-коды можно классифицировать по нескольким признакам:

По типу матрицы сдвигов

• Двоичные QC-LDPC: Элементы матрицы сдвигов \( p_{i,j} \) принимают значения \(-1\) (нулевой блок) или \( 0 \ldots Z-1 \). Это наиболее распространённый тип.
• Недвоичные QC-LDPC: Элементы матрицы сдвигов могут быть не только числами, но и элементами конечного поля \( GF(q) \), где \( q > 2 \). Такие коды могут обеспечивать лучшую корректирующую способность, но сложнее в реализации.

По способу построения

• Случайные QC-LDPC: Матрица сдвигов генерируется с помощью псевдослучайных чисел, но с учётом ограничений на длину циклов (girth) в графе Таннера.
• Алгебраические QC-LDPC: Матрица сдвигов строится на основе алгебраических структур, таких как конечные поля, циклические группы или комбинаторные конструкции (например, латинские квадраты). Это позволяет гарантировать отсутствие коротких циклов (длиной 4) и упрощает анализ.
• Прототипные (protograph-based) QC-LDPC: Сначала строится небольшая базовая матрица (протограф), а затем она расширяется с помощью циклических сдвигов. Этот метод широко используется в стандартах.

Применение

QC-LDPC-коды нашли широкое применение в системах связи и хранения данных благодаря своей эффективности и простоте реализации. Основные области применения:

Стандарты связи

• DVB-S2 и DVB-S2X (цифровое спутниковое телевидение): Используются QC-LDPC-коды с длиной кодового слова до 64800 бит для обеспечения высокой помехоустойчивости.
• IEEE 802.11n/ac/ax (Wi-Fi): В стандарте Wi-Fi 5 (802.11n) и более поздних версиях применяются QC-LDPC-коды с длиной 648, 1296 или 1944 бит.
• IEEE 802.16e (WiMAX): Используются QC-LDPC-коды с длиной от 576 до 2304 бит.
• 5G NR (New Radio): В стандарте 5G используются QC-LDPC-коды для каналов передачи данных (PDSCH, PUSCH) с длиной кодового слова до 8448 бит. Для каналов управления применяются полярные коды.
• CCSDS (Консультативный комитет по космическим системам данных): Для космической связи (например, с МКС или спутниками) рекомендованы QC-LDPC-коды с длиной 1024, 4096 или 16384 бит.

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

• NAND Flash-память: Многие современные твердотельные накопители (SSD) и карты памяти используют QC-LDPC-коды для коррекции ошибок, возникающих из-за износа ячеек памяти. Например, в контроллерах от компаний Samsung, Micron и Western Digital.
• Магнитные жёсткие диски (HDD): В некоторых моделях HDD, особенно с высокой плотностью записи (HAMR, MAMR), применяются QC-LDPC-коды для повышения надёжности.

Оптические сети

• ITU-T G.709 (OTN — Optical Transport Network): Используются QC-LDPC-коды для коррекции ошибок в оптических каналах связи со скоростью до 400 Гбит/с и выше.

Характеристики и производительность

QC-LDPC-коды обладают рядом характеристик, которые делают их привлекательными для практического использования:

• Высокая корректирующая способность: При достаточно большой длине кодового слова (например, 64800 бит) QC-LDPC-коды могут работать на расстоянии менее 1 дБ от предела Шеннона для канала с аддитивным белым гауссовским шумом (AWGN).
• Эффективность декодирования: Итеративные алгоритмы декодирования (например, алгоритм распространения доверия, Belief Propagation) имеют сложность, линейно зависящую от длины кодового слова, что позволяет декодировать со скоростью до нескольких гигабит в секунду в аппаратных реализациях.
• Низкая задержка: Благодаря структуре QC-LDPC, декодер может обрабатывать блоки данных параллельно, что снижает задержку по сравнению с последовательными декодерами (например, для турбокодов).
• Простота реализации: Квазициклическая структура позволяет использовать простые сдвиговые регистры для кодирования, а не сложные матричные операции. Это снижает площадь кристалла и энергопотребление.

Недостатки

• Чувствительность к коротким циклам: В графе Таннера QC-LDPC-кода могут возникать циклы длины 4, которые ухудшают производительность итеративного декодирования. Для устранения этой проблемы требуется тщательное проектирование матрицы сдвигов.
• Ограниченная гибкость: Для каждой длины кодового слова и скорости кода требуется своя матрица сдвигов, что может усложнить адаптацию к различным условиям канала.

Примеры

QC-LDPC в стандарте 5G NR

В стандарте 5G NR (3GPP TS 38.212) определены два базовых графа (Base Graph 1 и Base Graph 2) для QC-LDPC-кодов. Каждый базовый граф представляет собой матрицу размера \( m_b \times n_b \), где \( m_b = 46 \) для BG1 и \( m_b = 42 \) для BG2, а \( n_b = 68 \) и \( n_b = 52 \) соответственно. Размер циклического сдвига \( Z \) может принимать значения от 2 до 384, что позволяет адаптировать длину кодового слова к различным сценариям (от 256 до 8448 бит). Матрица сдвигов для каждого \( Z \) задаётся в таблицах стандарта.

QC-LDPC в DVB-S2

В стандарте DVB-S2 (ETSI EN 302 307) используются QC-LDPC-коды с длиной кодового слова 64800 бит (нормальный режим) и 16200 бит (короткий режим). Скорости кода варьируются от 1/4 до 9/10. Проверочная матрица строится из блоков размером \( Z = 360 \) для нормального режима и \( Z = 90 \) для короткого режима. Матрица сдвигов является фиксированной и приведена в приложении к стандарту.

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

• QC-LDPC-коды являются частным случаем так называемых «квазициклических кодов» (Quasi-Cyclic Codes), которые изучались ещё в 1960-х годах, но их связь с LDPC-кодами была установлена только в конце 1990-х.
• В 2016 году QC-LDPC-коды были выбраны для стандарта 5G NR вместо турбокодов, которые использовались в 4G LTE, из-за их лучшей производительности при высоких скоростях передачи данных.
• Аппаратные реализации QC-LDPC-декодеров в современных чипах (например, в ASIC для 5G) могут достигать пропускной способности до 100 Гбит/с при энергопотреблении менее 1 Вт.

Источники

• 3GPP TS 38.212: «NR; Multiplexing and channel coding» (v. 17.0.0, 2022).
• 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» (v. 1.2.1, 2009).
• IEEE Std 802.11-2020: «IEEE Standard for Information Technology—Telecommunications and Information Exchange between Systems—Local and Metropolitan Area Networks—Specific Requirements—Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications».
• R. Gallager, «Low-Density Parity-Check Codes», IRE Transactions on Information Theory, vol. 8, no. 1, pp. 21–28, 1962.
• D. MacKay, «Good Error-Correcting Codes Based on Very Sparse Matrices», IEEE Transactions on Information Theory, vol. 45, no. 2, pp. 399–431, 1999.
• T. Richardson and R. Urbanke, «Efficient Encoding of Low-Density Parity-Check Codes», IEEE Transactions on Information Theory, vol. 47, no. 2, pp. 638–656, 2001.
• S. Lin and D. Costello, «Error Control Coding: Fundamentals and Applications», 2nd ed., Pearson, 2004.
• CCSDS 131.1-O-2: «Low Density Parity Check Codes for Use in Near-Earth and Deep Space Applications», 2007.