В теории информации код с низкой плотностью проверки четности ( LDPC ) — это линейный код с исправлением ошибок , метод передачи сообщения по зашумленному каналу передачи. [1] [2] Код LDPC строится с использованием разреженного графа Таннера (подкласс двудольного графа ). [3] Коды LDPC являются кодами, приближающимися к пропускной способности , а это означает, что существуют практические конструкции, которые позволяют устанавливать шумовой порог очень близко к теоретическому максимуму ( пределу Шеннона ) для симметричного канала без памяти. Шумовой порог определяет верхнюю границу шума канала, до которой вероятность потери информации может быть минимальной. Используя итеративные методы распространения доверия , коды LDPC можно декодировать во времени, линейном по длине блока.
Коды LDPC также известны как коды Галлагера в честь Роберта Г. Галлагера , который разработал концепцию LDPC в своей докторской диссертации в Массачусетском технологическом институте в 1960 году . [4] [5] Однако коды LDPC требуют дорогостоящего итеративного декодирования. , поэтому они десятилетиями не использовались. В 1993 году недавно изобретенные турбокоды продемонстрировали, что коды с итеративным декодированием могут значительно превосходить другие коды, использовавшиеся в то время, но турбокоды были запатентованы и требовали платы за использование. Это вызвало возобновление интереса к кодам LDPC, которые, как было показано, имели аналогичные характеристики, но были намного старше и не имели патентов. [6] Теперь, когда срок действия фундаментального патента на турбокоды истек (29 августа 2013 г.), [7] [8] коды LDPC все еще используются из-за своих технических достоинств.
Было показано, что коды LDPC обладают идеальными комбинаторными свойствами. В своей диссертации Галлагер показал, что LDPC-коды с высокой вероятностью достигают границы Гилберта-Варшамова для линейных кодов над двоичными полями. В 2020 году было показано, что LDPC-коды Галлагера достигают способности декодирования списков , а также достигают границы Гилберта-Варшамова для линейных кодов над общими полями. [9]
Коды LDPC, впервые разработанные Галлагером в 1963 году, были непрактичны для реализации , [10] коды LDPC были забыты до тех пор, пока его работа не была вновь открыта в 1996 году . [11] Турбокоды , еще один класс кодов, приближающихся к емкости, открытый в 1993 году, стал предпочтительной схемой кодирования в в конце 1990-х годов использовался для таких приложений, как сеть дальнего космоса и спутниковая связь . Затем коды LDPC вновь вызвали интерес как непатентованная альтернатива с аналогичными характеристиками. [6] С тех пор достижения в области кодов с низкой плотностью контроля четности привели к тому, что они превзошли турбокоды с точки зрения минимального уровня ошибок и производительности в более высоком диапазоне кодовых скоростей , в результате чего турбокоды лучше подходят только для более низких скоростей кодирования. [12]
В 2003 году код LDPC в стиле нерегулярного повторения (IRA) превзошел шесть турбокодов и стал кодом исправления ошибок в новом стандарте DVB-S2 для цифрового телевидения . [13] Отборочный комитет DVB-S2 сделал оценку сложности декодера для предложений турбокода, используя гораздо менее эффективную архитектуру последовательного декодера, а не архитектуру параллельного декодера. Это вынудило предложения турбокодов использовать размеры кадров порядка половины размера кадра предложений LDPC. [ нужна цитата ]
В 2008 году LDPC превзошла сверточные турбокоды в качестве системы прямого исправления ошибок (FEC) для стандарта ITU-T G.hn. [14] G.hn предпочел коды LDPC турбокодам из-за их меньшей сложности декодирования (особенно при работе со скоростями передачи данных, близкими к 1,0 Гбит/с), а также потому, что предложенные турбокоды демонстрировали значительный минимальный уровень ошибок в желаемом диапазоне работы. [15]
Коды LDPC также используются для Ethernet 10GBASE-T , который передает данные со скоростью 10 гигабит в секунду по витой паре. С 2009 года коды LDPC также являются частью стандарта Wi-Fi 802.11 в качестве дополнительной части 802.11n и 802.11ac в спецификации PHY высокой пропускной способности (HT). [16] LDPC является обязательной частью стандарта 802.11ax (Wi-Fi 6). [17]
Некоторые системы OFDM добавляют дополнительную внешнюю коррекцию ошибок, которая исправляет случайные ошибки («минимальный уровень ошибок»), которые выходят за пределы внутреннего кода коррекции LDPC, даже при низкой частоте битовых ошибок .
Например: код Рида-Соломона с кодовой модуляцией LDPC (RS-LCM) использует внешний код Рида-Соломона. [18] Стандарты DVB-S2, DVB-T2 и DVB-C2 используют внешний код кода BCH для устранения остаточных ошибок после декодирования LDPC. [19]
5G NR использует полярный код для каналов управления и LDPC для каналов данных. [20] [21]
Хотя код LDPC добился успеха в коммерческих жестких дисках, для полного использования его возможностей исправления ошибок в твердотельных накопителях требуется нетрадиционное детальное определение флэш-памяти, что приводит к увеличению задержки чтения из памяти. LDPC-in-SSD [22] — это эффективный подход к развертыванию LDPC в SSD с очень небольшим увеличением задержки, который превращает LDPC в SSD в реальность. С тех пор LDPC широко применяется в коммерческих твердотельных накопителях как потребительского, так и корпоративного уровня крупными поставщиками систем хранения данных. Многие твердотельные накопители TLC (и более поздних версий) используют коды LDPC. Сначала предпринимается попытка быстрого жесткого декодирования (двоичного стирания), которая может вернуться к более медленному, но более мощному мягкому декодированию. [23]
Коды LDPC функционально определяются разреженной матрицей проверки четности . Эта разреженная матрица часто генерируется случайным образом с учетом ограничений разреженности — конструкция кода LDPC обсуждается позже. Эти коды были впервые разработаны Робертом Галлагером в 1960 году. [5]
Ниже приведен фрагмент графа примера кода LDPC с использованием нотации графа факторов Форни . В этом графе n узлов переменных в верхней части графа соединены с ( n − k ) узлами ограничений в нижней части графа.
Это популярный способ графического представления ( n , k ) LDPC-кода. Биты допустимого сообщения, помещенные в буквы Т в верхней части графика, удовлетворяют графическим ограничениям. В частности, все строки, соединяющиеся с узлом переменной (поле со знаком «=»), имеют одно и то же значение, а все значения, соединяющиеся с узлом фактора (поле со знаком «+»), должны суммироваться по модулю два до нуля (в другими словами, их сумма должна давать четное число или должно быть четное количество нечетных значений).
Игнорируя любые строки, выходящие за пределы изображения, существует восемь возможных шестибитовых строк, соответствующих допустимым кодовым словам: (т.е. 000000, 011001, 110010, 101011, 111100, 100101, 001110, 010111). Этот фрагмент кода LDPC представляет собой трехбитное сообщение, закодированное как шесть бит. Здесь используется избыточность, чтобы увеличить вероятность восстановления после ошибок канала. Это (6, 3) линейный код с n = 6 и k = 3.
Опять игнорируя линии, выходящие за пределы изображения, матрица проверки четности, представляющая этот фрагмент графа, имеет вид
В этой матрице каждая строка представляет одно из трех ограничений проверки четности, а каждый столбец представляет один из шести бит полученного кодового слова.
В этом примере восемь кодовых слов можно получить, придав матрице проверки четности H следующую форму с помощью базовых операций над строками в GF(2) :
Шаг 1: Х.
Шаг 2: Строка 1 добавляется к строке 3.
Шаг 3: Строки 2 и 3 меняются местами.
Шаг 4: Строка 1 добавляется к строке 3.
Отсюда матрица-генератор G может быть получена как (заметим, что в частном случае, когда это двоичный код ), или, в частности:
Наконец, умножая все восемь возможных 3-битных строк на G , получаются все восемь допустимых кодовых слов. Например, кодовое слово для битовой строки «101» получается следующим образом:
где – символ умножения по модулю 2.
Для проверки пространство строк G ортогонально H , так что
Битовая строка «101» находится в первых трех битах кодового слова «101011».
Во время кодирования кадра биты входных данных (D) повторяются и распределяются по набору составляющих кодеров. Составляющие кодеры обычно представляют собой аккумуляторы, и каждый аккумулятор используется для генерации символа четности. Единственная копия исходных данных (S 0,K-1 ) передается с битами четности (P) для формирования кодовых символов. Биты S от каждого составного кодера отбрасываются.
Бит четности может использоваться в другом составном коде.
В примере с использованием кода DVB-S2 со скоростью 2/3 размер кодированного блока составляет 64 800 символов (N=64 800) с 43 200 битами данных (K=43 200) и 21 600 битами четности (M=21 600). Каждый составной код (проверочный узел) кодирует 16 бит данных, за исключением первого бита четности, который кодирует 8 бит данных. Первые 4680 бит данных повторяются 13 раз (используются в 13 кодах четности), а остальные биты данных используются в 3 кодах четности (нерегулярный код LDPC).
Для сравнения, классические турбокоды обычно используют два составляющих кода, настроенных параллельно, каждый из которых кодирует весь входной блок (K) битов данных. Эти составляющие кодеры представляют собой рекурсивные сверточные коды (RSC) умеренной глубины (8 или 16 состояний), которые разделены перемежителем кода, который чередует одну копию кадра.
В коде LDPC, напротив, параллельно используется множество составных кодов малой глубины (аккумуляторов), каждый из которых кодирует лишь небольшую часть входного кадра. Многие составляющие коды можно рассматривать как множество « сверточных кодов » малой глубины (2 состояния), которые соединены посредством операций повторения и распределения. Операции повторения и распределения выполняют функцию перемежителя в турбокоде.
Возможность более точно управлять связями различных составляющих кодов и уровнем избыточности для каждого входного бита дает большую гибкость при разработке кодов LDPC, что в некоторых случаях может привести к более высокой производительности, чем турбокоды. Турбокоды по-прежнему работают лучше, чем LDPC, при низких скоростях кодирования, или, по крайней мере, для турбокодов проще разрабатывать хорошо работающие коды с низкой скоростью.
На практике оборудование, формирующее аккумуляторы, повторно используется в процессе кодирования. То есть, как только первый набор битов четности сгенерирован и биты четности сохранены, то же самое аппаратное обеспечение аккумулятора используется для генерации следующего набора битов четности.
Как и в случае с другими кодами, декодирование кода LDPC с максимальным правдоподобием в двоичном симметричном канале представляет собой NP-полную задачу, [24] показанную путем сокращения из трехмерного сопоставления . Таким образом, если предположить, что P != NP , что широко распространено, то выполнение оптимального декодирования для произвольного кода любого полезного размера непрактично.
Однако неоптимальные методы, основанные на итеративном декодировании с распространением доверия, дают отличные результаты и могут быть практически реализованы. Методы неоптимального декодирования рассматривают каждую проверку четности, составляющую LDPC, как независимый код одиночной проверки четности (SPC). Каждый код SPC декодируется отдельно с использованием методов soft-in-soft-out (SISO), таких как SOVA , BCJR , MAP и других их производных. Информация мягкого решения от каждого SISO-декодирования перекрестно проверяется и обновляется с помощью других избыточных SPC-декодирований того же информационного бита. Каждый код SPC затем снова декодируется с использованием обновленной информации мягкого решения. Этот процесс повторяется до тех пор, пока не будет получено допустимое кодовое слово или пока декодирование не будет исчерпано. Этот тип декодирования часто называют декодированием суммы произведений.
Декодирование кодов SPC часто называют обработкой «проверочного узла», а перекрестную проверку переменных часто называют обработкой «переменного узла».
В практической реализации декодера LDPC наборы кодов SPC декодируются параллельно для увеличения пропускной способности.
Напротив, распространение убеждений в канале двоичного стирания особенно просто, когда оно состоит из итеративного удовлетворения ограничений.
Например, предположим, что допустимое кодовое слово 101011 из приведенного выше примера передается по каналу двоичного стирания и принимается со стиранием первого и четвертого битов, что дает ?01?11. Поскольку переданное сообщение должно удовлетворять ограничениям кода, сообщение можно представить, записав полученное сообщение в верхней части графа коэффициентов.
В этом примере первый бит еще невозможно восстановить, поскольку все связанные с ним ограничения содержат более одного неизвестного бита. Чтобы приступить к декодированию сообщения, необходимо выявить ограничения, связанные только с одним из стертых битов. В этом примере достаточно только второго ограничения. При рассмотрении второго ограничения выяснилось, что четвертый бит должен быть нулевым, поскольку только ноль в этой позиции удовлетворяет ограничению.
Затем эта процедура повторяется. Новое значение четвертого бита теперь можно использовать в сочетании с первым ограничением для восстановления первого бита, как показано ниже. Это означает, что первый бит должен быть единицей, чтобы удовлетворить крайнему левому ограничению.
Таким образом, сообщение может быть декодировано итеративно. Для других моделей каналов сообщения, передаваемые между узлами переменных и узлами проверки, представляют собой действительные числа , которые выражают вероятности и вероятности доверия.
Этот результат можно проверить, умножив исправленное кодовое слово r на матрицу проверки четности H :
Поскольку результатом z ( синдромом ) этой операции является нулевой вектор три × один, результирующее кодовое слово r успешно проверяется.
После завершения декодирования исходные биты сообщения «101» можно извлечь, просмотрев первые 3 бита кодового слова.
Хотя этот пример стирания является иллюстративным, он не показывает использование декодирования с мягким решением или передачи сообщений с мягким решением, которые используются практически во всех коммерческих декодерах LDPC.
В последние годы [ когда? ] также было проведено много работы по изучению влияния альтернативных графиков обновления узлов переменных и узлов ограничений. Оригинальный метод, который использовался для декодирования кодов LDPC, был известен как лавинная рассылка . Этот тип обновления требовал, чтобы перед обновлением узла переменной необходимо было обновить все узлы ограничений, и наоборот. В более поздней работе Вила Касадо и др. [25] были изучены альтернативные методы обновления, в которых узлы переменных обновляются новейшей доступной информацией о контрольных узлах. [ нужна цитата ]
Интуиция этих алгоритмов заключается в том, что узлы переменных, значения которых различаются больше всего, — это те, которые необходимо обновить в первую очередь. Высоконадежные узлы, чья величина логарифмического отношения правдоподобия (LLR) велика и существенно не меняется от одного обновления к другому, не требуют обновлений с той же частотой, что и другие узлы, знак и величина которых колеблются более широко. [ нужна цитата ] Эти алгоритмы планирования показывают большую скорость сходимости и меньший уровень ошибок, чем те, которые используют лавинную рассылку. Эти более низкие уровни ошибок достигаются за счет способности алгоритма информированного динамического планирования (IDS) [25] преодолевать наборы перехватов близких кодовых слов. [26]
При использовании алгоритмов планирования без лавинной рассылки используется альтернативное определение итерации. Для ( n , k ) LDPC-кода со скоростью k / n полная итерация происходит, когда n переменных и n - k узлов ограничений были обновлены, независимо от порядка, в котором они были обновлены. [ нужна цитата ]
Для блоков большого размера коды LDPC обычно создаются путем предварительного изучения поведения декодеров. Поскольку размер блока стремится к бесконечности, можно показать, что декодеры LDPC имеют шумовой порог, ниже которого декодирование надежно достигается, а выше которого декодирование не достигается, [27] в просторечии называемый эффектом обрыва . Этот порог можно оптимизировать, найдя наилучшую пропорцию дуг из проверочных узлов и дуг из переменных узлов. Примерный графический подход к визуализации этого порога — диаграмма EXIT . [ нужна цитата ]
Построение конкретного LDPC-кода после такой оптимизации делится на два основных типа методов :
Построение псевдослучайным подходом основано на теоретических результатах, согласно которым для блоков большого размера случайная конструкция обеспечивает хорошую производительность декодирования. [11] В общем, псевдослучайные коды имеют сложные кодеры, но псевдослучайные коды с лучшими декодерами могут иметь простые кодеры. [28] Часто применяются различные ограничения, чтобы гарантировать, что желаемые свойства, ожидаемые при теоретическом пределе бесконечного размера блока, проявляются при конечном размере блока. [ нужна цитата ]
Комбинаторные подходы можно использовать для оптимизации свойств кодов LDPC небольшого размера или для создания кодов с простыми кодировщиками. [ нужна цитата ]
Некоторые коды LDPC основаны на кодах Рида-Соломона , например код RS-LDPC, используемый в стандарте 10 Gigabit Ethernet . [29] По сравнению со случайно генерируемыми кодами LDPC, структурированные коды LDPC, такие как код LDPC, используемый в стандарте DVB-S2 , могут иметь более простое и, следовательно, более дешевое оборудование, в частности, коды, построенные таким образом, что матрица H является циркулянтом . матрица . [30]
Еще одним способом построения кодов LDPC является использование конечной геометрии . Этот метод был предложен Ю. Коу и др. в 2001 году. [31]
Коды LDPC можно сравнить с другими мощными схемами кодирования, например турбокодами . [32] С одной стороны, на производительность турбокодов по BER влияют ограничения низких кодов. [33] Коды LDPC не имеют ограничений минимального расстояния, [34] это косвенно означает, что коды LDPC могут быть более эффективными при относительно больших скоростях кодирования (например, 3/4, 5/6, 7/8), чем турбокоды. Однако коды LDPC не являются полной заменой: турбокоды являются лучшим решением при более низких скоростях кодирования (например, 1/6, 1/3, 1/2). [35] [36]
